Kavraki Lab

The aim of Lazy PRM (an enhancement of the Probabilistic Roadmap technique) is to speed up single query path planning. We want to avoid the learning phase of the PRM, but still benefit from the simplicity and strengths of the method.

Our solution is to lazily evaluate the feasibility of the roadmap as follows. We initially build a roadmap consisting of nodes and edges, but, in contrast with PRM, we don’t check for collisions. The algorithm evaluates the roadmap by repeatedly searching the roadmap at hand for a shortest path between the initial and the goal node, and then checking the nodes and edges along the path for collision. If a collision with the obstacles occurs, the corresponding nodes and edges are removed from the roadmap, and a new shortest path is searched. The above process is repeated until a collision-free path is returned or no path exists in the roadmap. In the latter case we add more nodes and edges to the roadmap, and start searching again.

Our experiments show that in many cases only a very small fraction (less than 1%) of the roadmap must be explored to either find a feasible path, or determine that none exists in the roadmap. This lazy approach is particularly useful when collision-checking is an expensive operation.

Irb 4400 snapshot As a test example we have simulated part of a manufacturing process in which an ABB 4400 robot is tending a press breaking process. We have used the Lazy PRM to plan a number of paths in this environment. An example of paths obtained by the planner can be seen in the following animations. In the latter animation, the paths have been smoothed.

  • Irb 4400 (avi.gz, 482k) (mpg, 5.67M)
  • The same path, smoothed (avi.gz, 403k) (mpg, 4.57M)