一种新颖的电脑鼠走迷宫算法研究

王昕++++袁晓堂++++陈晨++++马浩++++袁臣虎

摘 要： 一款性能稳定，功能全面，算法优良的高效智能“电脑鼠”能在短时间内快速稳定地完成复杂迷宫的搜索和冲刺。本文将向心算法和洪水算法融合形成向洪算法，介绍了该算法的工作原理，并对该算法进行优化和评估后完成迷宫搜索、迷宫二次回程搜索。向洪算法在保持向心算法和洪水算法优势的基础上减轻了处理器的运算负担，使电脑鼠运行稳定性进一步提高。实验表明，与传统算法相比，加载该算法的“电脑鼠”可以探寻出更加有利的路径，获取更全面的迷宫信息，是一种高效的迷宫搜索算法。

引言

“电脑鼠”是一个具备自主运动能力的微型机器人，它能够在特定的迷宫中行进和搜索，由起点出发，自行搜索到迷宫的终点，并利用搜索过程中记录的迷宫墙壁资料寻找出由迷宫起点到达终点的最短路径，然后根据最短路径规划出最快的运动方式和路径，并以最快的速度完成由迷宫起点到终点的冲刺。

要在指定的复杂迷宫中比赛，就像是一个人置身于未知的环境中，必须靠自身的判断力、敏捷的动作和正确精准地探查周遭环境赢得最终比赛的胜利。“电脑鼠”必须具备三项基本功能：

（1）稳定及快速的行走能力；

（2）正确的预判能力；

（3）路径记忆功能；

随着人工智能的发展和新兴智能算法的突破，迷宫算法革新对迷宫求解来说相当重要，迷宫算法从非图论（NGT）发展到图论（GT）[2]，从简单的左右手法则、中左、中右法则发展到洪水填充法则、深度优先探索法则（DFS），且随着机器人多路径规划的不断深入探索，A■和D■等启发式算法也开始运用其中，甚至新兴智能算法如蚁群算法、遗传算法、粒子群算法应运而生。以上算法都存在着随机性，运算结果也不一定是最优解且搜索效率低。很多情况下需要遍历整个迷宫才能够找到终点，针对以上算法所存在的问题，本文提出一种经过改善和优化后的融合算法——向洪算法，此算法建立在向心算法和洪水算法的基础上，对墙壁信息进一步拓展，减少了搜索过程中的盲目性，有效地判别无效路径。向洪算法结合了向心法则和洪水算法的各自优势，既克服了洪水算法频繁制作等高图问题，又提高了向心算法对终点的指向性，此算法减轻了CPU频繁制作等高图带来的数据处理负担，同时减少不必要的路径搜索，为电脑鼠竞赛的胜利争取时间。

1.电脑鼠走迷宫的理论基础与迷宫建模

1.1电脑鼠走迷宫的理论基础

“电脑鼠”走迷宫竞赛的任务是电脑鼠在千变万化的未知迷宫中从迷宫起点自主探索到迷宫终点的最佳路径，用时最短者优胜。比赛成绩计算如式（1）所示。

式中，T为第一次从起点出发到第N次到终点所用的总时间；T为第N次的运行时间，电脑鼠每一次从迷宫起点运行到迷宫终点所用的时间，称为一次运行时间。T为奖励时间（一般为负数），T为惩罚时间，二者由比赛规则确定[1]；T为排障时间，在每次运行结束后都会获得一个数值，最终成绩为数值最小的T。

由式（1）可知，“电脑鼠”走迷宫竞赛的最终成绩由运行速度﹑迷宫求解效率和稳定性三个方面确定。搜索阶段获取的迷宫信息量越充分，进行路径的预判越精准，选取的路径越有效，对冲刺阶段最优路径的选择就越有利，前提是电脑鼠足够稳定。因此迷宫搜索算法的设计和优化目标是使电脑鼠稳定的在短时间内探寻到尽可能全面的迷宫墙壁资料，利用搜索的迷宫信息做出准确的决策分析和最优路径判断。向洪法则就是针对以上目标的一种迷宫搜索优化和实现算法。

1.2迷宫环境建模及方向表示

