Abstract: As a cutting-edge branch of unmanned aerial vehicle (UAV) technology, the cooperation of a group of UAVs has attracted increasing attention from both civil and military sectors, due to its remarkable merits in functionality and flexibility for accomplishing complex extensive tasks, e.g., search and rescue, fire-fighting, reconnaissance, and surveillance. Cooperative path planning (CPP) is a key problem for a UAV group in executing tasks collectively. In this paper, an attempt is made to perform a comprehensive review of the research on CPP for UAV groups. First, a generalized optimization framework of CPP problems is proposed from the viewpoint of three key elements, i.e., task, UAV group, and environment, as a basis for a comprehensive classification of different types of CPP problems. By following the proposed framework, a taxonomy for the classification of existing CPP problems is proposed to describe different kinds of CPPs in a unified way. Then, a review and a statistical analysis are presented based on the taxonomy, emphasizing the coordinative elements in the existing CPP research. In addition, a collection of challenging CPP problems are provided to highlight future research directions.

无人机群协同路径规划研究综述

[1]Aggarwal S, Kumar N, 2020. Path planning techniques for unmanned aerial vehicles: a review, solutions, and challenges. Comput Commun, 149:270-299.

[2]Ajlouni N, Hameed AA, Ajlouni F, et al., 2018. Design of a genetically fuzzy mapped swarms PID controller for UAV. Applied Research Int Conf on Science, Technology, Engineering & Mathematics, p.39-49.

[3]Avellar GSC, Pereira GAS, Pimenta LCA, et al., 2015. Multi-UAV routing for area coverage and remote sensing with minimum time. Sensors, 15(11):27783-27803.

[4]Azp‘urua H, Freitas GM, Macharet DG, et al., 2018. Multi-robot coverage path planning using hexagonal segmentation for geophysical surveys. Robotica, 36(8):1144-1166.

[5]Babel L, 2019. Coordinated target assignment and UAV path planning with timing constraints. J Intell Robot Syst, 94(3):857-869.

[6]Balampanis F, Maza I, Ollero A, 2017. Coastal areas division and coverage with multiple UAVs for remote sensing. Sensors, 17(4):808.

[7]Binol H, Bulut E, Akkaya K, et al., 2018. Time optimal multi-UAV path planning for gathering ITS data from roadside units. Proc IEEE 88^th Vehicular Technology Conf, p.1-5.

[8]Bouzid Y, Bestaoui Y, Siguerdidjane H, 2019. Guidance-control system of a quadrotor for optimal coverage in cluttered environment with a limited onboard energy: complete software. J Intell Robot Syst, 95(2):707-730.

[9]c Cakici F, Ergezer H, Irmak U, et al., 2016. Coordinated guidance for multiple UAVs. Trans Inst Meas Contr, 38(5):593-601.

[10]Casbeer DW, Kingston DB, Beard RW, et al., 2006. Cooperative forest fire surveillance using a team of small unmanned air vehicles. Int J Syst Sci, 37(6):351-360.

[11]Causa F, Fasano G, Grassi M, 2018. Multi-UAV path planning for autonomous missions in mixed GNSS coverage scenarios. Sensors, 18(12):4188.

[12]Cekmez U, Ozsiginan M, Sahingoz OK, 2016. Multi-UAV path planning with parallel genetic algorithms on CUDA architecture. Proc Genetic Evolutionary Computation Conf, p.1079-1086.

[13]Chen J, Zha WZ, Peng ZH, et al., 2013. Cooperative area reconnaissance for multi-UAV in dynamic environment. Proc 9^th Asian Control Conf, p.1-6.

[14]Chen J, Zhang X, Xin B, et al., 2016. Coordination between unmanned aerial and ground vehicles: a taxonomy and optimization perspective. IEEE Trans Cybern, 46(4):959-972.

[15]Chen QY, Lu YF, Jia GW, et al., 2018. Path planning for UAVs formation reconfiguration based on Dubins trajectory. J Centr South Univ, 25(12):2664-2676.

[16]Chen X, Li GY, Chen XM, 2017. Path planning and cooperative control for multiple UAVs based on consistency theory and Voronoi diagram. Proc 29^th Chinese Control and Decision Conf, p.881-886.

[17]Chen YB, Yu JQ, Su XL, et al., 2015. Path planning for multi-UAV formation. J Intell Robot Syst, 77(1):229-246.

[18]Chen YB, Yu JQ, Mei YS, et al., 2016. Trajectory optimization of multiple quad-rotor UAVs in collaborative assembling task. Chin J Aeron, 29(1):184-201.

