Global path planning of wheeled robots using multi-objective memetic algorithms

摘要

Global path planning is a fundamental problem of mobile robotics. The majority of global path planning methods are designed to find a collision-free path from a start location to a target location while optimizing one or more objectives like path length, smoothness, and safety at a time. It is noted that providing multiple tradeoff path solutions of different objectives is much more beneficial to the user's choice than giving a single optimal solution in terms of some specific criterion. This paper proposes a global path planning of wheeled robots using multi-objective memetic algorithms (MOMAs). Particularly, two MOMAs are implemented based on conventional multi-objective genetic algorithms with elitist non-dominated sorting and decomposition strategies respectively to optimize the path length and smoothness simultaneously. Novel path encoding scheme, path refinement, and specific evolutionary operators are designed and introduced to the MOMAs to enhance the search ability of the algorithms as well as guarantee the safety of the candidate paths obtained in complex environments. Experimental results on both simulated and real environments show that the proposed MOMAs are efficient in planning a set of valid tradeoff paths in complex environments.