IEEE电脑鼠迷宫路径选择及死区决策

IEEE电脑鼠路径选择及死区决策一、引言（一）IEEE电脑鼠走迷宫竞赛背景嵌入式系统融合了微电子、计算机软\硬件、通信和电子工程等多种技术，广泛应用于航空、航天、仪器仪表、工业控制和3C（Computer、Communication、Consumer）等领域，是科技集成创新的主要手段。

为了培养科技创性意识和动手能力，全国各地在近几年纷纷举办“电脑鼠走迷宫“邀请赛。

电脑鼠英文名叫做MicroMouse，是使用嵌入式微控制器、传感器和机电运动部件构成的一种智能行走装置（微型机器人）。

电脑鼠要在指定的迷宫中比赛，在迷宫中探索以找出通往终点的路径，并随时掌握自身的位置信息，准确获取墙壁信息并做记录，最终依靠记忆找出走出迷宫的最佳路径，以最短的时间解开迷宫，赢得比赛。

国际电工和电子工程学会（IEEE）每年都要举办一次国际性的电脑鼠走迷宫竞赛，自举办以来参加国踊跃，为此许多大学还开设了“电脑鼠原理和制作”选修课程。

2007 年和2008 年，上海市计算机学会率先在国内主办了两次IEEE 标准电脑鼠走迷宫邀请赛（长三角地区），有三十多所院校参加。

2009 年广州致远电子有限公司赞助了全国“IEEE 标准电脑鼠走迷宫”邀请赛，共邀请全国9 个赛区的52所高校参赛，反响强烈。

图1 所示为电脑鼠图2 所示为比赛迷宫本文主要以MicroMouse615为平台，介绍电脑鼠参赛的实现，对有些方面的基本算法提出改进，并在此基础上加上了一些自己的算法思想，比如说：用数学模型的方法提出了用改进后的数字PID算法对行进中的电脑鼠进行状态调整，进入死区的电脑鼠的人工智能决策，参赛时迷宫搜索的易于实现的算法以及植入操作系统的思想。

（二）竞赛平台简介MicroMouse615平台包含了微控制器、电机、红外线传感器、控制平台。

其中最重要的微控制器是LM3S615微控制器，如下图3为LM3S615的系统结构图。

其中内核用的是ARM Cortex-M3,外围还有存储器、系统时钟、定时器、输入输出端口、数模转换器等等。

ARM Cortex-M3 处理器为高性能、低成本的平台提供了一个能够满足小存储要求解决方案、简化管脚数、以及低功耗三方面要求的内核，与此同时，它还提供了出色的计算性能和优越的系统中断响应能力。

其特性如下：1、紧凑的内核2、Thumb-2 指令集，在与8 位和16 位器件相关的存储容量中，特别是在微控制器级应用的几千字节存储量中，提供了ARM 内核所期望的高性能。

3、优越的中断处理能力，通过执行寄存器操作来实现，这些寄存器操作在处理硬件中断时使用。

4、存储器保护单元（MPU），为复杂的应用提供特权操作模式5、功能齐全的调试解决方案，包括：串行线JTAG 调试端口（SWJ-DP）；Flash 修补和断点（FPB）单元，用于实现断点操作；数据观察点和触发单元（DWT），用于执行观察点、触发源和系统性能分析等操作；仪表跟踪宏单元（ITM），用于支持Printf 型调试。

图3 MicroMouse615 原理图图4 LM3S615 CPU结构图关于各个部件的接线图如图3，关于系统编程尤为重要；编程时主要注意引脚的链接和存储器的地址映射等。

在具体嵌入式编程方面，可以参照LM3S651微控制器数据手册，其中提供了存储器、串并口通信时序等全部信息。

电机使用的是BA6845FS，它是步进电机，最大输出电流为1.0A。

逻辑输入允许三种输出模式：前进、反转和节电模式。

集成电路具有低输出饱和电压，能以低电压驱动电机。

红外传感器使用的型号是IRM-8601S，该设备是一种小型红外遥控器系统接收器，开发和设计利用最新IC技术. PIN二极管前置放大器是组装和引线框架，环氧包装被设计成一个IR过滤器.解调输出信号可直接由微处理器解码。

控制台是使用ZLG7289B， ZLG7289B是广州周立功单片机发展有限公司自行设计的数码管显示驱动及键盘扫描管理芯片，可直接驱动8位共阴式数码管（或64 只独立LED），同时还可以扫描管理多达64 只按键。

ZLG7289B 内部含有显示译码器，可直接接受BCD 码或16 进制码，并同时具有2 种译码方式。

此外，还具有多种控制指令，如消隐﹑闪烁﹑左移﹑右移﹑段寻址等。

ZLG7289B 采用SPI 串行总线与微控制器接口，仅占用少数几根I/O 口线。

利用片选信号，多片ZLG7289B 还可以并接在一起使用，能够方便地实现多于8 位的显示或多于64 只按键的应用。

ZLG7289B 可广泛地应用于仪器仪表，工业控制器，条形显示器，控制面板等领域。

