智能老鼠走迷宫系统设计的优化与实现

尹会明

（南京信息职业技术学院, 南京,210046）

0 引言

智能老鼠走迷宫比赛中，能否迅速准确的找到迷宫的最佳路径已成为系统设计的关键问题。对于智能老鼠走迷宫的算法，国内外的研究者大体采用两种算法：深度优先搜索算法和广度优先搜索算法。传统的深度优先搜索算法从迷宫的入口出发, 若所在当前位置可通,则朝下一位置探索, 切换下一位置为当前位置； 若所在当前位置不可通, 则退回上一位置。如此重复, 直至到达出口。广度优先搜索法又叫流水法。从迷宫的入口出发, 若所在当前位置可通,则依次探索当前位置的邻接位置。然后依次将这些邻接位置设置为当前位置, 探索他们的邻接位置。层层推进, 直至找到迷宫出口。广度优先搜索与深度优先搜索相比，深度优先搜索在整个探索过程中,只需要一个探索点。而广度优先搜索比较适合在一个已知的迷宫中寻找最佳路径。相对来说，深度优先搜索成本较低,它适合于在一个未知的迷宫寻找一条通路，当然不一定是最优的。由此可见，利用深度优先算法肯定可以以顺利找到迷宫出口，但是对于有孤岛的迷宫，这种算法很容易陷入死循环[1]。本研究在分析以上两种算法的优缺点后，同时结合本次设计的实际要求，提出了一种改进的具有记忆能力的深广结合的迷宫探索方法，较好的解决了迷宫最佳路径的搜索问题，能够准确有效的找到最优路径。

1 智能老鼠系统的硬件设计

为了实现智能老鼠在迷宫中的顺利的行走，本设计的系统的硬件部分主要由几个模块组成，电源控制模块，主要用来为整个系统供电；PWM模块主要用来驱动直流步进电机；红外感知模块，用来检测智能老鼠周围是否有墙壁以及与墙壁的距离。系统的硬件框图如图1所示。

图1 系统的硬件框图

1.1 微控制器选择

微控制器采用luminray micro 公司生产的32位ARM Cortex™-M3内核的LM3S1138微控制器。具体的GPIO的功能配置如表1所示。

1.2 电机驱动模块

电机控制系统主要是用来控制智能老鼠的运动,电机的选择对机械结构的影响明显，它不但直接影响小车的尺寸和结构安排，并且对小车的运动灵活性起关键作用，主要包括电机和电机驱动电路两部份。电机采用的是直流反应式步进电机，开环控制，无需测速器件，也不需要减速器，减少了机构的复杂性。而电机驱动电路采用的是Rohm公司的生产的直流步进电机专用驱动芯片BA6845fs，具体的控制方法如表2所示[2-3]。

表1 GPIO的功能配置表

表2 BA6845fs电机驱动控制方式

1.3 红外传感电路模块

智能老鼠的红外传感模块主要负责对外部环境的监测和处理。本系统中的红外模块主要采用了IRM-8601S 红外线一体化接收头和普通的红外线发射管。为了让智能老鼠在迷宫中能够顺畅的行走，转弯，在传统3组传感器的布局基础上进行了改进，采用了5组红外传感器单元，除了正前正左正右3个方向外，还在车头前方再添加左右两个45度斜角传感器单元，在行进过程中对两侧墙壁进行实时探测，一旦任一斜角传感器单元接收到反射信号，则说明智能老鼠已经向该方向倾斜，需要及时调节步进电机使智能老鼠恢复到正确姿势。

1.4 电源部分

电源部分包括电池组和电压调节电路，电压调节电路使用的是Sipex公司的sp6641A生产的芯片, 该芯片是一个极低静态电流、高效率的DC-DC转换器, 输入电压3.3v, 输出电压5v.:电源模块主要是来为整个系统供电。对于移动机器人来说，其电源通常采用蓄电池，提供给功率器件和逻辑器件。对于一个机电控制系统来说，系统的抗干扰性能是非常重要的。对不同的功能部件提供相互隔离的电源是提高抗干扰性能的一个重要手段。

2 智能老鼠走迷宫的软件设计

迷宫机器人的软件采用模块化设计思想，这样软件实现模块化、标准化，易于理解和移植。电脑鼠的软件部分主要用来判断迷宫环境, 发送控制信息给相应的硬件模块, 对迷宫中的电脑鼠进行导航。迷宫的探索算法主要由主程序和实现各种功能的子程序组成, 主程序主要起到导向决策功能, 而智能老鼠具体的各种功能的实现则是通过调用子程序来实现的。

智能老鼠需在迷宫中完成探测道路和全速冲刺任务。智能老鼠一方面需具有探测周围环境的能力并能完成前进、转弯、停止等基本动作,另一方面还要能够寻找最优路径并沿着最优路径冲刺。迷宫搜索的算法选择是系统设计中很关键的一部分，传统的搜索迷宫算法很多，深度优先搜索，广度优先搜索，以及遗传算法都是比较经典的算法。在不同规模的迷宫中各有自己的优势[4]。

本算法根据广度优先搜索与深度优先搜索两种算法的优缺点，同时结合本次设计的实际要求，提出了一种新的改进的具有记忆能力的深广结合的迷宫探索方法，能够有效的找到最优路径。

