基于电脑鼠实验平台的Dijstra算法和Floor-fill算法比较研究*

薛盼为　王玉平　余　鹰

(湖北省安全生产应急救援中心1)　武汉　430070)　(武汉明德生物科技股份有限公司2)　武汉　430074)　(美国克莱姆森大学3)　克莱姆森　29631)



基于电脑鼠实验平台的Dijstra算法和Floor-fill算法比较研究*

薛盼为1)王玉平2)余鹰3)

(湖北省安全生产应急救援中心1)武汉430070)(武汉明德生物科技股份有限公司2)武汉430074)(美国克莱姆森大学3)克莱姆森29631)

介绍了迷宫环境的建模和2个路径规划算法，Djikstra和Flood-fill算法，并进一步通过流程图和仿真来阐述如何使用该算法在任意的迷宫环境中导航，以最佳路径从起始位置到达目标位置.结合实物实验来验证算法的正确性和分析其相对优缺点.

电脑鼠；Djikstra；Flood-fill

0　引　　言

在未知环境下的基于多种任务的的自主导航系统的设计是一件非常复杂的任务.随着同步完成捕获目标和规避障碍物的目的，这个挑战将变得更加复杂.如果障碍物和目标的配置产生局部极小点，就像在机器人和目标之间有凹的形状和曲径.纯粹的反应式的导航系统是不能恰当的处理这种阻碍性质的情况，而是需要额外的认知上的设备.因此，来自于免疫网络理论的概念用于将先前的反应式机器人控制，基于学习分类器系统，转换成链接模式的设备.从一开始没有先见的知识，分类器和链接模式将在机器人导航的过程中发展进化[1-3].

1　Djikstra算法

采用Djikstra最短路径算法来解决迷宫路径规划的问题，该算法利用有多个节点的有向图来找到最短路近.算法利用了多种行为的协调的策略，其中发展出了一种创新的路径规划行为来决定最短路径.

1.1Djikstra算法原理

算法的输入是由一个加权的有向图G和G中的一个起始顶点组成.将用V来表示G中所有顶点的集合.图中的每一个边是一个有序的顶点对(u,v)，表示从顶点u到顶点v的链接.所有边的集合由E表示.每一个边的权重由一个权重方程w表示：w:E→[0,∞]，因此w(u,v)即为从顶点u移动到顶点v的费用值.一个边e的费用值可以是两顶点之间的可行距离(需要转弯的地方e=e+1).任意2顶点之间路径的费用值则是其中经过的所有边的费用值之和.对于V中一对所给的顶点s和t，Djikstra算法将找出一条从s到t的具有最小费用值的路径.其本质是在代数图中优化可行路径的最小费用和[4].

2个相继的节点之间距离的计算是通过在机器人步进电机的步数计数器来实现，这个数值将代表了边e的费用值.迷宫的地图将由一个10×10的二维数组表示，单元坐标由[R,C]表示.因此顶点集合V是由一对变量[R,C]来表示每一个节点所组成.具体流程见图1.

图1　Djikstra算法流程图

生成有向图的节点需要机器人搜索整个迷宫为前提.搜索程序的流程见图2.

图2　搜索程序流程图

1.2迷宫路径规划仿真

在生成了有向图之后，最终的Djikstra最短路径算法将应用到有向图上生成最短路径[5]，机器人将利用它达到终点节点，即迷宫的中心，见图3～4.

图3　迷宫simulator

图4　迷宫由Djikstra算法所破解

1.3Djikstra算法存在的缺点

使用Djikstra算法存在一定的问题.最主要的是整个迷宫需要被穿越.为了鉴别所有的节点和边，穿行迷宫的全部尤为重要，不管这一部分是否包含了最短路近.即使对于较小的迷宫，它也要在开始寻找最短路径之前穿越所有的方格.所以很多时间和能量在穿越迷宫过程中被浪费了.在产生了有向图G后，算法也需要一定的时间来找到最短路径，它必须检查所有指向中点的边.这又增加了迷宫搜索的总体时间.

2　Flood-Fill算法

2.1Flood-fill算法原理

