TY - GEN
T1 - The minimum constraint removal problem with three robotics applications
AU - Hauser, Kris
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2013.
PY - 2013
Y1 - 2013
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85009495498&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85009495498&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-36279-8_1
DO - 10.1007/978-3-642-36279-8_1
M3 - Conference contribution
AN - SCOPUS:85009495498
SN - 9783642362781
T3 - Springer Tracts in Advanced Robotics
SP - 1
EP - 17
BT - Springer Tracts in Advanced Robotics
A2 - Frazzoli, Emilio
A2 - Roy, Nicholas
A2 - Lozano-Perez, Tomas
A2 - Rus, Daniela
PB - Springer
T2 - 10th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2012
Y2 - 13 June 2012 through 15 June 2012
ER -