A*算法在无人车路径规划中的应用

马 静，王佳斌，张 雪

(西安工业大学 计算机科学与工程学院，陕西 西安 710021)

A*算法在无人车路径规划中的应用

马 静，王佳斌，张 雪

(西安工业大学 计算机科学与工程学院，陕西 西安 710021)

近年来，无人车路径规划已经成为智能机器人研究的基础和核心方向之一，其为多学科技术研究提供了更加广阔的平台。针对路径规划算法进行研究，在理论模拟的基础上，结合车体的有向性实现智能车的路径规划策略。路径规划是无人车智能化的重要标志，也作为实现无人车自主导航的基础。以自主设计搭建的无人小车为实验平台，针对路径规划算法进行研究，在对Dijkstra算法等常用的路径规划算法进行优缺点分析后，选择了A*算法并实现了该算法。在理论模拟的基础上，对环境进行栅格化处理，并通过车体上的电子罗盘获取实时方向，结合A*算法进行车辆调转策略设置，最终实现了无人车路径规划策略。

无人车；路径规划；栅格地图；Dijkstra算法；A*算法；电子罗盘

0 引 言

无人车作为研究的热点问题之一，其研究方向主要包含传感器信息采集与融合技术、地图创建技术、图像识别和图像处理技术、导航及定位技术、路径规划技术以及车体控制技术等[1]。路径规划旨在实现无人车从起始状态到目标状态的一条最优或者近似最优的无碰撞路径。由于所处环境信息的不同，路径规划方案有两种：一种是基于已知的、静态的全局无人车路径规划方案；另一种是基于未知的、动态的局部无人车路径规划方案。

文中的无人车是以自制的、基于ARM Cortex-M3内核[2]的STM32系列处理器，并通过电子罗盘等传感器进行导向的“西工1号”作为实验研究平台。其主要是通过对已知环境状况进行栅格处理后，通过A*算法进行路径引导，并结合电子罗盘捕获的车体实时方向，最终实现已知静态环境下无人车的全局最短无碰撞路径规划[3]。

1 栅格法创建环境地图

环境地图的创建是无人车运转的基本条件，在机器人学中地图的表示信息创建方法有四种：拓扑地图[4]、特征地图[5]、直接表征法及栅格地图[6]。其中栅格法是通过将环境信息划分成一系列栅格，通过给栅格一个可能值来表示该栅格被占用的概率。在环境地图构建中，首先给所处环境建立二维坐标系，并对起始点、目标点、障碍物所在栅格设定不同标志，进而构造出一张环境状态栅格图。经过无人车平台测试，能够体现A*算法的执行效果。

2 寻径算法分类

针对寻径问题总结出的算法有很多种。在图论中，其主旨是解决从起点A到目标点B的一条通路问题。但在网络游戏中，寻径问题就变得更加复杂，考虑的因素更多，如游戏地图中，相关障碍物是否能够通过，以及目标点所在瓷砖能否通过等。针对不同环境的寻径问题，通常将地图寻径算法分为两大类，分别为盲目式搜索和启发式搜索。

2.1 盲目式搜索

盲目搜索作为一种传统的搜索算法，其主要采用的办法有深度优先搜索(Depth First Search)[7]、广度优先搜索(Breadth-First Search)[8]以及等价搜索。当针对这种问题进行搜索时，往往是采用某种固定的搜索方式进行搜索，不利用需解决问题的相关信息。因此其不利于进行一些较为复杂的寻径问题，因为这样会占用大量的计算空间和时间。

2.2 启发式搜索

启发式搜索[9](Heuristic Algorithm)就是在所构建的环境地图中，以起点A的相邻位置作为评估点，针对每个评估点的值进行比较，得到一个最佳的位置B，进而再以B的相邻位置作为下一部分评估点，直到最终找到目标点。通过这样的办法可以省去大量无用的路径搜索，从而提高效率。在启发式搜索中，对位置的评估是至关重要的，即选择的算法不同，其评估策略有所不同。常用的启发式算法有最好优先搜索法、局部择优搜索法等等，其中A*算法就是一种最好的优先算法。

