Multi-UAV Task Assignment Algorithm Based on Dynamic Auction

ZHANG Lei; YANG Dong-mei; WANG Qian

doi:10.3969/j.issn.2096-6091.2023.12.004

您当前的位置：

首页 >

文章列表页 >

Multi-UAV Task Assignment Algorithm Based on Dynamic Auction

RESEARCH PAPER | 更新时间：2025-03-26

- Multi-UAV Task Assignment Algorithm Based on Dynamic Auction
- New Generation of Information Technology Vol. 6, Issue 12, Pages: 17-23(2023)
- 作者机构：
  
  1.中国自控系统工程有限公司，北京 100026
  2.北京科技大学计算机与通信工程学院，北京 100083
- 作者简介：
- 基金信息：
- DOI：10.3969/j.issn.2096-6091.2023.12.004
  CLC： TP273
- Accepted：2023-05-29，
  
  Published：30 June 2023
- 稿件说明：
移动端阅览
张蕾, 杨冬梅, 王潜. 基于动态拍卖的多无人机任务分配算法[J]. 新一代信息技术, 2023, 6(12): 17-23

ZHANG Lei, YANG Dong-mei, WANG Qian. Multi-UAV Task Assignment Algorithm Based on Dynamic Auction[J]. New Generation of Information Technology, 2023, 6(12): 17-23
张蕾, 杨冬梅, 王潜. 基于动态拍卖的多无人机任务分配算法[J]. 新一代信息技术, 2023, 6(12): 17-23 DOI： 10.3969/j.issn.2096-6091.2023.12.004.

ZHANG Lei, YANG Dong-mei, WANG Qian. Multi-UAV Task Assignment Algorithm Based on Dynamic Auction[J]. New Generation of Information Technology, 2023, 6(12): 17-23 DOI： 10.3969/j.issn.2096-6091.2023.12.004.

摘要

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

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 research in the field of UAV clusters 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. Considering 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 is proposed. Firstly

a task computational unloading problem model is constructed

and then the auction algorithm is 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

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) . Piscataway : IEEE , 2015 : 1484 - 1489 .

SEMIZ F . Task Assignment and Scheduling in UAV Mission Planning with Multiple Constraints [D ] . Middle East Technical University , 2015 .

HUANG T Y , WANG Y , CAO X W , et al . Multi-UAV mission planning method [C ] // 2020 3rd International Conference on Unmanned Systems (ICUS) . Piscataway : 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) . Piscataway : 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 ] // Proceedings of the AIAA Guidance, Navigation, and Control Conference and Exhibit . Reston : AIAA , 2003 : AIAA2003-5664.

CHEN Y B , YANG D , YU J Q . 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) . Piscataway : IEEE , 2020 : 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 , 2021 , 25 ( 1 ): 249 - 253 .

CHANG T Q , KONG D P , 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 [M ] // Cooperative Systems . Boston, MA : Springer US , 2003 : 23 - 41 .

ALIGHANBARI M . Task Assignment Algorithms for Teams of UAVs in Dynamic Environments [D ] . Massachusetts : 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 ] // Proceedings of the AIAA Guidance, Navigation, and Control Conference . Reston : AIAA , 2009 : AIAA2009-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 ( 4/6 ): 601 - 611 .

KHOSIAWAN Y , PARK Y , MOON I , et al . Task scheduling system for UAV operations in indoor environment [J ] . Neural Computing and Applications , 2019 , 31 ( 9 ): 5431 - 5459 .

LIU W H , 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 .

SHI J A , WANG Y K , TIAN J F . Research on cooperative task assignment of UAV formation [J/OL ] . DEStech Transactions on Computer Science and Engineering , 2017 . DOI: 10.12783/dtcse/cii2017/17293 http://dx.doi.org/10.12783/dtcse/cii2017/17293 .

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) . Piscataway : 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

567

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Multi-UAV task assignment algorithm based on dynamic auction

AGV Task Scheduling Network Model Under the Integration of Computing and Networking Environments

Exploring the Construction of Security Management Platform for Urban Public 5G Smart Lighting System

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

Related Author

ZHANG Lei

YANG Dong-mei

WANG Qian

FENG Ze-jun

LIU Su-juan

ZHAO Lu-yü

XU Hao-ran

CHEN Yu-han

Related Institution

Jiangsu Province Research Center of Industrial Internet

School of Artificial Intelligence, Hebei Oriental University

Shenzhen Zhenzhi Huilian Technology Co., Ltd.

Shenzhen AOTO Electronics Co., Ltd.

Naval Aeronautical University

⁰