基于AVR ATmega128的迷宫电脑鼠软件设计与实现

李龙　林桂泉

摘要：根据IEEE标准电脑鼠走迷宫的比赛需求，介绍了一个基于AVR ATmega128的电脑鼠软件算法的设计与实现，主要包括底层驱动算法和顶层软件算法两个部分。该电脑鼠实现了在迷宫内快速稳定的行走及对迷宫最优路径的搜索. 电脑鼠迷宫竞赛有一定的难度，这是一种具有挑战性和趣味性的竞技比赛。Micromouse是一个涉及多个学科领域的理论与应用的综合性系统。

关键词：电脑鼠；迷宫；AVR ATmega128；IEEE

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）11-2660-04

Abstract： According to the IEEE standard computer mouse maze game needs， introduces the design and implementation of a computer mouse AVR ATmega128-based software algorithms， including algorithms underlying drivers and top software algorithms in two parts. The computer mouse to achieve a rapid and stable within walking labyrinth and maze searching for the optimal path. Computer mouse maze race with some difficulty， this is a challenging and interesting contests. Micromouse is a multidisciplinary field involving theory and application of the integrated system.

Key words： micromouse； maze； AVR ATmega128； IEEE

电脑鼠（micromouse）迷宫比赛是一个非常全面的比赛，涵盖学科包括人工智能，传感器，运动控制，软件工程，电气工程，嵌入式系统等。电脑鼠是一种基于微处理器控制的、拥有传感器和电机于一身的、能够自动识别和运动在迷宫中的智能小型机器人。它是涉及多领域知识的产物，能够协调电机、传感器、控制器的工作。在电脑鼠竞赛给定的时间内，按照一定的算法，通过检测与记录的迷宫地图，找到最佳路线，最后以最短的时间从起点运动到终点。

电脑鼠在IEEE标准迷宫中运动必须遵守一定的守则，所以必须拥有以下三个功能：

1） 有稳定且快速的行走能力；

2） 能正确判断能力；

3） 记忆路径的能力。

电脑鼠的设计过程，需要结合多个领域的知识与应用，从而推动有关技术的推陈出新和相关技术的应用实践，并且促进相关技术的利润化，产业化。电脑鼠设计过程中的一些技术与方法已经被广泛应用到大家的身边。并且电脑鼠竞赛的推广促使了国内甚至国际间的技术交流更为频繁，大家相互的竞争与学习，为该领域的进步奠定基础

1 系统整体方案

根据比赛需求电脑鼠在迷宫中应具有行走功能，并且检测和主动躲避障碍物，能在迷宫中任意行走搜索路径。其硬件结构图如。

电脑鼠实际上就是一个智能的小车，其灵活性主要由它的硬件结构设计决定，而其智能化的程度主要取决于软件的设计是否合理。智能程度越高的的电脑鼠，它的软件设计就越优秀，越合理。在电脑鼠软件设计时，把软件设计整体构架概括的分为两层，一层是底层驱动程序的设计，另一层是顶层算法程序的实现。软件设计时采用系统工程原理中的模块化的设计方法来设计，即把一个大的系统或者整体分割成小的或部分功能的系统，然后分别完成，当每个模块都完成时，将各个模块整合到一起，进行修改，处理，最后测试优化实现全部功能。在对电脑鼠软件进行设计时，主要是使用C语言进行编程。该文使用AVR ATM128单片机进行开发与设计，可以方便有效地使用C语言来实现所需要的全部功能，并且方便嵌入式开发。

2 电脑鼠底层驱动软设计

底层驱动完成了电脑鼠的基本功能，例如如直线行走，90度转弯，45度转弯，掉头，防止碰撞墙壁等。

底层软件驱动使用了模块化的程序设计方法。驱动程序主要包括初始化模块、传感器模块、电机模块和迷宫检测模块几个部分组成。

2.1 初始化模快

