论文标题
在具有昂贵评估边缘的图表上任何时间运动计划的后验采样
Posterior Sampling for Anytime Motion Planning on Graphs with Expensive-to-Evaluate Edges
论文作者
论文摘要
碰撞检查是运动计划中的计算瓶颈，需要明确推理何时执行此计算的懒惰算法。面对碰撞不确定性的乐观情绪可以最大程度地减少查找最短路径之前的检查。但是，在此期间没有发现其他可行的路径，这可能需要花费很长时间的计算。对于许多实时应用，我们需要随时进行强劲的表现，这定义为最小化可行路径的累积长度随着时间的流逝而产生的。我们介绍了运动计划（PSMP）的后验采样，这是一种懒惰运动计划算法，利用在边缘碰撞上学习的后二，以迅速发现最初的可行路径并逐渐产生较短的路径。 PSMP获得了$ \ tilde {o}（\ sqrt {\ Mathcal {s} \ Mathcal {a} t}）$的预期后悔，并且在一组2D和7D计划问题上均优于比较基线。
Collision checking is a computational bottleneck in motion planning, requiring lazy algorithms that explicitly reason about when to perform this computation. Optimism in the face of collision uncertainty minimizes the number of checks before finding the shortest path. However, this may take a prohibitively long time to compute, with no other feasible paths discovered during this period. For many real-time applications, we instead demand strong anytime performance, defined as minimizing the cumulative lengths of the feasible paths yielded over time. We introduce Posterior Sampling for Motion Planning (PSMP), an anytime lazy motion planning algorithm that leverages learned posteriors on edge collisions to quickly discover an initial feasible path and progressively yield shorter paths. PSMP obtains an expected regret bound of $\tilde{O}(\sqrt{\mathcal{S} \mathcal{A} T})$ and outperforms comparative baselines on a set of 2D and 7D planning problems.