标准电脑鼠比赛迷宫是由16×16格的迷宫墙壁组成，采用16×16的二维数组对迷宫格进行编号记录。数组的下标代表迷宫格位置，数组的元素代表该迷宫格的墙壁信息。若定义数组GucMapBlock[MAZETYPE][MAZETYPE]（MAZETYPE=16表示全迷宫），则每一格位置及信息由GucMapBlock[x][y]确定，第一个下标代表X轴坐标，第二个代表Y轴坐标。

根据坐标表示及竞赛规则看，每个单元的迷宫起点可以是迷宫的左下角或者右下角，即（0，0）或者（15，0）。电脑鼠开始搜索时，电脑鼠会将起点坐标设为（0，0），电脑鼠通过第一个转弯口方向判断未知起点位置。若第一个转弯口为右转，则起点坐标为（0，0）点，否则将起点标定为（15，0）。若起点坐标为后者，则需要进行迷宫坐标和墙壁资料的转换，将搜索过的迷宫信息的X坐标值加上15，并将墙壁资料赋给转换后的坐标。

电脑鼠在迷宫中的运动是以每格为单位，到达下一格后需要对坐标进行更新和墙壁资料的采集，为了方便记录电脑鼠当前位置和坐标的更新，需要进行绝对方向和相对方向的判定和转换。相对方向是以电脑鼠当前行进的方向为参照的方向，将相对于电脑鼠的前、右、后、左的方向定义0、1、2、3；绝对方向是以迷宫绝对坐标平面为参照的方向，将相对于迷宫的上、右、下、左的方向定义0、1、2、3；以绝对方向定义迷宫的墙壁资料，将迷宫的4面墙壁用4个方向定义，再以数值代替其名称，以便于程序的编写和运算处理。将16×16个迷宫格的墙壁资料存放于数组GucMapBlock[]中，其中低4位用于迷宫墙壁资料的保存（bit3～bit0分别代表左下右上，0为该方向有墙，1为有路），第4bit用于确定该迷宫是否搜索过。

2.向心法则与洪水算法的求解原理

2.1向心法则迷宫求解原理

此算法会把迷宫分成4个对等的部分（如图1所示），根据前方是否存在可行走方向并结合传统的左手法则、中左法则、右手法则和中右法则使搜索的目标始终指向中心点，根据分区转换法则（如图2所示）选择路径进行搜索。电脑鼠在此算法的引导下优先选择了更靠近中心的点进行搜索，可以使搜索更加偏向迷宫的中心点，提高了搜索效率，但是并未考虑接下来搜索的迷宫格及其附近迷宫格的墙壁情况，可以说向心算法只是机械地选取更“靠近”中心的格子。

图3所示即为向心法则的迷宫搜索路径示意图，电脑鼠目标指向非常明确，向心法则在这个地图上的搜索效率十分高效，但是在进入图中标注的“死胡同”后，判定当前电脑鼠所在迷宫右下角区域，当前行进方向为迷宫绝对方向的上方，此时采用中左法则进行路径搜索，根据图中标注的路径可知电脑鼠错失到达终点的机会，又进行左上角未知迷宫的探寻，增加迷宫时间，对优先取得一次最好成绩产生影响，所以向心法则需要优化，它在特殊路径决策上还存在改进方面。

2.2洪水算法迷宫求解原理

以8×8的迷宫举例说明洪水算法的基本思想，先进行迷宫墙壁的初始化，认定四面迷宫边界有墙，其余迷宫单元格都没有墙，如图5所示图中标注的数值为在迷宫无墙壁时各个单元格到终点的等高值即步数值，电脑鼠在迷宫中搜寻路径时朝着等高值小的迷宫格行进，若发现墙壁资料与之前设置有所不同时，如遇到岔路口、“死胡同”（当前单元格无可前行方向）和前方单元格等高值比当前单元格高时会更新并记录墙壁资料，等高图也会重新制作，依次规划各个单元格可能存在及可到达迷宫终点的等高值，整个过程都在反复制作等高图和更新等高值，根据等高值探索路线直至终点。

纯洪水算法相较其他搜索算法相比，不会再机械性地向终点迈进，而是在搜索过程中边搜索边进行推演和步数计算，图6为在洪水算法下规划出的等高值和最短路径，可以看出洪水算法在迷宫中的搜索效率较高。

