The minimum constraint removal problem with three robotics applications
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. © The Author(s) 2013.
Type
Journal articlePermalink
https://hdl.handle.net/10161/10778Published Version (Please cite this version)
10.1177/0278364913507795Publication Info
Hauser, K (2014). The minimum constraint removal problem with three robotics applications. International Journal of Robotics Research, 33(1). pp. 5-17. 10.1177/0278364913507795. Retrieved from https://hdl.handle.net/10161/10778.This is constructed from limited available data and may be imprecise. To cite this
article, please review & use the official citation provided by the journal.
Collections
More Info
Show full item recordScholars@Duke
Kris Hauser
Adjunct Associate Professor in the Department of Electrical and Computer Engineering
Robot motion planning and control, semiautonomous robots, and integrating perception
and planning. Applications of this research have included automated vehicle collision
avoidance, robotic manipulation, robot-assisted medicine, and legged locomotion.

Articles written by Duke faculty are made available through the campus open access policy. For more information see: Duke Open Access Policy
Rights for Collection: Scholarly Articles
Works are deposited here by their authors, and represent their research and opinions, not that of Duke University. Some materials and descriptions may include offensive content. More info