Multi-UAV task assignment algorithm based on dynamic auction

ZHANG Lei; YANG Dong-mei; WANG Qian

您当前的位置：

首页 >

文章列表页 >

Multi-UAV task assignment algorithm based on dynamic auction

更新时间：2023-06-07

- Multi-UAV task assignment algorithm based on dynamic auction
- New Generation of Information Technology Pages: 1-7(2023)
- 作者机构：
  
  1.中国自控系统工程有限公司，北京市 100026
  2.北京科技大学计算机与通信工程学院，北京市 100083
- 作者简介：
- 基金信息：
- DOI：
  CLC：
扫描看全文
张蕾,杨冬梅,王潜.基于动态拍卖的多无人机任务分配算法[J].新一代信息技术,

ZHANG Lei,YANG Dong-mei,WANG Qian.Multi-UAV task assignment algorithm based on dynamic auction[J].New Generation of Information Technology,
张蕾,杨冬梅,王潜.基于动态拍卖的多无人机任务分配算法[J].新一代信息技术, DOI：10.3969/j.issn.2096-6091.XXXX.XX.001.

ZHANG Lei,YANG Dong-mei,WANG Qian.Multi-UAV task assignment algorithm based on dynamic auction[J].New Generation of Information Technology, DOI：10.3969/j.issn.2096-6091.XXXX.XX.001.

摘要

无人机已被广泛用于为地面网络提供增强的信息覆盖和计算服务。相较于传统地面网络，无人机拥有部署、机动、成本、自组织和可扩展等多方面的优势，近年来随着无人机在军事与民用领域的大规模应用，无人机集群领域的研究也受到广泛关注，而多无人机之间的任务分配则成为了无人集群研究中至关重要的一环，其中涉及到无人机协作、信息共享和调度安排等诸多复杂的计算任务。考虑到大量处理能力有限的物联网设备可能无法处理繁重的计算任务。本文构建了多无人机辅助移动边缘计算系统，其中多架无人机作为边缘节点，为计算能力有限的地面设备提供计算服务。为了平衡无人机的计算收益，提出了基于拍卖算法的多无人机任务分配方法，首先构建任务计算卸载问题模型，然后采用拍卖算法进行求解。在此基础上，我们能够在保证无人机资源约束和满足用户任务卸载需求的同时，实现无人机集群的计算收益平衡。

Abstract

Unmanned Aerial Vehicles (UAVS) have been widely used to provide enhanced information coverage and computing services for terrestrial networks. Compared with traditional ground networks, UAVs have advantages in deployment, mobility, cost, self-organization, and scalability. In recent years, with the large-scale application of UAVs in military and civilian fields, the field of UAV clusters The research has also received extensive attention, and the task allocation among multi-UAVs has become a crucial part of the unmanned swarm research, which involves many complex calculations such as UAV cooperation, information sharing, and scheduling task. Consider the large number of Internet of things (IoT) devices with limited processing power that may not be able to handle heavy computing tasks. In this paper, a multi-UAV assisted moving edge computing system is constructed, in which several UAVs serve as edge nodes to provide computing services for ground equipment with limited computing capacity. In order to balance the computational benefits of UAVs, a multi-UAVs task allocation method based on auction algorithm was proposed. Firstly, a task computational unloading problem model was constructed, and then the auction algorithm was used to solve the problem. On this basis, we can ensure the resource constraints of UAVs and meet users' task unloading requirements, while achieving the balance of computing income of UAVs.

关键词

拍卖算法任务分配无人机边缘计算收益资源定价

Keywords

auction algorithmtask allocationUAVsedge computinggainresource pricing

references

Wang J J, Zhang Y F, Geng L, et al. Mission planning for heterogeneous tasks with heterogeneous UAVs[C]//2014 13th International Conference on Control Automation Robotics & Vision (ICARCV). IEEE, 2014: 1484-1489.

Semiz F. Task assignment and scheduling in UAV mission planning with multiple constraints[D]. Middle East Technical University, 2015.

Huang T, Wang Y, Cao X, et al. Multi-uav mission planning method[C]//2020 3rd International Conference on Unmanned Systems (ICUS). IEEE, 2020: 325-330.

Bahabry A, Ghazzai H, Vesonder G, et al. Space-time low complexity algorithms for scheduling a fleet of UAVs in smart cities using dimensionality reduction approaches[C]//2019 IEEE International Systems Conference (SysCon). IEEE, 2019: 1-8.

Bethke B, Valenti M, How J P. UAV task assignment[J]. IEEE robotics & automation magazine, 2008, 15(1): 39-44.

Schumacher C, Chandler P, Pachter M, et al. UAV task assignment with timing constraints[C]//AIAA Guidance, Navigation, and Control Conference and Exhibit. 2003: 5664.

Chen Y, Yang D, Yu J. Multi-UAV task assignment with parameter and time-sensitive uncertainties using modified two-part wolf pack search algorithm[J]. IEEE Transactions on Aerospace and Electronic Systems, 2018, 54(6): 2853-2872.

Autenrieb J, Strawa N, Shin H S, et al. A mission planning and task allocation framework for multi-UAV swarm coordination[C]//2019 Workshop on Research, Education and Development of Unmanned Aerial Systems (RED UAS). IEEE, 2019: 297-304.

Tun Y K, Park Y M, Tran N H, et al. Energy-efficient resource management in UAV-assisted mobile edge computing[J]. IEEE Communications Letters, 2020, 25(1): 249-253.

Chang T, Kong D, Hao N, et al. Solving the dynamic weapon target assignment problem by an improved artificial bee colony algorithm with heuristic factor initialization[J]. Applied Soft Computing, 2018, 70: 845-863.

Bellingham J, Tillerson M, Richards A, et al. Multi-task allocation and path planning for cooperating UAVs[J]. Cooperative control: models, applications and algorithms, 2003: 23-41.

Alighanbari M. Task assignment algorithms for teams of UAVs in dynamic environments[D]. Massachusetts Institute of Technology, 2004.

Bertuccelli L, Choi H L, Cho P, et al. Real-time multi-UAV task assignment in dynamic and uncertain environments[C]//AIAA guidance, navigation, and control conference. 2009: 5776.

Balicki J. Numerical experiments on Pareto-optimal task assignment representations by tabu-based evolutionary algorithm[J]. WSEAS Transactions on Information Science and Applications, 2008, 5(5): 695-705.

Khosiawan Y, Park Y, Moon I, et al. Task scheduling system for UAV operations in indoor environment[J]. Neural Computing and Applications, 2019, 31: 5431-5459.

Liu W, Zheng X, Garg H. Multi-UAV cooperative task assignment based on orchard picking algorithm[J]. International Journal of Computational Intelligence Systems, 2021, 14(1): 1461-1467.

Shi J, Wang Y K, Tian J F. Research on cooperative task assignment of UAV formation[C]//Proc 4 th Int Conf on Modelling, Simulation and Applied Mathematics. 2017: 489-496.

Ei N N, Kang S W, Alsenwi M, et al. Multi-UAV-assisted MEC system: Joint association and resource management framework[C]//2021 International Conference on Information Networking (ICOIN). IEEE, 2021: 213-218.

Hu X, Wong K K, Yang K, et al. UAV-assisted relaying and edge computing: Scheduling and trajectory optimization[J]. IEEE Transactions on Wireless Communications, 2019, 18(10): 4738-4752.

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Multi-UAV Task Assignment Algorithm Based on Dynamic Auction

The Local Path Planning Algorithm for Drones Based on Multi-Perspective and Multi-Resolution

Related Author

No data

Related Institution

Naval Aeronautical University

⁰