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

一种新颖的电脑鼠走迷宫算法研究 摘 要： 一款性能稳定，功能全面，算法优良的高效智能“电脑鼠”能在短时间内快速稳定地完成复杂迷宫的搜索和冲刺本文将向心算法和洪水算法融合形成向洪算法，介绍了该算法的工作原理，并对该算法进行优化和评估后完成迷宫搜索、迷宫二次回程搜索向洪算法在保持向心算法和洪水算法优势的基础上减轻了处理器的运算负担，使电脑鼠运行稳定性进一步提高实验表明，与传统算法相比，加载该算法的“电脑鼠”可以探寻出更加有利的路径，获取更全面的迷宫信息，是一种高效的迷宫搜索算法 引言 “电脑鼠”是一个具备自主运动能力的微型机器人，它能够在特定的迷宫中行进和搜索，由起点出发，自行搜索到迷宫的终点，并利用搜索过程中记录的迷宫墙壁资料寻找出由迷宫起点到达终点的最短路径，然后根据最短路径规划出最快的运动方式和路径，并以最快的速度完成由迷宫起点到终点的冲刺 要在指定的复杂迷宫中比赛，就像是一个人置身于未知的环境中，必须靠自身的判断力、敏捷的动作和正确精准地探查周遭环境赢得最终比赛的胜利电脑鼠”必须具备三项基本功能： （1）稳定及快速的行走能力； （2）正确的预判能力； （3）路径记忆功能； 随着人工智能的发展和新兴智能算法的突破，迷宫算法革新对迷宫求解来说相当重要，迷宫算法从非图论（NGT）发展到图论（GT）[2]，从简单的左右手法则、中左、中右法则发展到洪水填充法则、深度优先探索法则（DFS），且随着机器人多路径规划的不断深入探索，A■和D■等启发式算法也开始运用其中，甚至新兴智能算法如蚁群算法、遗传算法、粒子群算法应运而生。

以上算法都存在着随机性，运算结果也不一定是最优解且搜索效率低很多情况下需要遍历整个迷宫才能够找到终点，针对以上算法所存在的问题，本文提出一种经过改善和优化后的融合算法――向洪算法，此算法建立在向心算法和洪水算法的基础上，对墙壁信息进一步拓展，减少了搜索过程中的盲目性，有效地判别无效路径向洪算法结合了向心法则和洪水算法的各自优势，既克服了洪水算法频繁制作等高图问题，又提高了向心算法对终点的指向性，此算法减轻了CPU频繁制作等高图带来的数据处理负担，同时减少不必要的路径搜索，为电脑鼠竞赛的胜利争取时间 1.电脑鼠走迷宫的理论基础与迷宫建模 1.1电脑鼠走迷宫的理论基础 “电脑鼠”走迷宫竞赛的任务是电脑鼠在千变万化的未知迷宫中从迷宫起点自主探索到迷宫终点的最佳路径，用时最短者优胜比赛成绩计算如式（1）所示 式中，T为第一次从起点出发到第N次到终点所用的总时间；T为第N次的运行时间，电脑鼠每一次从迷宫起点运行到迷宫终点所用的时间，称为一次运行时间T为奖励时间（一般为负数），T为惩罚时间，二者由比赛规则确定[1]；T为排障时间，在每次运行结束后都会获得一个数值，最终成绩为数值最小的T。

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

此向洪融合算法不仅解决了向心法则对特殊路径的搜。