The minimum constraint removal problem with three robotics applications
Published
Conference Paper
© Springer-Verlag Berlin Heidelberg 2013. 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.
Full Text
Duke Authors
Cited Authors
- Hauser, K
Published Date
- January 1, 2013
Published In
Volume / Issue
- 86 /
Start / End Page
- 1 - 17
Electronic International Standard Serial Number (EISSN)
- 1610-742X
International Standard Serial Number (ISSN)
- 1610-7438
International Standard Book Number 13 (ISBN-13)
- 9783642362781
Digital Object Identifier (DOI)
- 10.1007/978-3-642-36279-8_1
Citation Source
- Scopus