基于IEEE标准的电脑鼠走迷宫的智能算法研究

王斌，张卫钢

（长安大学 信息工程学院，陕西 西安 710064）

电脑鼠[1]（Micromouse）是一个由微控制器、探测器、驱动电机等构成的，集感知、判断、行走功能于一体，能够自动寻找到达目的地最佳路径的小型机器人。它可以在迷宫中自动感知并记忆分析迷宫地图，在规定时间内，通过一定的智能算法，寻找一条最优路径，以最快的速度从起点冲刺到终点。IEEE标准规定，迷宫由16×16个、18 cm×18 cm大小的正方形单元格组成，隔板沿单元格布设，形成迷宫通道，起点在迷宫任意一角，终点在迷宫中心。

电脑鼠的基本功能是从起点开始走到终点，该过程称为1次“运行”，花费的时间称为“运行时间”[1]。从终点回到起点所花费的时间不计算在运行时间之内。从电脑鼠的第1次激活到每次运行开始，这期间所花费的时间称为“迷宫时间”[1]。若在比赛时需要手动辅助，则称为“碰触”[1]。竞赛主要采用这3个参数来进行评分，运行时间最短的电脑鼠获胜。因此，高效的迷宫搜索算法和转弯算法就显得至关重要。基于此对电脑鼠走迷宫的软件控制算法和转弯算法进行深入的探讨和研究。

1 电脑鼠探索迷宫

1.1 迷宫探索过程

根据IEEE标准电脑鼠走迷宫竞赛要求[1]，电脑鼠完成整个走迷宫任务可分为以下4个步骤：

1）第一次搜索 电脑鼠按照一定的搜索算法从起点开始搜索直至到达终点的任意一个单元格，并记忆走过的路径信息，该过程为第一次搜索。整个迷宫用二维坐标表示，左下角设为原点坐标（0，0），向上向右依次为Y轴正向和X轴正向。起点为任意一角，坐标为（0，0）或（15，0）的单元格，终点在中心，由坐标为（7，7）、（7，8）、（8，7）和（8，8）的 4 个单元格组成。

2）第二次搜索 从第一次搜索完成时所处的位置开始按照一定的智能算法进行搜索直至找到起点，并记忆走过的路径信息，该过程为第二次搜索。为了在最短时间内搜索到更多路径信息，此次搜索的路径尽可能避免和第一次搜索的重复，以便更加高效地搜索迷宫，增大找到最优解的可能性。

3）冲刺 根据两次搜索到的迷宫信息，按照一定的智能算法选择一条从起点到终点的最优路径，然后从起点快速到达终点，该过程为冲刺。因转弯和走直线耗时不同，在选择最优路径时还要考虑转弯加权比重问题。

4）回起点 电脑鼠沿原路返回至起点。

1.2 软件设计与实现

电脑鼠走迷宫过程可以分为4个状态：等待状态、启动状态、搜索状态和冲刺状态。主程序流程[2]如图1所示。

图1 主程序流程图Fig.1 Flow chart of main program

1）等待状态 在该状态中，电脑鼠静止在起点，等待触发启动键，当启动键按下后，电脑鼠进入启动状态。

2）启动状态 在该状态中，电脑鼠根据第一次转弯的方向判断起点的坐标是（0，0）还是（15，0），向左转时起点坐标为（15，0），向右转时起点坐标为（0，0）。

3）搜索状态 在该状态中，电脑鼠的任务就是探索并记忆迷宫信息。采用基于向心法则和向点法则的深度优先搜索算法和洪水填充法相结合的智能搜索算法，实现部分迷宫搜索。程序流程如图2所示。

图2 搜索程序流程图Fig.2 Flow chart of searching program

4）冲刺状态 迷宫搜索完毕后，补全迷宫信息，根据洪水填充法找出一条从起点到终点的最佳路径并冲刺到终点。

2 智能算法设计与分析

2.1 迷宫搜索算法

迷宫搜索常用的算法有深度优先法[3]、洪水填充法、遗传算法[4]等，本文提出一种基于向心法则和向点法则的深度优先法和洪水填充法相结合的智能搜索算法。基本思想：第1次搜索采用基于向心法则的深度优先搜索算法，逐次搜索直至找到终点，搜索过程中遇到需要回溯到上一节点的情况时，采用洪水填充法寻找到达上一节点的最短路径，并快速到达该节点。为了第二次搜索时的“热区”定义做准备，需要备份此次搜索的部分路径信息作为“热区”；第2次搜索采用基于向点法则的深度优先搜索算法，逐次搜索直至找到起点，搜索过程中遇到需要回溯到上一节点的情况时，采用洪水填充法寻找最优路径，在到达起点之前必然碰触“热区”，一旦碰触“热区”立即采用洪水填充法找到回起点的最优路径并快速回至起点；冲刺前要进行数据补全，然后采用洪水填充法根据已搜索过的迷宫信息找出一条从起点到终点的最优路径[5]，以最快的速度冲刺到终点。