[19]Cheng XM, Cao D, Li CT, 2014. Survey of cooperative path planning for multiple unmanned aerial vehicles. Appl Mech Mater, 668-669:388-393.

[20]Cho DH, Jang DS, Choi HL, 2019. Sampling-based tour generation of arbitrarily oriented Dubins sensor platforms. J Aerosp Inform Syst, 16(5):168-186.

[21]Dewangan RK, Shukla A, Godfrey WW, 2019. Three dimensional path planning using grey wolf optimizer for UAVs. Appl Intell, 49(6):2201-2217.

[22]Ding YL, Xin B, Chen J, 2019a. Curvature-constrained path elongation with expected length for Dubins vehicle. Automatica, 108:108495.

[23]Ding YL, Xin B, Chen J, 2019b. Precedence-constrained path planning of messenger UAV for air-ground coordination. Contr Theory Technol, 17(1):13-23.

[24]Dubins LE, 1957. On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents. Am J Math, 79(3):497-516.

[25]Ergezer H, Leblebiciou glu K, 2014. 3D path planning for multiple UAVs for maximum information collection. J Intell Robot Syst, 73(1-4):737-762.

[26]Falomir E, Chaumette S, Guerrini G, 2018. A mobility model based on improved artificial potential fields for swarms of UAVs. IEEE/RSJ Int Conf on Intelligent Robots and Systems, p.8499-8504.

[27]Ghamry KA, Kamel MA, Zhang YM, 2017. Multiple UAVs in forest fire fighting mission using particle swarm optimization. Int Conf on Unmanned Aircraft Systems, p.1404-1409.

[28]Girard AR, Howell AS, Hedrick JK, 2004. Border patrol and surveillance missions using multiple unmanned air vehicles. Proc 43^rd IEEE Conf on Decision and Control, p.620-625.

[29]Govindaraju V, Leng G, Qian Z, 2014. Multi-UAV surveillance over forested regions. Photogr Eng Remote Sens, 80(12):1129-1137.

[30]Guo M, Xin B, Chen J, et al., 2020. Multi-agent coalition formation by an efficient genetic algorithm with heuristic initialization and repair strategy. Swarm Evol Comput, 55:100686.

[31]Gupta SK, Dutta P, Rastogi N, et al., 2017. A control algorithm for co-operatively aerial survey by using multiple UAVs. Int Conf on Recent Developments in Control, Automation & Power Engineering, p.280-285.

[32]Harounabadi M, Bocksberger M, Mitschele-Thiel A, 2018. Evolutionary path planning for multiple UAVs in message ferry networks applying genetic algorithm. IEEE 29^th Annual Int Symp on Personal, Indoor and Mobile Radio Communications, p.1-7.

[33]Hoang VT, Phung MD, Dinh TH, et al., 2018. Angle-encoded swarm optimization for UAV formation path planning. IEEE/RSJ Int Conf on Intelligent Robots and Systems, p.5239-5244.

[34]Hu XX, Liu YH, Wang GQ, 2017. Optimal search for moving targets with sensing capabilities using multiple UAVs. J Syst Eng Electron, 28(3):526-535.

[35]Huang LW, Qu H, Ji P, et al., 2016. A novel coordinated path planning method using k-degree smoothing for multi-UAVs. Appl Soft Comput, 48:182-192.

[36]Jang I, Shin HS, Tsourdos A, et al., 2019. An integrated decision-making framework of a heterogeneous aerial robotic swarm for cooperative tasks with minimum requirements. Proc Inst Mech Eng Part G, 233(6):2101-2118.

[37]Ji XT, Wang XK, Niu YF, et al., 2015. Cooperative search by multiple unmanned aerial vehicles in a nonconvex environment. Math Probl Eng, 2015:196730.

[38]Jia NP, Yang ZW, Yang KW, 2019. Operational effectiveness evaluation of the swarming UAVs combat system based on a system dynamics model. IEEE Access, 7:25209-25224.

[39]Khoshnoud F, Esat II, de Silva CW, et al., 2020. Self-powered solar aerial vehicles: towards infinite endurance UAVs. Unmann Syst, 8(2):95-117.

[40]Kothari M, Postlethwaite I, Gu DW, 2009. Multi-UAV path planning in obstacle rich environments using rapidly-exploring random trees. Proc 48^th IEEE Conf on Decision and Control held jointly with 28^th Chinese Control Conf, p.3069-3074.

[41]Lazarus SB, Tsourdos A, White BA, et al., 2010. Co-operative unmanned aerial vehicle searching and mapping of complex obstacles using two-dimensional splinegon. Proc Inst Mech Eng Part G, 224(2):149-170.

