Journal Home > Volume 1 , Issue 3

Dynamic task allocation of unmanned aerial vehicle swarms for ground targets is an important part of unmanned aerial vehicle (UAV) swarms task planning and the key technology to improve autonomy. The realization of dynamic task allocation in UAV swarms for ground targets is very difficult because of the large uncertainty of swarms, the target and environment state, and the high real-time allocation requirements. Hence, dynamic task allocation of UAV swarms oriented to ground targets has become a key and difficult problem in the field of mission planning. In this work, a dynamic task allocation method for UAV swarms oriented to ground targets is comprehensively and systematically summarized from two aspects: the establishment of an allocation model and the solution of the allocation model. First, the basic concept and trigger scenario are introduced. Second, the research status and the advantages and disadvantages of the two allocation models are analyzed. Third, the research status and the advantages and disadvantages of several common dynamic task allocation algorithms, such as the algorithm based on market mechanisms, intelligent optimization algorithm, and clustering algorithm, are evaluated. Finally, the specific problems of the current UAV swarm dynamic task allocation method for ground targets are highlighted, and future research directions are established. This work offers important reference significance for fully understanding the current situation of UAV swarm dynamic task allocation technology.


menu
Abstract
Full text
Outline
About this article

Review of Dynamic Task Allocation Methods for UAV Swarms Oriented to Ground Targets

Show Author's information Qiang Peng1Husheng Wu1( )Ruisong Xue2
College of Equipment Support and Management, Engineering University of PAP, Xi’an 710086, China
Institute of NBC Defence, Beijing 102205, China

Abstract

Dynamic task allocation of unmanned aerial vehicle swarms for ground targets is an important part of unmanned aerial vehicle (UAV) swarms task planning and the key technology to improve autonomy. The realization of dynamic task allocation in UAV swarms for ground targets is very difficult because of the large uncertainty of swarms, the target and environment state, and the high real-time allocation requirements. Hence, dynamic task allocation of UAV swarms oriented to ground targets has become a key and difficult problem in the field of mission planning. In this work, a dynamic task allocation method for UAV swarms oriented to ground targets is comprehensively and systematically summarized from two aspects: the establishment of an allocation model and the solution of the allocation model. First, the basic concept and trigger scenario are introduced. Second, the research status and the advantages and disadvantages of the two allocation models are analyzed. Third, the research status and the advantages and disadvantages of several common dynamic task allocation algorithms, such as the algorithm based on market mechanisms, intelligent optimization algorithm, and clustering algorithm, are evaluated. Finally, the specific problems of the current UAV swarm dynamic task allocation method for ground targets are highlighted, and future research directions are established. This work offers important reference significance for fully understanding the current situation of UAV swarm dynamic task allocation technology.

Keywords: task allocation, unmanned aerial vehicle swarm, ground target, dynamic, research status

References(76)

[1]

H. Zhang, B. Xin, L. H. Dou, J. Chen, and K. Hirota, A review of cooperative path planning of an unmanned aerial vehicle group, Front. Inform. Technol. Electron. Eng., vol. 21, no. 12, pp. 1671–1694, 2020.

[2]

G. A. Korsah, A. Stentz, and M. B. Dias, A comprehensive taxonomy for multi-robot task allocation, Int. J. Robot. Res., vol. 32, no. 12, pp. 1495–1512, 2013.

[3]

L. Zhou, H. Ma, Z. Yang, S. D. Zhou, and W. Zhang, Unmanned aerial vehicle communications: Path-loss modeling and evaluation, IEEE Veh. Technol. Mag., vol. 15, no. 2, pp. 121–128, 2020.

[4]

S. L. Cheng, J. Chen, and N. Wang, Overview of air vehicle mission planning techniques, (in Chinese), Acta Aeronaut. Astronaut. Sin., vol. 35, no. 3, pp. 593–606, 2014.

[5]

G. W. Jia and J. F. Wang, Research review of UAV swarm mission planning methods, (in Chinese), Syst. Eng. Electron., vol. 43, no. 1, pp. 99–111, 2021.

[6]
M. Zhao, Research on cooperative target assignment and path planning for multi-unmanned aircraft systems, (in Chinese), PhD dissertation, Harbin Inst. Technol., Harbin, China, 2016.
[7]

O. Cheikhrouhou and I. Khoufi, A comprehensive survey on the multiple traveling salesman problem: Applications, approaches and taxonomy, Comput. Sci. Rev., vol. 40, p. 100369, 2021.

[8]