机器人寻找路径所花费的时间主要由执行的算法所影响.如果使得迷宫搜索和最短路径的寻找同步进行，则可以降低总体时间.Flood-fill算法正由此而生.其基本原理包含了给迷宫中每一个单元进行赋值.这些值代表着从它到迷宫目标单元的距离.目标单元因此被赋予了0.例如：如果机器人正在被赋予3的单元中，它距离目标还有3个单元.文中假设机器人无法走对角线，且每当它到达一个单元时已经获取并存储其4面的墙壁信息.

迷宫的赋值用一个10×10的矩阵MazeValue[R][C]存表示，终点被赋予(0,0).最初该迷宫矩阵被分割为4个镜像区域，然后每个单元如下进行赋值.

行的增加和减少：R-(i×decr)+(i×incr).

列的增加和减少：C-(j×decr)+(j×incr).

整个方程如下.

MazeValue[R-(i×decr)+(i×incr)]

利用石门桂花村的历史文化背景进行推广，可以打造石门桂花村“画家之乡”、“金桂花海”等品牌，加大宣传力度，通过广播、电视、报纸、网络等现代媒体广泛宣传介绍，并结合“五一”、“国庆”等旅游黄金周的强势推介，提高知名度。

[C-(j×decc)+(j×incc)]=i+j

式中：变量i,j在循环中由0～8变化.

现在赋值已经完成，整个数值分布见图5.

图5　单元的赋值分布图

另外，算法针对任意单元形成一个临时的栈temp[4].该栈用于存储机器人当前所在单元的相邻单元信息.包括其坐标(R,C)和赋值，见图6.

图6　在temp[4]中存储元素

当机器人准备运行下一个动作之前，它必须检测所有相邻的且没有被墙壁阻隔的单元，并选择一个赋值最低的单元.在程序中，将相邻单元的信息存储于栈temp[4]中，运用排序的方法决定最低赋值的单元.这里使用了选择排序法，决策的流程见图7.

图7　选择单元策略图

机器人穿越迷宫的同时记录经过的每一个单元的信息.显然，迷宫墙壁信息将影响到机器人选择下一个移动到的单元.因为当检测到新单元的墙壁信息时，整个或局部迷宫的单元信息本身将受到影响.算法需要对其进行更新.更新程序改变需要更新单元的赋值，以保证机器人选择的路径永远是从赋值高的单元到赋值低的单元.更新程序的流程图见图8.

图8　单元赋值的更新程序

综上，Flood-fill算法的主程序由以下两步组成，每次机器人到达一个新的单元时运行一次该程序来搜索从当前单元到目标单元的最短路径[6-7]：(1)更新迷宫地图的单元信息赋值；(2)选择最小赋值的相邻单元并移动到该单元.

2.2迷宫仿真破解

图9是由Flood-fill算法仿真的具体线路.其中上方的路径为机器人的破解路径.下方的路径为迷宫的全局最优路径.

2.3Flood-fill算法的缺点

Flood-fill算法的缺点在于对环境的探索未完成之前即作出了优化路径的决策选择，所以很难保证作出的决策是全部路径规划的最优解.对于非常大型复杂的迷宫或含有设计陷阱的迷宫，Flood-fill算法所生产的路径有可能陷于局部极小点中，从而使得机器人运行过程中走了很多“弯路”，浪费了很多时间和能量.

3　迷宫破解实验的实施

3.1实验步骤

步骤1部署迷宫，将机器人置于迷宫起始位置(0,0).

步骤2执行机器人搜索迷宫程序.待其搜索完整个迷宫之后回到起始位置.

步骤3执行Djikstra算法获取最短路径，并按照该路径运行到目标位置.

步骤4再次执行Djikstta算法获取最短路径，并按照该路径回到起始位置.

2) 基于Flood-fill算法的迷宫破解实验.

步骤1部署迷宫，将机器人置于迷宫起始位置(0,0).

步骤2执行Flood-fill算法搜索迷宫并同时获取最短路径，并按照该路径运行到目标位置.

步骤3再次执行Flood-fill算法搜索迷宫并同时获取最短路径，并按照该路径回到起始位置.

