The minimum constraint removal problem with three robotics applications
Author:
- 9 December 2013
- journal article
- research article
- Published by SAGE Publications in The International Journal of Robotics Research
- Vol. 33 (1) , 5-17
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.Keywords
This publication has 14 references indexed in Scilit:
- Proving path non-existence using sampling and alpha shapes2012
- Incremental Sampling-based Algorithms for Optimal Motion Planning2010
- A Simple Path Non-existence Algorithm Using C-Obstacle Query2008
- NAVIGATION AMONG MOVABLE OBSTACLES: REAL-TIME REASONING IN COMPLEX ENVIRONMENTSInternational Journal of Humanoid Robotics, 2005
- Path planning in expansive configuration spaces2002
- Disconnection proofs for motion planning2002
- Randomized Kinodynamic PlanningThe International Journal of Robotics Research, 2001
- Fully Dynamic Algorithms for Maintaining Shortest Paths TreesJournal of Algorithms, 2000
- An empirical study of phase transitions in binary constraint satisfaction problemsArtificial Intelligence, 1996
- On the hardness of approximating minimization problemsJournal of the ACM, 1994