F. Tamke and U. Buscher, A branch-and-cut algorithm for the vehicle routing problem with drones, Transp. Res. Part B:Methodol., vol. 144, pp. 174–203, 2021.

[9]

J. R. Peters, A. Surana, and F. Bullo, Robust scheduling and routing for collaborative human/unmanned aerial vehicle surveillance missions, J. Aerosp. Inform. Syst., vol. 15, no. 10, pp. 585–603, 2018.

[10]

J. C. Amorim, V. Alves, and E. P. de Freitas, Assessing a swarm-GAP based solution for the task allocation problem in dynamic scenarios, Expert Syst. Appl., vol. 152, p. 113437, 2020.

[11]

D. Q. Zhu, H. Huang, and S. X. Yang, Dynamic task assignment and path planning of multi-AUV system based on an improved self-organizing map and velocity synthesis method in three-dimensional underwater workspace, IEEE Trans. Cybern., vol. 43, no. 2, pp. 504–514, 2013.

[12]

Z. J. Fu, Y. H. Mao, D. J. He, J. N. Yu, and G. W. Xie, Secure multi-UAV collaborative task allocation, IEEE Access, vol. 7, pp. 35579–35587, 2019.

[13]

T. Shima, S. J. Rasmussen, A. G. Sparks, and K. M. Passino, Multiple task assignments for cooperating uninhabited aerial vehicles using genetic algorithms, Comput. Oper. Res., vol. 33, no. 11, pp. 3252–3269, 2006.

[14]

F. Su, Y. Chen, and L. C. Shen, UAV cooperative multi-task assignment based on ant colony algorithm, (in Chinese), Acta Aeronaut. Astronaut. Sin., vol. 29, no. S1, pp. 184–191, 2008.

[15]

L. Shi, C. S. Liu, Q. Ye, and T. Ma, Particle swarm optimization for dynamic resource allocation in UAV cooperative attack, (in Chinese), Flight Dynam., vol. 32, no. 4, pp. 368–371, 375, 2014.

[16]

X. L. Zhao, K. W. Zhang, Z. Z. Li, D. J. Ding, and M. Y. Wu, On dynamic reconnaissance resource allocation for multiple UAVs, (in Chinese), Electron. Opt. Control, vol. 27, no. 6, pp. 11–15, 31, 2020.

[17]
S. D. Chen and J. X. Liu, Study on cooperative attack strategy to time-sensitive target based proactive information delivery, presented at 2012 Int. Conf. Machine Learning and Cybernetics, Xi’an, China, 2012, pp. 972–976.
[18]

L. Evers, A. I. Barros, H. Monsuur, and A. Wagelmans, Online stochastic UAV mission planning with time windows and time-sensitive targets, Eur. J. Oper. Res., vol. 238, no. 1, pp. 348–362, 2014.

[19]

L. Cao, H. S. Tan, H. Peng, and M. C. Pan, Mixed dynamic task allocation for multiple UAV, (in Chinese), J. Nanjing Univ. Technol. (Nat. Sci. Ed.), vol. 39, no. 2, pp. 206–214, 2015.

[20]

Z. Liu, W. Li, and J. C. Ren, Modeling of multi-base multi-UCAV task allocation and its solving method, (in Chinese), J. Southeast Univ. (Nat. Sci. Ed.), vol. 49, no. 1, pp. 88–93, 2019.

[21]

Z. Liu, X. G. Gao, X. W. Fu, and Z. Y. Mou, Coalition formation of multiple heterogeneous unmanned aerial vehicles in cooperative search and attack in unknown environment, (in Chinese), Acta Armamentarii, vol. 36, no. 12, pp. 2284–2297, 2015.

[22]
C. Sampedro, H. Bavle, J. L. Sanchez-Lopez, R. A. S. Fernández, A. Rodríguez-Ramos, M. Molina, and P. Campoy, A flexible and dynamic mission planning architecture for UAV swarm coordination, presented at 2016 Int. Conf. Unmanned Aircraft Systems (ICUAS), Arlington, VA, USA, 2016, pp. 7–10.
DOI
[23]

X. Chen and T. Tang, Study on the dynamic task assignment of multi-UCAV under dynamic uncertain environment, (in Chinese), Fire Control &Command Control, vol. 38, no. 1, pp. 45–49, 53, 2013.

[24]
Z. J. Ding, Task allocation technology of unmanned aerial vehicles for emergency relief in an urban terrain, (in Chinese), Master dissertation, Nanjing University of Aeronautics and Astronautics, Nanjing, 2016.
[25]

