电脑鼠走迷宫智能算法的研究与优化

王艺宁　蒋涵　王博　于娜

摘 要：电脑鼠（Micromouse）是智能机电鼠的简称，实际上是一个由微处理器控制的，集感知、判断、行走功能于一体，能够自动寻找最佳路径到达目的地的微型机器人。该文简要分析了电脑鼠的硬件组成和工作原理，在此基础上重点对电脑鼠软件部分的探测策略模块、等高图制作模块、冲刺模块进行了分析研究与优化，并通过大量实验进行了验证。实验结果表明优化后的算法能够在一定程度上有效地提高电脑鼠走迷宫的运行速度、减少电脑鼠的搜索时间。

关键词：电脑鼠 嵌入式系统 智能算法 搜索法则

中图分类号：TP36 文献标识码：A 文章编号：1674-098X（2015）11（b）-0129-03

Abstract：Micromouse （computer mouse） is the abbreviation of the intelligent electrical mouse. It is actually a micro robot which is controlled by the microprocessor with abilities to perceive、judge and walk， which is capable of finding the best path to reach the destination automatically. In this paper， the hardware and working principle of the micromouse are briefly analyzed， and the key part of this paper is to analyze and optimize the search strategy module， the contour map-module drawn module and the module of sprint of the software， and verified these through a lot of experiments .The experimental results show that the optimized algorithm can effectively improve the running speed of the micromouse and reduce the searching time of the micromouse.

Key Words：Embedded System；Micromouse；Intelligent Algorithm；Search strategy

该文以TQD-Micromouse-JZ电脑鼠为研究对象，以电脑鼠走迷宫比赛为背景。电脑鼠车体采用四轮驱动结构，内核控制器采用32位ARM Cortex-M3 STM32，控制和检测红外传感器；微控制器根据检测到的传感信号，控制电机驱动电路，调整行走，按照载入搜索算法进行迷宫的探测，寻找最短路径，最终实现从起点到终点的冲刺。

1 电脑鼠硬件研究

该部分主要研究的是TQD-Micromouse-JZ电脑鼠的硬件设计，针对电源模块、微控制器单元模块、传感器模块和直流电机控制模块[1]四个模块进行研究。其中ARM Cortex-M3 STM32内核控制器是电脑鼠的核心，通过检测传感器信号，结合载入的搜索算法，控制直流电机，从而实现电脑鼠在迷宫中的行走。

2 电脑鼠软件研究与优化

电脑鼠的软件部分主要用来检测迷宫环境，传送控制信号给相应的硬件模块，对在迷宫中行走的电脑鼠进行制导与导航[2]。软件部分分为相对方向与绝对方向的转换模块、墙壁资料存储模块、探测策略模块、等高图制作模块、冲刺模块、转弯模块。该文主要对探测策略模块、等高图制作模块、冲刺模块进行了分析研究与优化，并通过大量实验进行了验证。

2.1 探测策略

电脑鼠走迷宫可以采用全迷宫探测策略或部分迷宫探测策略，从中找出最佳的路径。在时间有限的情况下只能选择后者。做此种处理的电脑鼠要时刻掌握自己的位置及姿态，记录所有访问过的方块四周是否有墙壁，记忆曾经搜索过的路径。

2.1.1 现有搜索法则

现有基础搜索法则有左手法则、右手法则、中左法则和中右法则，中心法则由以上基础法则按照一定的规则有机组合起来，随时根据电脑鼠与迷宫终点的相对位置智能的选择最有效的基础法则，使得电脑鼠搜索方向始终以目标点所在方向为最优方向。

根据比赛规则，电脑鼠首先从起点出发，找到目标点后回到起点准备第一次冲刺。在实际试验中发现，电脑鼠使用中心法则搜索到目标点后根据已知的迷宫信息计算出一条最短路回到起点，但是由于电脑鼠采用部分迷宫搜索策略，往往这条路不是最优路径。根据比赛规则，电脑鼠比赛成绩=迷宫时间/30+运行时间-奖励时间[3]，所以，要尽可能找到更优路径来减小运行时间。

2.1.2 中心法则优化

