路径规划

路径规划

机器人路径规划研究综述

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中，再沿着各节点的父节点回溯遍历，将遍历得到的节点坐标保存下来，所得的节点就是最短路径。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。