P. Chen, F. Yan, Z. Liu, and G. D. Cheng, Task allocation method for heterogeneous multi-UAVs under communication constraints, (in Chinese), Acta Aeronautica Sinica, vol. 42, no. 8, pp. 313–326, 2021.

[26]

H. S. Tan, L. Cao, H. Peng, and M. C. Pan, Method of multi-UAV hierarchical task allocation, (in Chinese), J. PLA Univ. Sci. Technol. (Nat. Sci. Ed.), vol. 15, no. 1, pp. 18–24, 2014.

[27]

X. Chen, X. M. Wei, and G. Y. Xu, Multi aircraft cooperative air combat decision based on distributed invitation auction algorithm, (in Chinese), J. Syst. Simul., vol. 26, no. 6, pp. 1257–1261,1266, 2014.

[28]

B. Di, R. Zhou, and Q. X. Ding, Distributed coordinated heterogeneous task allocation for unmanned aerial vehicles, (in Chinese), Control Decis., vol. 28, no. 2, pp. 274–278, 2013.

[29]

M. Q. Wang and S. Cao, Task assignment based on improved contract net in dynamic environment, Global Journal of Engineering and Technology Advances, vol. 2, no. 3, pp. 45–53, 2020.

[30]

K. S. Kim, H. Y. Kim, and H. L Choi, A bid-based grouping method for communication-efficient decentralized multi-UAV task allocation, Int. J. Aeronaut. Space Sci., vol. 21, no. 1, pp. 290–302, 2020.

[31]

X. W. Fu, P. Feng, and X. G. Gao, Swarm UAVs task and resource dynamic assignment algorithm based on task sequence mechanism, IEEE Access, vol. 7, pp. 41090–41100, 2019.

[32]
N. Buckman, Decentralized task allocation for dynamic, time-sensitive tasks, Master dissertation, MIT, Boston, MA, USA, 2018.
[33]

M. G. Kim, S. H. Shin, E. B. Lee, and S. D. Chi, Modified consensus based auction algorithm for task allocation of multiple unmanned aerial vehicle, J. Korea Soc. Simulat., vol. 23, no. 4, pp. 197–202, 2014.

[34]

C. Chen, W. D. Bao, T. Men, X. M. Zhu, J. Wang, and R. Wang, Nectar-an agent-based dynamic task allocation algorithm in the UAV swarm, Complexity, vol. 2020, p. 6747985, 2020.

[35]
M. Zhao, Research and simulation of distributed multi type UAV cooperative task allocation, (in Chinese), Master dissertation, Nanjing University of Technology, Nanjing, China, 2009.
[36]

J. Y. Chen, P. Y. Yao, J. Tang, and F. C. Jia, Multi-UAV decentralized coopertative dynamic target assignment method, (in Chinese), J. Air Force Eng. Univ. (Nat. Sci. Ed.), vol. 15, no. 6, pp. 11–16, 2014.

[37]
X. E. Wu, Coordination tasks Pre-allocation and redistribution studies in UAVS, (in Chinese), Master dissertation, Nanchang Aeronautical University, Nanchang, China, 2018.
[38]

R. G. Smith, The contract net protocol: high-level communication and control in a distributed problem solver, IEEE Trans. Comput., vol. C-29, no. 12, pp. 1104–1113, 1980.

[39]

Y. P. Qian, J. Xia, and T. Y. Liu, Task assignment scheme based on contract net, (in Chinese), J. Syst. Simulat., vol. 23, no. 8, pp. 1672–1676, 2011.

[40]
M. Atkinson, Contract nets for control of distributed agents in unmanned air vehicles, presented at 2nd AIAA “Unmanned Unlimited” Conf. Workshop & Exhibit, San Diego, CA, USA, 2003, p. 6532.
DOI
[41]

G. Oh, Y. Kim, Y. Ahn, and H. L. Choi, Market-based task assignment for cooperative timing missions in dynamic environments, J. Intell. Robot. Syst., vol. 87, no. 1, pp. 97–123, 2017.

[42]

Y. F. Liu and A. Zhang, Cooperative task assignment method of manned/unmanned aerial vehicle formation, (in Chinese), Syst. Eng. Electron. Technol., vol. 32, no. 3, pp. 584–588, 2010.

[43]
Y. F. Liu, J. Zou, and H. J. Sun, Task allocation method of manned/unmanned aerial vehicle formation based on extended CNP, presented at 2016 IEEE Chinese Guidance, Navigation and Control Conf. (CGNCC), Nanjing, China, 2016, pp. 1975–1979.
[44]

