Stephane Redon and Ming C. Lin

Department of Computer Science
University of North Carolina at Chapel Hill

Planning the motion of a Puma Robot (800 triangles, 7 dofs) in a partial Auxiliary Machine Room model (117,000 triangles). Complex environments and tasks involving cluttered or narrow passages are typically difficult for randomized planning methods. Our local planning method efficiently samples the contact space and constrains the sampling to accelerate planning on these challenging scenarios. Our preliminary results indicate up to 70 times performance improvement when our contact-space planning method is incorporated with a state-of-the-art planning library.

Abstract

Proximity query is an integral part of any motion planning algorithm and takes up the majority of planning time. Due to performance issues, most existing planners perform queries at fixed sampled configurations, sometimes resulting in missed collisions. Moreover, randomly determining collision-free configurations makes it difficult to obtain samples close to, or on, the surface of C-obstacles in the configuration space. In this paper, we present an efficient and practical local planning method in contact-space which uses “continuous collision detection” (CCD). We show how, using the precise contact information provided by a CCD algorithm, a randomized planner can be enhanced by efficiently sampling the contact-space, as well as by constraining the sampling when the roadmap is expanded. We have included our contact-space planning methods in a freely available state-of-the-art planning library - the Stanford MPK library. We have been able to observe that in complex scenarios involving cluttered and narrow passages, which are typically difficult for randomized planners, the enhanced planner offers up to 70 times performance improvement when our contact-space sampling and constrained sampling methods are enabled. 

Results

For each set of benchmarks, we have varied the difficulty of the problem by modifying the scale of the mobile robot, so as to increase the difficulty of sampling the narrow passages (i.e. increasing the narrowness in configuration space). For each scale tested, we have conducted 10 tests and measured the time required to plan the motion for each test, as well as the total number of nodes present in the roadmap when the planner terminates. We then average the results over the ten tests for each scale. For each test, the planner is queried twice on the same pair of initial and final configurations: the first time with the default MPK settings, and the second time with contact-space planning enabled.

Single Rigid Body

A single rigid body must go from one side of the obstacle to the other through the opening (robot scale: 1.85).

Benefits of our contact-space planning method when the scale of the rigid body increases. In the most difficult benchmark, enabling both contact-space sampling and constrained sampling allows us to determine a path within a few minutes, providing up to 20 times performance gain. As expected, much fewer nodes are required to determine a path when contact-space planning is enabled.

Planning the motion of a Puma Robot (800 triangles, 7 dofs) in a partial Auxiliary Machine Room model (117,000 triangles). The Puma robot must go from an initial uncluttered position (b) to a final position close to environment obstacles (c, close-by obstacles indicated by arrows). The scale of the Puma robot in this figure is 1.095, in which case enabling contact-space planning leads to about 70 times performance improvement.

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

Last revision : September 15, 2004