2.1.1 向心法则

向心法则是深度优先搜索迷宫过程中遇到叉路口时采用的一种搜索法则，常用的搜索法则有以下4种，向心法则是对这4种法则的综合运用。

1）左手法则：优先左转，其次是直走、右转。2）右手法则：优先右转，其次是直走、左转。3）中左法则：优先直走，其次是左转、右转。4）中右法则：优先直走，其次是右转、左转。

5）向心法则：由于终点在迷宫中心，遇叉路口时，以向迷宫中心方向为优先的前进方向。如下图3所示，把整个迷宫均分为A、B、C和D 4个区域，每个区域使用不同的法则组合，例如，在A区中，向上搜索时采用中右法则，向下搜索时采用左手法则，向左搜索时采用右手法则，向右搜索时采用中左法则。

图3 向心法则示意图Fig.3 Schematic diagram of the rule towards the center

2.1.2 洪水填充法

洪水填充法[6]可以想象为洪水从迷宫的某一个单元格涌出，沿所有走过的路径方向流动，每流动一格就将该单元格进行递增的数字编码，直至到达目的单元格。实际在某种程度上洪水填充法运用了绘制等高图的原理，寻找一条从一点到另一点的最优路径。

2.1.3 向点法则

向点法则是把整个迷宫看成一个区域，电脑鼠从迷宫终点出来后继续搜索，当遇到叉路口时运用向点法则（迷宫起点坐标为（15，0）时）：向上搜索采用右手法则，向下搜索采用中左法则，向左搜索采用左手法则，向右搜索采用中右法则。当起点坐标为（0，0）时以此类推。

2.1.4 “热区”选择

从第一次搜索过的迷宫中选取部分合适的迷宫格作为特殊区域，这个特殊区域即为“热区”。例如，假设起点坐标为（15，0）， 设 11＜X≤15 且 0≤Y≤15 区域为 S1，0≤X≤15 且0≤Y＜4区域为S2，S1和S2中在第一次搜索过程中被搜索到的所有迷宫格的集合即可设为“热区”。这是为第二次搜索过程中找到一个合适的位置后快速返回至起点而设计的。“热区”范围的定义有多种，本文仅举其一例，如在2010年电脑鼠走迷宫竞赛（西北赛区）迷宫图中的“热区”选择如图4中的黑点所在单元格的集合，箭头处为发生碰触的地方。

图4 “热区”选择Fig.4 Choices of“hot zone”

2.1.5 数据补全

数据补全，就是对未探测到的单元格，通过周围已有的墙壁资料，可进行补充的一种方法[6]。由于采用一个8位二维数组GucmapBlock[X][Y]存储迷宫墙壁信息（如表1），迷宫墙壁资料全部初始化为0，凡是已走过的迷宫格至少有一个方向墙壁资料不为0，根据未探测到的单元格上下左右4个相邻单元格的墙壁资料分析并大胆设想该单元格的墙壁信息。如图5（a）为某单元格补全前墙壁信息，图5（b）为补全后墙壁信息。

表1 墙壁资料存储方式Tab.1 The storage mode of walls information

图5 数据补全前后对照表Fig.5 Table of data before and after completion

2.1.6 最优路径

电脑鼠要在最短的时间内完成由起点到终点的冲剌，最优路径的选择至关重要，步数少的路径是最佳路径的条件之一，但不是唯一条件。考虑到电脑鼠在拐弯时也要耗时，所以要对拐弯次数加权后加到步数中得到加权步数[6]。

加权步数=实际步数+拐弯次数×拐弯权重

拐弯次数：一个90°的拐弯算一次，一个180°的拐弯算二次（可根据实际测试情况而定）。

拐弯权重：需要结合电脑鼠的机械结构、直道速度、转弯速度等因素来确定。实际测试计算出拐弯权重大约为0.5。迷宫图4中的最优路径选择如图6中的粗实线路径所示，路径A的加权步数N1=55+24×0.5=67；路径B的加权步数N2=59+22×0.5=70；路径 C 的加权步数 N3=59+20×0.5=69；因此，最优路径为路径A。

