转载：https://zhuanlan.zhihu.com/p/51372134 1 自主机器人近距离操作运动规划体系 在研究自主运动规划问题之前，首先需建立相对较为完整的自主运动规划体系，再由该体系作为指导，对自主运动规划的各项具体问题进行深入研究。根据自主机器人的思维方式、运动形式、任务行为等特点，建立与之相适应的自主运动规划体系。并按照机器人的数量与规模，将自主运动规划分为单个机器人的运动规划与多机器人协同运动规划两类规划体系。 1.1 单个自主机器人的规划体系 1.2 多自主机器人协同规划体系 2 路径规划研究 当给定了某一特定的任务之后，如何规划机器人的运动方式将至关重要。机器人的规划包括两部分内容：基座移动到适合操作的位置和转动手臂关节完成操作。包括三个问题：基座点到点运动规划；关节空间规划；综合规划。 本章研究几种常用的运动规划算法：图搜索法、RRT算法、人工势场法、BUG算法。 2.1 图搜索法 图搜索法依靠已知的环境地图以及地图中的障碍物信息构造从起点到终点的可行路径。主要分成深度优先和广度优先两个方向。深度优先算法优先扩展搜索深度大的节点，可以快速的得到一条可行路径，但是深度优先算法得到的第一条路径往往是较长的路径。广度优先算法优先扩展深度小的节点，呈波状的搜索方式。广度优先算法搜索到的第一条路径就是最短路径。 2.1.1 可视图法 可视图法能求得最短路径，但搜索时间长，并且缺乏灵活性，即一旦机器人的起始点和目标点发生改变，就要重新构造可视图，比较麻烦。可视图法适用于多边形障碍物，对于圆形障碍物失效。切线图法和Voronoi图法对可视图法进行了改进。切线图法用障碍物的切线表示弧，因此是从起始点到目标点的最短路径的图，移动机器人必须几乎接近障碍物行走。其缺点是如果控制过程中产生位置误差，机器人碰撞障碍物的可能性会很高。Voronoi图法用尽可能远离障碍物和墙壁的路径表示弧。因此，从起始点到目标点的路径将会增长，但采用这种控制方式时，即使产生位置误差，移动机器人也不会碰到障碍物。 2.1.2 Dijkstra算法 Dijkstra算法由荷兰计算机科学家艾兹赫尔·戴克斯特拉（Edsger Wybe Dijkstra）发明，通过计算初始点到自由空间内任何一点的最短距离可以得到全局最优路径。算法从初始点开始计算周围4个或者8个点与初始点的距离，再将新计算距离的点作为计算点计算其周围点与初始点的距离，这样计算像波阵面一样在自由空间内传播，直到到达目标点。这样就可以计算得到机器人的最短路径。 Dijkstra算法是一种经典的广度优先的状态空间搜索算法，即算***从初始点开始一层一层地搜索整个自由空间直到到达目标点。这样会大大增加计算时间和数据量。而且搜索得到的大量对于机器人运动是无用的。 详情请参考：https://zhuanlan.zhihu.com/p/51112799 2.1.3 A*算法 为了解决Dijkstra算法效率低的问题，A*算法作为一种启发式算法被提出。该算法在广度优先的基础上加入了一个估价函数。 详情请参考：https://zhuanlan.zhihu.com/p/51099376 2.2 RRT算法 快速搜索随机树（RRT）算法是一种增量式采样的搜索方法，该方法在应用中不需要任何参数整定，具备良好的使用性能。它利用增量式方法构建搜索树，以逐渐提高分辨能力，而无须设置任何分辨率参数。在极限情况，该搜索树将稠密的布满整个空间，此时搜索树由很多较短曲线或路经构成，以实现充满整个空间的目的。增量式方法构建的搜索树其导向取决于稠密采样序列，当该序列为随机序列时，该搜索树称为快速搜索随机树（Rapidly Exploring Random Tree，RRT），而不论该序列为随机还是确定性序列，都被称为快速搜索稠密树（Rapidly Exploring Dense Trees，RDTs），这种规划方法可处理微分等多种约束。 2.2.1 算法步骤 2.2.2 改进算法 2.3 滚动在线RRT算法 2.3.1 滚动规划 2.3.2 滚动在线RRT算法流程 2.4 人工势场法 2.4.1 基本人工势场法 2.4.2 人工势场法算法改进 2.5 BUG算法 2.5.1 BUG1算法 2.5.2 BUG2算法 2.5.3 TangentBUG算法 2.6 增量式启发算法 2.6.1 LPA*算法 2.6.2 D* Lite算法 2.7 小结