Target-bundled genetic algorithm for multi-unmanned aerial vehicle cooperative task assignment considering precedence constraints

Abstract

This paper presents a modified genetic algorithm using target-bundle-based encoding and tailored genetic operators to effectively tackle cooperative multiple task assignment problems of heterogeneous unmanned aerial vehicles. In the cooperative multiple task assignment problem, multiple tasks including reconnaissance, attack, and verification have to be sequentially performed on each target (e.g. ground control stations, tanks, etc.) by one or multiple unmanned aerial vehicles. Due to the precedence constraints of different tasks, a singular task-execution order may cause deadlock situations, i.e. one or multiple unmanned aerial vehicles being trapped in infinite waiting loops. To address this problem, a target-bundled genetic algorithm is proposed. As a key element of target-bundled genetic algorithm, target-bundle-based encoding is derived to fix multiple tasks on each target as a target-bundle. And individuals are generated by fixing the task-execution order on each target-bundle subject to task precedence constraints. During the evolution process, bundle-exchange crossover and multi-type mutation operators are customized to generate deadlock-free offspring. Besides, the time coordination method is developed to ensure that task-execution time satisfies task precedence constraints. The comparison results on numerical simulations demonstrate that target-bundled genetic algorithm outperforms particle swarm optimization and random search methods in terms of optimality and efficiency.

Keywords

Heterogeneous unmanned aerial vehicle task assignment combinatorial optimization genetic algorithm target-bundled-based encoding

Get full access to this article

View all access options for this article.

References

Shima T and Rasmussen SJ. UAV cooperative decision and control: challenges and practical approaches. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2009.

Schumacher C, Chandler PR, Rasmussen SJ, et al. Task allocation for wide area search munitions with variable path length. In: Proceedings of the 2003 IEEE American control conference, Denver, CO, USA, 2003.

Darrah M, Niland W, Stolarik B, et al. UAV cooperative task assignments for a SEAD mission using genetic algorithms. In: AIAA guidance, navigation, and control conference, Keystone, CO, USA, 2006.

Tsourdos A, White B and Shanmugavel M. Cooperative path planning of unmanned aerial vehicle. Chichester: John Wiley & Sons, 2010.

Moon S, Shim DH and Oh E. Cooperative task assignment and path planning for multiple UAVs. Handbook of Unmanned Aerial Vehicles. Netherlands: Springer, 2015.

Shima

Rasmussen

Sparks

, et al. Multiple task assignments for cooperating uninhabited aerial vehicles using genetic algorithms. Comput Oper Res 2006; 33: 3252–3269.

Ernesto

Marie

Hakim

, et al. A taxonomy for task allocation problems with temporal and ordering constraints. Robot Auton Syst 2017; 90: 55–70.

Shima T, Rasmussen SJ and Sparks AG. UAV cooperative multiple task assignments using genetic algorithms. In: Proceedings of 2005 IEEE American control conference, Portland, OR, USA, 2005.

Shima

Schumacher

. Assigning cooperating UAVs to simultaneous tasks on consecutive targets using genetic algorithms. J Oper Res Soc 2009; 60: 973–982.

10.

Edison

Shima

. Integrated task assignment and path optimization for cooperating uninhabited aerial vehicles using genetic algorithms. Comput Oper Res 2011; 38: 340–356.

11.

Deng

Wang

. Cooperative task assignment of multiple heterogeneous unmanned aerial vehicles using a modified genetic algorithm with multi-type genes. Chinese J Aeronaut 2013; 26: 1238–1250.

12.

Jia

, et al. Cooperative multiple task assignment problem with stochastic velocities and time windows for heterogeneous unmanned aerial vehicles using a genetic algorithm. Aerospace Science and Technology 2018; 76(2018): 112–125.

13.

Cristian

Gema

Maria

DRM

, et al. Solving complex multi-UAV mission planning problems using multi-objective genetic algorithms. Soft Computing 2017; 21(17): 4883–4900.

14.

Ollero

Maza

. Multiple heterogeneous unmanned aerial vehicles, Berlin Heidelberg: Springer, 2007.

15.

Darrah M, Niland W and Stolarik B. Multiple UAV dynamic task allocation using mixed integer linear programming in a SEAD mission. In: AIAA Infotech@Aerospace conference, 2006. Reston, VA: AIAA.

16.

Rasmussen

Shima

. Tree search algorithm for assigning cooperating UAVs to multiple tasks. Int J Robust Nonlinear Control 2008; 18: 135–153.

17.

Schumacher C, Chandler PR, Rasmussen SJ, et al. Task allocation for wide area search munitions via iterative network flow. In: AIAA guidance, navigation, and control conference, Monterey, CA, USA, 2003.

18.

Gyeongtaek

Youdan

Jaemyung

, et al. Market-based task assignment for cooperative timing missions in dynamic environments. J Intell Robot Syst 2017; 87: 97–123.

19.

Nilakantan

Ponnambalam

. Robotic U-shaped assembly line balancing using particle swarm optimization. Eng Optim 2016; 48: 231–252.

20.

Karaman S, Shima T and Frazzoli E. Task assignment for complex UAV operations using genetic algorithms. In: AIAA guidance, navigation, and control conference, Chicago, IL, USA, 2009.

21.

Eun

Bang

. Cooperative task assignment/path planning of multiple unmanned aerial vehicles using genetic algorithm. J Aircraft 2009; 46: 338–343.

22.

Edison E and Shima T. Genetic algorithm for cooperative UAV task assignment and path optimization. In: AIAA guidance, navigation and control conference, Honolulu, HI, 2008.

23.

Sebt

Afshar

Alipouri

. Hybridization of genetic algorithm and fully informed particle swarm for solving the multimode resource-constrained project scheduling problem. Eng Optim 2017; 49: 513–530.

24.

Karakatic

Podgorelec

. A survey of genetic algorithms for solving multi depot vehicle routing problem. Appl Soft Comput 2015; 27: 519–532.

25.

Lim

. Structured population genetic algorithms: a literature survey. Artif Intell Rev 2014; 41: 385–399.

26.

Larranaga

Kuijpers

CMH

Murga

, et al. Genetic algorithms for the travelling salesman problem: a review of representations and operators. Artif Intell Rev 1999; 13: 129–170.

27.

Halil

Murat

. Efficient route planning for an unmanned air vehicle deployed on a moving carrier. Soft Comput 2016; 20: 2905–2920.

28.

Bai

Yan

, et al. An integrated multi-population genetic algorithm for multi-vehicle task assignment in a drift field. Inform Sci 2018; 453: 227–238.

29.

Deng

Mei

. Deadlock-free consecutive task assignment of multiple heterogeneous unmanned aerial vehicles. J Aircraft 2014; 51: 596–605.

30.

Yao

Wan

, et al. An iterative strategy for task assignment and path planning of distributed multiple unmanned aerial vehicles. Aerosp Sci Technol 2019; 86: 455–464.

31.

Dubins

. On curves of minimal length with a constraint on average curvature and with prescribed initial and terminal positions and tangents. Am J Math 1957; 79: 497–516.

32.

Clerc

. Discrete particle swarm optimization, illustrated by the traveling salesman problem, Berlin Heidelberg: Springer, 2004.

33.

Sujit PB, Georget JM and Beard R. Multiple UAV task allocation using particle swarm optimization. In: AIAA guidance, navigation, and control conference, Honolulu, HI, USA, 2008.