图6 最优路径的选择Fig.6 Choices of the optimal path

该智能算法的关键点如下：1）向心法则和向点法则使深度优先法在迷宫搜索中的运用更加合理。2）在第二次搜索过程中搜索到某一节点时检测到该节点的临格已搜索过且在“热区”内，那么电脑鼠立即根据洪水填充法快速回至起点，目的是为了避免搜索过多路径而耗费更多时间。此外，一旦碰触“热区”也就意味着搜索到至少有两条以上的路径可到达终点，路径具有可选择性和可比性。3）墙壁资料补全和加权步数的设计大大增加寻找到最优路径的可能性。

2.2 转弯算法

2.2.1 停转算法

停转算法思想：电脑鼠在前进中遇到叉路口需要转弯时，两轮同时停转，一轮正转若干步，一轮反转若干步，然后继续前进。每次转完后，小车必在格子中心，实现准确定位。以左转为例如图7（a）所示，电脑鼠在行进中不断检测墙壁信息，当左面的传感器检测到无墙时，再前进若干步停止，然后左轮反转若干步，右轮正转相同的若干步，这样保证电脑鼠转90°后安稳的停在格子中心，随后赋新的任务量，准备进行下一个动作。实验证明，该算法转弯准确率高，安全系数大，适合前期路径搜索，缺点是速度慢，严重影响解迷宫效率。

2.2.2 连续转弯算法

连续转弯算法思想：电脑鼠在前进中遇到叉路口需要转弯时，一轮低于直道速度前进若干步，一轮速度突然提高到某一值前进另一若干步，保证在最短的时间内实现快速转90°，然后两轮同时恢复到直道速度继续前进。这种方法转弯迅速且不失坐标，相对于停转速度快几倍。以左转为例如图7（b）所示，电脑鼠在行进中不断检测墙壁信息，当左面的传感器检测到无墙时，两轮同时前进相同合适的步数之后，左轮以低于直道速度前进若干步，右轮通过人为修改定时器频率使其速度突变并前进另一若干步，实现左右两轮行进中连续转弯，具有转弯速度快，求解迷宫效率高的优点。

图7 电脑鼠转弯Fig.7 Micromouse turning

3 结束语

本文提出的算法可以大大避免了重复搜索、“孤岛”[7]等问题，实现了搜索部分迷宫即可找出从起点到终点的最优路径。由图6可以看出搜索过的单元格占整个迷宫单元格的比例近2/3，且四角基本未进行搜索，该智能算法搜索迷宫效率高，比较科学合理。此外，采用连续转弯算法也在一定程度上缩短了运行时间。另外，该智能算法在2010电脑鼠走迷宫（西北赛区）竞赛中也得到了验证，并取得了优异的成绩。电脑鼠的历史已经超过了50年，但迄今为止几乎没有一种智能算法能保证在任意未知迷宫中都比其他算法好，因此对电脑鼠走迷宫智能算法的研究仍任重道远。

[1]周立功.IEEE电脑鼠开发指南[M].广州：广州致远电子有限公司，2008.

[2]朱姗，傅或哲，吴忠丽，等.一种走迷宫电脑鼠的设计与实现[J].微型电脑应用，2008，24（9）：59-62.ZHU Shan，FU Huo-zhe，WU Zhong-li，et al.Research and realization on micromouse for maze searching[J].Microcomputer Applications，2008 24（9）：59-62.

[3]严蔚敏，陈文博.数据结构及算法应用教程[M].北京：清华大学出版社，2001.

[4]徐守江.迷宫算法综述[J].信息与电脑，2009（10）：91-92.XU Shou-jiang.Labyrinth algorithm[J].China Computer&Communication，2009（10）：91-92.

[5]杨新.矿区中一种走迷宫电脑鼠的研究与实现[J].煤炭技术，2010，29（6）：168-171.YANG Xin.Research and realization on micromouse for maze searching in coalmine[J].Coal Technology，2010，29（6）：168-171.

[6]张新谊.一种电脑鼠走迷宫的算法[J].单片机与嵌入式系统应用，2007（5）：84-85.ZHANG Xin-yi.Analgorithm ofmicromousemaze[J].Microcontrollers&Embedded System，2007（5）：84-85.

[7]朱闻达.IEEE迷宫电脑鼠的迷宫搜索算法研究[J].科技博览，2009（27）：7-8.ZHU Wen-da.Maze search algorithm research of IEEE maze micromouse[J].China Science and Technology Review，2009（27）：7-8.