Memetic algorithm-based path generation for multiple Dubins vehicles performing remote tasks

ABSTRACT

This paper formalises path planning problem for a group of heterogeneous Dubins vehicles performing tasks in a remote fashion and develops a memetic algorithm-based method to effectively produce the paths. In the setting, the vehicles are initially located at multiple depots in a two-dimensional space and the objective of planning is to minimise a weighted sum of the total tour cost of the group and the largest individual tour cost amongst the vehicles. While the presented formulation takes the form of a mixed-integer linear programme (MILP) for which off-the-shelf solvers are available, the MILP solver easily loses the tractability as the number of tasks and agents grow. Therefore, a memetic algorithm tailored to the presented formulation is proposed. The algorithm features a sophisticated encoding scheme to efficiently select the order of performing tasks. In addition, a path refinement technique that optimises detailed tours with the sequence of visits fixed is proposed to finally obtain further optimised trajectories. Comparative numerical experiments show the validity and efficiency of the proposed methods compared with the previous methods in the literature.

KEYWORDS:

• Path planning
• travelling salesman problem
• remote surveillance
• memetic algorithm
• multi-agent systems
• evolutionary computation
• robotics

Disclosure statement

No potential conflict of interest was reported by the authors.

Notes

1 The ‘fmincon’ function in MATLAB is used for the local optimisation.

2 All implementations for the comparison were mex-compiled to make similar as the C environment.

3 The C code of the LKH heuristic was mex-compiled to use in MATLAB environment.

Additional information

Funding

This work was supported by the Agency for Defense Development under contract UD150047JD.

Notes on contributors

Doo-Hyun Cho

Doo-Hyun Cho received the B.S., M.S., and Ph.D. degrees in aerospace engineering from Korea Advanced Institute of Science & Technology (KAIST), Daejeon, South Korea, in 2013, 2015, and 2019, respectively. He works in Mechatronics R&D Center, Samsung Electronics. His recent interest is to optimize the available resources for a system where multiple modules are interactively operating. Recently, he has focused on the machine learning based methodologies to solve the problems related to the manufacturing applications. His hope is that these efforts will lead to public convenience that save assets and protect human lives.

Dae-Sung Jang

Dae-Sung Jang received the B.S. and Ph.D. degrees in aerospace engineering from Korea Advanced Institute of Science & Technology (KAIST), Daejeon, South Korea, in 2008 and 2015, respectively. He is currently an Assistant Professor with the School of Aerospace and Mechanical Engineering, Korea Aerospace University, Goyang, South Korea. His research interests include multi-agent system decision making and task assignment/scheduling, sensor system resource management, combinatorial optimization and approximation algorithms, and cooperative estimation/control.

Han-Lim Choi

Han-Lim Choi received the B.S. and M.S. degrees in aerospace engineering from Korea Advanced Institute of Science and Technology (KAIST), Daejeon, South Korea, in 2000 and 2002, respectively, and the Ph.D. degree in aeronautics and astronautics from Massachusetts Institute of Technology (MIT), Cambridge, MA, USA, in 2009. He is an Associate Professor of aerospace engineering with KAIST. His current research interests include planning and control of multi-agent systems, planning and control under uncertainty, resource management in radars, and Bayesian inference for largescale systems.