H. T. Liang and F. J. Kang, A novel task optimal allocation approach based on contract net protocol for agent-oriented UUV swarm system modeling, Optik, vol. 127, no. 8, pp. 3928–3933, 2016.

[45]
T. Long, Research on distributed task allocation and coordination for multiple UCAVS cooperative mission control, (in Chinese), PhD dissertation, Graduate School of National Defense Science and Technology University, Changsha, China, 2006.
[46]

X. L. Li, J. T. Zhai, and Y. W. Dai, A task allocation algorithm base on improved contract net protocol under the dynamic environment, (in Chinese), Sci. Technol. Eng., vol. 13, no. 27, pp. 8014–8019, 2013.

[47]

F. Yan, X. P. Zhu, Z. Zhou, and Y. Tang, Real-time task allocation for a heterogeneous multi-UAV simultaneous attack, (in Chinese), Sci. Sin. Inform., vol. 49, no. 5, pp. 555–569, 2019.

[48]

M. Y. Zhang, M. Y. Wang, X. D. Wang, and X. Song, Cooperative real-time task assignment of UAV Group based on improved contract net, (in Chinese), Aero Weaponry, vol. 26, no. 4, pp. 38–46, 2019.

[49]
X. P. Gu and D. Q. Tang, Multi UAV mission planning based on bacterial foraging algorithm, (in Chinese), Syst. Eng. Electron. Technol., http://kns.cnki.net/kcms/detail/11.2422.TN.20210510.0831.002.html, 2021.
[50]

S. Chang and Z. Y. Jia, Multi UAV task allocation based on improved contract net algorithm, (in Chinese), Int. Things Technol., vol. 10, no. 5, pp. 98–100, 2020.

[51]

J. Yang, J. X. Xi, C. Wang, and X. L. Xie, Summary of multi-UAV cooperative patrol task planning methods, (in Chinese), Flight Mech., vol. 36, no. 5, pp. 1–6, 2018.

[52]
L. Wang, Intelligent Optimization Algorithm and its Application, (in Chinese). Beijing, China: Tsinghua University Press, 2001.
[53]
N. Ajlouni, A. A. Hameed, F. Ajlouni, and K. Dehghanian, Design of a genetically fuzzy mapped swarms PID controller for UAV, presented at Applied Research Int. Conf. Science, Technology, Engineering & Mathematics, Istanbul, Turkey, 2018, pp. 39–49.
[54]

J. Y. Zhang, P. Y. Yao, X. X. Zhou, and X. Wang, Approach to operation task and platform resource matching based on DLS and GA, (in Chinese), J. Syst. Eng. Electron. Technol., vol. 34, no. 5, pp. 947–954, 2012.

[55]
B. Rosenberg, J. Burge, and P. Gonsalves, Applying evolutionary multi-objective optimization to mission planning for time-sensitive targets, in Proc. Genetic and Evolutionary Computation Conference, Washington, DC, USA, 2005, pp. 1–8.
[56]

X. Q. Li, X. X. Sun, D. Wang, S. B. Li, and Y. F. Liu, Dynamic UCAV mission assignment using genetic algorithm, (in Chinese), J. Syst. Simulat., vol. 20, no. 16, pp. 4387–4389, 4403, 2008.

[57]

W. N. Wu, Y. Z. Guan, J. F. Guo, and N. G. Cui, Research on cooperative task assignment method used to the mission SEAD with real constraints, (in Chinese), Control Decis., vol. 32, no. 9, pp. 1574–1582, 2017.

[58]

Y. Q. Wang, A. Zhang, and W. H. Bi, Mission planning of manned/unmanned aerial vehicle formation for Time Critical Target attacking, (in Chinese), Electron. Opt. Contro1, vol. 25, no. 8, pp. 7–10, 2018.

[59]
M. Dorigo and T. Stützle, The ant colony optimization metaheuristic: Algorithms, applications, and advances, in Handbook of Metaheuristics, F. Glover and G. A. Kochenberger, eds. Boston, MA, USA: Springer, 2003, pp. 250–285.
[60]
J. Kennedy and R. Eberhart, Particle swarm optimization, in Proc. ICNN'95-Int. Conf. Neural Networks, Perth, Australia, 1995, pp. 1942–1948.
[61]

J. Jing and Q. Feng, Real-time dynamic task allocation based on CPSO algorithm, (in Chinese), Fire Control &Command Control, vol. 39, no. 9, pp. 40–43, 47, 2014.

[62]

