Useful cycles in probabilistic roadmap graphs

Over the last decade, the probabilistic road map method (PRM) has become one of the dominant motion planning techniques. Due to its random nature, the resulting paths tend to be much longer than the optimal path despite the development of numerous smoothing techniques. Also, the path length varies a lot every time the algorithm is executed. We present a new technique that results in higher quality (shorter) paths with much less variation between the executions. The technique is based on adding useful cycles to the roadmap graph.

I. Introduction

Automated motion planning has become important in various fields. Originally the problem was mainly studied in robotics, but in the past few years many new applications arose in fields such as animation, computer games, virtual environments, maintenance planning and training in industrial CAD systems. Such applications put new demands on the motion planner.