3 基于栅格的路径规划算法

在无人车路径规划问题上，首先应解决对环境的建模问题，其次应解决的是寻找合适的算法实现路径规划策略。其中常有的路径规划算法有Dijkstra算法、A*算法、遗传算法[10]、蚁群算法[11]等。

3.1 基于栅格构图下的Dijkstra算法的最短路径规划

Dijkstra算法[12]使用了广度优先搜索解决非负权有向图的单元路径规划问题，它是典型的单元最短路径算法，用于计算一个节点到其他节点的最短路径，是很有代表性的最短路径算法。主要特点是以起始点为中心，向外层进行层层扩展，直到终点为止。如图1所示，在带权有向图G中从出发点即源点V0到目标点V5寻找一条最优路径。

图1 带权有向图G

3.1.1Dijkstra算法基本思想

按路径长度递增次序产生最短路径算法，把V分成两组：

(1)S：已求出最短路径的顶点集合。

(2)V-S=T：尚未确定最短路径的顶点集合。

将T中顶点按最短路径递增的次序加入到S中，并确保(1)从源点V0到S中各顶点的最短路径长度都不大于从V0到T中任何顶点的最短路径长度。

(3)每个顶点对应一个距离值。

S中顶点：从V0到此顶点的最短路径长度。

T中顶点：从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度。

3.1.2 算法实现

(1)初始时令S={V0},T={其余顶点}，T中顶点对应的距离值：

若存在，d(V0,Vi)为弧上的权值；

若不存在，d(V0,Vi)为∝。

(2)从T中选取一个其距离值为最小的顶点W且不在S中，加入S。

(3)对S中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值缩短，则修改此距离值。

重复上述步骤(2)、(3)，直到S中包含所有顶点，即W=Vi为止。

Dijkstra算法的成功率很高，它总能找到两点间的最短路径，但算法的时间复杂度为O(n2)，效率比较低，并且空间占用率较大，在路径规划中会受到地图大小以及节点个数的影响，因此搜索的速度较慢。

3.2 基于栅格构图下的A*算法最短路径规划

通过栅格法对无人车所处环境进行建模，如图2所示，并设定无人车的起点S和目标点G。在起点S和终点G之间通过算法选择一条最优或者近似最优的无碰撞路径。A*算法作为一种典型的启发式算法，在人工智能寻径问题中具有很广泛的应用，其将整个环境构造成栅格状，通过设定起点S、目标点G和障碍物B(灰色)，并通过相应的评价函数来进行最优路径分析，最终查找出最优路径。查找出最优路径后，通过与电子罗盘的结合，实现从仿真到实际的最短路径规划[13]。

图2 无人车环境建模

3.2.1A*算法

图3 A*栅格

3.2.2A*算法实施策略

A*算法评价函数为：

F'(n)=G'(n)+H'(n)

其中，F'(n)为起始节点经由节点n到目标节点的评估函数；G'(n)为起始节点到当前节点n的最优路径值，其为已经确定的值；H'(n)作为A*算法评价函数的核心，其为当前节点n到目标节点的启发值，即预估开销。

预估方法通常有两种：第一种为Manhattan预估方法[14]，即计算通过水平和垂直方向的平移到达目的所经过的方格数值的移动开销；第二种为Euclidean预估方法[15]，即计算当前节点n到目标节点的距离的移动开销。在此，文中采用第一种评估方法。

对于A*算法的搜索过程如下：

创建两个表OPEN和CLOSED，其中OPEN表保存所有已经生成而未考察的节点，CLOSED表保存已访问过的节点。

1.将S点放入OPEN表中，并且将CLOSED表置为空。

2.重复执行以下步骤：