初始化模块完成的工作有：系统初始化、定时器初始化、电动机的初始化、红外传感器的初始化、I/O口的初始化及中断的初始化。设计初始化状态主要是为了电脑鼠后续软件的运行提供保证，并且提前收集迷宫信息，为后面的检测提供方便。

2.2 红外传感模块

红外传感模块主要是处理好输入信号和输出信号，其中作为输出信号的核心内容是怎么利用软件编程产生一段调制波作为输出发射信号。载波和调制信号相互叠加生成调制波。一般生成调制波有两种方法，一种是通过软件编程生成载波和调制信号，然后利用硬件电路的合成调制波。另外一种是直接利用软件生成调制信号。其中后一种方法让系统通过MCU定时器的PWM模式产生38KHz的调制信号，然后通过MCU定时器产生频率为250Hz的边沿触发中断，通过定时中断服务子函数控制PWM输出的使能与停止，即可产生红外发送模块所需要的调制波。通过对六组红外发射模块发出载波频率各不相同的调制波，用来收集小车正前方（2组）、左右侧（2组）、左右斜前方（2组）远近距离障碍物的情况。然后收集红外接收信号其实就是将TPS601A的输出端信号输入到MCU的A/D采样端。MCU根据采样值计算出挡板的情况和电脑鼠的姿态进行调整。endprint

2.3 电机模块

1）速度控制：电脑鼠在运行的时候，一定需要加速前进、减速前进、匀速运动等运动状态。通过定时器的PWM模式产生一定频率的调制信号来控制电机的转速以及电机的正反转，实现对电脑鼠速度的控制。

2）转弯控制：当电脑鼠检测到路口需要拐弯的时候，就需要使用这个程序。这个子程序的实现需要先测出直走时的PWM占空比，然后根据需要测出45度转弯和90度转弯的左右轮PWM占空比的比值。

3）直线控制（姿态修正）：在系统定时中断中，根据左右两边两对红外传感器输入的信号来检测电脑鼠是不是运行在迷宫跑道的中间线上。如果有偏离，则调节直流电机的某一边运行脉冲，使电机速度减低或者加速，调整电脑鼠的运行角度，从而来保证电脑鼠运行在迷宫的中间线上。如果想要让电脑鼠向右边行驶，就让左边电动机的PWM信号的占空比比右边电动机高一点；另外想让电脑鼠向左边行驶，就让右边电动机的PWM信号的占空比比左边的电动机高一点。

2.4 迷宫检测模块

1）挡板检测：在对迷宫挡板检测的过程中，首先通过软件发出38kHz红外信号，如果遇到挡板，则由红外传感器的接收模块记录下接收到的红外信号，并将结果输送给MCU进行判断分析。

2）路口检测：由安装在正前方（2组）、左右侧（2组）、左右斜前方45度（2组）的6个红外发射管发射38kHz的调制波实现远距离检查测试，依据红外传感器输入的数值，分析迷宫的路口信息和挡板情况，以便做出正确的决策。

3 电脑鼠顶层软件设计

电脑鼠的顶层软件程序设计一般是指关于电脑鼠的智能迷宫算法的实现，例如依据收集到的迷宫的消息来决策电脑鼠的运动方向和速度，记录已经搜索过得迷宫的位置信息，通过分析与计算，找出从起点到终点的最短路径等。

3.1 迷宫信息的建立

电脑鼠要能在迷宫中自由的运行，首先要知道所处的地方和行驶的方向， 所以需要设立平面坐标系，用来对迷宫方格标示，并且还需要设立一个方向变量来表示电脑鼠运行的方向以及角度。

为了简便的将迷宫的消息储存在电脑鼠中，将迷宫的挡板数据使用16*16的矩阵来标示，并且原始设置都为0，每次电脑鼠走过一格新的，就会依据电脑鼠的红外传感的测试结果更新现在位置的挡板和位置消息，需要使用数值数组Mousesize[i][j]表示方格（i， j）的挡板信息， 其bit0～bit3 分别用来标示该位置迷宫的上面、下面、左面、右面有没有挡板（1为有路，即没有挡板； 0为无路，即有挡板）， 所以当电脑鼠每经过一格的时候，就可以标示这一格的挡板信息，并且电脑鼠到过的格子必有数值存在，这样就可以判断电脑鼠有没有到过某一个格子，成为搜索迷宫的依据。

