Using spheres to improve motion planning algorithms
MetadataShow full item record
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 avoid. A useful abstraction is the object's configuration space (C-space). Each point in the C-space represents a unique position and 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 probabilistic roadmap method use different methods to generate and connect roadmap nodes. Probabilistic roadmaps work well in many applications, but in some situations they can by inefficient and unsuccessful. Our research provides an optimization of theses 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 approximated. Intersecting spheres no longer identify collision-free edges but now only likely edges. Verifying that the edge is valid can be postponed until query time. In practice, most edges identified by intersecting 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.
DescriptionDue to the character of the original source materials and the nature of batch digitization, quality control issues may be present in this document. Please report any quality issues you encounter to firstname.lastname@example.org, referencing the URI of the item.
Includes bibliographical references (leaves 24-25).
Miller, Shawna Lynn (2001). Using spheres to improve motion planning algorithms. Texas A&M University. Available electronically from