常用的路径规划算法浅析

路径规划

所谓路径规划，也就是在起点和终点之间找到一条连续的运动轨迹，在尽可能优化路径的同时避开环境中的障碍物。

常用的路径规划算法有传统的基于图搜索算法、基于采样的路径规划算法，以及考虑动力学的路径规划算法等。那么，这几种路径规划算法分别适用于什么情况下呢？接下来我们就为大家详细介绍一下。

>>>>基于搜索的路径规划算法

基于搜索的路径规矩算法主要包含：BFS(广度优先)算法、DFS(深度优先)算法、Dijkstra算法、启发式搜索 A* 算法等。

一般而言，基于搜索的规划算法适用于运行在栅格地图上。通过在栅格地图上不断地搜索，进而检索出一条到达终点的连续轨迹。

虽然基于图搜索的规划算法总是能够给出一个全局范围内的最优解（路径最短、效率最优），但是当地图过大，规划的维度过高时，它的搜索效率就会变得很慢。

>>>>基于采样的路径规划

基于采样的路径规划主要包含：RRT(快速扩展随机树)算法、RRT*算法、informed RRT *算法等。

在某些场景下，对于路径规划算法的关注点主要放在效率上，那么基于采样的规划算法就更加符合要求。

这类算法的核心在于随机采样，从父节点开始，随机地在地图上生成子节点，连接父子节点并进行碰撞检测，若无碰撞，就扩展该子节点。通过不断地随机扩展样本点，直到生成一条连接起点和终点的路径。由于样本点是随机生成，所以最终执行的路径可能不是全局最优解，甚至还会明显感觉机器人在“绕路”。

相对于基于搜索的规划算法，基于采样的规划算法在效率上更优，因其不用遍历整个栅格地图，就能快速生成一条可行路径。

以上两种类型的算法并未考虑机器人运动限制，都只是考虑了“最近的路径”或“最快的路径”。如果想要在最短的时间内获得全局最优解，那么考虑动力学的路径规划算法将是一个不错的选择。

>>>>考虑动力学的路径规划

考虑动力学的路径规划主要包含：混合A* 算法、Kinodynamic RRT*算法等。

以无人车为例，如果生成一条有直角拐点的路径，对于两轮差速运动模型的无人车勉强可以通过这个直角拐点，因为差速模型无人车最小转弯半径为0，也就意味着可以原地旋转（但在实际运动过程也无法达到瞬间转向）。对于阿克曼运动模型的无人车（生活中的汽车就是采用的阿克曼转向系统），由于转弯半径不为0，因此经过直角拐点时就无法通过。考虑动力学的规划算法不再把机器人当作一个质点考虑，而是考虑了规划轨迹要满足动力学，生成的轨迹能使得机器人能真正执行。

以混合A*算法举例，考虑车辆运动学之后，出来的路径就不是直来直去的折线，而是较为平滑的曲线，并且在障碍物碰撞检测时，也不会单纯地将机器人作为一个质点，而是会考虑机器人轮廓。如下图所示，A*算法扩展节点时为八个格子，Hybrid A*算法扩展节点时有六个运动基原，向前扩展三个运动模式，向后扩展三个运动模式。

 目前Prometheus开源项目也包含了路径规划算法，若大家有相关需求，可以通过阿木实验室官网（开源项目 - 阿木实验室）进一步了解Prometheus开源项目。