洪水算法虽然在迷宫搜索过程中效率较高，但比赛前迷宫地图都是未知的，若遇到较复杂的地形，在探索过程中则会经常性地制作等高图和更新等高值，这期间处理的数据量较大，然而频繁地制作等高图势必会占用CPU处理和计算数据的时间。电脑鼠在运行过程中需要存储的信息量较大，处理的数据量较多，对电脑鼠控制精度要求较高，这些都需要控制系统保证高实时性，所以控制器的性能对能否高效地完成算法设计起到至关重要的作用，而在实际算法设计时发现电脑鼠往往会因为坐标存储及转换，墙壁资料保存等多信息的处理及高频率的制作等高图而出现控制器处理能力不足，因此路径搜索出错，发生撞墙现象就在所难免。

3.向洪算法的基本思想与实现过程

3.1向洪算法的基本思想

向洪算法是向心法则和洪水算法的融合算法，此算法有以下几点优势：首先，此算法不再使已知的迷宫墙壁资料受到局限，扩展并充分利用已知墙壁信息剔除无效路径。其次，电脑鼠利用此算法进行搜索时，遇到分支路口将使用向心法则进行路径探索，直至电脑鼠进入“死胡同”后将之前选择的路径进行预推演，预推演的过程包括路径选择，等高图的制作和等高值的更新，在完成推演后会判定是否可到达终点，若能到达，转换搜索法则继续行进，若不能到达，则将此支路及通过此支路的路径标记为死路，下次搜索回到附近处直接避开此支路。如图7所示为向洪算法的搜索路径示意图，为了展示向洪算法的优势，采用与图3所示相同的地图进行实验，我们会直观地发现电脑鼠前期一直采用向心法则进行搜索，直至到达图中标注的“死胡同”时进行路径信息的更新和预推演，填入新的等高值后直接沿等高值小的方向成功搜索到终点，解决图3所示存在的问题。改进后的算法不仅提高向心法则对终点的指向性，而且克服洪水算法频繁地制作等高图，对搜索路径进行优化，筛除无效路径，明确搜索范围，使电脑鼠在搜索过程中保有快速性的前提下作出更精准的路径判断。

3.2向洪算法的求解步骤

步骤1：定义三个16×16的二维数组GucMapBlock[x][y]，GucMapBlock0[x][y]，GucMapBlock1[x][y]，GucMapBlock[x][y]是在向心法则的路径搜索下储存的墙壁资料，GucMapBlock1[x][y]是在洪水算法的路径搜索下储存的墙壁资料，GucMapBlock0[x][y]储存的是已探寻过的墙壁信息和进行预推演的墙壁资料（bit3～bit0分别代表左下右上，0表示此方向无路，1为有路，第4bit用于确定该迷宫是否搜索过）；

步骤2：首先进行数组的初始化，GucMapBlock[x][y]的全部元素值填0，墙壁资料初始化使GucMapBlock1[x][y]中利用循环迭代使x=0时的所有元素的bit2值为0（此时对应迷宫绝对方向的下边界），同理可得x=15的所有元素的bit0值为0（对应迷宫上边界），y=0的所有元素的bit3值为0（对应迷宫左边界），y=15的所有元素的bit1值为0（对应迷宫右边界），这表示只有迷宫四周边界处有墙，其余地方无墙，靠后期搜索及推演的过程进行隔墙添加。GucMouseTask表示电脑鼠的状态处理，GucMouseTask=START开始进行搜索过程，此时可根据第一个转弯口方向判定起始点坐标来决定是否进行坐标转换，先利用洪水算法对迷宫单元格进行等高值的填写，再根据等高值的由大到小进行路径探索，遇到支路口时，程序会先行统计可前进的支路数，若可前行支路数大于0，则利用向心法则进行搜索直至进入“死胡同”后进行等高图的制作和路径推演；

步骤3：电脑鼠在搜索时利用已知迷宫单元格的墙壁信息可推断出其余相邻迷宫单元格的信息，两个数组在进行等高图制作时会同步更新内容，GucMapBlock1[x][y]保存实际探寻过的迷宫墙壁资料，GucMapBlock0[x][y]保存实际迷宫信息及推演后的墙壁资料，当电脑鼠已探寻出GucMapBlock1[x][y]的bit1为0（表示当前单元格坐标（x，y）右方有墙壁，无可前进方向），可通过推演法推断GucMapBlock0[x-1][y]的bit3为0（表示当前单元格坐标（x-1，y）左方有墙壁，无可前进方向），以此类推可知已知地图信息的单元格四个方向的各个坐标处的墙壁信息。当再次探寻到支路口时又将转换成向心法则进行路径搜寻，如此循环上述过程，直至当前目标点为终点结束操作；