[42]Li CH, Fang C, Wang FY, et al., 2019. Complete coverage path planning for an Arnold system based mobile robot to perform specific types of missions. Front Inform Technol Electron Eng, 20(11):1530-1542.

[43]Li JD, Li XQ, Yu LJ, 2018. Multi-UAV cooperative coverage path planning in plateau and mountain environment. Proc 33^rd Youth Academic Annual Conf of Chinese Association of Automation, p.820-824.

[44]Li T, Jiang J, Zhen ZY, et al., 2016. Mission planning for multiple UAVs based on ant colony optimization and improved Dubins path. IEEE Chinese Guidance, Navigation and Control Conf, p.954-959.

[45]Li XH, Zhao Y, Zhang J, et al., 2016. A hybrid PSO algorithm based flight path optimization for multiple agricultural UAVs. Proc IEEE 28^th Int Conf on Tools with Artificial Intelligence, p.691-697.

[46]Li XY, Ci LL, Yang MH, et al., 2012. Multi-decision making based PSO optimization in airborne mobile sensor network deployment. Proc IEEE 6^th Int Symp on Embedded Multicore SoCs, p.128-134.

[47]Lin W, Zhu Y, Zeng WC, et al., 2018. Track planning model for multi-UAV based on new multiple ant colony algorithm. Proc Chinese Automation Congress, p.3862-3867.

[48]Liu W, Zheng Z, Cai KY, 2013. Distributed on-line path planner for multi-UAV coordination using bi-level programming. Proc 25^th Chinese Control and Decision Conf, p.5128-5133.

[49]Liu Y, Zhang XJ, Zhang Y, et al., 2019. Collision free 4D path planning for multiple UAVs based on spatial refined voting mechanism and PSO approach. Chin J Aeron, 32(6):1504-1519.

[50]Liu Z, Gao XG, Fu XW, 2018. A cooperative search and coverage algorithm with controllable revisit and connectivity maintenance for multiple unmanned aerial vehicles. Sensors, 18(5):1472.

[51]Long GQ, Zhu XP, 2011. Cooperative area coverage reconnaissance method for multi-UAV system. Adv Mater Res, 383-390:4141-4146.

[52]Luo DL, Shao J, Xu Y, et al., 2019. Coevolution pigeon-inspired optimization with cooperation-competition mechanism for multi-UAV cooperative region search. Appl Sci, 9(5):827.

[53]Ma PB, Fan ZE, Ji J, 2014. Cooperative control of multi-UAV with time constraint in the threat environment. Proc IEEE Chinese Guidance, Navigation and Control Conf, p.2424-2428.

[54]Ma XB, Jiao ZY, Wang ZK, et al., 2016. Decentralized prioritized motion planning for multiple autonomous UAVs in 3D polygonal obstacle environments. Int Conf on Unmanned Aircraft Systems, p.292-300.

[55]Ma XB, Jiao ZY, Wang ZK, et al., 2018. 3-D decentralized prioritized motion planning and coordination for high-density operations of micro aerial vehicles. IEEE Trans Contr Syst Technol, 26(3):939-953.

[56]Mansouri SS, Kanellakis C, Fresk E, et al., 2018. Cooperative coverage path planning for visual inspection. Contr Eng Pract, 74:118-131.

[57]Manyam SG, Rasmussen S, Casbeer DW, et al., 2017. Multi-UAV routing for persistent intelligence surveillance & reconnaissance missions. Int Conf on Unmanned Aircraft Systems, p.573-580.

[58]Maza I, Ollero A, 2007. Multiple UAV cooperative searching operation using polygon area decomposition and efficient coverage algorithms. Int Symp on Distributed Autonomous Robotic Systems, p.221-230.

[59]Merino L, Caballero F, Dios JRMD, et al., 2005. Cooperative fire detection using unmanned aerial vehicles. Proc IEEE Int Conf on Robotics and Automation, p.1884-1889.

[60]Mohiuddin A, Tarek T, Zweiri Y, et al., 2020. A survey of single and multi-UAV aerial manipulation. Unmann Syst, 8(2):119-147.

[61]Moon S, Oh E, Shim DH, 2013. An integral framework of task assignment and path planning for multiple unmanned aerial vehicles in dynamic environments. J Intell Robot Syst, 70(1-4):303-313.

[62]Ning Q, Tao GP, Chen BC, et al., 2019. Multi-UAVs trajectory and mission cooperative planning based on the Markov model. Phys Commun, 35:100717.

[63]Park SY, Shin CS, Jeong D, et al., 2018. DroneNetX: network reconstruction through connectivity probing and relay deployment by multiple UAVs in ad hoc networks. IEEE Trans Veh Technol, 67(11):11192-11207.

