Robot path planning with distance-safety criterion

Abstract

Euclidean distance is the most popular criterion for robot path planning. However, the shortest path (SP) is dangerous in some cases because such a path drives the robot too close to obstacles. When safety is the main concern, a center-line path (CLP) providing the maximum clearance from obstacles would be preferable over the SP, although the length of a CLP could be considerably longer than that of a SP. Since the SP and CLP are two extremes with respect to the distance and safety criteria, respectively, it would be useful in practice to strike a compromise between the two criteria. The purpose of this paper is to develop a method for determining an optimal path with a weighted distance-safety criterion. The method is composed of three parts: (i) construction of a region map by dividing the workspace, (ii) inter-region optimization to determine the entry and departure points of the path in each region, and (iii) intra-region optimization for determining the (optimal) path segment within each region. The region map is generated by using an approximate Voronoi diagram, and the inter- (intra-) region optimization is achieved by using the variational dynamic programming. Although it is developed for 2D problems, our method can be easily extended to a class of 3D problems. Numerical examples are also presented to demonstrate the method.