下图8所示为本论文所提的向洪融合算法软件流程图。此向洪融合算法不仅解决了向心法则对特殊路径的搜寻问题，减少了没有必要的路径搜索，而且大大减轻了CPU的运算负担，大幅度提高了指令的执行效率。本实验室成员已参加了四届天津市电脑鼠竞赛及全国性电脑鼠比赛，从整体效果说，本融合算法对迷宫的适应性广，对策略的嵌入性好，相较其他算法来说较为高效，适合进行推广应用。

4.向洪算法实验测试

4.1测试平台简介

为了检验文中所提算法的合理性及有效性，需要搭载一个硬件平台方便算法的验证和测试。本文实验所用的电脑鼠硬件是实验室开发的第三代MicroMouse3，其微处理器是意法公司生产的基于Cortex-M3内核的ARM处理器—STM32F103。采用IEEE国际标准电脑鼠走迷宫竞赛迷宫作为测试迷宫。

4.2算法测试过程及结果

为了便于算法的测试和实验结果的对比，我们随机选取5幅往年天津市电脑鼠竞赛的迷宫图进行测试，同时为了使算法得到充分的验证，选取相同的迷宫环境、相同的硬件架构和同一运行策略进行实验，有且仅在迷宫算法上有所不同。

相同的迷宫环境：是指排除迷宫板，迷宫地面的缝隙及外界灯光环境对电脑鼠的影响；

相同的硬件架构：是指所用的电脑鼠采用相同的底层驱动，速度参数和红外阈值设定；

同一运行策略：是指起点到终点的搜索→原路径返回起点→起点到终点的冲刺→终点到起点的迷宫二次搜索→第二次冲刺→第三次冲刺；

结果分析：算法测试结果如上表所示，每幅迷宫图我们进行了5次测试，然后将搜索时间、排障时间进行均值计算后记录比对，只要按照预设的策略完整地运行下来即算成功一次，计算成功率并记录。从上表可知，向洪算法的搜索时间和排障时间相对向心法则都有不同幅度的减少，比起洪水法则最好成绩相近。在第2幅和第4幅的迷宫测试过程中，我们发现向洪融合算法的成功率比洪水算法成功率高，原因在于在迷宫二次回程中向洪算法信息处理得较合理，使电脑鼠在快速运行时保证高稳定性。综合评价向洪算法的高效性更便于电脑鼠的稳定运行。

结语

本文针对传统迷宫搜索算法低效和处理器的局限性问题研究和实现了基于向心法则和洪水算法的电脑鼠走迷宫的向洪融合算法，并结合实验测试了优化后的算法，提出了一些能提高比赛效率的策略。通过与现有的常用算法比较后发现，本文所提算法在搜索步数、转弯次数及成功率方面具有一定优势。实验测试结果表明，改进后的搜索向洪融合算法在保证原有两种算法高效的前提下，能更好地处理一些特殊迷宫信息，总体提高算法效率和实用价值。

参考文献：

[1]王凤林，王宜怀.一种电脑鼠走迷宫算法的设计与实现.计算机应用与软件，2010，27（12）：270-273.

[2]王磊.基于IEEE电脑鼠走迷宫竞赛的迷宫算法分析与实现.山东大学，2013.

[3]Jong-Kwon Lee，Sang Kim，IEEE.Student Activities Conference-Micromouse Competition Rules[J/OL]. IEEE，2007.http：//www.ieee.uc.edu/main/files/sac2007/mm_rules.pdf.

[4]王斌，张卫钢.基于IEEE标准的电脑鼠走迷宫的智能算法研究[J].电子设计工程，2011，19（12）：42-45.

[5]贺少波，孙克辉.基于向心法则的电脑鼠走迷宫算法设计与优化.计算机系统应用，2012，21（9）.

[6]Manoj Sharma， Kaizen Robeonics Algorithms for Micro-mouse. International Conference on future Computer and Communication， 2009，（38）：581-585.

[7]蒋雄，任化龙，马忠丽.基于ARM的电脑鼠走迷宫研究.现代电子技术，2011，34（8）.

[8]林国恩.电脑鼠设计与制作[D].桃园：台湾龙华科技大学，2010.

[9]徐守江.迷宫算法综述[J].信息与电脑：理论版，2009，10（9）.