A simple, but NP-hard, motion planning problem

Lawrence H. Erickson, Steven M. La Valle

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Determining the existence of a collision-free path between two points is one of the most fundamental questions in robotics. However, in situations where crossing an obstacle is costly but not impossible, it may be more appropriate to ask for the path that crosses the fewest obstacles. This may arise in both autonomous outdoor navigation (where the obstacles are rough but not completely impassable terrain) or indoor navigation (where the obstacles are doors that can be opened if necessary). This problem, the minimum constraint removal problem, is at least as hard as the underlying path existence problem. In this paper, we demonstrate that the minimum constraint removal problem is NP-hard for navigation in the plane even when the obstacles are all convex polygons, a case where the path existence problem is very easy.

Original languageEnglish (US)
Title of host publicationProceedings of the 27th AAAI Conference on Artificial Intelligence, AAAI 2013
Pages1388-1393
Number of pages6
StatePublished - Dec 1 2013
Event27th AAAI Conference on Artificial Intelligence, AAAI 2013 - Bellevue, WA, United States
Duration: Jul 14 2013Jul 18 2013

Publication series

NameProceedings of the 27th AAAI Conference on Artificial Intelligence, AAAI 2013

Other

Other27th AAAI Conference on Artificial Intelligence, AAAI 2013
CountryUnited States
CityBellevue, WA
Period7/14/137/18/13

ASJC Scopus subject areas

  • Artificial Intelligence

Fingerprint Dive into the research topics of 'A simple, but NP-hard, motion planning problem'. Together they form a unique fingerprint.

  • Cite this

    Erickson, L. H., & La Valle, S. M. (2013). A simple, but NP-hard, motion planning problem. In Proceedings of the 27th AAAI Conference on Artificial Intelligence, AAAI 2013 (pp. 1388-1393). (Proceedings of the 27th AAAI Conference on Artificial Intelligence, AAAI 2013).