为了提高迷宫搜索的有效性，对中心法则进行优化，电脑鼠从目标点回到起点时再继续搜索其他路径，同样采用最高效的中心法则，以起点或电脑鼠搜索到的第一个分支节点为中心进行搜索。为了验证优化后算法的性能，该文搭建如图1所示的迷宫，分别以4个顶点为起点模拟完整的比赛。电脑鼠的搜索结果如图1所示。

记录4组成功完成且无触碰实验的实验数据，如表1所示。通过实验数据不难发现，当二次搜索的路径为更优路径时（A，B为出发点），优化后的算法能显著提高比赛成绩；当二次搜索路径没有更优时（C，D为出发点），虽然会延长搜索时间，但对比赛成绩影响不大。

2.2 等高图的制作

经过有限次的探测后，已经可以得到部分或大部分描述迷宫图线路的二维表，其中可能包含了若干条可以到达终点的路径，为了寻找到达终点的路径，需要制作等高图[4]。

由于电脑鼠在转弯和直行时，走相等的步数时间代价是不同的，不能单纯的用步数来确定等高值，因此，对转弯加权制作等高图对最优路径的选择更有效。

由于电脑鼠转弯需要花费较长时间，所以，要对拐弯次数（90°的转弯为一次，180°的转弯为二次）加权后加到步数中得到加权步数，因此，拐弯权重是一个对结果有重要影响的参数，要结合电脑鼠的结构和试跑确定。根据上文所得数据可计算出该电脑鼠在搜索过程中转弯权值为1.0。

2.3 冲刺

电脑鼠从起点开始，根据等高图信息直接调用行进函数，控制电脑鼠走完记录好的步数。在冲刺阶段可以通过调整不同步数的直道前进速度，实现电脑鼠的变速冲刺，既节省了时间，又能保证电脑鼠前进的稳定性。

根据比赛规则，要不断刷新运行时间来提高比赛成绩，但是由于电脑鼠运行速度越快越不稳定，越容易发生碰撞，因此，可以先用保守速度冲刺完成比赛，在实验中发现，当速度为160时，电脑鼠能稳定运行，冲刺成功率几乎为100%，平均冲刺时间为13.5 s。因此，选用160为保守冲刺速度，再通过实验确定后续冲刺速度。用节省的时间（T）来显示多次冲刺的优势。（Ti=（13.5-Si）-（13.5×2×1/30））

根据表2实验结果，并综合考虑节省时间和电脑鼠冲刺成功率，将第2次冲刺速度确定为200，平均冲刺时间为10.2 s。以此为基础进行实验确定第3次冲刺速度。（Ti=（10.2-Si）-（（13.5+10.2）×2×1/30））

根据表3实验结果，当第3次的冲刺速度低于220时，不能刷新成绩，所以冲刺是没有意义的，综合考虑电脑鼠冲刺成功率，将3次冲刺速度确定为235，平均冲刺时间为7.9s。

3 结语

通过不断地实验对电脑鼠走迷宫智能算法进行优化，并进行反复验证，实验结果表明，优化后的算法能够在一定程度上有效地提高电脑鼠走迷宫的运行速度、减少电脑鼠的搜索时间。但由于笔者研究能力有限，对电脑鼠走迷宫智能算法的优化方法的学习和实践还处于初级阶段，今后还需进一步深入学习、研究和实践。

参考文献

[1] 付秀伟，张骅.基于ARM—M3的电脑鼠硬件设计[J].吉林化工学院学报，2012，29（1）：47-49.

[2] 祝学云，况迎辉，杨海波.“基于LM3S615的电脑鼠实践”研讨班课程建设[J].电气电子教学学报，2011（4）：25-26.

[3] IEEE国际电工和电子工程学会.IEEE电脑鼠（迷宫）竞赛规则和介绍—嵌入之梦[Z].

[4] 张新谊.一种电脑鼠走迷宫的算法[J].单片机与嵌入式系统应用，2007（5）：84-85.

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

[6] UK Micromouse Championship.UK Micromouse Hampion-ship Rules.UK Mieromouse Championship，2006.