The minimum constraint removal problem with three robotics applications

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

Abstract

This paper formulates a new Minimum Constraint Removal (MCR) motion planning problem in which the objective is to remove the fewest geometric constraints necessary to connect a start and goal state with a free path. I present a probabilistic roadmap motion planner for MCR in continuous configuration spaces. The planner operates by constructing increasingly refined roadmaps, and efficiently solves discrete MCR problems on these networks. A number of new theoretical results are given for discrete MCR, including a proof that it is NP-hard by reduction from SET-COVER, and I describe two search algorithms that perform well in practice. The motion planner is proven to produce the optimal MCR with probability approaching 1 as more time is spent, and its convergence rate is improved with various efficient sampling strategies. The planner is demonstrated on three example applications: generating human-interpretable excuses for failure, motion planning under uncertainty, and rearranging movable obstacles.

Original languageEnglish (US)
Title of host publicationSpringer Tracts in Advanced Robotics
EditorsEmilio Frazzoli, Nicholas Roy, Tomas Lozano-Perez, Daniela Rus
PublisherSpringer-Verlag Berlin Heidelberg
Pages1-17
Number of pages17
ISBN (Print)9783642362781
DOIs
StatePublished - 2013
Externally publishedYes
Event10th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2012 - Cambridge, United States
Duration: Jun 13 2012Jun 15 2012

Publication series

NameSpringer Tracts in Advanced Robotics
Volume86
ISSN (Print)1610-7438
ISSN (Electronic)1610-742X

Other

Other10th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2012
CountryUnited States
CityCambridge
Period6/13/126/15/12

ASJC Scopus subject areas

  • Electrical and Electronic Engineering
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'The minimum constraint removal problem with three robotics applications'. Together they form a unique fingerprint.

Cite this