Multi-UAV Cooperative Trajectory Planning Based on Many-Objective Evolutionary Algorithm

Hui Bai; Tian Fan; Yuan Niu; Zhihua Cui

doi:10.23919/CSMS.2022.0006

Complex System Modeling and Simulation 2022, 2(2): 130-141 https://doi.org/10.23919/CSMS.2022.0006

Open Access | Issue | Published: 30 June 2022

Multi-UAV Cooperative Trajectory Planning Based on Many-Objective Evolutionary Algorithm

Show Author's Information Hide Author's Information Hui Bai^¹, Tian Fan^¹, Yuan Niu^¹, Zhihua Cui^¹(

)

1 School of Computer Science and Technology, Taiyuan University of Science and Technology, Taiyuan 030024, China

Keywords:

multiple unmanned aerial vehicles (multi-UAV), coordinated trajectory planning, NSGA-III, many-objective optimization

Cite this article:

Bai H, Fan T, Niu Y, et al. Multi-UAV Cooperative Trajectory Planning Based on Many-Objective Evolutionary Algorithm. Complex System Modeling and Simulation, 2022, 2(2): 130-141. https://doi.org/10.23919/CSMS.2022.0006

Download citation

EndNote(RIS)

BibTeX

826

Views

Downloads

Citations

Crossref

N/A

WoS

Scopus

N/A

CSCD

Abstract Full text About this article

Abstract

The trajectory planning of multiple unmanned aerial vehicles (UAVs) is the core of efficient UAV mission execution. Existing studies have mainly transformed this problem into a single-objective optimization problem using a single metric to evaluate multi-UAV trajectory planning methods. However, multi-UAV trajectory planning evolves into a many-objective optimization problem due to the complexity of the demand and the environment. Therefore, a multi-UAV cooperative trajectory planning model based on many-objective optimization is proposed to optimize trajectory distance, trajectory time, trajectory threat, and trajectory coordination distance costs of UAVs. The NSGA-III algorithm, which overcomes the problems of traditional trajectory planning, is used to solve the model. This paper also designs a segmented crossover strategy and introduces dynamic crossover probability in the crossover operator to improve the solving efficiency of the model and accelerate the convergence speed of the algorithm. Experimental results prove the effectiveness of the multi-UAV cooperative trajectory planning algorithm, thereby addressing different actual needs.

Full text

Abstract

Full text

Outline

About this article

Multi-UAV Cooperative Trajectory Planning Based on Many-Objective Evolutionary Algorithm

Show Author's information Hide Author's Information Hui Bai^¹, Tian Fan^¹, Yuan Niu^¹, Zhihua Cui^¹(

)

1 School of Computer Science and Technology, Taiyuan University of Science and Technology, Taiyuan 030024, China

Abstract

Keywords: multiple unmanned aerial vehicles (multi-UAV), coordinated trajectory planning, NSGA-III, many-objective optimization

References(36)

Z. H. Cui, M. Q. Zhang, H. Wang, X. J. Cai, W. S. Zhang, and J. J. Chen, Hybrid many-objective cuckoo search algorithm with Lévy and exponential distributions, Memet. Comput., vol. 12, no. 3, pp. 251–265, 2020.

DOI Google Scholar

Z. H. Cui, L. H. Zhao, Y. Q. Zeng, Y. Q. Ren, W. S. Zhang, and X. Z. Gao, Novel PIO Algorithm with multiple selection strategies for many-objective optimization problems, Complex System Modeling and Simulation, vol. 1, no. 4, pp. 291–307, 2021.

DOI Google Scholar

X. Zhang, Y. Fang, X. Zhang, P. Shen, and X. Cen, Attitude-constrained time-optimal trajectory planning for rotorcrafts: Theory and application to visual servoing, IEEE/ASME Trans. Mechatron., vol. 25, no. 4, pp. 1912–1921, 2020.

DOI Google Scholar

Z. Huang, C. Chen, and M. Pan, Multi-objective UAV path planning for emergency information collection and transmission, IEEE Internet. Things. J., vol. 7, no. 8, pp. 6993–7009, 2020.

DOI Google Scholar

R. Radmanesh, M. Kumar, D. French, and D. Casbeer, Towards a PDE-based large-scale decentralized solution for path planning of UAVs in shared airspace, Aerosp. Sci. Technol., vol. 105, p. 105965, 2020.

DOI Google Scholar

G. Tang, Z. P. Hou, C. Claramunt, and X. Hu, UAV trajectory planning in a port environment, J. Mar. Sci. Eng., vol. 8, no. 8, p. 592, 2020.