(1)遍历OPEN，查找F'(n)min并将其作为预处理节点。

(2)将步骤(1)得到的节点移入CLOSED表中。

(3)对于当前节点的8个相邻节点的每一个节点作如下处理：

①如果其为障碍物或者已经移入CLOSED表中，则忽略掉此节点。

②如果其不在OPEN表中，则将其移入OPEN表，并将当前节点设置为其父节点，并记录F'(n)值。

③如果其已经在OPEN表中，通过G'(n)对OPEN表中节点再进行判断，如果有更小值，则将其父节点设置为当前节点，并重新计算F'(n)和G'(n)。

④将目标节点加入OPEN表中，即表示路径已经找到，否则查找失败，且OPEN为空，即无路径。

(4)保存路径，路径即为从目标节点开始，沿着父节点移动至起始节点所组成。

A*算法作为一种典型的启发式搜索算法，在人工智能寻径问题有着广泛的应用。其不必遍历所有节点，搜寻速度快，但由于评估进行移动开销预测，所以可能存在找不到最优路径的问题，有待于同其他寻径算法的对比论证和后期的改进。

4 电子罗盘

电子罗盘[16]能实时提供移动物体的航向和姿态，是一种重要的导航工具，也是路径规划技术研究中不可缺少的导向传感器。MAG3110是高精度的数字地磁传感器，方向定位准确，校准数据掉电保存。该罗盘分为3个轴，能定位准确的独立罗盘航向信息。在文中所提到的无人车路径规划中，主要用到X轴和Y轴，在水平面上为无人车的车头方向进行定位。

通过电子罗盘和A*算法结合实现路径规划，基于栅格地图的A*算法确定无人车行驶的路径，电子罗盘确定无人车实时车头方向。

4.1 设定下一步行走方向标志和车头实时方向标志

在栅格法构建的地图中，对中心栅格的相邻8个方向进行标识，如图4所示。其中，“0”代表无人车当前所处位置，“1”到“8”为无人车下一步可能行进的方向的标志。通过A*算法得到的路径来设定无人车下一步行进方向的方向标志位dir_sg，即dir_sg的值可能为“1”到“8”的任意值。通过电子罗盘对无人车车头实时方向进行判断，设定8个方向标志位，用dir_lp表示。如图4所示，“1”到“8”为dir_lp可能取得的值。

123804765

图4 栅格地图方向

4.2 两个标志结合实现路径规划

设定标志位dir，令dir=dir_sg-dir_lp，并设定无人车最小调转量为45°，最终通过dir值确定无人车调转方向和角度。无人车具体调转策略如下：

(1)当1≤dir≤4,无人车右转，转角为 dir*45°；

(2)当4≤dir≤7,无人车左转，转角为(8-dir)*45°；

(3)当-4≤dir≤(-1),无人车左转，转角为|dir|*45°；

(4)当-7≤dir<(-4)，无人车右转，转角为(8-|dir|)*45°。

例如，当前车头所指方向为“4”，即dir_lp=4，参考图4。以无人车当前所处栅格作为标志位为“0”栅格，并且通过A*算法确定下一步无人车要行进的栅格的标志位为“2”，即dir_sg=2。通过公式dir=dir_sg-dir_lp得dir=(-2),根据调转策略(3)可知，无人车左转|-2|*45°=90°，即无人车通过左转90°后车头可调整到目标方向，到达目标方向后前进即可到达目标栅格。

5 结束语

在无人车路径规划项目中，利用栅格法构建地图，A*算法来搜索从起点到终点的最优行驶路径，同时利用电子罗盘作为无人车行驶的导向，通过实验和仿真无人车能够寻找一条从起始状态到目标状态的无碰撞路径。栅格法划归地图并结合A*算法实现路径规划，是静态环境下无人车自主寻径的研究，对后续在动态环境下无人车自主寻径的研究打下了基础，也是该项目进一步研究的方向。

