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,
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|
|Mobile robots||clearance, smoothness|
|Ligand binding||low potential|
|Protein folding||low 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.
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.
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
Parasol Home | Research | People | General info | Seminars | Resources
Parasol Lab, 301 Harvey R. Bright Bldg, 3112 TAMU, College Station, TX 77843-3112
firstname.lastname@example.org Phone 979.458.0722 Fax 979.458.0718
Department of Computer Science and Engineering | Dwight Look College of Engineering | Texas A&M University
Privacy statement: Computer Science and Engineering Engineering TAMU
Web Accessibility Policy and Law - Web Accessibility and Usability Standards - Contact Webmaster