需要设立迷宫的方向变量MouseDir， MouseDir=0～3表示电脑鼠行驶的方向分别为向上、向右、向下、向左，每次电脑鼠行驶的方向或者角度旋转90度或180度时，需要将方向变量MazeDir做出相对应的改变， 所以电脑鼠就可以一直明白行驶的方向和角度，不会因为旋转而迷路。如果电脑鼠在迷宫中运行时遇到有两个或者三个可以行使的路口时，就定义为分支节点，我们采用数据结构中的栈来处理，将几个路口的信息存入栈中。当哪个路口已经走过，就将该节点从栈中取出来，当栈为空的时候即表示分支节点的各个分支电脑鼠全部都走过，即搜索结束。

电脑鼠在走迷宫时，分支节点是极其关键的。因为当电脑鼠在迷宫中搜索，会遇到走投无路，无法在前进的时候，当这个时候电脑鼠就需要回到最近的一个分支节点处继续搜索。在迷宫中搜索并寻找最短的路径从起点到终点是十分重要的， 当电脑鼠回到分支节点时，并且从栈中取出一个节点，从这个节点开始继续搜索。当电脑鼠迷宫搜索完成时，就需要利用算法分析计算出一条最优路径即从起点到终点运行的最短路径，进行全力行驶，以达到最短时间完成。

3.2 迷宫搜索算法

电脑鼠在刚进入迷宫的时候并不知道迷宫轨道和挡板的情况，所以电脑鼠要先进行迷宫的搜索，获取迷宫中跑道和挡板的信息。一般的迷宫搜索算法有洪水填充法、左手法则、向心法则、向点法则和右手法则等等。

右手法则：碰到分支节点的时候，一般是优先向右行驶进行迷宫的搜索，然后依次是前方，左方向搜索。

左手法则：碰到分支节点的时候，一般是优先向左行驶进行迷宫的搜索，然后依次是前方，右方向搜索。

向心法则：因为电脑鼠的终点是在迷宫的中心位置，所以当电脑鼠遇到分支节点的时候，将优先向着迷宫中心位置行驶。

向点法则：将迷宫当成一整体的区域，当遇到岔口时：当朝上搜索时使用右手法则，当朝下搜索时使用中左法则，当朝左搜索时使用左手法则，当朝右搜索时使用中右手法则。

洪水填充法：类似于在迷宫的起点不断的涌入洪水，洪水将沿着跑道向每一个单元格前进，每前进一个单元格就将该单元格的数值增加编码，最后到达终点，即终点数值最大。

我们改进了一个新的智能搜索算法，将洪水填充法与向心法则和向点法则的深度优先法相互结合。它的基本思想：首先使用基于向心法则的深度优先搜索算法搜索迷宫网格，依次搜索，当找到终点就结束。在搜索的时候遇到无路可走时需要回到最近的一个分支节点，则使用洪水填充法则分析搜索前一个节点的最优路径，全速返回到该节点，准备下次的搜索。并且将这次搜索的路径保存当做“热区”：接着则使用基于向点法则的深度优先搜索算法搜索。依次搜索，最终找到起点为止，搜索时候遇到无路可走则需返回上一个分支节点。依然使用洪水填充法则分析最优路径，电脑鼠在迷宫中一定会再次遇到 “热区”。如果电脑鼠碰触到“热区”，先将获得的资料保存，然后就利用洪水填充法快速回至起点。最后则使用洪水填充法和已获得的迷宫网格消息，在起点与终点中选择一天最优最短的路径，并且电脑鼠全速冲刺到终点。endprint

3.3 最优路径算法

