UAV Task Allocation for Hierarchical Multiobjective Optimization in Complex Conditions Using Modified NSGA-III with Segmented Encoding

doi:10.1007/s12204-021-2269-5

Abstract

Abstract: With the recent boom in unmanned aerial vehicle (UAV) technology, many UAV applications involving complex and risky tasks in military and civilian fields have emerged, such as military strikes and disaster monitoring. Task allocation for UAVs is the process of planning the division of work among UAVs, controlled from ground stations by human operators. This study formulates the UAV task-allocation problem as an extended traveling salesman problem and presents a novel UAV task-allocation model for complex air concentration monitoring tasks. Then, an optimized non-dominated sorting genetic algorithm III (NSGA-III) based on a twin-exclusion mechanism, hierarchical objective-domination operator, and segmented gene encoding (i.e., NSGA-III-TEHOD) is developed to solve complex task-allocation problems involving multiple UAVs, hierarchical objectives, obstacles, and ambient wind. The algorithm is tested in several simulations, and the results demonstrate that the new algorithm outperforms NSGA-III, non-dominated sorting genetic algorithm II (NSGA-II), and genetic algorithm (GA) in terms of efficiency of global convergence and early maturation prevention and is available for the hierarchical objective-optimization problems.

Key words: unmanned aerial vehicle (UAV)| task allocation| non-dominated sorting genetic algorithm (NSGA)|multiobjective optimization

摘要： With the recent boom in unmanned aerial vehicle (UAV) technology, many UAV applications involving complex and risky tasks in military and civilian fields have emerged, such as military strikes and disaster monitoring. Task allocation for UAVs is the process of planning the division of work among UAVs, controlled from ground stations by human operators. This study formulates the UAV task-allocation problem as an extended traveling salesman problem and presents a novel UAV task-allocation model for complex air concentration monitoring tasks. Then, an optimized non-dominated sorting genetic algorithm III (NSGA-III) based on a twin-exclusion mechanism, hierarchical objective-domination operator, and segmented gene encoding (i.e., NSGA-III-TEHOD) is developed to solve complex task-allocation problems involving multiple UAVs, hierarchical objectives, obstacles, and ambient wind. The algorithm is tested in several simulations, and the results demonstrate that the new algorithm outperforms NSGA-III, non-dominated sorting genetic algorithm II (NSGA-II), and genetic algorithm (GA) in terms of efficiency of global convergence and early maturation prevention and is available for the hierarchical objective-optimization problems.

关键词: unmanned aerial vehicle (UAV)| task allocation| non-dominated sorting genetic algorithm (NSGA)|multiobjective optimization

CLC Number:

TP 273

JIN Yudong (靳宇栋), FENG Jiabo (冯家波), ZHANG Weijun (张伟军). UAV Task Allocation for Hierarchical Multiobjective Optimization in Complex Conditions Using Modified NSGA-III with Segmented Encoding[J]. J Shanghai Jiaotong Univ Sci, 2021, 26(4): 431-445.

References 25

