卷烟厂AGV小车路径规划地图的构建探讨

摘 要：上世纪六十年代末期，Hart等人公开发表了一篇论文，该论文中阐述了一种设计思路十分精巧且高效的路径规划算法，这种算法呗命名为A-Star算法，简称A*算法。

关键词：卷烟厂；AGV；小车路径规划；构建

A*算法是一种静态路网中求解最短路最有效的直接搜索方法，要想理解A*算法的奥义，还需从启发式搜索算法说起。启发式搜索算法（Heuristically Search）亦称为信息搜索法，它是利用问题拥有的启发信息来引导搜索，达到减少搜索范围、降低问题复杂度的目的。启发式搜索与有序搜索有着本质的不同，启发式搜索引入了估价函数这一概念，通过估价函数对下一步节点的估价值来确定下一步路径方向。因此启发信息越多，估价函数的估价将会越准确，扩展的无用节点数就会越少，这一遍可以大大降低系统工作量，提高系统的工作效率。而有序搜索方法极具代表性的有深度优先搜索（Depth First Search，DFS）、广度优先搜索（Breadth First Search，BFS）及上文所介紹的Dijkstra算法。Dijkstra算法此处便不再赘述，DFS和BFS是两种早期的有序搜索方法，但二者均属于盲目型搜索。也就是说，它不会选择哪个结点在下一次搜索中更优而去跳转到该结点进行下一步的搜索。二者属于盲目且执着的搜索方法，有时经常需要试探完整个解集空间才能完成路径搜索，显然，此类方法只能适用于问题规模不大的搜索问题中。而与DFS和BFS不同的是，一个经过设计的启发函数，往往会在很快的时间内就可得到一个搜索问题的最优解。

A*算法作为启发式搜索算法中较为优秀的一员，在实际工业生产应用中被广泛使用。该方法与Dijkstra算法类似，都可以找到一条最优路径，其不同之处就是A*算法具备了一个估价函数，如式（1-1）所示：

f（n）=g（n）+h（n） （1-1）

其中，f（n）是每个可能节点的评估值，g（n）表示从起始节点到当前节点的代价值，h（n）则表示从当前节点到目标节点的估计值，是启发式搜索中的核心部分，h（n）设计的好坏直接影响着A*算法的性能。

一种具有f（n）=g（n）+h（n）策略的启发式算法能成为A*算法的充分条件是：

①搜索树上存在着从起始点到终了点的最优路径；

②问题域是有限的；

③所有结点的子结点的搜索代价值>0；

④h（n）≤h*（n），其中h*（n）为实际问题的代价值。

当以上四个条件都满足时，一个具有f（n）=g（n）+h（n）策略的启发式算法能成为A*算法，并一定能找到最优解。

对于一个合格的A*算法而言，其h（n）函数的选取是决定算法性能的重中之重，现阶段常用的几种估算方法有曼哈顿距离法、欧式距离法以及契比雪夫距离法。

一、曼哈顿距离

曼哈顿距离（Manhattan Distance）又称出租车集合距离，是十九世纪有赫尔曼闵可夫斯基所常遭的集合度量用语。曼哈顿距离所表述的意思是两个点在标准坐标系上的绝对轴距总和，其在二维空间中的表述如公式（1-2）所示：

d=|x1-x2 |+|y1-y2 | （1-2）

其中x和y为两点坐标。

二、欧式距离

欧氏距离（Euclidean Distance）也称为欧几里得度量（Euclidean Metric），是一个惯用的距离定义，指在m维空间中两个点之间的真实距离，或者向量的自然长度（即该点到原点的距离）。其在二维空间中的表述如公式（1-3）所示：

（1-3）

三、契比雪夫距离

契比雪夫距离（Chebyshev Distance）是对向量空间中的一种度量，两个点之间的距离定义为其各坐标数值差的最大值。例如存在两个点坐标分别为（x1，y1）和（x2，y2），其契比雪夫距离为：

d=max（|x1-x2|，|y1-y2|） （1-4）

以上三种方法所适用的范围不同，且效果也不尽相同。

如图1-11所示设在一片环境区域内存在两个节点，一个为起始节点（绿色）另一个为目标节点（红色），首先用上文所述的Dijkstra算法来为起始节点到目标节点进行最优路径规划，左右下角数字之和为上面的数字，本实验里有两个函数，一个是g（n），一个是h（n），这两个数分别是它俩的值，它俩之和为f（n），具体情况如图1-11所示。

从图1-11中不难看出，Dijkstra算法在进行路径搜索时，几乎遍历了整个搜索范围，说明Dijkstra算法在路径搜索过程中付出了较大的计算量，致使搜索速度慢，对速度要求较高的移动机器人来讲该算法可能并不是十分适合。

从图1-12中不难看出，采用了曼哈顿距离法的A*算法搜索效果较Dijkstra算法要好很多，其无需遍历整个搜索范围即可准确找到最佳路径，其计算量相对较少，运算速度快，十分适合对速度有一定要求的移动机器人自主导航使用。为了验证其他两种距离方法在该问题上的实际效果，本文章也对采用了其他两种距离算法的A*算法进行了测试研究，具体情况请参照图1-13和1-14。

从图1-12、1-13和1-14中不难看出，在完全相同的情况下，采用曼哈顿距离法的A*算法遍历的范围最小，其他两种方法均较多。所以我们选定卷烟厂AGV小车路径规划地图的构建探讨。

作者简介：郑晓耘，河北白沙烟草有限责任公司。