2.1 迷宫的探测子程序

在本次设计中，由于迷宫的规模不大，探测阶段的策略主要还是采用传统的深度优先的算法,即在有限的时间或探测次数下,只探测迷宫的一部分,从中找出一条可行的路径。智能老鼠在巷道内行走,如果最后无路可走,则该巷为“死巷”[5-7]；智能老鼠在巷道内行走的方向最多只有3个(前、左、右) ,如果存在2 个或2 个以上的方向可以行走,称为“交叉”。在遇有交叉时本次设计采用的是右手法则。即当遇到障碍和交叉时，以右边为优先的前进方向[8]。

2.2 最优路径选择阶段

本文采用一种改进的深广结合的算法来搜索最优路径。首先，要引入几个概念，本算法把迷宫细分为8种状况：死胡同，右转弯 ，左转弯，直丁字路口，直通道，右丁字路口，左丁字路口，十字路口。

算法思想：根据迷宫的特点, 如果存在不只一条迷宫通道, 则在通道的路径上必然存在一个分叉口。如果先用深度优先搜索探出一条通道, 然后再在分叉点处增加搜索的宽度, 则必然能找到最短的通道。同时，记录下已搜索到的路径，在下一次深度优先搜索时候，如果碰到上次已经走过的分叉路口时，则根据上次的转向，决定当前的运动，或前进，或左转或右转，这样就大大的节省了计算量，即改进的具有记忆能力的深广结合的迷宫探索法[9]。

本算法其实是在计算量和最短通路之间一个较好的折衷，实际测试结果也表明，与传统的迷宫算法相比，本文所采用的最优路径的搜索算法更适用于探索未知的迷宫，即在本阶段的深度优先搜索阶段时，遇到迷宫分叉口，就可以利用上次在探测阶段的路况数据，决定智能老鼠的运动。

2.3 冲刺阶段

找到了最短路径, 智能老鼠就可以从起点开始以最快的速度冲到终点, 冲刺子程序可以实现该功能。

2.4 其他控制子程序

在智能老鼠的行走过程中肯定还需要调用其他的一些子程序，如老鼠行走时候需要检测其前方以及两侧的障碍状况的时候，就要用到红外检测子程序[10-11]。转弯时候需要转弯子程序和行走控制子程序，系统一些延时功能则需要延时子程序来实现。

3 实验结果及分析

为了验证本文所采用的改进的深广结合的最佳路径搜索算法在迷宫搜索时的有效性，选取了5种规模的迷宫：5×5,10×10,15×15,20×20,40×40[12-13].从智能老鼠的实际行走的路径长度以及算法的指令的执行状况两个方面对比了本算法和经典的两种算法，下面的两张表格给出了实验结果。表3展示了在不同规模的迷宫中采用不同的算法，智能老鼠的判断次数和调整次数。表4给出了在不同的规模的迷宫环境下采用不同的迷宫算法时智能老鼠所走的实际路径长度以及算法执行的指令条数。

表3 不同迷宫智能老鼠的判断次数和调整次数比较

表4 路径长度和执行指令条数的对比结果

以上的实际数据的对比结果表明，在规模较小的迷宫时候，本算法和经典的算法差别不大，没有太大的优势，但是在大型的未知迷宫探索时，本算法的优越性就明显的体现出来。智能老鼠所走的实际路径长度是最短的，算法的实验结果比较令人满意。

4 结语

本文设计了一种基于LM3S1138处理器的走迷宫智能老鼠，实验表明，智能老鼠在迷宫中行走的比较平稳，并能顺利完成前进，后退，转弯避障等相关的系统功能。算法方面，本文采用了一种改进的深广结合的最优路径搜索办法。实际的测试表明，本文的所提出的算法大大减少了路径搜索的次数，减少了计算量，提高了迷宫搜索的准确性和有效性。

[1]严蔚民.数据结构[M].北京:清华大学出版社，2003:5052.

[2]胡小兵,黄席樾.蚁群算法在迷宫最优路径问题中的应用[J].计算机仿真，2005,22(4).

[3]宗光华等.机器人的创意设计与实践[M].北京：北京航空航天大学出版社，2004.

[4]西原主计等[日],机器人C 语言机电一体化接口[M].牛连强、赵文珍译.北京：科学出版社，2002.

[5]孙巧榆等.八方向走迷宫算法[J].计算机工程，2004(1)：90-91.

[6]周立功等.Cortex-M3 开发指南—基于LM3S8000[M].北京：北京航空航天大学出版社，2005.

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

[8]周航慈.单片机程序设计基础[M].北京：航空航天大学出版社，2003

[9]李学海.PIC 单片机实用教程—提高篇[M].北京：航空航天大学出版社，2002.

[10]潘道才,陈一华.数据结构[M].成都:电子科技大学出版社,1995.

[11]袁蒲佳,龙玉国,杨薇薇.数据结构[M].武汉:华中理工大学出版社,1995.

[12]王会丽,傅卫平,方宗德等.基于改进势场函数的移动机器人路径规划[J].机床与液压，2002，10(6):67-68.

[13]Zhangb,ZhangL.AnAlgorithmfo{FindPathwi士hRotation.ln:Proe.} EEEInt.Conf Roboties and Automation，1988:917-921.