Proving path non-existence using sampling and alpha shapes

Zoe McCarthy, Timothy Wolfe Bretl, Seth Andrew Hutchinson

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In this paper, we address the problem determining the connectivity of a robot's free configuration space. Our method iteratively builds a constructive proof that two configurations lie in disjoint components of the free configuration space. Our algorithm first generates samples that correspond to configurations for which the robot is in collision with an obstacle. These samples are then weighted by their generalized penetration distance, and used to construct alpha shapes. The alpha shape defines a collection of simplices that are fully contained within the configuration space obstacle region. These simplices can be used to quickly solve connectivity queries, which in turn can be used to define termination conditions for sampling-based planners. Such planners, while typically either resolution complete or probabilistically complete, are not able to determine when a path does not exist, and therefore would otherwise rely on heuristics to determine when the search for a free path should be abandoned. An implementation of the algorithm is provided for the case of a 3D Euclidean configuration space, and a proof of correctness is provided.

Original languageEnglish (US)
Title of host publication2012 IEEE International Conference on Robotics and Automation, ICRA 2012
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages2563-2569
Number of pages7
ISBN (Print)9781467314039
DOIs
StatePublished - Jan 1 2012
Event 2012 IEEE International Conference on Robotics and Automation, ICRA 2012 - Saint Paul, MN, United States
Duration: May 14 2012May 18 2012

Publication series

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

Other

Other 2012 IEEE International Conference on Robotics and Automation, ICRA 2012
CountryUnited States
CitySaint Paul, MN
Period5/14/125/18/12

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Artificial Intelligence
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Proving path non-existence using sampling and alpha shapes'. Together they form a unique fingerprint.

  • Cite this

    McCarthy, Z., Bretl, T. W., & Hutchinson, S. A. (2012). Proving path non-existence using sampling and alpha shapes. In 2012 IEEE International Conference on Robotics and Automation, ICRA 2012 (pp. 2563-2569). [6225300] (Proceedings - IEEE International Conference on Robotics and Automation). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICRA.2012.6225300