DOI Google Scholar

X. Wu, L. Xu, R. Zhen, and X. Wu, Bi-directional adaptive A* algorithm toward optimal path planning for large-Scale UAV under multi-constraints, IEEE Access, vol. 8, pp. 85431–85440, 2020.

DOI Google Scholar

G. Flores-Caballero, A. Rodríguez-Molina, M. Aldape-Pérez, and M. G. Villarreal-Cervantes, Optimized path-planning in continuous spaces for unmanned aerial vehicles using meta-heuristics, IEEE Access, vol. 8, pp. 176774–176788, 2020.

DOI Google Scholar

C. A. Monje, S. Garrido, L. E. Moreno, C. Balaguer, and V. González, Coverage mission for UAVs using differential evolution and fast marching square methods, IEEE Aerosp. Electron. Syst., vol. 35, no. 2, pp. 18–29, 2020.

DOI Google Scholar

C. Yan, X. Xiang, and C. Wang, Towards real-time path planning through deep reinforcement learning for a UAV in dynamic environments, J. Intell. Rob. Syst., vol. 98, no. 2, pp. 297–309, 2019.

DOI Google Scholar

S. Y. Xiao, W. J. Wang, H. Wang, and Z. K. Huang, A new multi-objective artificial bee colony algorithm based on reference point and opposition, Int. J. Bio-Inspir. Comput., vol. 19, no. 1, pp. 18–28, 2022.

DOI Google Scholar

Z. L. Guo, W. S. Zhang, and S. W. Wang, Improved gravitational search algorithm based on chaotic local search, Int. J. Bio-Inspir. Comput., vol. 17, no. 3, pp. 154–164, 2021.

DOI Google Scholar

D. Kumar, N. K. Jain, and U. Nangia, Perfectly convergent particle swarm optimisation in multidimensional space, Int. J. Bio-Inspir. Comput., vol. 18, no. 4, pp. 221–228, 2021.

DOI Google Scholar

S. Balaji, S. T. Vikram, and G. Kanagasabapathy, Jumping particle swarm optimisation method for solving minimum weight vertex cover problem, Int. J. Bio-Inspir. Comput., vol. 18, no. 3, pp. 143–152, 2021.

DOI Google Scholar

N. Nedjah, L. D. M. Mourelle, and R. G. Morais, Inspiration-wise swarm intelligence meta-heuristics for continuous optimisation: A survey - part III, Int. J. Bio-Inspir. Comput., vol. 17, no. 4, pp. 199–214, 2021.

DOI Google Scholar

Z. H. Cui and J. J. Zhang, A hybrid many-objective optimization algorithm for coal green production problem, Concurr. Comp-Pract. E., vol. 33, no. 6, p. e6040, 2021.

DOI Google Scholar

Z. H. Cui, J. J. Zhang, D. Wu, X. J. Cai, H. Wang, W. S. Zhang, and J. J. Chen, Hybrid many-objective particle swarm optimization algorithm for green coal production problem, Inf. Sci., vol. 518, pp. 256–271, 2020.

DOI Google Scholar

Z. Shang, J. Bradley, and Z. Shen, A co-optimal coverage path planning method for aerial scanning of complex structures, Expert Syst. Appl., vol. 158, p. 113535, 2020.

DOI Google Scholar

H. B. Duan, M. Z. Huo, Z. Y. Yang, Y. H. Shi, and Q. N. Luo, Predator-prey pigeon-inspired optimization for UAV ALS longitudinal parameters tuning, IEEE Trans. Aerosp. Electron. Syst., vol. 55, no. 5, pp. 2347–2358, 2019.

DOI Google Scholar

B. Zhang and H. B. Duan, Three-dimensional path planning for uninhabited combat aerial vehicle based on predator-prey pigeon-inspired optimization in dynamic environment, IEEE/ACM Trans. Comput. Biol. Bioinform., vol. 14, no. 1, pp. 97–107, 2017.

DOI Google Scholar

G. G. Wang, L. H. Guo, H. Duan, H. Q. Wang, L. Liu, and M. Z. Shao, A hybrid metaheuristic DE/CS algorithm for UCAV three-dimension path planning, The Scientific World Journal, doi: 10.1100/2012/583973.https://doi.org/10.1100/2012/583973

DOI

H. B. Duan, Y. X. Yu, X. Y. Zhang, and S. Shao, Three-dimension path planning for UCAV using hybrid meta-heuristic ACO-DE algorithm, Simul. Model. Pract. Th., vol. 18, no. 8, pp. 1104–1115, 2010.

