Cooperative task allocation for heterogeneous multi-UAV using multi-objective optimization algorithm

Abstract

The application of multiple UAVs in complicated tasks has been widely explored in recent years. Due to the advantages of flexibility, cheapness and consistence, the performance of heterogeneous multi-UAVs with proper cooperative task allocation is superior to over the single UAV. Accordingly, several constraints should be satisfied to realize the efficient cooperation, such as special time-window, variant equipment, specified execution sequence. Hence, a proper task allocation in UAVs is the crucial point for the final success. The task allocation problem of the heterogeneous UAVs can be formulated as a multi-objective optimization problem coupled with the UAV dynamics. To this end, a multi-layer encoding strategy and a constraint scheduling method are designed to handle the critical logical and physical constraints. In addition, four optimization objectives: completion time, target reward, UAV damage, and total range, are introduced to evaluate various allocation plans. Subsequently, to efficiently solve the multi-objective optimization problem, an improved multi-objective quantum-behaved particle swarm optimization (IMOQPSO) algorithm is proposed. During this algorithm, a modified solution evaluation method is designed to guide algorithmic evolution; both the convergence and distribution of particles are considered comprehensively; and boundary solutions which may produce some special allocation plans are preserved. Moreover, adaptive parameter control and mixed update mechanism are also introduced in this algorithm. Finally, both the proposed model and algorithm are verified by simulation experiments.

Keywords

unmanned aerial vehicles / cooperative task allocation / heterogeneous / constraint / multi-objective optimization / solution evaluation method

References

[1] EunY, BangH. Cooperative task assignment/path planning of multiple unmanned aerial vehicles using genetic algorithm [J]. Journal of Aircraft, 2009, 46(1): 338-343

[2] DengQ-b, YuJ-q, WangN-fei. Cooperative task assignment of multiple heterogeneous unmanned aerial vehicles using a modified genetic algorithm with multi-type genes [J]. Chinese Journal of Aeronautics, 2013, 26(5): 1238-1250

[3] ZhaiZ-y, OrtegaJ M, MartinezN L, RodriguezmolinaJ. A mission planning approach for precision farming systems based on multi-objective optimization [J]. Sensors, 2018, 18(6): 1795

[4] ChenH-x, NanY, YangYi. Multi-UAV reconnaissance task assignment for heterogeneous targets based on modified symbiotic organisms search algorithm [J]. Sensors, 2019, 193734

[5] BuckmanN, ChoiH L, HowJ P. Partial replanning for decentralized dynamic task allocation [C]. AIAA Scitech 2019 Forum, 2019, San Diego, AIAA, 0915

[6] EdisonE, ShimaT. Integrated task assignment and path optimization for cooperating uninhabited aerial vehicles using genetic algorithms [J]. Computers & Operations Research, 2011, 381340-356

[7] Lozano, CaridadJ, DeJ P, VillarrubiaG G, BajoJ. Smart waste collection system with low consumption lorawan nodes and route optimization [J]. Sensors, 2018, 18(5): 1465

[8] JiangJ, NgK M, PohK L, TeoK M. Vehicle routing problem with a heterogeneous fleet and time windows [J]. Expert Systems with Applications, 2013, 4183748-3760

[9] SavlaK, FrazzoliE, BulloF. Traveling salesperson problems for the dubins vehicle [J]. IEEE Transactions on Automatic Control, 2008, 53(6): 1378-1391

[10] ZhaoZ, YangJ, NiuY-f, ZhangY, ShenL-cheng. A hierarchical cooperative mission planning mechanism for multiple unmanned aerial vehicles [J]. Electronics, 2019, 8(4): 443

[11] WangZ, LiuL, LongT, WenY-lu. Multi-UAV reconnaissance task allocation for heterogeneous targets using an opposition-based genetic algorithm with double- chromosome encoding [J]. Chinese Journal of Aeronautics, 2018, 312339-350

[12] SchwarzrockJ, ZacariasI, BazzanA L C, MoreiraL H, FreitasE P D. Solving task allocation problem in multi unmanned aerial vehicles systems using swarm intelligence [J]. Engineering Applications of Artificial Intelligence, 2018, 72: 10-20

[13] WangJ-j, ZhangY F, GengL, FuhJ Y H, TeoS H. A heuristic mission planning algorithm for heterogeneous tasks with heterogeneous uavs [J]. Unmanned Systems, 2015, 3(3): 205-219

[14] ShimaT, RasmussenS, ShimaT, RasmussenS. Uav cooperative decision and control: Challenges and practical approaches [M]. Society for Industrial and Applied Mathematics, 2008