H. B. Duan, P. Li, and Y. X. Yu, A predator-prey particle swarm optimization approach to multiple UCAV air combat modeled by dynamic game theory, IEEE/CAA J. Automat., vol. 2, no. 1, pp. 11–18, 2015.

[63]

S. J. Yang, S. W. Wang, J. Tao, P. Wen, and W. J. Zhou, Multi-UCAV cooperative task allocation in dynamic environment, (in Chinese), Electron. Opt. Control, vol. 19, no. 7, pp. 32–36,79, 2012.

[64]

R. X. Wei and Z. C. Wu, Study on task allocation of UAV swarm based on cognitive control, (in Chinese), J. Syst. Simulat., vol. 33, no. 7, pp. 1574–1581, 2021.

[65]

J. Zhang and Y. Q. Cao, Research on multi agent dynamic task allocation based on Hybrid Genetic Ant Colony Algorithm, (in Chinese), Comput. Sci., vol. 38, no. 10A, pp. 268–270, 2011.

[66]

A. W. Zhou and Y. F. Yu, The Research about Clustering Algorithm of K-means, (in Chinese), Comput. Technol. Dev., vol. 21, no. 2, pp. 62–65, 2011.

[67]

H. B. Shi, R. Y. Zhang, G. Sun, and L. Li, Task allocation strategy of multi-agent based on ISODATA algorithm, (in Chinese), J. Northwest Univ. Technol., vol. 35, no. 3, pp. 507–512, 2017.

[68]

S. C. Xu, Q. Wang, and X. M. Liu, Multi-UAV dynamic task assignment by particle swarm optimization algorithm based on division and union strategy, (in Chinese), Fire Control &Command Control, vol. 37, no. 4, pp. 188–191, 2012.

[69]

Y. N. Cui, J. Ren, and W. C. Du, Time-sensitive task dynamic allocation algorithm for multi-UAVs in battlefield environments, (in Chinese), Syst. Eng. Electron. Technol., vol. 38, no. 4, pp. 828–835, 2016.

[70]

C. Chen, SVD algorithm for multiple unmanned combat air vehicles emergent task allocation, (in Chinese), J. Ordnance Equip. Eng., vol. 37, no. 10, pp. 93–95, 2016.

[71]
S. D. Ramchurn, J. E. Fischer, Y. Ikuno, F. Wu, J. Flann, and A. Waldock, A study of human-agent collaboration for multi-UAV task allocation in dynamic environments, in Proc. 24th Int. Joint Conf. Artificial Intelligence (IJCAI), Buenos Aires, Argentina, 2015, pp. 1184–1192.
[72]

X. M. Li, J. Y. Tang, J. J. Dai, and N. Bo, Dynamic task allocation of heterogeneous multi agent alliance, (in Chinese), J. Northwest Univ. Technol., vol. 38, no. 5, pp. 1094–1104, 2020.

[73]
G. H. Li, Y. Tamura, and H. Asama, Dynamical task allocation and reallocation based on body expansion behavior for multi-robot coordination system, presented at 2011 IEEE Int. Conf. Mechatronics and Automation (ICMA), Beijing, China, 2011, pp. 537–542.
[74]

J. Ren, X. G. Gao, J. S. Zheng, and Y. Zhang, Mission decision-making for UAV under dynamic environment, (in Chinese), Syst. Eng. Electron., vol. 32, no. 1, pp. 100–103, 2010.

[75]

X. Chen and Z. G. Guo, UCAV targets assignment method based on uncertain information, (in Chinese), J. Syst. Simulat., vol. 24, no. 8, pp. 1651–1654, 2012.

[76]

J. Yang, X. H. You, G. X. Wu, M. M. Hassan, A. Almogren, and J. Guna, Application of reinforcement learning in UAV cluster task scheduling, Future Generat. Comput. Syst., vol. 95, pp. 140–148, 2019.

Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 12 May 2021
Revised: 19 June 2021
Accepted: 07 September 2021
Published: 29 October 2021
Issue date: September 2021

Copyright

© The author(s) 2021

Acknowledgements

Acknowledgements

This work was partially supported by the Military Science Project of National Social Science Foundation (No. 2019-SKJJ-C-092), the National Natural Science Foundation of China (No. 61502534), the Natural Science Foundation of Shanxi Province (No. 2020JQ-493), Military Equipment Research Project (No. WJ2020A020029), Military Theory Project of PAP (No. WJJY21JL0618), and Research Foundation of Armed Police Force Engineering University (Nos. WJY202148 and JLY2020084).

Rights and permissions

The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).

Return