Voronoi Boundary Visibility for Efficient Path Planning

Abstract

The subject of this paper is the computation of paths for mobile robots that navigate from a start position to a goal position in environments with static obstacles. Specifically, we focus on paths that are represented by straight lines. Such paths can for example directly be followed by omni-directional robots or can be used as an initial solution for path smoothing. In this context, the most common performance metrics are the path length, the obstacle clearance and the computation time. In this paper, we develop a new path planning algorithm that addresses all the stated performance metrics. Our method first determines all possible connections between the start position and goal position along the edges of the generalized Voronoi diagram (GVD) of a given obstacle map. The shortest connections are then refined using a balanced method for creating shortcuts along existing waypoints and introducing new waypoints in order to cut corners. As an important feature, our method reduces the number of required waypoints by iteratively adding new waypoints and then removing unnecessary waypoints along solution paths. Moreover, our method takes into account multiple start-goal connections, since the shortest start-goal connection along the edges of the GVD might not lead to the shortest solution path. A comprehensive computational evaluation for a large number of maps with different properties shows that the proposed method outperforms sampling-based algorithms such as Probabilistic Roadmaps (PRM) and exact methods such as Visibility Graphs (VG) by computing close-to-optimal solution paths with a specified minimum obstacle clearance in less time.