Advertisement
Published in:
2013 | OriginalPaper | Chapter
The Minimum Constraint Removal Problem with Three Robotics Applications
Author : Kris Hauser
Published in: Algorithmic Foundations of Robotics X
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.