二、实时状态采集及更新方法要想使电脑鼠具备智能选路的本领，必须使其具备记忆迷宫信息的能力，并且电脑鼠还需记忆当前所在迷宫格和前进方向的信息，这些信息将随着电脑鼠在迷宫格中行走而不断被刷新。

用CurDir 存储当前方向，用CurPosition[1][1]存储当前坐标，用MazeShape[16][16]存储每个迷宫格的形状，用CurWall存储当前传感器采集到迷宫格墙壁情况。

信息采集算法的核心是确定何时刷新信息以及输入参数。

为此用三张表格来表示这三个刷新逻辑。

当迷宫是以类似于如图5建立座标时：图5以下是数据的更新方法：表1 CurDir更新方法原始状态N S W E左转弯W E S N右转弯 E W N S后转弯S N E W其中转弯项代表：准备和刚转完时的小车位置，且用于非连续转弯。

表2 CurPosition更新方法原始状态N (X,Y) S (X,Y) W (X,Y) E (X,Y)直走（X,Y+1） (X,Y-1) (X-1，Y) (X+1，Y)左转弯（X,Y+1） (X,Y-1) (X-1，Y) (X+1，Y)右转弯（X,Y+1） (X,Y-1) (X-1，Y) (X+1，Y)后转弯（X,Y+1） (X,Y-1) (X-1，Y) (X+1，Y)其中转弯项代表：准备和刚转完时的小车位置，且用于非连续转弯。

表3 MazeShape[16][16]更新方法原始状态参数N (X,Y) S (X,Y) W (X,Y)CurWall CurWall CurWallE (X,Y)CurWallMazeShape更新CurWall直接 CurWall CurWall赋给顺时针转180°顺时针转90°MazeShape 赋给MazeShape 赋给MazeShape[x][y] [x][y] [x][y]CurWall逆时针转90°赋给MazeShape[x][y]需要注意的是由上述三个刷新逻辑表可知，WallShape 需要CurPosition 作为参数，而CurPosition 需要CurDir作为输入参数来更新自身。

因此当需要同时刷新三个变量的两个或三个时，应先刷新CurDir 再刷新CurPosition 最后刷新WallShape。

收集完迷宫状态之后，就是怎么进行电脑鼠的行进过程，我们参考迷宫的整体状态，可以设计程序如下：（其中等高法在下面介绍）void objectGoTo (int8 x, int8 y){uint8 ucStep = 1;int8 cNBlock = 0, cDirTemp;int8 cX,cY;cX = GmcMouse.cX;cY = GmcMouse.cY;mapStepEdit(x,y); /* 制作等高图*//*根据等高值向目标点运动，直到达到目的地*/while ((cX != x) || (cY != y)) {ucStep = GucMapStep[cX][cY];/*任选一个等高值比当前自身等高值小的方向前进*/if ((GucMapBlock[cX][cY] & 0x01) && /* 上方有路*/(GucMapStep[cX][cY + 1] < ucStep)){ /* 上方等高值较小*/cDirTemp = UP; /* 记录方向*/if (cDirTemp == GucMouseDir) { /*优先选择不需要转弯的方向*/ cNBlock++; /* 前进一个方格*/cY++;continue; /* 跳过本次循环*/}}if ((GucMapBlock[cX][cY]&0x02) &&(GucMapStep[cX+1][cY] < ucStep)){cDirTemp = RIGHT;if (cDirTemp == GucMouseDir) {cNBlock++;cX++;continue;}}if ((GucMapBlock[cX][cY] & 0x04) &&(GucMapStep[cX][cY - 1] < ucStep)) {cDirTemp = DOWN;if (cDirTemp == GucMouseDir) {cNBlock++;cY--;continue;}}if ((GucMapBlock[cX][cY] & 0x08) &&(GucMapStep[cX - 1][cY] < ucStep)) {cDirTemp = LEFT;if (cDirTemp == GucMouseDir) {cNBlock++;cX--;continue;}}cDirTemp = (cDirTemp + 4 - GucMouseDir)%4;/* 计算方向偏移量*/ if (cNBlock) {mouseGoahead(cNBlock); /* 前进cNBlock步*/}cNBlock = 0; /* 任务清零*//*控制电脑鼠转弯*/switch (cDirTemp) {case 1:mouseTurnright();break;case 2:mouseTurnback();break;case 3:mouseTurnleft();break;default:break;}}if (cNBlock) { /*判断任务是否完成，否则继续前进*/mouseGoahead(cNBlock); }}三、迷宫算法的研究（一）传统算法我们把电脑鼠的迷宫算法分为两个层次，迷宫搜索算法和迷宫最优路径算法。

迷宫搜索算法的目的是在没有预知迷宫路径的情况下从起点迷宫格搜索到终点迷宫格，再从终点迷宫格搜索到起点迷宫格，好的搜索算法要求以更短的时间搜索到更多的迷宫格，所以要尽量避免重复搜索已经搜索过的地方。

迷宫最短路径算法要求根据已知的迷宫信息找出一条从入口到出口的最优路径，最优路径不仅要短而且要求弯道尽量少。

在很多地方容易得知常见的迷宫搜索算法有：1.右手法则: 以右边为优先的前进方向,然后是直线方向、左边方向。