Practicality-Based Probabilistic Roadmaps Method

Probabilistic roadmap methods (PRMs) are a commonly used approach to path planning problems in a high-dimensional search space. Although PRMs can often find a solution to solving the path finding problem the solutions are often not practical in that they can cause the device to flail around or to pass very close to obstacles in the environment. This paper presents a variant of PRMs that addresses the practicality problem of the paths found by the planner. A simple and general sample adjustment method is developed, which adjusts the randomly generated nodes that make up the PRM within their local neighborhood to satisfy soft constraints required by the problem. The resulting roadmap can then be used to generate more practical paths. The approach is general and can be adapted to path planning problems with different practical requirements.

I. Introduction

Path planning emerged as a crucial and productive research area in robotics in the late 1960's [1] and its applications in real world problems continue to attract researchers. In basic path planning (see [1]), given a robot and a static workspace containing a set of obstacles, the objective is to determine a collision-free motion between a specified start and goal for . Although a tractable problem for small dimensional versions of the task, the problem becomes more difficult when the dimensionality of the problem and complexity of the environment increases. It has been proven that the basic path planning problem is PSPACE-complete in the dimensionality of the problem [2], [3]. As a consequence, a number of heuristic approaches to path planning have been developed and have been used to solve high-dimensional real-world path planning problems (a summary is provided in [4]). Probabilistic Roadmap Methods (PRMs) [5] have proven to be an effective solution to high dimensional versions of the problem. PRMs first construct a roadmap in the configuration space by connecting randomly sampled collision-free configurations and then answer queries by attempting to connect the start and goal to the roadmap.