基于室内环境智能机器人路径规划算法的研究
尹 远 阳1，金 纯1 2， 王升刚1
（1.重庆邮电大学 通信与信息工程学院，重庆 400065；2.重庆金瓯科技发展有限责任公司，重庆
400041；）
该论文发表于《通信技术》2013年第33卷第251期
刊号为：ISSN 1006-6403
|
摘要:随着无线传感器及家庭服务机器人的出现，而现有的路径规划算法中大多不能满足实时性要求。本文提出一种针对室内环境的路径规划算法。该算法中通过采用栅格模型建立地图，设定新的启发函数，仿真结果表明该算法简单实用、且计算速度快，且在已知家庭地图的情况下该算法搜索时间有明显的优势，同时该算法能适用多障碍物的室内环境。
关键词：智能机器人；无线传感器；栅格法；路径规划；
中图法分类号：TP 301
Intelligent robot path planning algorithm based on indoor environment
YIN Yuan-yang1，JIN Chun1、2，WANG Sheng-gang1
(1. Wireless Transmission Key Laboratory, School of Communication and Information Engineering，Chongqing University of Posts and Telecommunications，Chongqing 400065，China; 2. Chongqing Jinou Science & Technology Development Co., Ltd., Chongqing 400041, China)
Abstract：With the appearance of wireless sensor and family service robot, the existing path planning algorithm can’t meet the real-time requirements. This paper presents a path planning algorithm for indoor environment. The algorithm by using grid model map, setting new heuristic function, the simulation results show that the algorithm is simple and practical, and the calculation speed is fast. Under the condition of known family map the algorithm search time has obvious advantages, and the algorithm can be applied to many obstacles indoor environment.
Keywords：intelligent robot；wireless sensor；grid method；path planning；
1.引言
随着物联网、计算机技术、智能机器人的发展，移动机器人的应用场合也越来越受到人类的关注。移动机器人是集监测传感器、动态决策和控制于一体的复杂控制系统。在这过程中，路径规划是移动机器人控制系统的核心技术之一[1]。上个世纪的60年代开始，国内外的学者就开对移动机器人的路径规划[2、3]进行了相关的研究，主要的路径搜索算法有Dijkstra算法、A*算法[4]、人工势场法，以及最近研究较多的神经网络算法[5]、蚁群优化算法[6、7]、遗传算法[8]等搜索技术。Dijkstra算法是荷兰计算机科学家艾兹格?迪科斯彻发现的，是一种比较经典的求最短路径的算法，采用的是广度优先的遍历算法，时间复杂度为O（n2），当在大地图中使用该方法时，搜索时间明显增加。蚁群算法、神经网络算法、遗传算法[5、6、7、8]等智能算法已经应用到机器人足迹规划中。这些算法本身存在着一些缺陷，如局部寻优能力差、早熟现象等问题就很突出，严重影响路径规划的计算效率和可靠性。
本文结合服务机器人越来越多的在智能家居中应用，而提出在复杂的室内环境中运用机器人辅助完成各项任务的路径规划研究，该过程中机器人采用事件驱动工作模式。通过路径算法机器人可以快速到达事发现场进行拍照和指令操作。这就要就机器人路径规划要有实时性，因此本文提出了一种基于栅格模型下的机器人实时路径规划算法。
2. 机器人的工作环境建模
在移动机器人工作环境中可以通过建立一个坐标系来具体描述，并将建好的坐标系分割成一个个小单元，形成栅格[9]。栅格边的大小可以根据机器人一步行走的距离来划分，这样可以更精确地规划出行走路径，再通过放缩因子就可以准确得到现实中的距离。划分的栅格分为两种，自由栅格和障碍物栅格。自由栅格：栅格位置是可达的，机器人可以没有约束地行走；障碍物栅格：机器人不能通过的场所。为了保证栅格的划分，只要所分栅格中存在障碍物，该栅格就抽象为一个满栅格块。在MATLAB2009版中编程建立机器人工作的环境模型如图所示。图中每个栅格大小为一个单位长度的正方形，其中黑色部分表示的是环境中的障碍物，白色栅格表示为自由栅格。该模型近似于室内的家居环境。
虚拟栅格[9、10]是在机器人探知未知环境的同时所建立起来的环境信息，能通过编程实现的模拟环境。本文是通过以下假设实现：1>机器人能对室内的二维环境进行全覆盖感知。2>当机器人进入某一栅格时，恰好是对该栅格的全覆盖。3>机器人在环境中运动时忽略自身因机械损耗和摩擦带来的误差。4> 机器人在每个自由栅格中的移动选择是以当前栅格为中心的其它八个相邻自由栅格，且每次一步运动为一个栅格，具体运动关系如图所示。
3.启发式算法理论及分析
3.1 路径规划
家庭服务机器人运用在智能家居环境中，是为了能在家庭帮助户主管理家庭内部设备的控制。而这就要求该家庭服务机器人对事件处理要有实时性，操作简单性。因此针对室内环复杂境研究出一种实时快速的室内机器人路径规划是十分必要的。在众多路径规划算法中，蚁群算法、遗传算法等虽然能取得较好的最优路径或次优路径，但这些算法都是以时间为代价来取得好的效果，这不符合室内机器人快速达到现场查看的要求，因此本文选择一种启发函数[12]并结合栅格设定的室内地图来实现机器人路径规划，工作流程如图所示。
3.2 A*算法的思想和启发函数的设计
A*算法[5、12]是对传统的Dijkstra算法的有效改进，Dijkstra算法只是对路径进行深度或广度搜索后，选择代价函数值最小的链路，因此对于节点数量多的网络连通图，计算量会明显增加。为了解决这样一个问题，A*算法中引入了估价函数，减少节点选择搜索的盲目性，通过计算结果来选择候选节点，这样在某种程度上能减少对节点的搜索范围，增加节点的选择效率。
A*算法搜索过程中涉及到的每个节点的估价函数f(n)其形式如公式（1）所示[5]：
在式（1）中，其中f(n)代表A*算法中从起点（S）经过中间节点N到终点（T）的最短路径的成本估计值；g(n)表示从起点S到当前节点N的实际消费值，h(n)则表示从当前节点N到达目标T点所需要的消费的预估值。而A*算法比Dijkstra算法优越性就体现在h(n)这个启发函数上，因此启发函数h(n)设计越好，所得的路径规划就越优越。
当室内设备发生故障时，机器人可通过无线传感网络收到警报信息确定故障的具体位置（因为机器人对室内环境已知）设为目标T，其坐标为( , )，为了进一步确认事故现场的情况及进行有效操作，机器人需要快速爬到故障位置处进行初步（主人通过终端发机器指令）。因此本文对启发函数h(n)进行了精心设计。
传统的A*算法所采用的启发函数有曼哈顿距离、欧氏距离信息作为路径搜索节点的信息，如果当前节点的坐标为( , )曼哈顿距离计算公式如式（2）所示：
由欧氏距离作为启发函数h(n)的计算公式如式（3）所示：
这种节点的选择作为评估方式存在一定的弊端，因为实际距离远远会比所估计的距离相差很大，其实在搜索过程中要得到快速且又近的路径，不仅与所选择的距离函数作为预测有关，还受到很多其他因素的影响，但传统的方法只对距离因素进行了约束。本文就是在这基础上不但选择距离作为约束条件，还增加了机器人对目标搜索的方向函数作为约束条件，新设计的启发函数如式（4）所示：
其中 为提高节点角度信息的一个权重因子，表示该节点的重要程度， 的具体取值是根据地图的实际大小来确定， 是当前节点与目标节点组成的矢量与起始节点和目标节点组成的矢量的夹角，表示当前节点方向选择，如果所得角度越小，则预估价函数的方向性选择越强，越容易趋向目标节点，具体表示如图所示。
由式（5）可以求得 的取值，且可以知道 的取值范围为[0,90]度之间：
通过（5）式求得 的值后，结合式（4）可知 在[0,90]内是单调递增的函数，这样可以进一步保证代价函数f(n)取得最小，而使路径搜索方向更明确，时间更快。
4 本文算法设计步骤
通过上述分析，可以知道启发函数的好坏是路径搜索的关键，在此详细介绍本文的算法步骤。
Step1 算法初始化。建立栅格地图，为地图中的每个栅格分配好坐标，确定目标点位置（T），起点位置就为机器人当时所在位置（S）。
Step2 建立两个列表。一个为CLOSED列表，用来储存已搜索的节点和障碍物节点；另一个为OPEN列表，用来储存当前节点的相邻自由栅格。
Step3 设定估价函数初始值。将step1中的起点位置S放入OPEN中，并设估价函数初始值f(n)=0,g(n)=0。
Step4 确定搜索方向。以机器人最原始位置S到目标点T的矢量作为参考方向，计算当前节点的可选自由栅格(N)到目标节点组成的矢量与参考矢量的夹角，同时计算相应的欧氏距离，确定h(n)。
Step5 更新搜索节点。通过根据建立好的移动策略，机器人移动到下一栅格并更新g(n)、f(n)。选择最小的f(n)值点作为当前选择的点，并将该点放入CLOSED列表中。
Step6 判断是否达到目标节点。如果达到则进入step7，否则跳入step4。
Step7 输出路径，算法结束。
该算法的具体流程如图所示。
5 仿真实验与分析
本文是在matlab2009版本软件，CPU（AMD）处理频率为2.5GHz，内存2GB的环境下进行的仿真，并结合了蚁群算法的路径规划进行了对比，针对不同的情况分别进行了三种不同的仿真分析。
仿真分析1：针对室内环境进行了栅格地图的创建，该环境是20*20的栅格地图，并在建好的地图中随机设置目标点和机器人的起始位置（这样设置的目的是更能真实的反应机器人在巡逻时收到跌倒报警信息时，可以自由的从室内任何一个位置快速到达跌倒位置进行查看），在系统中是把跌倒处理事件设置为优先级最高，通过这样的规定能确保机器人第一反应的是对跌倒进行检测工作。在该环境下的仿真结果如图6 所示，其中图中（a）表示本文算法，（b、c）分别表示蚁群算法的仿真图。
由仿真可知本文算法能较好的得到一条通往目标点的路径，相对蚁群算法能得到更好短的路径，虽然蚁群算法经过多次迭代最终也能寻找到一条相对较优的路径，但本文算法更能满足实时性的路径规划要求。
仿真分析2 ：为了验证本文算法对不同栅格数地图在路径搜索的实时性，分别针对栅格数为10*10、15*15、20*20、30*30的地图进行仿真分析，每一种相同栅格地图中障碍物相同，并对每种栅格地图随机设置障碍物经过10次统计每种地图中路径搜索时间和再求均值，10次平均搜索耗时如表1所示，列出了本文算法同传统的A*算法以及蚁群算法在不同环境下的时间统计平均耗时。
仿真2通过对不同栅格数的地图下进行了分析，从表1可以看到随着栅格数目的增加，这几种算法在障碍物相同的情况下搜索时间都在不断变大，但本文算法的搜索时间变化不是特别明显，能很好的满足时间效率。这对机器人用于突发事件的实时性处理的路径规划非常有意义。
仿真分析3：为了讨论在固定栅格地图中障碍物所占比例不同，对机器人路径规划搜索的影响。该仿真在同一种栅格地图（20*20）中，随机设置障碍物比例分别为10%、20%、30%、50%四种情形，仿真结果如图7a、7b、7c、7d所示。为了统计搜索时间，每种情形通过10次仿真后对搜索时间进行统计平均，搜索时间如表所示。
通过仿真3可知，在同一种栅格地图中，随着障碍物的不断增大，虽然都能找到一条到目标点的路径，但蚁群算法的搜索时间在增大。由于本文算法中对设置的障碍物直接放入了不需要搜索的链表中，从而保证了搜索节点相应减少，因此搜索时间反而变快（且这种情况在更大的栅格地图中更能体现这种优势），这更能说明本文算法能适用已知地图环境中更复杂、障碍物多的环境，当然遗传算法、蚁群算法等在路径规划中也有它独特的优势。
6. 结 论
本文针对智能家居环境中服务机器人的发展，从而针对室内服务机器人情形研究了一种运用栅格模型建立地图和采用启发函数作为搜索因子的快速路径规划算法。通过上述的三种仿真结果可以知道，本文算法能有效的解决室内障碍物的影响，并能快速针对目标位置进行搜索，具有很好的鲁棒性。由于机器人是集成多传感器的一个整体，机器人通过搜索的路径到达事发地点，启用相应的设备完成检测任务。同时本文算法还可以应用到其他复杂环境，特别是在已知环境地图、同时也有大量障碍物的路径搜索的情况下更能体现它的优势。
参考文献
[1] SOULIGNAC M. Feasible and optimal path planning in strong current fileds[J].IEEE Transactions on Robotics, 2011，27（1）: 89-98.
[2] ALEXOPOULOS C, GRIFFIN P M. Path planning for a mobile robot[J].IEEE Trans on System Man and Cybemetics,1992, 22(2): 318-322.
[3]TSAI C C,HUANG H C,CHAN C K. Parallel elite genetic algorithm and its application to global path planning for autonomous robot navigation[C].In Proceedings of IEEE international Conference on Computer Applications，Shipbuilding, 2011, : 4813-4821.
[4] 漆阳华,杨战平,黄清华. A*的改进路径规划算法[J].信息与电子工程，2009, 7(4): 326-329.
[5] 宋勇，李贻斌，栗春等.基于神经网络的移动机器人路径规划方法[J].系统工程与电子技术，2008, 30(2):316-319.
[6] 张美玉，黄翰，郝志峰等.基于蚁群算法的机器人路径规划[J].计算机工程与应用，2005, 25: 34-37.
[7] 潘杰，王雪松，程玉虎. 改进蚁群算法的移动机器人路径规划[J].中国矿业大学学报， 2012, 41(1): 108-113.
[8] 崔瑾娟. 基于遗传算法的机器人路径规划[J].洛阳师范学院学报，2013, 32(2)：35-42.
[9] 吴 锋, 杨宜民. 一种基于栅格模型的机器人路径规划算法[J].现代计算机，2012, 02: 7-13.
[10] 周郭许,唐西林. 基于栅格模型的机器人路径规划快速算法[J]. 计算机工程与应用， 2006, 21: 197-199.
[11] ZHOU FENGYU, SONG BAOYE, TIAN Guohui. Bezier Curve Based Smooth Path Planning for Mobile Robot[J].Journal of Information & Computational Science, 2011, 12(8): 2441–2450.
[12] 贾振华，斯庆巴拉，王慧娟．基于启发式机器人路径规划仿真研究[J]．计算机仿真，2012，29（1）：135-138．
作者简介：
尹远阳 （1986—） 硕士研究生 研究方向：无线通信、智能算法等
金纯 （1966—） 博士、教授、研究生导师 主要研究方向：无线通信、
计算机软件、物联网、数字电视等
王升刚 （1986-）硕士研究生 研究方向：无线传感器网络、机器人定位等
|
