Multi-Objective Roadmap Optimization for Multiagent Navigation

Abstract

In this paper, we investigate multi-objective opti-mization of roadmaps for multi-robot path planning. We propose a new representation for roadmaps based on polygons and explore its potentials on various scenarios. In addition, we define three objective functions to estimate the suitability of each roadmap for navigation, and propose a modification of the well-known NSGA-II algorithm to optimize the roadmaps. In our experiments, we compare the quality of the proposed optimized roadmaps with those based on regular grids. The results show that in complex environments with obstacles, the optimized roadmaps perform much more efficient than those on regular grids. In addition, the performance of the optimization can be significantly improved by using the regular grids to initialize the optimization process.