The minimum constraint removal problem with three robotics applications

Loading...
Thumbnail Image

Date

2014-01-01

Journal Title

Journal ISSN

Volume Title

Repository Usage Stats

180
views
525
downloads

Citation Stats

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.

Department

Description

Provenance

Subjects

Citation

Published Version (Please cite this version)

10.1177/0278364913507795

Publication 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.


Unless otherwise indicated, scholarly articles published by Duke faculty members are made available here with a CC-BY-NC (Creative Commons Attribution Non-Commercial) license, as enabled by the Duke Open Access Policy. If you wish to use the materials in ways not already permitted under CC-BY-NC, please consult the copyright owner. Other materials are made available here through the author’s grant of a non-exclusive license to make their work openly accessible.