规划层技术之路径规划（1）

所谓路径规划，也就是在起点和终点之间找到一条连续的运动轨迹，在尽可能优化路径的同时避开环境中的障碍物。
常用的路径规划算法有传统的基于图搜索的路径规划算法、基于采样的路径规划算法、考虑动力学的路径规划算法等。

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

主要包含：BFS（广度优先）算法、DFS（深度优先算法）、Dijkstra算法、A Star算法等。
该类算法适用于运行在栅格地图上，通过在栅格地图上不断地搜索，进而检索出一条到达终点的连续轨迹。
虽然最后总是能够给出一个全局范围内的最优解（路径最短、效率最高），但是当地图过大，规划的维度过高时，它的搜索效率就会变得很慢。

基于采样的路径规划算法

主要包含：RRT（快速拓展随机树）算法、RRT Star算法、informed RRT Star算法等。
在某些场景下，对于路径规划算法的关注点主要放在效率上，那么基于采样的规划算法就更加符合要求。
这类算法的核心在于随机采样，从父节点开始，随机地在地图上生成子节点，连接父节点并进行碰撞检测，若无碰撞就扩展该子节点。通过不断地随机扩展样本点，直到生成一条连接起点和终点的路径。由于样本点是随机生成，所以最终执行的路径可能不是全局最优解，甚至还会明显感觉机器人在”绕路”。
相对于基于搜索的规划算法，基于采样的规划算法在效率上更优，因其不用遍历整个栅格地图，就能生成一条可行路径。

考虑动力学的路径规划算法

主要包含：混合A Star算法、Kinodynamic RRT Star算法等。
前面的两种类型的算法并未考虑机器人的运动限制，都只是考虑了”最近的路径”或”最快的路径”。考虑动力学的规划算法不再把机器人当作一个质点，而是考虑了规划轨迹要满足动力学，生成的轨迹能使得机器人能真正执行。