基于GIS地图的移动机器人路径规划

张丽娟，毕德学

(天津科技大学机械工程学院，天津 300222)

基于GIS地图的移动机器人路径规划

张丽娟，毕德学

(天津科技大学机械工程学院，天津 300222)

针对移动机器人路径规划实现条件的限制，提出基于GIS(geographic information system)地图的移动机器人路径规划．该方法应用改进A*算法，较好地实现了移动机器人的最优路径规划．在任意给定的地图中，只要确定了机器人的起点和终点，就可以找到该机器人在实际工作环境中符合需求的路径规划轨迹．应用VC++编程进行实验，证明了该方法的有效性．

机器人路径规划；GIS地图；改进A*算法；估价函数

机器人路径规划是智能机器人研究领域中的一个核心问题，其研究的目的是希望未来的智能机器人具有感知、规划和控制等高层能力，即它们能从周围的环境中收集信息，构建一个关于所在环境的模型，并且利用这个模型来规划和执行高层任务．路径规划的核心是，在给定全局信息的地图中机器人能够躲避障碍物，并且按照一定的评价标准找到一条从起点到终点的可行路径[1–2]．

典型的机器人路径规划方法有可视图法、自由空间法、栅格法、人工势场法等．因为各种方法在环境信息完全已知的情况下，均对地域地形、障碍物形状有严格要求，所以对移动机器人的应用环境有一定的局限性．A*算法是人工智能中的一种典型的启发式搜索算法，它引入了启发函数的概念，加入了全局信息[2]．可以将传统A*算法用于机器人路径规划，寻求最短路径[3]．但是在实际应用中，还需要根据实际情况进行道路的选择，即对于不同的环境信息(例如：公路、房屋、草坪、操场等)，要权衡各种路况信息，进行综合评价后决策．

本文应用改进A*算法提出基于GIS(geographic information system)地图的移动机器人路径规划，可以实现在任意地图中综合考虑环境中的所有信息，按照一定的评价标准找到相对评价标准的最优路径，而并非可行走意义上的最短路径．

1 A*算法

1.1 A*算法原理

A*算法广泛应用于最优路径求解和一些策略设计的问题中，其关键元素是启发函数，记为f(n)，f(n)为起点到达节点的耗散g(n)和从该节点到目标节点的耗散h(n)的综合评价，即：f(n)＝g(n)＋h(n)．其中，g(n)给出了从起始节点到节点n的路径耗散，而h(n)是启发式搜索中最为重要的一部分，是从节点n到目标节点的最低耗散路径的估计耗散值．因此，f(n)等于经过节点n的最低耗散解的估计耗散[4]．当启发函数f(n)＝g(n)，即h(n)＝0时，A*算法退化为广度优先搜索算法；当启发函数f(n)＝h(n)，即g(n)＝0时，A*算法退化为贪心算法[5]．

1.2 A*算法核心过程

在每次选择下一个当前搜索点时，是从所有已探知的但未搜索过的点中选取最有希望到达终点的点(f最小的点)进行展开，其中“所有已探知的但未搜索过的点”可通过一个按f升序排列的表获得．在f升序排列的表中，取表头节点，对其可能子节点计算g、h和f的数值，直到表为空或找到终点为止[6]．

2 改进A*算法

2.1 改进A*算法思想

改进A*算法的思想是通过改变代价函数的权值来处理不同的环境信息．针对不同的路况和不同的需求信息，选择不同的权值进行代价函数的优化处理，改进的A*算法提高了机器人路径规划的智能化程度．

在一些情况下，还需要对可行路径进行优化，即减少不必要的路过点．假设机器人路径规划中记录的可行点为(n1，n2，…)，那么可通过计算其中两点间是否有障碍物来进行筛选，如果两点间无障碍物，则直接保存这两点，忽略中间的可行路径点，达到优化可行路径的目的．另外，某些情况还需要进行路径平滑．此时，可通过对可行路径节点的代价值进行加权处理得到，如果下一可行路径点相对于之前所走路径有转角，则增加此下一可行节点的代价值，使其所选节点走出的路径尽量平滑[7]．

2.2 改进A*算法的实现

(1)创建列表Open，初始化为只包含起始点．(2)创建列表Close，初始化为空．

(3)从Open表中选择f数值最小的节点nmin，将其从Open表中删除，并插入到Close表的表头．

(4)如果nmin是目标节点，停止搜索．

(5)对于nmin的8个相邻节点：如果m在Close表中，则跳过此节点；如果m在Open表中且当前g(m)更小，更新节点m的g(m)，并使其父节点指向nmin；如果m不在Open和Close两表中，根据具体情况，区分出道路、房屋、草坪、操场等，按照给定的具体情况的不同权值分别计算f，将m插入到Open表中，插入的同时排序，使得Open表中f数值始终都为从小到大排列，计算m点的f，并将其父节点指向nmin．

(6)返回(3)，继续搜索．

(7)从终点向上回溯到起始点，记录栅格路径．

3 实 验

为验证算法用于机器人路径规划的有效性，将本文算法与A*算法进行对比．实验用的计算机配置：处理器Inel(R)Pentium(R)Dual E2160 @ 1.80,GHz 1.79,GHz，内存1,GB 266.0,MHz．

3.1 地图的基本处理