[1] 李江抒.多移动机器人路径规划算法与导航系统研究[D].长春：吉林大学,2004.

[2] 林恒杰.对基于ARM Cortex-M3嵌入式系统的仿真[D].上海：上海交通大学,2008.

[3] 刘淑华，夏 菁，孙学敏，等.已知环境下一种高效全覆盖路径规划算法[J].东北师大学报:自然科学版,2012,43(4):39-43.

[4] 王 娜.移动机器人拓扑地图创建研究[D].济南：山东大学,2009.

[5] 熊 蓉.室内未知环境线段特征地图构建[D].杭州：浙江大学,2009.

[6] 陈晓娥，苏 理.一种基于环境栅格地图的多机器人路径规划方法[J].机械科学与技术，2009，28(10)：1335-1339.

[7] 刘中华，张颖超.深度优先搜索的非递归算法[J].科技信息,2010(25)：160-161.

[8] 刘 翔，龚道雄.深度优先搜索算法和A*算法在迷宫搜索中的仿真研究[J].制造业自动化,2011,33(11)：101-104.

[9] 乐美龙，李 贞.基于深度优先搜索算法的机组复原研究[J].武汉理工大学学报，2012，34(9)：63-68.

[10] 孙树栋，林 茂.基于遗传算法的多移动机器人协调路径规划[J].自动化学报，2000,26(5):672-676.

[11] 段海滨,王道波,朱家强,等.蚁群算法理论及应用研究的进展[J].控制与决策，2004,19(12):1321-1326.

[12] 谭浩强，陈 明.实用数据结构基础[M].北京:清华大学出版社，2002.

[13] 樊 莉,孙继银,王 勇.人工智能中的A*算法应用及编程[J].微机发展(现更名：计算机技术与发展)，2003，13(5):33-35.

[14] 顾 青,豆风铅,马 飞.基于改进A*算法的电动车能耗最优路径规划[J].农业机械学报，2015，46(12):316-322.

[15] 王殿君.基于改进A*算法的室内移动机器人路径规划[J].清华大学学报:自然科学版，2012,52(8):1085-1089.

[16] 王勇军,李 智,李 翔.三轴电子罗盘的设计与误差校正[J].传感器与微系统，2010，29(10):110-112.

Application of A* Algorithm in Unmanned Vehicle Path Planning

MA Jing,WANG Jia-bin,ZHANG Xue

(School of Computer Science and Engineering,Xi’an Technological University,Xi’an 710021,China)

In recent years,path planning for unmanned vehicle is the basis and one of the core directions in intelligent robot research,which provides an extensive platform for multidisciplinary technology research.Aiming at the path planning,on the basis of theoretic simulation,the path planning strategy for intelligent vehicles is realized combining the direction of vehicle.Path planning is an important symbol of unmanned vehicle intelligence,also as a basis for autonomous navigation of unmanned vehicles.Taking unmanned vehicle of autonomous design as experiment platform,in view of the path planning algorithm for research,after analyzing the advantage and disadvantage for common path planning algorithms like Dijkstra,the A* algorithm is selected and implemented.On the basis of the theoretical simulation,rasterizing the environment,and through electronic compass in vehicle to get real-time direction,the A* algorithm is combined to carry out the vehicle shift strategy,finally realizing unmanned vehicle path planning strategy.

unmanned vehicle;path planning;grid map;Dijkstra algorithm;A*algorithm;electronic compass

2016-01-29

2016-05-11

时间：2016-10-24

国家大学生创新创业项目(201410702037)；西安工业大学跨学科研究基金(CXY1340-6)

马 静(1980-)，女，研究生，讲师，研究方向为嵌入式系统。

http://www.cnki.net/kcms/detail/61.1450.TP.20161024.1117.068.html

TP242.6

A

1673-629X(2016)11-0153-04

10.3969/j.issn.1673-629X.2016.11.034