[15] DeA, KumarS K, GunasekaranA, TiwariM K. Sustainable maritime inventory routing problem with time window constraints [J]. Engineering Applications of Artificial Intelligence, 2017, 61: 77-95

[16] KuoR J, ChengW C. Hybrid meta-heuristic algorithm for job shop scheduling with due date time window and release time [J]. International Journal of Advanced Manufacturing Technology, 2013, 67(1-4): 59-71

[17] SchumacherC, ChandlerP, PachterM, PachterL. Uav task assignment with timing constraints via mixed-integer linear programming [C]. AIAA 3rd Unmanned Unlimited Technical Conference, 20046410

[18] SchumacherC, ChandlerP R, PachterM, PachterL S. Optimization of air vehicles operations using mixed-integer linear programming [J]. Journal of the Operational Research Society, 2007, 58(4): 516-527

[19] SinghM R, MahapatraS S. A quantum behaved particle swarm optimization for flexible job shop scheduling [M]. Pergamon Press, 2016

[20] BuiK H, JungJ, CamachoD. Consensual negotiationbased decision making for connected appliances in smart home management systems [J]. Sensors, 2018, 18(7): 2206

[21] Perez-CarabazaS, Besada-PortasE, LopezorozcoJ A, JesusM. Ant colony optimization for multiuav minimum time search in uncertain domains [J]. Applied Soft Computing, 2018, 62: 789-806

[22] MiloradovicB, ÇürüklüB, EkströmM. A genetic planner for mission planning of cooperative agents in an underwater environment [C]. IEEE Symposium Series on Computational Intelligence. Athens: IEEE, 20161-8

[23] SunJ, FengB, XuW-bo. Particle swarm optimization with particles having quantum behavior [C]. Congress on Evolutionary Computation. Portland: IEEE, 2004325331

[24] ChandlerP, SparksA. Decentralized control for an autonomous team [C]. AIAA Unmanned Unlimited Conference 2013, 2013, San Diego, AIAA

[25] ChenQ-y, LuY-f, JiaG-w, LiY, ZhuB-j, LinJ-can. Path planning for uavs formation reconfiguration based on dubins trajectory [J]. Journal of Central South University, 2018, 25: 2664-2676

[26] LinQ-z, LiuS-b, ZhuQ-l, TangC-y, SongR-z, CoelloC A C, WongK C, ZhangJun. Particle swarm optimization with a balanceable fitness estimation for many-objective optimization problems [J]. IEEE Transactions on Evolutionary Computation, 2016, 22(1): 32-46

[27] WangR, PurshouseR C, FlemingP J. Preferenceinspired coevolutionary algorithms for many-objective optimization [J]. IEEE Transactions on Evolutionary Computation, 2013, 17(4): 474-494

[28] LiM-q, YangS-x, LiuX-hui. Shift-based density estimation for pareto-based algorithms in many-objective optimization [J]. IEEE Transactions on Evolutionary Computation, 2014, 18(3): 348-365

[29] YangJ-j, ZhouJ-z, FangR-c, LiY-h, LiuLi. Multi-objective particle swarm optimization based on adaptive grid algorithms [J]. Journal of System Simulation, 2008, 20(21): 5843-5847

[30] AlM N, PetrovskiA, MccallJ. D2MOPSO: Mopso based on decomposition and dominance with archiving using crowding distance in objective and solution spaces [J]. Evolutionary Computation, 2014, 22(1): 47-77

[31] XuM-m, ZhangL-p, DuB, ZhangL-f, FanY-g, SongD-mei. A mutation operator accelerated quantum-behaved particle swarm optimization algorithm for hyperspectral endmember extraction [J]. Remote Sensing, 2017, 9(3): 197

[32] FanZ, LiW-j, CaiX-y, WeiC-m, ZhangQ-f, DebK, GoodmanE D. Push and pull search for solving constrained multi-objective optimization problems [J]. Swarm and Evolutionary Computation, 2017, 44: 665-679

[33] CoelloC A C, LechugaM S. MOPSO: A proposal for multiple objective particle swarm optimization [C]. Congress on Evolutionary Computation, 20021051-1056

[34] PengG, FangY-w, PengW-s, ChaiD, XuYang. Multi-objective particle optimization algorithm based on sharing-learning and dynamic crowding distance [J]. Optik, 2016, 127(12): 5013-5020

[35] ZhangQ-f, LiHui. MOEA/D: A multiobjective evolutionary algorithm based on decomposition [J]. IEEE Transactions on Evolutionary Computation, 2007, 11(6): 712-731

[36] DebK, PratapA, AgarwalS, MeyarivanT. A fast and elitist multiobjective genetic algorithm: NSGA-II [J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197