The minimum constraint removal problem with three robotics applications

Research output: Contribution to journalArticlepeer-review

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. It describes a probabilistic roadmap motion planner for MCR in continuous configuration spaces that 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. Two search algorithms are described 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. It is demonstrated on three example applications: generating human-interpretable excuses for failure, motion planning under uncertainty, and rearranging movable obstacles.

Original languageEnglish (US)
Pages (from-to)5-17
Number of pages13
JournalInternational Journal of Robotics Research
Volume33
Issue number1
DOIs
StatePublished - Jan 2014
Externally publishedYes

Keywords

  • Motion planning
  • computational complexity
  • configuration space
  • robot manipulators

ASJC Scopus subject areas

  • Software
  • Modeling and Simulation
  • Mechanical Engineering
  • Artificial Intelligence
  • Electrical and Electronic Engineering
  • Applied Mathematics

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

Cite this