[64]Qin Z, Li AJ, Dong C, et al., 2018. Fair-energy trajectory plan for reconnaissance mission based on UAVs cooperation. Proc 10^th Int Conf on Wireless Communications and Signal Processing, p.1-6.

[65]Quintin F, Iovino S, Savvaris A, et al., 2017. Use of co-operative UAVs to support/augment UGV situational awareness and/or inter-vehicle communications. IFAC, 50(1):8037-8044.

[66]Radmanesh M, Kumar M, Sarim M, 2018a. Grey wolf optimization based sense and avoid algorithm in a Bayesian framework for multiple UAV path planning in an uncertain environment. Aerosp Sci Technol, 77:168-179.

[67]Radmanesh M, Kumar M, Guentert PH, et al., 2018b. Overview of path-planning and obstacle avoidance algorithms for UAVs: a comparative study. Unmann Syst, 6(2):95-118.

[68]Sahingoz OK, 2013. Flyable path planning for a multi-UAV system with genetic algorithms and Bezier curves. Int Conf on Unmanned Aircraft Systems, p.41-48.

[69]Sahingoz OK, 2014. Generation of Bezier curve-based flyable trajectories for multi-UAV systems with parallel genetic algorithm. J Intell Robot Syst, 74(1-2):499-511.

[70]Shao Z, Yan F, Zhou Z, et al., 2019. Path planning for multi-UAV formation rendezvous based on distributed cooperative particle swarm optimization. Appl Sci, 9(13):2621.

[71]Shi J, Wang YK, Tian JF, 2017. Research on cooperative task assignment of UAV formation. Proc 4^th Int Conf on Modelling, Simulation and Applied Mathematics, p.489-496.

[72]Skorobogatov G, Barrado C, Salamì E, 2020. Multiple UAV systems: a survey. Unmann Syst, 8(2):149-169.

[73]Sorli JV, Graven OH, Bjerknes JD, 2017. Multi-UAV cooperative path planning for sensor placement using cooperative coevolving genetic strategy. Proc 8^th Int Conf on Advances in Swarm Intelligence, p.433-444.

[74]Souissi O, Benatitallah R, Duvivier D, et al., 2013. Path planning: a 2013 survey. Proc Int Conf on Industrial Engineering and Systems Management, p.849-856.

[75]Su XH, Zhao M, Zhao LL, et al., 2016. A novel multi stage cooperative path re-planning method for multi UAV. Proc 14^th Pacific Rim Int Conf on Artificial Intelligence, p.482-495.

[76]Sujit PB, Sousa J, Pereira FL, 2009. UAV and AUVs coordination for ocean exploration. OCEANS Conf, p.1-7.

[77]Sun JY, Tang J, Lao SY, 2017. Collision avoidance for cooperative UAVs with optimized artificial potential field algorithm. IEEE Access, 5:18382-18390.

[78]Sun XL, Liu YF, Yao WR, et al., 2015. Triple-stage path prediction algorithm for real-time mission planning of multi-UAV. Electron Lett, 51(19):1490-1492.

[79]Wang Z, Liu L, Long T, 2017. Minimum-time trajectory planning for multi-unmanned-aerial-vehicle cooperation using sequential convex programming. J Guid Contr Dynam, 40(11):2972-2978.

[80]Wang Z, Liu L, Long T, et al., 2019. Efficient unmanned aerial vehicle formation rendezvous trajectory planning using Dubins path and sequential convex programming. Eng Optim, 51(8):1412-1429.

[81]Wu JY, Yi J, Gao L, et al., 2017. Cooperative path planning of multiple UAVs based on PH curves and harmony search algorithm. Proc IEEE 21^st Int Conf on Computer Supported Cooperative Work in Design, p.540-544.

[82]Wu QP, Zhou SL, Yan S, et al., 2014. A cooperative region surveillance strategy for multiple UAVs. Proc IEEE Chinese Guidance, Navigation and Control Conf, p.1744-1748.

[83]Wu ZY, Li JH, Zuo JM, et al., 2018. Path planning of UAVs based on collision probability and Kalman filter. IEEE Access, 6:34237-34245.

[84]Xing DJ, Zhen ZY, Gong HJ, 2019. Offense-defense confrontation decision making for dynamic UAV swarm versus UAV swarm. Proc Inst Mech Eng Part G, 233(15):5689-5702.

[85]Yan F, Zhu XP, Zhou Z, et al., 2019a. Heterogeneous multi-unmanned aerial vehicle task planning: simultaneous attacks on targets using the Pythagorean hodograph curve. Proc Inst Mech Eng Part G, 233(13):4735-4749.

