A hybrid approach for complete motion planning

Liangjun Zhang, Young J. Kim, Dinesh Manocha

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

42 Scopus citations

Abstract

We present an efficient algorithm for complete motion planning that combines approximate cell decomposition (ACD) with probabilistic roadmaps (PRM). Our approach uses ACD to subdivide the configuration space into cells and computes localized roadmaps by generating samples within these cells. We augment the connectivity graph for adjacent cells in ACD with pseudo-free edges that are computed based on localized roadmaps. These roadmaps are used to capture the connectivity of free space and guide the adaptive subdivision algorithm. At the same time, we use cell decomposition to check for path non-existence and generate samples in narrow passages. Overall, our hybrid algorithm combines the efficiency of PRM methods with the completeness of ACD-based algorithms. We have implemented our algorithm on 3-DOF and 4-DOF robots. We demonstrate its performance on planning scenarios with narrow passages or no collision-free paths. In practice, we observe up to 10 times improvement in performance over prior complete motion planning algorithms.

Original languageEnglish
Title of host publicationProceedings of the 2007 IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2007
Pages7-14
Number of pages8
DOIs
StatePublished - 2007
Event2007 IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2007 - San Diego, CA, United States
Duration: 29 Oct 20072 Nov 2007

Publication series

NameIEEE International Conference on Intelligent Robots and Systems

Conference

Conference2007 IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2007
Country/TerritoryUnited States
CitySan Diego, CA
Period29/10/072/11/07

Fingerprint

Dive into the research topics of 'A hybrid approach for complete motion planning'. Together they form a unique fingerprint.

Cite this