DOI Google Scholar

H. Kurdi, S. A. Megren, E. Aloboud, A. A. Alnuaim, H. Alomair, R. Alhanouf, A. B. Muhayya, N. Alharbi, M. Alenzi, and K. Y. Toumi, Bee-inspired task allocation algorithm for multi-UAV search and rescue missions, Int. J. Bio-Inspir. Comput., vol. 16, no. 4, pp. 252–263, 2020.

DOI Google Scholar

B. F. Wang, S. Li, J. Guo, and Q. W. Chen, Car-like mobile robot path planning in rough terrain using multi-objective particle swarm optimization algorithm, Neurocomputing, vol. 282, pp. 42–51, 2018.

DOI Google Scholar

Z. Shao, F. Yan, Z. Zhou, and X. P. Zhu, Path planning for multi-UAV formation rendezvous based on distributed cooperative particle swarm optimization, Appl. Sci., vol. 9, no. 13, p. 2621, 2019.

DOI Google Scholar

X. Chen, Y. T. Liu, L. Y. Yin, and L. J. Qi, Cooperative task assignment and track planning for multi-UAV attack mobile targets, J. Intell. Rob. Syst., vol. 100, nos. 3&4, pp. 1383–1400, 2020.

DOI Google Scholar

C. Qu, W. Gai, M. Zhong, and J. Zhang, A novel reinforcement learning based grey wolf optimizer algorithm for unmanned aerial vehicles (UAVs) path planning, Appl. Soft Comput., vol. 89, p. 106099, 2020.

DOI Google Scholar

X. J. Cai, Z. M. Hu, Z. X. Zhang, Q. Wang, Z. H. Cui, and W. S. Zhang, Multi-UAVs coordinated routing planning based on many-objective optimization, (in Chinese), Sci. China Inf. Sci., vol. 51, no. 6, pp. 985–996, 2021.

DOI Google Scholar

Z. Xu, E. Z. Zhang, and Q. W. Chen, Rotary unmanned aerial vehicles path planning in rough terrain based on multi-objective particle swarm optimization, J. Syst. Eng. Electron., vol. 31, no. 1, pp. 130–141, 2020.

DOI Google Scholar

X. B. Xu, C. L. Li, and J. F. Zhou, A constrained differential evolution algorithm to solve UAV path planning in disaster scenarios, Knowl-Based. Syst., vol. 204, p. 106209, 2020.

DOI Google Scholar

C. Xu, M. Xu, and C. J. Yin, Optimized multi-UAV cooperative path planning under the complex confrontation environment, Comput. Commun., vol. 162, pp. 196–203, 2020.

DOI Google Scholar

Z. H. Cui, P. Zhao, Z. M. Hu, X. J. Cai, W. S. Zhang, and J. J. Chen, An improved matrix factorization based model for many-objective optimization recommendation, Inf. Sci., vol. 579, pp. 1–14, 2021.

DOI Google Scholar

Z. M. Hu, Y. Lan, Z. X. Zhang, and X. J. Cai, A many-objective particle swarm optimization algorithm based on multiple criteria for hybrid recommendation system, KSII Trans. Internet Inf. Syst., vol. 15, no. 2, pp. 442–460, 2021.

DOI Google Scholar

K. Deb and H. Jain, An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: Solving problems with box constraints, IEEE Trans. Evol. Comput., vol. 18, no. 4, pp. 577–601, 2014.

DOI Google Scholar

R. Cheng, Y. Jin, M. Olhofer, and B. Sendhoff, A reference vector guided evolutionary algorithm for many-objective optimization, IEEE Trans. Evol. Comput., vol. 20, no. 5, pp. 773–791, 2016.

DOI Google Scholar

S. X. Yang, M. Q. Li, X. H. Liu, and J. H. Zheng, A grid-based evolutionary algorithm for many-objective optimization, IEEE Trans. Evol. Comput., vol. 17, no. 5, pp. 721–736, 2013.

DOI Google Scholar

About this article

Publication history

Acknowledgements

Rights and permissions

Publication history

Received: 09 March 2022

Revised: 25 March 2022

Accepted: 24 April 2022

Published: 30 June 2022

Issue date: June 2022

Copyright

Acknowledgements

Acknowledgment

This work was supported by the National Natural Science Foundation of China (No. 61806138), the Key R&D Program of Shanxi Province (International Cooperation) (No. 201903D421048), the Science and Technology Development Foundation of the Central Guiding Local (No. YDZJSX2021A038), and the Postgraduate Innovation Project of Shanxi Province (No. 2021Y696).

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/).