Path Planning Using Lazy PRM

Describes an 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 and hence minimize the running time of the planner. Our algorithm builds a roadmap in the configuration space, whose nodes are the user-defined initial and goal configurations and a number of randomly generated nodes. Neighboring nodes are connected by edges representing paths 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 the obstacles occurs, the corresponding nodes and edges are removed from the roadmap. Our planner either finds a new shortest path, or first updates the roadmap with new nodes and edges, and then searches for a shortest path. The above process is repeated until a collision-free path is returned. Lazy PRM is tailored to efficiently answer single planning queries, but can also be used for multiple queries. Experimental results presented in the paper show that our lazy method is very efficient in practice.

Authors

• Robert Bohlin
• Lydia E. Kavraki

Keywords

• Path planning
• Road accidents
• Orbital robotics
• Mathematics
• Random number generation
• Joining processes
• Manufacturing automation
• Manufacturing processes
• Mobile robots
• Animation
• Shortest Path
• Configuration Space
• Collision Detection
• Number Of Checks
• Multiple Queries
• Collision-free Path
• Urban Planning
• Steps Of Algorithm
• Pair Of Nodes
• Learning Phase
• Industrial Environment
• Planning Time
• Straight Path
• Task Planning
• Path Search
• Expensive Operations
• Feasible Path
• Single Query
• Straight-line Path