Home research People General Info Seminars Resources Intranet
| Algorithms & Applcations Group | Home | Research | Publications | People | Resources | News
Algorithms & Applications Group
C-PRM: An Efficient, Adaptable, and Customizable PRM

Project Personnel:Shawna Thomas,Nancy Amato

In this project, we propose a new approach for building and querying probabilistic roadmaps. In the roadmap construction stage, we build coarse roadmaps by performing only an approximate validation of the roadmap nodes and/or edges. In the query stage, the roadmap is validated and refined only in the area of interest for the query, and moreover, is customized in accordance with any specified query preferences. This approach, which postpones some of the validation checks (e.g., collision checks) to the query phase, yields more efficient solutions to many problems. This approach is used in our work on protein folding, assembly planning, nonholonomic planning for car-like robots, and several other problems.

This framework includes all previous PRM variants as special cases. In particular,

  • it encompases variable levels of validation (from none to complete) of nodes and edges during roadmap construction,
  • it provides for various edge evaluation schedules when validing paths extracted from the roadmap, and
  • it enables path customization to satisfy variable, adaptive query requirements.

An important benefit of our approach is that it gives one the ability to customize the same roadmap in accordance with multiple, variable, query preferences. For example, our approach enables one to find a path which maintains a particular clearance, or makes at most some specified number of sharp turns. Our preliminary results on problems drawn from diverse application domains show that this new approach dramatically improves performance, and shows remarkable flexibility when adapting to different query requirements.

Common Path Requirements
ApplicationRequirement
CADclearance
Mobile robotsclearance, smoothness
Manipulatorssingularity, clearance
Ligand bindinglow potential
Protein foldinglow potential

We experimented with different levels of node evaluation and path validation schedules for the piano mover's problem. Table 3 shows that it is useful to preform some level of node valiation. If no validation is preformed, the query takes significantly longer as the roadmap contains many invalid nodes that it must discover and remove. For this relatively uncluttered environment, priority-based path validation performs significantly better than sequential path validation.

The piano mover's problem.

We experimented with different levels of edge evaluation and path validation schedules for the cluttered environment. Table 4 shows that approximate edge validation greatly reduces roadmap construction time while eliminating most invalid edges. The benefit of eliminating these invalid edges is clearly seen in the query time. For this relatively cluttered environment, priority-based path validation is only slightly better in most cases.

Cluttered environment.

A General Framework for PRM Motion Planning, Guang Song, Shawna Thomas, Nancy M. Amato, In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), pp. 4445-4450, Taipei, Taiwan, Sep 2003.
Proceedings(ps, pdf, abstract)

Randomized Motion Planning for Car-like Robots with C-PRM, Guang Song, Nancy M. Amato, In Proc. IEEE Int. Conf. Intel. Rob. Syst. (IROS), pp. 37-42, Maui, Hawaii, Nov 2001. Also, Technical Report, TR01-002, Department of Computer Science and Engineering, Texas A&M University, Mar 2001.
Proceedings(ps, pdf, abstract) Technical Report(ps, pdf, abstract)

Customizing PRM Roadmaps at Query Time, Guang Song, Shawna Miller, Nancy M. Amato, In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), pp. 1500-1505, Seoul, Korea, May 2001.
Proceedings(ps, pdf, abstract)

Supported by NSF

Project Alumni:Guang Song