Diversity Maintenance for Efficient Robot Path Planning

Abstract

Path planning is present in many areas, such as robotics, video games, and unmanned autonomous vehicles. In the case of robots, it is a primary low-level prerequisite for the successful execution of high-level tasks. It is a known and difficult problem to solve, especially in terms of finding optimal paths for robots working in complex environments. Recently, population-based methods for multi-objective optimization, i.e., swarm and evolutionary algorithms successfully perform on different path planning problems. Knowing the nature of the problem is hard for optimization algorithms, it is expected that population-based algorithms might benefit from some kind of diversity maintenance implementation. However, advantages and potential traps of implementing specific diversity maintenance methods into the evolutionary path planner have not been clearly spelled out and experimentally demonstrated. In this paper, we fill this gap and compare three diversity maintenance methods and their impact on the evolutionary planner for problems of different complexity. Crowding, fitness sharing, and novelty search are tailored to fit specific problems, implemented, and tested for two scenarios: mobile robot operating in a 2D maze, and 3 degrees of freedom (DOF) robot operating in a 3D environment including obstacles. Results indicate that the novelty search outperforms the other two methods for problem domains of higher complexity.

Keywords

• robotics
• optimization
• path planning
• evolutionary computation
• diversity maintenance
• novelty search