
Motion planning algorithms aim to solve the problem of finding a collisionfree path to move an object between start and goal positions in an environment. An environment consists of obstacles that the object must aviod. A useful abstraction is the object's configuration space (Cspace). Each point in the Cspace represents a unique positiona dn orientation of the object in the environment. A valid point is a configuration where the object is not colliding with itself or an obstacle. The Cspace consists of all possible positions and orientations, valid or not. Although the robot is simplified to a single point, the obstacles become very complicated in the Cspace. It is too expensive to compute them.
Probabilistic roadmap methods are one type of method to solve motion planning problems. They use randomization to overcome this difficulty. The roadmap represents collisionfree paths that the object can navigate. The basic probabilistic roadmap method generates nodes through uniform random sampling in the Cspace. Variations of the probabilisitic roadmap method use different methods to generate and connect roadmap nodes.
Probabilistic roadmaps work well in many applications, but in some situations they can be inefficient and unsuccessful. Our research provides an optimization of these algorithms using Cspace spheres. Spheres, centered at each configuration in the roadmap, define free areas of the Cspace. The radius of a sphere is the node's Cspace clearance.
Intersecting spheres identify good pairs of nodes for connection. Since an edge connecting the two nodes lies entirely inside both spheres, it is automatically known to be collisionfree. Cspace obstacles are not explicitly computed, so the Cspace clearance must be approzimated. Intersecting spheres no longer identify collisionfree edges by now only likely edges. Verifying that the edges is valid can be postponed until query time. In practice, most edges identified by intersencting spheres are collisionfree. This could dramatically reduce the running time of the algorithm.
These spheres also aid in expanding the roadmap. The roadmap is expanded by generating new nodes whose spheres intersect the spheres of existing nodes. This keeps the number of connected components small and gives good coverage of Cspace.
Here are some video clips of paths computed by the algorithm. I used the medial axis to generate roadmap nodes. In both cases, the roadmap began with 20 seed nodes, grew 3 times, and expanded each new node twice during a growth period.
house.avi (213KB) 
helico.avi (457KB) 
"Using Spheres to Improve Motion Planning Algorithms." Shawna Miller, Senior Honors Thesis, Texas A&M University, April 2001. ps, pdf
Parasol Home  Research  People  General info  Seminars  Resources Parasol Laboratory, 425 Harvey R. Bright Bldg, 3112 TAMU, College Station, TX 778433112 parasoladmin@cse.tamu.edu 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 