本文为美国卡内基梅隆大学（作者：Ross A. Knepper）的博士论文，共145页。

机器人运动规划的目标是与人类在环境中移动和互动的便捷性、效率相匹配。然而，最先进的机器人规划缺乏人类具备的能力，这些算法的计算速度较慢，输出结果的质量较低。在传统的运动规划中，一个绊脚石是点和路径常常被孤立地考虑。许多规划者没有意识到路径选择之间存在大量的共享信息。因此，利用路径选择之间的几何和拓扑关系可以提高效率和性能。这些好处包括：更优的信息路径采样、更快的碰撞检查以及对路径选择权衡的更深入理解。

在路径采样中，引入局部性原理作为构造自适应概率几何模型的基础，以影响碰撞试验路径的选择。我们认识到碰撞测试消耗了相当大的大部分规划时间，而且只有无碰撞路径才能为机器人选择执行路径提供价值，该模型通过绕过预测与障碍物碰撞的碰撞测试路径，显著提高了效率。在碰撞测试领域，使用一种称为局部路径等价的关系来发现测试路径的工作何时已经执行过。相邻路径备选方案的扫描区域经常重叠，这意味着中间路径的连续体也存在。通过识别具有相关形状和结果的此类相邻路径，可以在实验中隐式地测试多达90%的路径，绕过传统的、代价昂贵的碰撞测试，能够在碰撞测试性能上提高300%。局部路径等价也可以应用于路径选择问题，以识别更高层次的导航选择，并做出更明智的选择。这篇论文给出了这三个领域的理论和实验结果，以及对人类如何思考在空间运动的启示。

Robotic motion planning aspires to matchthe ease and efficiency with which humans move through and interact with theirenvironment. Yet state of the art robotic planners fall short of humanabilities; they are slower in computation, and the results are often of lowerquality. One stumbling block in traditional motion planning is that points andpaths are often considered in isolation. Many planners fail to recognize thatsubstantial shared information exists among path alternatives. Exploitation ofthe geometric and topological relationships among path alternatives cantherefore lead to increased efficiency and competency. These benefits include:better-informed path sampling, dramatically faster collision checking, and adeeper understanding of the trade-offs in path selection. In path sampling, theprinciple of locality is introduced as a basis for constructing an adaptive,probabilistic, geometric model to influence the selection of paths forcollision test. Recognizing that collision testing consumes a sizable majorityof planning time and that only collision-free paths provide value in selectinga path to execute on the robot, this model provides a significant increase inefficiency by circumventing collision testing paths that can be predicted tocollide with obstacles. In the area of collision testing, an equivalencerelation termed local path equivalence, is employed to discover when the workof testing a path has been previously performed. The swept volumes of adjoiningpath alternatives frequently overlap, implying that a continuum of intermediatepaths exists as well. By recognizing such neighboring paths with related shapesand outcomes, up to 90% of paths may be tested implicitly in experiments,bypassing the traditional, expensive collision test and delivering a net 300%boost in collision test performance. Local path equivalence may also be appliedto the path selection problem in order to recognize higherlevel navigationoptions and make smarter choices. This thesis presents theoretical andexperimental results in each of these three areas, as well as inspiration onthe connections to how humans reason about moving through spaces.

1. 引言

2. 分层规划

3. 分层规划器的应用

4. 路径集理论

5. 路径集设计

6. 路径采样

7. 碰撞测试

8. 路径选择

9. 本文扩展与未来工作展望

10.       结论

更多精彩文章请关注公众号：