A Lazy Probabilistic Roadmap Planner for Single Query Path Planning

Autonomous path planning addresses the problem of nding collision-free paths for moving objects robots among obstacles. In this paper we consider robots operating in workspaces occupied by stationary, completely known obstacles. We describe a new approach to probabilistic roadmap planners (PRMs). The overall theme of the algorithm, called Lazy PRM, is to minimize the number of collision checks performed during planning. Our algorithm builds a roadmap in the conguration space, whose nodes are the user-dened initial and goal congurations and a number of randomly generated congurations. Neighboring nodes are connected by edges representing the straight line path between the nodes. In contrast with PRMs, our planner initially assumes that all nodes and edges in the roadmap are collision-free, and searches the roadmap at hand for a shortest path between the initial and the goal node. The nodes and edges along the path are then checked for collision. If a collision with th...