Safe and Efficient Path Planning for Omni-directional Robots using an Inflated Voronoi Boundary

摘要

Path planning algorithms for mobile robots are concerned with finding a feasible path between a start and goal location in a given environment without hitting obstacles. In the existing literature, important performance metrics for path planning algorithms are the path length, computation time and path safety, which is quantified by the minimum distance of a path from obstacles. The subject of this paper is the development of path planning algorithms for omni-directional robots, which have the ability of following paths that consist of concatenated line segments. As the main contribution of the paper, we develop three new sampling-based path planning algorithms that address all of the stated performance metrics. The original idea of the paper is the computation of a modified environment map that confines solution paths to the vicinity of the Voronoi boundary of the given environment. Using this modified environment map, we adapt the sampling strategy of the popular path planning algorithms PRM (probabilistic roadmap), PRM* and FMT (fast marching tree). As a result, we are able to generate solution paths with a reduced computation time and increased path safety. Computational experiments with different environments show that the proposed algorithms outperform state-of-the-art algorithms.