Distributed Task Allocation Based on Auction-PIO Algorithm for Multi-UAV Tracking

被引：0
作者：
Hu C. [1 ]
Song S. [1 ]
Xu J. [1 ]
Wang D. [1 ]
机构：
[1] School of Electrical and Information Engineering, Tianjin University, Tianjin
来源：
Beijing Ligong Daxue Xuebao/Transaction of Beijing Institute of Technology | 2024年 / 57卷 / 04期
关键词：
auction; pigeon-inspired optimization(PIO); target tracking; task allocation; unmanned aerial vehicle(UAV);
D O I：
10.11784/tdxbz202301009
中图分类号：
学科分类号：
摘要：
Unmanned aerial vehicle(UAV)technology has been applied widely in various research fields. Task allocation is crucial in multi-UAV cooperation and has a significant impact on the quality of task completion. In this paper，a distributed allocation method based on auction algorithm with pigeon-inspired optimization(auction-PIO)was proposed for multi-UAV task allocation in a multi-target tracking scenario. First，three performance indices including total tracking distance，allocation balance，and task completion time，were proposed. Along with the constraints of the tracking task，a distributed multi-index 0-1 integer programming model was established. Second，the auction strategy was used as the distributed optimization framework，and the UAV was regarded as the auctioneer to bid for the ground target. The task allocation result was determined through multiple rounds of bidding. In order to enhance the optimality of allocation，the information shared among UAVs was increased such that UAVs were able to bid for all targets. Additionally，the PIO algorithm was introduced to update the bidding prices for targets. The position of pigeon was encoded into the increment of UAVs bidding prices for targets. The map compass operator and landmark operator were used to update swarm positions iteratively so that the bidding prices of UAVs could be updated as well. On this basis，a solution strategy based on target priority was designed to convert the computation result of bidding matrix and distance matrix into allocation matching relationship. Moreover，the computational complexity of the proposed algorithm was analyzed. Finally，the numerical simulation，Gazebo virtual simulation，and outdoor flight experiment of actual UAVs were implemented for the proposed algorithm. The results show that the proposed auction-PIO algorithm has a good allocation performance. In the numerical simulation，the optimization performance of the proposed algorithm is improved by 12.16% compared with that of the classical auction algorithm. Moreover，the virtual simulation and the outdoor experiment also show that the proposed algorithm can meet the requirement of practicability. © 2024 Beijing Institute of Technology. All rights reserved.
引用
收藏
页码：403 / 414
页数：11
相关论文
共 20 条
  • [1] Hou Yonghong, Liu Yan, Lu Hualong, Et al., An autonomous navigation systems of UAVs based on binocular vision[J], Journal of Tianjin University (Science and Technology), 52, 12, pp. 1262-1269, (2019)
  • [2] Kurdi H A，, Ebtesam A，, Maram A，, Et al., Autonomous task allocation for multi-UAV systems based on the locust elastic behavior[J], Applied Soft Computing, 71, 1, pp. 110-126, (2018)
  • [3] Silvestrin P V，, Ritt M., An iterated tabu search for the multi-compartment vehicle routing problem[J], Computers & Operations Research, 81, 1, pp. 192-202, (2017)
  • [4] Li Yan, Dong Yuna, Weapon-target assignment based on simulated annealing and discrete particle swarm optimization in cooperative air combat, Acta Aeronautica et Astronautica Sinica, 31, 3, pp. 626-631, (2010)
  • [5] Muhuri P K，, Rauniyar A., Immigrants based adaptive genetic algorithms for task allocation in multi-robot systems[J], International Journal of Computational Intelligence and Applications, 16, 1, (2017)
  • [6] Pendharkar P C., An ant colony optimization heuristic for constrained task allocation problem[J], Journal of Computational Science, 7, 1, pp. 37-47, (2015)
  • [7] Cui R X, Gao B., Game theory-based negotiation for multiple robots task allocation[J], Robotica, 31, 6, pp. 923-934, (2013)
  • [8] Adaptive task allocation inspired by a model of division of labor in social insects[C], Biocomputation and Emergent Computing, pp. 36-45, (1997)
  • [9] Bertsekas D P., The auction algorithm：A distributed relaxation method for the assignment problem[J], Annals of Operations Research, 14, 1, pp. 105-123, (1988)
  • [10] Adhau S，, Mittal M L，, Mittal A., A multi-agent system for distributed multi-project scheduling ： An auction-based negotiation approach[J], Engineering Applications of Artificial Intelligence, 25, 8, pp. 1738-1751, (2012)
12