首先电脑鼠要先搜索迷宫的网格，当电脑鼠搜索完成时，收集到足够的迷宫信息时，就依据信息分析计算出一条最优路径。在分析计算最优路径时，通常使用等高图的方式来分析寻找最优路径。采用迷宫的等高图方法，不仅仅能表示出每一个网格迷宫的离起点的步数的关系，并且能从中很明显的判断出从起点到终点的最优路径。

等高图制作原理：先设置一个16*16的二维数组空间 （MapStep[16][16]），二维数组的每个元素都表示迷宫的一个网格，其中存储的数值表示的是等高线中的与起点的步数的关系 （其中的步数是指电脑鼠行驶时经过的迷宫网格格数）。 以起点的迷宫网格等高线坐标为0，与0相邻的迷宫跑道都为1，以此类推，离起点越远的迷宫网格的等高线坐标值越大，这样就形成了类似等高线的标示。但是即使等高线相同的网格，电脑鼠的运行时间也是不同的，如图3所示，（0 ， 3）点和（1 ， 2）点的迷宫网格等高线值都为4，但一般认为电脑鼠从（ 0 ， 3）点到起点比从（ 1 ， 2）点到起点所需的时间要少，因为电脑鼠转弯要多花许多时间。所以为了避免出现错误，就需要给有分支节点的迷宫网格要加点拐弯权重，才可以得到一条从起点到终点花费时间最少的路径。其中加权步数=步数+拐弯次数×拐弯权重。

拐弯次数：每个90度都算拐弯一回，每个180度就算拐弯两回。

拐弯权重：是由电脑鼠的物理结构以及试跑的结果决定的，它对电脑鼠最后的软件设计具有至关重要的作用。一般来说，当电脑鼠没有加速的性能时，拐弯权重可以选在0.4～1.0之间，如果电脑鼠拥有多种速度时，可以依据电脑鼠的速度的变化来调节权重的比值。

4 总结

本文是以“IEEE标准电脑鼠”迷宫竞赛的要求着手，研究了电脑鼠的软件设计的过程及其改进。电脑鼠在迷宫中如何进行路径选择、障碍躲避等方面进行了研究，介绍了IEEE电脑鼠的软件模块化的分析与设计、电脑鼠驱动设计、电脑鼠在迷宫中路径选择和障碍避免算法的设计与实现。虽然电脑鼠的诞生已经过去了60多年，但是到目前为止还是没有研发出一种迷宫算法是适合于任何迷宫最智能的，最优的路径。所以对电脑鼠的智能搜索算法研究前景依然很好，并且还有一段很长得路要走。

基于电脑鼠的产品具有广泛的应用场合，该文的智能小车具拥有编程方法简便、方便控制小车，稳定性好、拓展性强等优势。经过实验，成功完成小车的加减速、向前、向后、向左，向右、持续转弯，回送速度和路程的数据等功能。由于智能小车的应用范围广泛，例如盲人导航机器小车、考古机器小车、地震搜索机器小车、远距摄像机器小车等等。伴随着计算机与电子科学的快速发展，对智能小车的研究不断地深入，智能小车的应用前景十分好。

参考文献：

[1] 周立功.ARM嵌入式系统基础教程[M].北京：北京航空航天大学出版社，2005.

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

[3] 杜春雷.ARM体系结构与编程[M].北京：清华大学出版社，2004.

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

[5] 侯益坤，侯聪玲，刘益标.基于ARM 嵌入式的智能小车的控制系统设计[J].机电工程技术，2010，39（1）：21-23.

[6] 周丰.迷宫最短路径问题的计算机解法[J].高等函授学报，2004，17（1）：42-45.

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

[8] David Sea1.ARM Architecture Reference Manual[M].Pearson Education limitied，2001.

[9] Marco Dorigo and Thomas Sti itzle.Ant Colony Optimization[M].MIT Press，2004.

[10] Mishra S，Bande P.Maze Solving Algori thms for Micro Mouse[Z].Signal Image Technology and Internet Based Systems，2008：86-93.endprint

3.3 最优路径算法

