Fast C-obstacle query computation for motion planning

Liangjun Zhang, Young J. Kim, Gokul Varadhan, Dinesh Manocha

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

10 Scopus citations


The configuration space of a robot is partitioned into free space and C-obstacle space. Most of the prior work in collision detection and motion planning algorithms is targeted towards checking whether a configuration or a 1D path lies in the free space. In this paper, we address the problem of checking whether a C-space primitive or a spatial cell lies completely inside C-obstacle space, without explicitly computing the boundary of C-obstacle. We refer to the problem as the C-obstacle query. We present a fast and conservative algorithm to perform this C-obstacle query. Our algorithm uses the notion of generalized penetration depth that takes into account both translational and rotational motion. We compute the generalized penetration depth for polyhedral objects and compare it with the extent of the motion that the polyhedral robot can undergo. Our approach is general and useful for designing practical algorithms for complete motion planning of rigid robots. We have integrated our query computation algorithm with star-shaped roadmaps [1] - a deterministic sampling approach for complete motion planning. We have applied our modified planning algorithm to planar robots undergoing translational and rotational motion in complex 2D environments. Our algorithm is able to perform the C-obstacle query in milliseconds and improves the performance of the complete motion planning algorithm.

Original languageEnglish
Title of host publicationProceedings 2006 IEEE International Conference on Robotics and Automation, ICRA 2006
Number of pages6
StatePublished - 2006
Event2006 IEEE International Conference on Robotics and Automation, ICRA 2006 - Orlando, FL, United States
Duration: 15 May 200619 May 2006

Publication series

NameProceedings - IEEE International Conference on Robotics and Automation
ISSN (Print)1050-4729


Conference2006 IEEE International Conference on Robotics and Automation, ICRA 2006
Country/TerritoryUnited States
CityOrlando, FL


Dive into the research topics of 'Fast C-obstacle query computation for motion planning'. Together they form a unique fingerprint.

Cite this