Hardness of 3D Motion Planning Under Obstacle Uncertainty
| Autor: | Brian Axelrod, Luke Shimanuki |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
0209 industrial biotechnology
Mathematical optimization Computer science Polytope 02 engineering and technology 010501 environmental sciences Collision 01 natural sciences Computer Science::Robotics 020901 industrial engineering & automation Obstacle Graph (abstract data type) Configuration space Motion planning 0105 earth and related environmental sciences |
| Zdroj: | Springer Proceedings in Advanced Robotics ISBN: 9783030440503 WAFR |
| Popis: | We consider the problem of motion planning in the presence of uncertain obstacles, modeled as polytopes with Gaussian-distributed faces (PGDF). A number of practical algorithms exist for motion planning in the presence of known obstacles by constructing a graph in configuration space, then efficiently searching the graph to find a collision-free path. We show that such a class of algorithms is unlikely to be efficient in the domain with uncertain obstacles. In particular, we show that safe 3D motion planning among PGDF obstacles is \(NP-\)hard with respect to the number of obstacles, and remains \(NP-\)hard after being restricted to a graph. Our reduction is based on a path encoding of \(3-\)SAT and uses the risk of collision with an obstacle to encode the variable assignment. This implies that, unlike in the known case, planning under uncertainty is hard, even when given a graph containing the solution. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|