首先电脑鼠要先搜索迷宫的网格，当电脑鼠搜索完成时，收集到足够的迷宫信息时，就依据信息分析计算出一条最优路径。在分析计算最优路径时，通常使用等高图的方式来分析寻找最优路径。采用迷宫的等高图方法，不仅仅能表示出每一个网格迷宫的离起点的步数的关系，并且能从中很明显的判断出从起点到终点的最优路径。

等高图制作原理：先设置一个16*16的二维数组空间 （MapStep[16][16]），二维数组的每个元素都表示迷宫的一个网格，其中存储的数值表示的是等高线中的与起点的步数的关系 （其中的步数是指电脑鼠行驶时经过的迷宫网格格数）。 以起点的迷宫网格等高线坐标为0，与0相邻的迷宫跑道都为1，以此类推，离起点越远的迷宫网格的等高线坐标值越大，这样就形成了类似等高线的标示。但是即使等高线相同的网格，电脑鼠的运行时间也是不同的，如图3所示，（0 ， 3）点和（1 ， 2）点的迷宫网格等高线值都为4，但一般认为电脑鼠从（ 0 ， 3）点到起点比从（ 1 ， 2）点到起点所需的时间要少，因为电脑鼠转弯要多花许多时间。所以为了避免出现错误，就需要给有分支节点的迷宫网格要加点拐弯权重，才可以得到一条从起点到终点花费时间最少的路径。其中加权步数=步数+拐弯次数×拐弯权重。

拐弯次数：每个90度都算拐弯一回，每个180度就算拐弯两回。

拐弯权重：是由电脑鼠的物理结构以及试跑的结果决定的，它对电脑鼠最后的软件设计具有至关重要的作用。一般来说，当电脑鼠没有加速的性能时，拐弯权重可以选在0.4～1.0之间，如果电脑鼠拥有多种速度时，可以依据电脑鼠的速度的变化来调节权重的比值。

4 总结

本文是以“IEEE标准电脑鼠”迷宫竞赛的要求着手，研究了电脑鼠的软件设计的过程及其改进。电脑鼠在迷宫中如何进行路径选择、障碍躲避等方面进行了研究，介绍了IEEE电脑鼠的软件模块化的分析与设计、电脑鼠驱动设计、电脑鼠在迷宫中路径选择和障碍避免算法的设计与实现。虽然电脑鼠的诞生已经过去了60多年，但是到目前为止还是没有研发出一种迷宫算法是适合于任何迷宫最智能的，最优的路径。所以对电脑鼠的智能搜索算法研究前景依然很好，并且还有一段很长得路要走。

基于电脑鼠的产品具有广泛的应用场合，该文的智能小车具拥有编程方法简便、方便控制小车，稳定性好、拓展性强等优势。经过实验，成功完成小车的加减速、向前、向后、向左，向右、持续转弯，回送速度和路程的数据等功能。由于智能小车的应用范围广泛，例如盲人导航机器小车、考古机器小车、地震搜索机器小车、远距摄像机器小车等等。伴随着计算机与电子科学的快速发展，对智能小车的研究不断地深入，智能小车的应用前景十分好。

参考文献：

[1] 周立功.ARM嵌入式系统基础教程[M].北京：北京航空航天大学出版社，2005.

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

[3] 杜春雷.ARM体系结构与编程[M].北京：清华大学出版社，2004.

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

[5] 侯益坤，侯聪玲，刘益标.基于ARM 嵌入式的智能小车的控制系统设计[J].机电工程技术，2010，39（1）：21-23.

[6] 周丰.迷宫最短路径问题的计算机解法[J].高等函授学报，2004，17（1）：42-45.

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

[8] David Sea1.ARM Architecture Reference Manual[M].Pearson Education limitied，2001.

[9] Marco Dorigo and Thomas Sti itzle.Ant Colony Optimization[M].MIT Press，2004.

[10] Mishra S，Bande P.Maze Solving Algori thms for Micro Mouse[Z].Signal Image Technology and Internet Based Systems，2008：86-93.endprint

3.3 最优路径算法