3.2实验数据记录

根据上一章所建立的坐标系，实验中可以记录下机器人在路径中关键点的坐标值.通过和仿真分析对比作出验证性分析.

1) 基于Djikstra算法的迷宫破解实验实验过程中，机器人经过一个有向图的顶点则记录并显示其当前坐标值，仿真分析与实验数据见表1～2.

表1　Djikstra算法(步骤3)数据记录表　格

表2　Djikstra算法(步骤4)数据记录表　格

2) 基于Flood-fill算法的迷宫破解实验实验过程中，机器人经过一个需要更新赋值的单元则记录并显示其当前坐标值，仿真分析与实验数据见表3～4.

表3　Flood-fill算法(步骤2)数据记录表　格

表4　Flood-fill算法(步骤3)数据记录表　格

为了比较2种算法的优劣，在实验中记录了2次实验中机器人每一个步骤所经历的时间和路程，见表5.

表5　两种算法的比较数据记录表

3.3实验结果分析

通过上面的实验数据记录发现，不管是Djikstra算法还是Flood-fill算法，实验所得的路径和仿真的路径相同.而且机器人均通过搜索和决策过程从起始位置运行到目标位置，并返回到起始位置，从而验证了两种算法的正确性.

不难发现虽然Djikstra算法所得到的是全局的最优路径，但是大部分的时间花费在搜索迷宫的过程中，所花费的总时间大于Flood-fill算法所花费的总时间.而Flood-fill第一次破解迷宫并没有发现全局最优路径，花费的时间要大于Djikstra算法.即使在第二次回到起点的过程中发现了全局最优路径，也因为搜索到非最优路径的迷宫部分而花费了一些额外的时间.这也说明了Flood-fill算法在未知迷宫环境下搜索的局限性.

4　结 束 语

如果没有时间和位置环境的限制，Djikstra算法能够有效的找到迷宫的最优路径.但如果考虑到这两个约束，Flood-fill算法将更加优异.因此，对于当前的机器人迷宫搜索比赛(比如电脑鼠比赛)Flood-fill是迄今为止最有效的算法.另外机器人完成任务的能力也取决于其处理器的运算能力，硬件的性能，运行速度，控制策略等多方面的因素.在改进硬件等方面是有其机械或电子上的限制，而在改进算法方面仍有很大的优化空间，还有待进一步研究.

[1]李文锋.无线传感器网络与移动机器人系统[M].北京：科学出版社，2009.[2]MISHRA S. Maze solving algorithms for micro mouse[C]. Pune: IEEE,2008.[3]WANG Duyao. A new method of infrared sensor measure-ment for micromouse control[C]. Shanghai: IEEE,2008.

[4]SERGIO G V. An integrated undergraduate research experience in control, power electronics, and design using a micromouse[C]. Mayagüez: IEEE,2010.[5]PARASURAMAN S, GANAPATHY V, SHIRINZADEH B. Behavior based mobile robot navigation technique using ai system: experimental investigations[C]. Cairo: CICC,2005.

[6]李铁柱.机器人导航中的定位与避碰方法研究[D].吉林：东北电力大学，2006.

[7]梁文君.机器人动态路径规划与协作路径规划研究[D].杭州：浙江大学，2010.

Comparison Research of Dijkstra and Floor-fill Based on Micromouse Experimental Platform

XUE PanweiWANG YupingYU Ying

(HubeiAdministrationforWorkSafetyEmergencyResponse,Wuhan430070,China)

This paper presents the mathematical model of maze environment and two path-planning algorithms including Djikstra and Flood-fill algorithm. This paper further shows how to apply them to navigate the robot in an arbitrary maze and find the optimal route from the starting position to the target position with detailed flowcharts and simulation. Lastly, it verifies the correctness of the above algorithms and evaluates their relative advantages and disadvantages with experiments.

micromouse; Djikstra; Flood-fill

2016-07-09

TP242.6

10.3963/j.issn.2095-3844.2016.04.036

薛盼为(1987- )：男，硕士，主要研究领域为环境感知与系统协作控制、物流自动化与机器人控制等

*广东省科技专项资金项目资助(0104)