路径规划——精选推荐

机器⼈路径规划研究综述1.什么是路径规划

路径规划技术是机器⼈研究领域中的⼀个重要分⽀。所谓机器⼈的最优路径规划问题，就是依据某个或某些优化准则（如⼯作代价最⼩，⾏⾛路线最短，⾏⾛时间最短等)，在其⼯作空间中找到⼀条从起始状态到⽬标状态的能避开障碍物的最优路径。依据某种最优准则，在⼯作空间中寻找⼀条从起始状态到⽬标状态的避开障碍物的最优路径。需要解决的问题：1.始于初始点⽌于⽬标点。2.避障。

3.尽可能优化的路径。2.路径规划技术分类

a.静态结构化环境下的路径规划，⽐如说slam把图做好了之后，在已有的图上进⾏路径规划，已知地图进⾏全局规划。

b.动态已知环境下的路径规划，⽐如说地图已知了，但是地图中有⼀些可以移动的障碍物，这些障碍物在⼀定时间内它的信息是未知的。c.动态不确定环境下的路径规划，环境是未知的，它要求机器⼈⾃⼰去⽣成⼀条路径，然后主动去探索环境。3.路径规划算法的分类第⼀种分类⽅式：

基于节点的⽅法也叫栅格法，把环境地图分为⼀个⼀个的栅格点，然后，在这些点上做路径规划。第⼆种分类⽅式：4.A*，D*算法

在计算机科学中，A*算法作为Dijkstra算法的扩展，因其⾼效性⽽被⼴泛应⽤于寻路及图的遍历，如星际争霸游戏中就⼤量使⽤。在理解算法前，我们需要知道⼏个概念：开放列表（Open List）：

我们将路径规划过程中待检测的节点存放于Open List中，⽽已检测过的格⼦则存放于Close List中。⽗节点（parent）：

在路径规划中⽤于回溯的节点，开发时可考虑为双向链表结构中的⽗结点指针。路径排序（Path Sorting）

具体往哪个结点移动由以下公式确定：F（n）=G（n）+H（n）

G代表的是从初始位置A沿着已⽣成的路径到指定待检测格⼦的移动开销。H指定待测格⼦到⽬标节点B的估计移动开销。启发函数（Heuristics Function）：

H为启发函数，也被认为是⼀种试探，由于在找到唯⼀路径前，我们不确定在前⾯会出现什么障碍物，因此⽤了⼀种计算H的算法，具体根据实际场景决定。在我们简化额模型中，H采⽤的是传统的曼哈顿距离（Manhattan Distance），也就是横纵向⾛的距离之和。如下图所⽰，绿⾊⽅块为机器⼈起始位置A，红⾊⽅块为⽬标位置B，蓝⾊为障碍物。

现⽤A*算法寻找出⼀条⾃绿⾊A到红⾊B的最短路径，经简化，每个⽅格的边长为10，即垂直⽅向移动开销为10.节点对⾓线为10，因此斜对⾓移动开销约等于14.因此具体步骤如下：

1.将A点加⼊到Open List中，图中所⽰，上下左右移动⼀格距离为10，斜对⾓移动距离为14.环绕绿⾊⽅块的就是待检测格⼦，左下⾓的值就是G值，右下⾓为H值，左上⾓对应的就是F值，找到F值最⼩的节点作为新的起始位置。

2.绿⾊格⼦右侧的节点F为40，选做为当前处理节点，并将这个节点从Open List删除，增加到Close List中，对这个节点周围的8个格⼦进⾏判断，若是不可通过或已经在Close List中，则忽略之。否则执⾏以下步骤：

若当前处理格⼦的相邻格⼦已经在OpenList中，那就计算临近节点经当前处理节点到起点的距离G是否⽐原G值⼩，若⼩，则把相邻节点的⽗节点（parent）设置为当前处理节点。若没有，则把当前节点从closeList中删掉，重新开始步骤1,2.若当前处理格⼦的相邻格⼦不在OpenList中，那么把它加⼊，并将它的⽗节点设置为该节点。

3.重复1、2步骤，直到终点B加⼊到了OpenList中，再沿着各节点的⽗节点回溯遍历，将遍历得到的节点坐标保存下来，所得的节点就是最短路径。