考虑协同航路规划的多无人机任务分配

doi:10.7527/S1000-6893.2020.24234

Abstract

Abstract: To solve the problem of task allocation and cooperative route planning for multiple unmanned aerial vehicles (UAVs), this paper takes the distributed contract network auction algorithm as the basis, designs auction architecture and auction revenue function of UAVs cluster, combines the simulated annealing algorithm to coordinate the task execution order, predicts the range between two task points using the A^* algorithm, completes the initial planning of cooperative route among multiple unmanned aerial vehicles synchronously in the task allocation phase, determines the optimal task execution order, and achieves the tight coupling between the task allocation and cooperative route planning. The simulation results show that, considering the threat of no-fly zones and obstacles, this algorithm can effectively complete the assignment of different targets with reasonable target assignments and execution orders, low total execution cost, and balanced loads among the aircraft. In the stage of task assignment, it has obvious effect to consider cooperative route planning and can effectively improve the rationality of task allocation.

Key words: UAVs, task allocation, route planning, contract nets, multi-aircraft cooperation

CLC Number:

V249

WANG Ranran, WEI Wenling, YANG Mingchao, LIU Wei. Task allocation of multiple UAVs considering cooperative route planning[J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2020, 41(S2): 724234-724234.

References

[1] 宗群, 王丹丹, 邵士凯, 等. 多无人机协同编队飞行控制研究现状及发展[J]. 哈尔滨工业大学学报, 2017, 49(3):1-14. ZONG Q, WANG D D, SHAO S K, et al. Research status and development of multi UAV coordinated formation flight control[J]. Journal of Harbin Institute of Technology, 2017, 49(3):1-14(in Chinese).
[2] ARSIE A, SAVLA K, FRAZZOLI E. Efficient routing algorithms for multiple vehicles with no explicit communications[J]. IEEE Transactions on Automatic Control, 2009, 54(10):2302-2317.
[3] WANG C, MU D, ZHAO F, et al. A parallel simulated annealing method for the vehicle routing problem with simultaneous pickup-delivery and time windows[J]. Computers & Industrial Engineering, 2015, 83(C):111-122.
[4] 梁星星, 马扬, 冯旸赫, 等. 面向多旅行商问题的多目标模拟退火算法研究[J]. 南京师范大学学报(自然科学版),2017, 40(3):80-86. LIANG X X, MA Y, FENG Y H, et al. Research on multi-objective simulated annealing algorithm for multi-traveling salesman problem[J]. Journal of Nanjing Normal University (Natural Science Edition), 2017, 40(3):80-86(in Chinese).
[5] DARRAH M A, NILAND W, STOLARIK B M. Multiple UAV dynamic task allocation using mixed integer linear programming in a SEAD mission[C]//AIAA Infotech & Aerospace Conference. Reston:AIAA, 2005:2005-7164.
[6] 温攀, 王社伟, 徐明仁. 基于Memetic算法的多无人机任务分配研究[J]. 计算机仿真, 2013, 30(5):82-85, 103. WEN P, WANG S W, XU M R. Research in task assignment of multi-UAV based on Memetic algorithm[J]. Computer Simulation, 2013, 30(5):82-85, 103(in Chinese).
[7] 田震, 王晓芳. 基于多基因遗传算法的异构多无人机协同任务分配[J]. 飞行力学, 2019, 37(1):39-44. TIAN Z, WU X F. Cooperative multiple task assignment for heterogeneous multi-UAVs with multi-chromosome genetic algorithm[J]. Flight Dynamics, 2019, 37(1):39-44(in Chinese).
[8] BERTSEKAS D P. The auction algorithm:A distributed relaxation method for the assignment problem[J]. Annals of Operations Research, 1988, 14(1):105-123.
[9] ZAVLANOS M M, SPESIVTSEV L, PAPPAS G J. A distributed auction algorithm for the assignment problem[C]//Proceedings of the 47th IEEE Conference on Decision & Control. Piscataway:IEEE Press, 2008:1212-1217.
[10] 沈林成, 牛轶峰, 朱华勇. 多无人机自主协同控制理论与方法[M]. 北京:国防工业出版社, 2013. SEHN L C, NIU Y F, ZHU H Y. Theories and methods of autonomous cooperative control for multiple UAVs[M]. Beijing:National Defense Industry Press, 2013(in Chinese).
[11] 严飞, 祝小平, 周洲, 等. 考虑同时攻击约束的多异构无人机实时任务分配[J]. 中国科学:信息科学, 2019, 49(5):53-67. YAN F, ZHU X P, ZHOU Z, et al. Real-time task allocation for a heterogeneous multi-UAV simultaneous attack[J]. Scientia Sinica:Informationis, 2019, 49(5):53-67(in Chinese).
[12] CETIN O, YILMAZ G. Real-time autonomous UAV formation flight with collision and obstacle avoidance in unknown environment[J]. Journal of Intelligent & Robotic Systems, 2016, 84(1-4):415-433.
[13] 叶媛媛, 闵春平, 朱华勇, 等. 基于整数规划的多UCAV任务分配问题研究[J]. 信息与控制, 2005, 34(5):548-552. YE Y Y, MIN C P, ZHU H Y, et al. Multiple UCAV mission assignment based on integer programing[J]. Information and Control, 2005, 34(5):548-552(in Chinese).
[14] CAO W, SHI H, ZHU S, et al. Application of an improved A^* algorithm in route planning[C]//Global Congress on Intelligent Systems. New York:IEEE Computer Society, 2009:253-257.
[15] HOWLETT J K, MCLAIN T W, GOODRICH M A. Learning real-time A^* path planner for unmanned air vehicle target sensing[J]. Journal of Aerospace Computing Information and Communication, 2012, 3(3):108-122.
[16] PEHLIVANOGLU Y V. A new vibrational genetic algorithm enhanced with a Voronoi diagram for path planning of autonomous UAV[J]. Aerospace Science and Technology, 2012, 16(1):47-55.
[17] 李春. 无人机集群自主协同搜索方法研究[D]. 杭州:浙江大学, 2019. LI C. Research on autonomous cooperative search using UAV swarms[D]. Hangzhou:Zhejiang University, 2019(in Chinese).
[18] YANG K, KEAT G S, SUKKARIEH S. A Gaussian process-based RRT planner for the exploration of an unknown and cluttered environment with a UAV[J]. Advanced Robotics, 2013, 27(6):431-443.
[19] 杨希祥, 李晓斌, 肖飞, 等. 智能优化算法及其在飞行器优化设计领域的应用综述[J]. 宇航学报, 2009, 30(6):7-17. YANG X X, LI X B, XIAO F, et al. Overview of intelligent optimization algorithm and its application in flight vehicles optimization design[J]. Journal of Astronautics, 2009, 30(6):7-17(in Chinese).
[20] 彭辉, 王林, 沈林成. 区域目标搜索中基于改进RRT的UAV实时航迹规划[J]. 国防科技大学学报, 2009, 31(5):86-91. PENG H, WANG L, SHEN L C. The modified RRT-based real-time route planning for UAV area target searching[J]. Journal of National University of Defense Technology, 2009, 31(5):86-91(in Chinese).

Task allocation of multiple UAVs considering cooperative route planning

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	WANG Rui, ZHOU Zhou, GUO Ronghua, HUANG Yuechen. Multi-body dynamics simulation and experiment of solar-powered UAV parachute landing [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022, 43(8): 225721-225721.
[2]	BAI Chunyu, GUO Yazhou, LIU Xiaochuan, WANG Yafeng, WANG Jizhen, QIN Qinghua. Research progress of collision safety characteristics of civil light and small UAVs [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022, 43(6): 526832-526832.
[3]	FU Xiaowei, WANG Hui, XU Zhe. Cooperative pursuit strategy for multi-UAVs based on DE-MADDPG algorithm [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022, 43(5): 325311-325311.
[4]	SUN Qin, LI Hongxu, WANG Yuzhi, ZHOU Liping, ZHANG Yingchao. Resilient UAV swarm modeling and solving based on multi-domain collaborative method [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022, 43(5): 325340-325340.
[5]	XUE Zhentao, CHEN Jian, ZHANG Zichao, LIU Xuzan, MIAO Xiansheng, HU Gui. Multi-UAV coverage path planning based on optimization of convex division of complex plots [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022, 43(12): 325990-325990.
[6]	CHEN Weishi, HUANG Yifeng, CHEN Xiaolong, LU Xianfeng, ZHANG Jie. Development and applications of airport avian radar: Review [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022, 43(1): 24758-024758.
[7]	CHEN Pu, YAN Fei, LIU Zhao, CHENG Guoda. Communication-constrained task allocation of heterogeneous UAVs [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2021, 42(8): 525844-525844.
[8]	LUO Zong, DU Chun, CHEN Hao, PENG Shuang, LI Jun. Multi-satellite scheduling approach for emergency scenarios based on hierarchical forecasting with Transformer network [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2021, 42(4): 524721-524721.
[9]	NI Yuan, YANG Hao, JIANG Bin. Fault tolerant game control of swarm confrontation with decision faults [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2021, 42(4): 524978-524978.
[10]	XIANG Xiaojia, YAN Chao, WANG Chang, YIN Dong. Coordination control method for fixed-wing UAV formation through deep reinforcement learning [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2021, 42(4): 524009-524009.
[11]	ZHANG Maoquan, CHEN Haixin. Estimated model of range and endurance of small electric UAVs [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2021, 42(3): 625085-625085.
[12]	XIANG Qian, ZHANG Xiaohui, WANG Zhengping, LIU Li. Control method of small fuel cells for UAVs [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2021, 42(3): 623960-623960.
[13]	WU Kun, TAN Shaochang. Path planning of UAVs based on improved whale optimization algorithm [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2020, 41(S2): 724286-724286.
[14]	JIANG Longting, WEI Ruixuan, ZHANG Qirui, WANG Dong. Anti-collision control of UAVs based on swarm intelligence mechanism [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2020, 41(S2): 724294-724294.
[15]	YANG Sen, ZHANG Xianglun. Energy optimized maneuver trajectory generation for unmanned aerial vehicles [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2020, 41(S2): 724288-724288.