[86]Yan F, Zhu XP, Zhou Z, et al., 2019b. A hierarchical mission planning method for simultaneous arrival of multi-UAV coalition. Appl Sci, 9(10):1986.

[87]Yang F, Ji XL, Yang CW, et al., 2017. Cooperative search of UAV swarm based on improved ant colony algorithm in uncertain environment. Proc IEEE Int Conf on Unmanned Systems, p.231-236.

[88]Yang J, Xi JX, Wang C, et al., 2018. Multi-base multi-UAV cooperative patrol route planning novel method. Proc 33^rd Youth Academic Annual Conf of Chinese Association of Automation, p.688-693.

[89]Yang XX, Zhou WW, Zhang Y, 2016. On collaborative path planning for multiple UAVs based on Pythagorean hodograph curve. IEEE Chinese Guidance, Navigation and Control Conf, p.971-975.

[90]Yang YL, Polycarpou MM, Minai AA, 2007. Multi-UAV cooperative search using an opportunistic learning method. J Dynam Syst Meas Contr, 129(5):716-728.

[91]Yao P, Wang HL, Ji HX, 2017. Gaussian mixture model and receding horizon control for multiple UAV search in complex environment. Nonl Dynam, 88(2):903-919.

[92]Yao P, Wang XD, Yi K, 2018. Optimal search for marine target using multiple unmanned aerial vehicles. Proc 37^th Chinese Control Conf, p.4552-4556.

[93]Yao WR, Wan N, Qi NM, 2016. Hierarchical path generation for distributed mission planning of UAVs. IEEE 55^th Conf on Decision and Control, p.1681-1686.

[94]Yao WR, Qi NM, Wan N, et al., 2019. An iterative strategy for task assignment and path planning of distributed multiple unmanned aerial vehicles. Aerosp Sci Technol, 86:455-464.

[95]Yoon J, Jin Y, Batsoyol N, et al., 2017. Adaptive path planning of UAVs for delivering delay-sensitive information to ad-hoc nodes. IEEE Wireless Communications and Networking Conf, p.1-6.

[96]Zeng J, Dou LH, Xin B, 2018a. A joint mid-course and terminal course cooperative guidance law for multi-missile salvo attack. Chin J Aeron, 31(6):1311-1326.

[97]Zeng J, Dou LH, Xin B, 2018b. Multi-objective cooperative salvo attack against group target. J Syst Sci Compl, 31(1):244-261.

[98]Zengin U, Dogan A, 2007. Real-time target tracking for autonomous UAVs in adversarial environments: a gradient search algorithm. IEEE Trans Robot, 23(2):294-307.

[99]Zhang DF, Duan HB, 2018. Social-class pigeon-inspired optimization and time stamp segmentation for multi-UAV cooperative path planning. Neurocomputing, 313:229-246.

[100]Zhang QJ, Tao JW, Yu F, et al., 2015. Cooperative solution of multi-UAV rendezvous problem with network restrictions. Math Probl Eng, 2015:878536.

[101]Zhang X, Chen J, Xin B, et al., 2014. A memetic algorithm for path planning of curvature-constrained UAVs performing surveillance of multiple ground targets. Chin J Aeron, 27(3):622-633.

[102]Zhao M, Zhao LL, Su XH, et al., 2017. Improved discrete mapping differential evolution for multi-unmanned aerial vehicles cooperative multi-targets assignment under unified model. Int J Mach Learn Cybern, 8(3):765-780.

[103]Zhao YJ, Zheng Z, Liu Y, 2018. Survey on computational-intelligence-based UAV path planning. Knowl Based Syst, 158:54-64.

[104]Zhao Z, Yang J, Niu YF, et al., 2019. A hierarchical cooperative mission planning mechanism for multiple unmanned aerial vehicles. Electronics, 8(4):443.

[105]Zhen ZY, Xing DJ, Gao C, 2018. Cooperative search-attack mission planning for multi-UAV based on intelligent self-organized algorithm. Aerosp Sci Technol, 76:402-411.

[106]Zheng XC, Wang F, Li ZH, 2018. A multi-UAV cooperative route planning methodology for 3D fine-resolution building model reconstruction. ISPRS J Photogr Remote Sens, 146:483-494.

[107]Zhong YJ, Liu ZX, Zhang YM, et al., 2019. Active fault-tolerant tracking control of a quadrotor with model uncertainties and actuator faults. Front Inform Technol Electron Eng, 20(1):95-106.

[108]Zhu SQ, Wang DW, 2012. Adversarial ground target tracking using UAVs with input constraints. J Intell Robot Syst, 65(1-4):521-532.