In this study, we address a coupled task allocation and path planning problem for a multi-unmanned aerial vehicle (UAV) reconnaissance/attack. Both coupled task allocation and path planning problem are addressed. We propose a task allocation algorithm for maximizing system utility and a path planning algorithm for simultaneous arrival. Moreover, we consider the target's resource requirement and UAV's resource constraints based on a contract net protocol for task allocation. Benefits of destroying the target and costs of UAV attacking target are considered in the objective function. To address the multi-UAV path planning problem, a combination of cooperative particle swarm optimization algorithm, coordination variables, and coordination functions is proposed. UAV's kinematics constraint is considered for the path planning method. Compared with a polynomial time coalition formation algorithm (PTCFA), simulation results show that the proposed algorithm improves the average performance by at least $8%$ with simultaneous arrival using the path planning method.
国防预研项目(41411030401)
[1] Meng W, He Z R, Su R. Decentralized Multi-UAV Flight Autonomy for Moving Convoys Search and Track. IEEE Trans Contr Syst Technol, 2017, 25: 1480-1487 CrossRef Google Scholar
[2] Zhen Z, Xing D, Gao C. Cooperative search-attack mission planning for multi-UAV based on intelligent self-organized algorithm. Aerospace Sci Tech, 2018, 76: 402-411 CrossRef Google Scholar
[3] Shen L C, Chen J, Wang N. Overview of vehicle mission planning techniques. Acta Aeronaut Astronaut Sin, 2014, 35: 593--606. Google Scholar
[4] Tsourdos A, White B, Shanmugavel M. Cooperative Path Planning of Unmanned Aerial Vehicles. Hoboken: John Wiley & Sons, 2010. Google Scholar
[5] Redding J, Boskovic J D, Mehra R K, et al. Heterogeneous cooperative control of multiple UAVs with collaborative assignment and reactive motion planning. In: Proceedings of AIAA Guidance, Navigation and Control Conference and Exhibit, 2008. Google Scholar
[6] Ghamry K A, Kamel M A, Zhang Y M, et al. Multiple UAVs in forest fire fighting mission using particle swarm optimization. In: Proceedings of 2017 International Conference on Unmanned Aircraft Systems, Miami, 2017. 1404--1409. Google Scholar
[7] Shima T, Rasmussen S, Gross D. Assigning Micro UAVs to Task Tours in an Urban Terrain. IEEE Trans Contr Syst Technol, 2007, 15: 601-612 CrossRef Google Scholar
[8] Gottlieb Y, Shima T. UAVs Task and Motion Planning in the Presence of Obstacles and Prioritized Targets.. Sensors, 2015, 15: 29734-29764 CrossRef PubMed Google Scholar
[9] Yao W, Qi N, Liu Y. Online Trajectory Generation with Rendezvous for UAVs Using Multistage Path Prediction. J Aerosp Eng, 2017, 30: 04016092 CrossRef Google Scholar
[10] Manathara J G, Sujit P B, Beard R W. Multiple UAV Coalitions for a Search and Prosecute Mission. J Intell Robot Syst, 2011, 62: 125-158 CrossRef Google Scholar
[11] Kim M H, Baik H, Lee S. Resource Welfare Based Task Allocation for UAV Team with Resource Constraints. J Intell Robot Syst, 2015, 77: 611-627 CrossRef Google Scholar
[12] McLain T W, Beard R W. Coordination Variables, Coordination Functions, and Cooperative Timing Missions. J Guidance Control Dyn, 2005, 28: 150-161 CrossRef ADS Google Scholar
[13] Manathara J G, Ghose D. Rendezvous of Multiple UAVs with Collision Avoidance Using Consensus. J Aerosp Eng, 2012, 25: 480-489 CrossRef Google Scholar
[14] Yuan L P, Chen Z J, Zhou R, et al. Decentralized control for simultaneous arrival of multiple UAVs. Acta Aeronaut Astronaut Sin, 2010, 31: 797--805. Google Scholar
[15] Shanmugavel M, Tsourdos A, White B. Co-operative path planning of multiple UAVs using Dubins paths with clothoid arcs. Control Eng Practice, 2010, 18: 1084-1092 CrossRef Google Scholar
[16] Qu H, Xing K, Alexander T. An improved genetic algorithm with co-evolutionary strategy for global path planning of multiple mobile robots. Neurocomputing, 2013, 120: 509-517 CrossRef Google Scholar
[17] Choe R, Puignavarro J, Cichella V, et al. Cooperative Trajectory Generation Using Pythagorean Hodograph Bézier Curves. Journal of Guidance Control & Dynamics, 2016, 39: 1-20. Google Scholar
[18] George J, Sujit P B, Sousa J B. Search Strategies for Multiple UAV Search and Destroy Missions. J Intell Robot Syst, 2011, 61: 355-367 CrossRef Google Scholar
[19] Askari A, Mortazavi M, Talebi H A. A new approach in UAV path planning using Bezier-Dubins continuous curvature path. Proc Institution Mech Engineers Part G-J Aerospace Eng, 2016, 230: 1103-1113 CrossRef Google Scholar
Figure 1
Task allocation process based on contract network protocol
Figure 2
Path planning process using cooperative particle swarm optimization algorithm (CPSO)
Figure 3
(Color online) Search task for multi-UAVs. (a) Initial time; (b) target 1 is detected ($t=29.4$ s)
Figure 4
(Color online) The trajectories and curvature for UAV coalition. (a) Simultaneous arrival path for attacking target 1; (b) curvature for target 1; (c) simultaneous arrival path for attacking target 2; (d) curvature for target 2
Figure 5
(Color online) Control inputs of angular velocity and velocity for six UAVs. (a) Angular velocity control inputs; (b) velocity control inputs
Figure 6
(Color online) The performance of three tasks allocation algorithms by var-ying the number of UAVs. (a) Average mission time; (b) average system utility; (c) computation time of task allocation
| Target | Position (m) | Resource requirement |
| 1 | (1500, 1500) | (4, 2) |
| 2 | (2000, 1500) | (3, 1) |
Input: potential coalition members set $U_i^R$, the resource requirement of the target $T_j$: $R^{T_j}$. |
Output: feasible coalitions set $C_{\rm~feasible}$. |
Step 1: set minimum coalition size $s_{\rm~min}=1$. |
Step 2: calculate all potential coalitions of size $s_{\rm~min}$ using the UAVs in the potential coalition members set $U_i^R$. |
Step 3: calculate the resource of each potential coalition of size $s_{\rm~min}$, if it satisfies the resource requirement ( |
Step 4: if $C_{\rm~feasible}~\not=~\emptyset$, then output $C_{\rm~feasible}$. Otherwise, go to Step 5. |
Step 5: $s_{\rm~min}=s_{\rm~min}+1$, go to Step 2. |
| UAV | Position (m) | Heading angle (rad) | Resource | Type |
| $U_1$ | (0, 0) | $\pi/6$ | (2, 1) | 1 |
| $U_2$ | (0, 0) | $\pi/3$ | (0, 0) | 2 |
| $U_3$ | (1000, 2000) | $\pi/6$ | (3, 2) | 1 |
| $U_4$ | (1000, 2000) | $\pi/3$ | (2, 0) | 1 |
| $U_5$ | (2000, 2000) | $\pi/6$ | (2, 2) | 1 |
| $U_6$ | (2000, 2000) | $\pi/3$ | (2, 0) | 1 |
| Parameter | Value | Parameter | Value |
| $V_{\rm~min}$ | 40 m/s | $\omega_{\rm~max}$ | 2 rad/s |
| $V_{\rm~max}$ | 60 m/s | $c_1$ | 2 |
| $\kappa_{\rm~max}$ | 0.02 | $c_2$ | 2 |
| $R_{s1}$ | 500 m | Popsize | 30 |
| $R_{s2}$ | 800 m |
| Number of UAVs | The proposed algorithm | PTCFA | Percentage increase in utility (%) |
| 6 | 60.19 | 55.67 | 8.12 |
| 8 | 64.81 | 57.83 | 12.07 |
| 10 | 66.88 | 59.58 | 12.25 |
| 15 | 73.56 | 57.03 | 28.96 |
| 20 | 77.75 | 56.22 | 38.30 |
| Case | Number of UAVs | Number of reconnaissance UAVs | Number of attack UAVs |
| 1 | 6 | 1 | 5 |
| 2 | 8 | 1 | 7 |
| 3 | 10 | 2 | 8 |
| 4 | 15 | 3 | 12 |
| 5 | 20 | 4 | 16 |
Download PDF