实验中机器人实时提取信息，故地图采用灰度图像. 灰度图像只包含亮度信息，通常划分成0～255共256个级别，0最暗，255最亮．灰度图像具有以下优点：(1)灰度图像是将彩色图像的RGB值通过一定的算法量化得到，其同一像素的RGB值相等；(2)图像数据即调色板索引值，也就是实际的RGB亮度值；(3)灰度图像使用256色的调色板，图像数据中一个字节代表一个像素，便于计算机处理．

图1为应用于机器人路径规划的基本地图，图中的环境信息中包含房屋、道路、草坪、树木等．为满足需要，在实验前已对地图进行必要的处理，包括灰度转化、直方图均衡化等处理．

图1 实验用基本地图Fig. 1 Basic map for the experiment

3.2 基于A*算法的机器人路径规划

实验中设置：房屋、草坪、树木为机器人不可达区域，道路、平地为机器人可行走区域．对图1采用A*算法进行机器人路径规划，其结果如图2所示．图

2中路径规划的节点个数为258，耗时1.844,s．

图2 基于A* 算法的机器人路径规划轨迹Fig. 2 Path of the robot based on A* algorithm

3.3 基于改进A*算法的机器人路径规划

路径规划采用的评价标准为在安全性的情况下，路径最短，耗能和时间最少．实验中设置：房屋墙壁、树木不可通行，即权值为无穷大；因为公路摩擦力小，耗能少，时间短，则相应选取的权值小；草坪在路过时摩擦力大，耗能大，则相应选取的权值较大．

分别取不同的权值进行机器人路径规划．设置在道路的权值为0.8，草坪的权值为1.4，路径规划结果如图3(a)所示．图3(a)中路径规划的节点个数为205，耗时0.172,s．设置道路的权值为0.8，草坪的权值为1.8，路径规划结果如图3(b)所示．图3(b)路径规划的节点个数为214，耗时0.109,s．

3.4 结果分析

由图2可以看出应用A*算法找到了一条可行的最短路径．对于两点间求解最优路径问题，只要有解，A*算法一定可以求得最优解，在图2也得到证明.

由图3可以看出，机器人找到一条由起点通向终点的最优路径．与图2不同的是，在图3中机器人选择穿过草坪到达目的地．出现图3中路径规划结果的原因是，在给定的评价标准中，草坪并非严格不可行，只是相对道路而言不是优先选择．应用改进A*算法的机器人路径规划相比应用A*算法的机器人路径规划而言，实现了自主选择通过草坪而到达终点的目的，并且可以通过改变道路或者草坪的权值来实现不同的路径规划，可满足实际应用的需求．

对比图3(a)和图3(b)可知，在不改变道路的权值，而增大草坪权值的情况下，机器人选择尽量避开草坪．在实际生活中，如果发生紧急事件，要求综合考虑整体评价标准，且对时间性要求很高时，可以像基于改进A*算法实验中所选择的一样，通过草坪而到达目的地，此时A*算法不能实现．

图3 基于改进A*算法的机器人路径规划轨迹Fig. 3 Path of the robot based on improved A* algorithm

综上可以看出，改进A*算法的机器人路径规划方法通过综合评价，选择对整体更有利的路线，达到整体效果最优，可得到实际应用中的最优路径．

4 结 语

本文基于改进A*算法实现基于GIS地图的移动机器人路径规划，并进行实验．通过实验结果可以看出，该方法考虑更多实际因素，能实现符合实际需求的最优路径规划，而并非只是可行走意义上的最短路径规划，从而更符合实际需求.

［1］ 黎红. 自主移动机器人路径规划中的主要方法[J]. 中国电力教育，2010(s1)：814–816.

［2］ Masehian E，Amin-Naseri M R. A voronoi diagramvisibility graph-potential field compound algorithm for robot path planning[J]. Journal of Robotic Systems，2004，21(6)：275–300.

［3］ 石为人，黄兴华，周伟. 基于改进人工势场法的移动机器人路径规划[J]. 计算机应用，2010，30(8)：2021–2023.

［4］ 周毅，崔刚. 基于机器视觉和A*算法的迷宫机器人路径规划[J]. 微计算机信息，2010，26(3-2)：155–156.

［5］ 朱耿青. A*算法实现及其应用[J]. 福建电脑，2008 (2)：74–75.

［6］ 熊伟，张仁平，刘奇韬，等. A*算法及其在地理信息系统中的应用[J]. 计算机系统应用，2007(4)：14–17.

［7］ Russell S，Norvig P. Artificial Intelligence：A Modern Approach[M]. 3,rd. Upper Saddle River：Prentice Hall Press，2009.

［8］ 陈刚，付少锋，周利华. A*算法在游戏地图寻径中的几种改进策略研究[J]. 科学技术与工程，2007，7(15)：3731–3736.

责任编辑：常涛

Path Planning of Mobile Robot Based on GIS Map

ZHANG Lijuan，BI Dexue
(College of Mechanical Engineering，Tianjin University of Science & Technology，Tianjin 300222，China)

The realization of the mobile robot path planning has certain restrictions. To deal with this problem, a novel mobile robot path planning method based on GIS(geographic information system)map was proposed. The optimal path planning was realized through improved A*algorithm. If the starting and ending points in any given map are given to a mobile robot，the path of the robot can be traced. The proposed path planning has been proved optimal and can satisfy the requirement of the practical environment. The experiments were based on VC++ and the effectiveness of this method has been proved.

robot path planning；GIS map；improved A*algorithm；estimable function

TP242

A

1672-6510(2012)03-0068-03

2011–11–29；

2012–02–22

张丽娟（1986—），女，天津人，硕士研究生；通信作者：毕德学，教授，dexue@tust.edu.cn.