[1]	GIESE S, CARR D, CHAHL J. Implications for unmanned systems research of military UAV mishap statistics [C]//2013 IEEE Intelligent Vehicles Symposium.Gold Coast, Australia: IEEE, 2013: 1191-1196.
[2]	WU J, ZHOU G. High-resolution planimetric mappingfrom UAV video for quick-response to natural disaster[C]//2006 IEEE International Symposium on Geoscienceand Remote Sensing. Denver, CO, USA: IEEE,2006: 3333-3336.
[3]	THIELS C A, AHO J M, ZIETLOW S P, et al. Useof unmanned aerial vehicles for medical product transport[J]. Air Medical Journal, 2015, 34(2): 104-108.
[4]	SHIMA T, RASMUSSEN S. UAV cooperative decisionand control: Challenges and practical approaches [M].Philadelphia, PA, USA: Society for Industrial and AppliedMathematics, 2009.
[5]	AGATZ N, BOUMAN P, SCHMIDT M. Optimizationapproaches for the traveling salesman problem withdrone [J]. Transportation Science, 2018, 52(4): 965-981.
[6]	LIN J C, JIA G W, HOU Z X. Research on the taskassignment of heterogeneous UAV formation in theanti-radar combat [C]//The 30th Chinese Control andDecision Conference (2018 CCDC). Shenyang, China:IEEE, 2018: 2028-2033.
[7]	VIVALDINI K C T, MARTINELLI T H, GUIZILINI V C, et al. UAV route planning for active disease classification[J]. Autonomous Robots, 2019, 43(5): 1137-1153.
[8]	BELLINGHAM J, TILLERSON M, RICHARDS A, et al. Multi-task allocation and path planning for cooperatingUAVs [M]//Cooperative control: Models, applicationsand algorithms. Boston, MA, USA: Springer,2003: 23-41.
[9]	WANG Z, LIU L, LONG T, et al. Multi-UAV reconnaissancetask allocation for heterogeneous targets usingan opposition-based genetic algorithm with doublechromosomeencoding [J]. Chinese Journal of Aeronautics,2018, 31(2): 339-350.
[10]	EDISON E, SHIMA T. Integrated task assignment andpath optimization for cooperating uninhabited aerialvehicles using genetic algorithms [J]. Computers & OperationsResearch, 2011, 38: 340-356.
[11]	XU G T, LIU L, TENG L, et al. Cooperative multipletask assignment considering precedence constraintsusing multi-chromosome encoded genetic algorithm[C]//2018 AIAA Guidance, Navigation, and Control Conference. Kissimmee, Florida, USA: AIAA, 2018:1859.
[12]	RAMIREZ-ATENCIA C, R-MORENO M D, CAMACHOD. Handling swarm of UAVs based on evolutionarymulti-objective optimization [J]. Progress in ArtificialIntelligence, 2017, 6(3): 263-274.
[13]	WEN T X, ZHANG Z N, WONG K K L. Multiobjectivealgorithm for blood supply via unmannedaerial vehicles to the wounded in an emergency situation[J]. PloS One, 2016, 11(5): e0155176.
[14]	ZITZLER E, K¨UNZLI S. Indicator-based selection inmultiobjective search [C]//International Conferenceon Parallel Problem Solving from Nature. Berlin, Germany:Springer, 2004: 832-842.
[15]	POHL A J, LAMONT G B. Multi-objective UAVmission planning using evolutionary computation[C]//Proceedings of the 40th Conference on WinterSimulation. Miami Florida, USA: IEEE, 2008: 1268-1279.
[16]	NIKOOFARD A H, HAJIMIRSADEGHI H, RAHIMIKIAN A, et al. Multiobjective invasive weed optimization:Application to analysis of Pareto improvementmodels in electricity markets [J]. Applied Soft Computing,2012, 12: 100-112.
[17]	DEB K, PRATAP A, AGARWAL S, et al. A fastand elitist multiobjective genetic algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation,2002, 6(2): 182-197.
[18]	RAMIREZ-ATENCIA C, CAMACHO D. Constrainedmulti-objective optimization for multi-UAV planning[J]. Journal of Ambient Intelligence and HumanizedComputing, 2019, 10(6): 2467-2484.
[19]	ZITZLER E, LAUMANNS M, THIELE L. SPEA2:Improving the strength Pareto evolutionary algorithm[R]. Zurich, Switzerland: Swiss Federal Institute ofTechnology (ETH) Zurich, 2001.
[20]	DEB K, JAIN H. An evolutionary many-objective optimizationalgorithm using reference-point based nondominatedsorting approach, Part I: Solving problemswith box constraints [J]. IEEE Transactions on EvolutionaryComputation, 2014, 18(4): 577-601.
[21]	JAIN H, DEB K. An evolutionary many-objectiveoptimization algorithm using reference-point basednondominated sorting approach, Part II: Handlingconstraints and extending to an adaptive approach[J]. IEEE Transactions on Evolutionary Computation,2014, 18(4): 602-622.
[22]	CENSOR Y. Pareto optimality in multiobjective problems[J]. Applied Mathematics and Optimization, 1977,4(1): 41-59.
[23]	LI J, SUN X X. A route planning’s method for unmannedaerial vehicles based on improved A-star algorithm[J]. Acta Armamentarii, 2008, 29(7): 788-792(in Chinese).
[24]	TECHY L, WOOLSEY C A. Minimum-time pathplanning for unmanned aerial vehicles in steady uniformwinds [J]. Journal of Guidance, Control, and Dynamics,2009, 32(6): 1736-1746.
[25]	ODA T, BAROLLI A, XHAFA F, et al. WMN-GA: A simulation system for WMNs and its evaluation consideringselection operators [J]. Journal of Ambient Intelligenceand Humanized Computing, 2013, 4(3): 323-330.