Hardness of 3D Motion Planning Under Obstacle Uncertainty
Hardness of 3D Motion Planning Under Obstacle Uncertainty
复制标题
障碍物不确定性下的3D运动规划的硬度
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Brian Axelrod
中科院分区：
文献类型：
--
作者：
Luke Shimanuki;Brian Axelrod
我们考虑存在不确定障碍物的运动规划问题，将其建模为具有高斯分布面（PGDF）的多面体。在已知障碍物的情况下，通过在构形空间中构造一个图，然后在图中进行有效的搜索，找到一条无碰撞的路径，这类算法在障碍物不确定的情况下是不可能有效的。特别是，我们证明了PGDF障碍物之间的安全3D运动规划对于障碍物的数量是\（NP-\）困难的，并且在被限制到图之后仍然是\（NP-\）困难的。我们的约简基于\（3-\）SAT的路径编码，并使用与障碍物碰撞的风险来编码变量分配。这意味着，与已知的情况不同，即使给出一个包含解的图，在不确定性下进行规划也是困难的。
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.