首先电脑鼠要先搜索迷宫的网格，当电脑鼠搜索完成时，收集到足够的迷宫信息时，就依据信息分析计算出一条最优路径。在分析计算最优路径时，通常使用等高图的方式来分析寻找最优路径。采用迷宫的等高图方法，不仅仅能表示出每一个网格迷宫的离起点的步数的关系，并且能从中很明显的判断出从起点到终点的最优路径。

等高图制作原理：先设置一个16*16的二维数组空间 （MapStep[16][16]），二维数组的每个元素都表示迷宫的一个网格，其中存储的数值表示的是等高线中的与起点的步数的关系 （其中的步数是指电脑鼠行驶时经过的迷宫网格格数）。 以起点的迷宫网格等高线坐标为0，与0相邻的迷宫跑道都为1，以此类推，离起点越远的迷宫网格的等高线坐标值越大，这样就形成了类似等高线的标示。但是即使等高线相同的网格，电脑鼠的运行时间也是不同的，如图3所示，（0 ， 3）点和（1 ， 2）点的迷宫网格等高线值都为4，但一般认为电脑鼠从（ 0 ， 3）点到起点比从（ 1 ， 2）点到起点所需的时间要少，因为电脑鼠转弯要多花许多时间。所以为了避免出现错误，就需要给有分支节点的迷宫网格要加点拐弯权重，才可以得到一条从起点到终点花费时间最少的路径。其中加权步数=步数+拐弯次数×拐弯权重。

拐弯次数：每个90度都算拐弯一回，每个180度就算拐弯两回。

拐弯权重：是由电脑鼠的物理结构以及试跑的结果决定的，它对电脑鼠最后的软件设计具有至关重要的作用。一般来说，当电脑鼠没有加速的性能时，拐弯权重可以选在0.4～1.0之间，如果电脑鼠拥有多种速度时，可以依据电脑鼠的速度的变化来调节权重的比值。

4 总结

本文是以“IEEE标准电脑鼠”迷宫竞赛的要求着手，研究了电脑鼠的软件设计的过程及其改进。电脑鼠在迷宫中如何进行路径选择、障碍躲避等方面进行了研究，介绍了IEEE电脑鼠的软件模块化的分析与设计、电脑鼠驱动设计、电脑鼠在迷宫中路径选择和障碍避免算法的设计与实现。虽然电脑鼠的诞生已经过去了60多年，但是到目前为止还是没有研发出一种迷宫算法是适合于任何迷宫最智能的，最优的路径。所以对电脑鼠的智能搜索算法研究前景依然很好，并且还有一段很长得路要走。

基于电脑鼠的产品具有广泛的应用场合，该文的智能小车具拥有编程方法简便、方便控制小车，稳定性好、拓展性强等优势。经过实验，成功完成小车的加减速、向前、向后、向左，向右、持续转弯，回送速度和路程的数据等功能。由于智能小车的应用范围广泛，例如盲人导航机器小车、考古机器小车、地震搜索机器小车、远距摄像机器小车等等。伴随着计算机与电子科学的快速发展，对智能小车的研究不断地深入，智能小车的应用前景十分好。

参考文献：

[1] 周立功.ARM嵌入式系统基础教程[M].北京：北京航空航天大学出版社，2005.

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

[3] 杜春雷.ARM体系结构与编程[M].北京：清华大学出版社，2004.

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

[5] 侯益坤，侯聪玲，刘益标.基于ARM 嵌入式的智能小车的控制系统设计[J].机电工程技术，2010，39（1）：21-23.

[6] 周丰.迷宫最短路径问题的计算机解法[J].高等函授学报，2004，17（1）：42-45.

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

[8] David Sea1.ARM Architecture Reference Manual[M].Pearson Education limitied，2001.

[9] Marco Dorigo and Thomas Sti itzle.Ant Colony Optimization[M].MIT Press，2004.

[10] Mishra S，Bande P.Maze Solving Algori thms for Micro Mouse[Z].Signal Image Technology and Internet Based Systems，2008：86-93.endprint