Home research People General Info Seminars Resources Intranet
| Algorithms & Applcations Group | Home | Research | Publications | People | Resources | News
Using Spheres to Improve Motion Planning Algorithms

Motion planning algorithms aim to solve the problem of finding a collision-free 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 (C-space). Each point in the C-space 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 C-space 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 C-space. 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 collision-free paths that the object can navigate. The basic probabilistic roadmap method generates nodes through uniform random sampling in the C-space. 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 C-space spheres. Spheres, centered at each configuration in the roadmap, define free areas of the C-space. The radius of a sphere is the node's C-space 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 collision-free. C-space obstacles are not explicitly computed, so the C-space clearance must be approzimated. Intersecting spheres no longer identify collision-free 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 collision-free. 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 C-space.

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