路径规划算法-备忘

图搜索法

可视图法

1979年提出，机器人由点来描述，障碍物用多边形来描述，组合连接各顶点，且各顶点间连线时可见的，再利用优化算法搜索从起点S到终点G的最优路径。

Dijkstra算法

属于广度优先的状态空间搜索算法，耗时间与空间较大，维护两个顶点集合，第一个集合初始含源点，每次从另一个集合中选取最短路径点到前集合中，直到另一个结合为空。

A*算法

为了解决Dijkstra算法效率低的问题，作为一种启发式算法被提出。该算法在广度优先的基础上加了一个估价函数。

f(n)=g(n)+h(n)f(n)=g(n)+h(n)f(n)=g(n)+h(n)

其中g(n)称为耗散函数，表示从起始节点到节点n的实际代价。h(n)称为启发函数，表示节点n到目标节点的估计代价。距离表中按f(n)排序。启发函数的取值可以是两点间的欧式距离或曼哈顿距离（绝对轴距之和）等。

需要维护open list及close list和路径代价G、H和F。

是一个可采纳的最好优先算法。

RRT算法

快速搜索随机树算法（Rapidly Exploring Random Tree）是一种增量式采样的搜索方法。每次随机生成一个点，从树中找到与其最近节点后朝随机点方向生长一段距离，如非障碍物则加入树中，否则放弃这次生长。

概率完备非最优。

滚动在线RRT算法

人工势场法

基本思想是将目标和障碍物对机器人运动的影响具体化成人造势场。目标处势能低，障碍物处势能高。这种势差产生了目标对机器人的引力和障碍物对机器人的斥力，其合力控制机器人沿势场的负梯度方向向目标点运动。

优点：计算方便、得到的路径安全平滑；缺点：复杂势场环境可能导致机器人无法到达目标。

BUG算法

原理类似昆虫爬行的运动决策策略。在未遇到障碍物时，沿直线向目标运动；在遇到障碍物后，沿着障碍物边界绕行，并利用一定的判断准则离开障碍物继续直行。

计算方便，不需要获知全局地图和障碍物形状，具备完备性。但是生成的路径不够平滑，对机器人的各种微分约束适应性比较差。

增量式启发算法

LPA*算法

D* Lite算法

总结

人工势场法应用灵活，可以在保证安全的情况下获得一条平滑路径，并且对于动态环境可以实现实时运动控制，适合于长距离机动且障碍物较少的情况。而基于随机采样的搜索树方法可以在复杂约束环境中获得可行解，适合于机械臂近距离操作。