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

IEEE电脑鼠路径选择及死区决策一、引言（一）IEEE电脑鼠走迷宫竞赛背景嵌入式系统融合了微电子、计算机软\硬件、通信和电子工程等多种技术，广泛应用于航空、航天、仪器仪表、工业控制和3C（Computer、Communication、Consumer）等领域，是科技集成创新的主要手段。为了培养科技创性意识和动手能力，全国各地在近几年纷纷举办“电脑鼠走迷宫“邀请赛。电脑鼠英文名叫做MicroMouse，是使用嵌入式微控制器、传感器和机电运动部件构成的一种智能行走装置（微型机器人）。电脑鼠要在指定的迷宫中比赛，在迷宫中探索以找出通往终点的路径，并随时掌握自身的位置信息，准确获取墙壁信息并做记录，最终依靠记忆找出走出迷宫的最佳路径，以最短的时间解开迷宫，赢得比赛。国际电工和电子工程学会（IEEE）每年都要举办一次国际性的电脑鼠走迷宫竞赛，自举办以来参加国踊跃，为此许多大学还开设了“电脑鼠原理和制作”选修课程。2007年和2008年，上海市计算机学会率先在国内主办了两次IEEE标准电脑鼠走迷宫邀请赛（长三角地区），有三十多所院校参加。2009年广州致远电子有限公司赞助了全国“IEEE标准电脑鼠走迷宫”邀请赛，共邀请全国9个赛区的52所高校参赛，反响强烈。图1所示为电脑鼠图2所示为比赛迷宫 本文主要以MicroMouse615为平台，介绍电脑鼠参赛的实现，对有些方面的基本算法提出改进，并在此基础上加上了一些自己的算法思想，比如说：用数学模型的方法提出了用改进后的数字PID算法对行进中的电脑鼠进行状态调整，进入死区的电脑鼠的人工智能决策，参赛时迷宫搜索的易于实现的算法以及植入操作系统的思想。（二）竞赛平台简介MicroMouse615平台包含了微控制器、电机、红外线传感器、控制平台。其中最重要的微控制器是LM3S615微控制器，如下图3为LM3S615的系统结构图。其中内核用的是ARMCortex-M3,外围还有存储器、系统时钟、定时器、输入输出端口、数模转换器等等。ARMCortex-M3处理器为高性能、低成本的平台提供了一个能够满足小存储要求解决方案、简化管脚数、以及低功耗三方面要求的内核，与此同时，它还提供了出色的计算性能和优越的系统中断响应能力。其特性如下：1、紧凑的内核2、Thumb-2指令集，在与8位和16位器件相关的存储容量中，特别是在微控制器级应用的几千字节存储量中，提供了ARM内核所期望的高性能。3、优越的中断处理能力，通过执行寄存器操作来实现，这些寄存器操作在处理硬件中断时使用。4、存储器保护单元（MPU），为复杂的应用提供特权操作模式5、功能齐全的调试解决方案，包括：串行线JTAG调试端口（SWJ-DP）；Flash修补和断点（FPB）单元，用于实现断点操作；数据观察点和触发单元（DWT），用于执行观察点、触发源和系统性能分析等操作；仪表跟踪宏单元（ITM），用于支持Printf型调试。图3MicroMouse615原理图图4LM3S615CPU结构图关于各个部件的接线图如图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建立座标时： Y（02）（12）（22）（01）（11）（21）（00）（10）X（20）X图5以下是数据的更新方法：表1CurDir更新方法原始状态NSWE左转弯WESN右转弯EWNS后转弯SNEW其中转弯项代表：准备和刚转完时的小车位置，且用于非连续转弯。表2CurPosition更新方法原始状态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)其中转弯项代表：准备和刚转完时的小车位置，且用于非连续转弯。表3MazeShape[16][16]更新方法原始状态参数N(X,Y)S(X,Y)W(X,Y)CurWallCurWallCurWallE(X,Y)CurWallMazeShape更新CurWall直接CurWallCurWall赋给顺时针转180°顺时针转90°MazeShape赋给MazeShape赋给MazeShape[x][y][x][y][x][y]CurWall逆时针转90°赋给MazeShape[x][y]需要注意的是由上述三个刷新逻辑表可知，WallShape需要CurPosition作为参数，而CurPosition需要CurDir作为输入参数来更新自身。因此当需要同时刷新三个变量的两个或三个时，应先刷新CurDir再刷新CurPosition最后刷新WallShape。收集完迷宫状态之后，就是怎么进行电脑鼠的行进过程，我们参考迷宫的整体状态，可以设计程序如下：（其中等高法在下面介绍）voidobjectGoTo(int8x,int8y){uint8ucStep=1;int8cNBlock=0,cDirTemp;int8cX,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){case1:mouseTurnright();break;case2:mouseTurnback();break;case3:mouseTurnleft();break;default:break;}}if(cNBlock){/*判断任务是否完成，否则继续前进*/mouseGoahead(cNBlock);}}三、迷宫算法的研究（一）传统算法我们把电脑鼠的迷宫算法分为两个层次，迷宫搜索算法和迷宫最优路径算法。迷宫搜索算法的目的是在没有预知迷宫路径的情况下从起点迷宫格搜索到终点迷宫格，再从终点迷宫格搜索到起点迷宫格，好的搜索算法要求以更短的时间搜索到更多的迷宫格，所以要尽量避免重复搜索已经搜索过的地方。迷宫最短路径算法要求根据已知的迷宫信息找出一条从入口到出口的最优路径，最优路径不仅要短而且要求弯道尽量少。在很多地方容易得知常见的迷宫搜索算法有：1.右手法则:以右边为优先的前进方向,然后是直线方向、左边方向。2.左手法则:以左边为优先的前进方向,然后是直线方向、右边方向。3.中左法则:以直线为优先的前进方向,然后是左边方向、右边方向4.中右法则:以直线为优先的前进方向,然后是右边方向、左边方向5.乱数法则:取随机值作为前进方向。6.向心法则:遇有交叉时,以指向迷宫中心的方向为优先的前进方向。本人倾向于向心算法+中右法则，即当遇有交叉时,以指向迷宫中心的方向为优先的前进方向。但是当向中心方向的路没有时，利用中右法则。以直线为优先的前进方向,然后是右边方向、左边方向。经典的最优路径算法有：1、深度优先搜索(DFS) 从入口出发，顺着某一方向向前探索，若能走通，则继续往前走；否则沿原路退回(回溯)，换一个方向再继续探索．直至所有可能的通路都探索到为止。如果恰好某一步探索到出口，则就找到了从入口到出口的路径。为了保证在任何位置上都能沿原路退回，防止死循环，需要使用堆栈来保存大量记录。而要求解迷宫最短路径，则必须用深度优先搜索出所有到达出口的路径，通过比较得到最短距离的路径．这样也必然要求增加数据空间来保存搜索过程中当前最短路径．增加了空间复杂度。2、广度优先搜索(BFS)从入口出发，离开入口后依次访问与当前位置邻接的单元格(上下左右方向)，然后分别从这些相邻单元格出发依次访问它们的邻接格，并使“先被访问的单元格的邻接格‘先于’后被访问的单元格的邻接格”被访问，直至访问到迷宫出口，则找到了迷宫问题的最优解，即迷宫最短路径。该算法的显著特点是“层层推进”，探索点会随着探索的深入急剧增加，相应地，需要大量的空间用来保存探索过程的记录。空间复杂度大。但是上述两种算法都比较抽象复杂,编程时由于牵涉到回溯、递归等较复杂的算法，实现起来容易出现问题,非常容易出错，尤其牵涉到复杂数据结构栈(深度优先搜索)、队列(广度优先搜索)的操作,调试跟踪比较麻烦，所以本人不认为是一种很好的方法。（二）适于实践的算法在比赛中，采用计时的方法计算成绩，本人认为用以上传统方法选择最优路径，是十分费时的，而且实现起来不是很简便。实现电脑鼠的快速确定最优路径的算法应该利用向心算法+中右法则来回遍历出一部分的迷宫，再利用等高法求出相对于已遍历出的迷宫状态的最短路径，我们把这条路径称之为最优路径。首先用上文所说的搜索迷宫算法（向心算法+中右法则），走到终点，然后从以终点为起点，以上一次的起点为终点再次利用向心算法+中右法则的算法走回去。这两次走的路最好满足以前走过的在之后的一次遍历中不再重复，为了实现这样的要求，可以在第一次从起点到终点的遍历中，在走过的迷宫格上加上flag，标志已走过，从此电脑鼠只走没有阻碍和没有标志迷宫格，当没有阻碍迷宫格都是标志过的，那也只能走以前走的路了。就这样利用搜索迷宫算法+迷宫格限制条件就可以快速遍历一部分迷宫格，并记录迷宫格的状况。将迷宫格的状态存入MazeShape[16][16]中，然后回到终点利用等高法确定最优路径。等高法介绍：假设迷宫状态如图6所示，其中（##）代表的单元格表示此处有阻碍（这些状态来源是在上一节的MazeShape[16][16]更新中给出）。假设图中A代表起点，B代表终点，按照下图用等高法来确定最优路径：######A######B################

图6我们从A点出发，以此为第一个扩展节点，与该扩展节点相邻并且可达的方格成为可行节点被加入到活节点队列中，并将这些方格标志为1，即从起始方格A到这些方格距离为1；接着从活动队列中取出队首节点作为下一个扩展节点，并将与当前扩展节点相邻且为标志过的节点标志位2，并存入活动队列中。这一过程一直继续到算法搜索到目标方格B或活节点队列为空为止。将图6标志如下：32##21####1A1##212####B##234##8######5678######678 图7易知到达终点B时，最短距离为9;则可选择出最优路径如图8：######A######B################ 图8到此为止，我们就选择出了一条最优路径，电脑鼠就可以按照这条最有路径向终点冲刺了。代码如下：voidmapStepEdit(int8cX,int8cY){uint8n=0;/*GmcStack[]下标*/uint8ucStep=1;/*等高值*/uint8ucStat=0;/*统计可前进的方向数*/uint8i,j;GmcStack[n].cX=cX;/*起点X值入栈*/GmcStack[n].cY=cY;/*起点Y值入栈*/n++;/*初始化各坐标等高值*/for(i=0;i<MAZETYPE;i++){for(j=0;j<MAZETYPE;j++){GucMapStep[i][j]=0xff;}}/*制作等高图，直到堆栈中所有数据处理完毕*/while(n){GucMapStep[cX][cY]=ucStep++;/*填入等高值*//*对当前坐标格里可前进的方向统计*/ucStat=0;if((GucMapBlock[cX][cY]&0x01)&&(GucMapStep[cX][cY+1]>(ucStep))){/*前方有路前方等高值大于计划设定值*/ucStat++;/*可前进方向数加1*/}if((GucMapBlock[cX][cY]&0x02)&&(GucMapStep[cX+1][cY]>(ucStep)))/*右方有路,右方等高值大于计划设定值,可前进方向数加1*/ {ucStat++;}if((GucMapBlock[cX][cY]&0x04)&&(GucMapStep[cX][cY-1]>(ucStep))){ucStat++;}if((GucMapBlock[cX][cY]&0x08)&&(GucMapStep[cX-1][cY]>(ucStep))){ucStat++;}/*没有可前进的方向，则跳转到最近保存的分支点否则任选可前进方向前进*/if(ucStat==0){n--;cX=GmcStack[n].cX;cY=GmcStack[n].cY;ucStep=GucMapStep[cX][cY];}else{if(ucStat>1){/*有多个可前进方向，保存坐标*/GmcStack[n].cX=cX;/*横坐标X值入栈*/GmcStack[n].cY=cY;/*纵坐标Y值入栈*/n++;}/*任意选择一条可前进的方向前进*/if((GucMapBlock[cX][cY]&0x01)&&(GucMapStep[cX][cY+1]>(ucStep)))/*前方有路,前方等高值大于计划设定值,修改坐标*/{cY++;continue;}if((GucMapBlock[cX][cY]&0x02)&&(GucMapStep[cX+1][cY]>(ucStep)))/*右方有路右方等高值大于计划设定值修改坐标*/{cX++;continue;}if((GucMapBlock[cX][cY]&0x04)&&(GucMapStep[cX][cY-1]>(ucStep)))/*后方有路后方等高值大于计划设定值修改坐标*/{cY--;continue;}if((GucMapBlock[cX][cY]&0x08)&&(GucMapStep[cX-1][cY]>(ucStep)))/*左方有路左方等高值大于计划设定值修改坐标*/{cX--;continue;}}}}这种等高图算法也叫洪泛法求最短路径法。其实这个最优路径并不是最短路径，因为不是所有的迷宫信息都被电脑鼠收集到，我们只是在电脑鼠收集到的已有信息中找出最优的路径。我认为这样的做法是可取的，因为电脑鼠如果想得到所有的迷宫格信息，必然要全部遍历迷宫，但是这样做太花时间了，要走很多重复的路，并且电脑鼠遍历运行的时间越长，很难保证它的偏差足够小，就越容易出现不稳定现象。所以我认为在电脑鼠速度足够快的情况下，最短路径和最优路径所花时间没什么区别，但大大节省了遍历的时间和系统算法的复杂度，同时降低了电脑鼠的不稳定性。 制作完等高图，就要用等高图作为最优路径选择的基础，以存储在数组里面的等高值作为参照，以上面的思想作为依据开始让电脑属自主选择路径。（三）基于迷宫范围已知时比赛的算法在网上我曾看见过一个台湾的电脑鼠竞赛获奖的视频，视频里的电脑鼠跑得异常快，并且小车一开始就好像就“认识”路似的，直接就选择了最优的路径，关于小车跑得快，可能是因为电脑鼠硬件过得去，电机驱动和控制，转弯算法调整得好。但是电脑鼠的路径规划给我很大的启发。因为IEEE电脑鼠竞赛是已知比赛迷宫图的，尽管有很多张，我个人认为光就比赛来说，我们可以用如下的方法，把电脑鼠对应每个迷宫的最优路径存进去（对于基于Cortex-M3内核LM3S615来说，这点开销是完全可以承受的）。例如2010年天津赛区的IEEE电脑鼠竞赛之前有九张图，我们在此简单的取出两个迷宫来说明：图9比赛用的一二号迷宫图我们可以让电脑鼠先走一段迷宫探测迷宫开始的状态，如图一号迷宫在（0,4）处有出口，而二号迷宫在（0,2）处有出口，我们在比赛中就可以设置这样的算法：小车开始出发如果探测到（0,2）格处有出口，我们立刻执行存在微控制器中的2号路径。否则执行1号路径。当有很多迷宫图时，基本思想一样，就是先走一段路，当电脑鼠彻底区分现在行走的到底是哪个迷宫时，用switch开关来控制选择的最短路径。虽然这种算法能很快的是电脑鼠到达终点，取得成绩，但是这样的算法只适用于比赛，却没有什么研究的价值。四、进入死区的人工智能决策在比赛参观了一次天津赛区的电脑鼠比赛中，我发现有些代表队电脑鼠在行进中状态不好（路线不再迷宫跑道中间、行进方向有偏差），常常会出现电脑鼠进入一个死区（如图10），首先左边的传感器探测到阻碍，于是电脑鼠右转；但是右转一定角度后右边的传感器也探测到阻碍，于是电脑鼠再左转；左转后右边的传感器又会探测到阻碍……此时电脑鼠就会困在墙角里出不来，选手被迫重新返回起点继续开始，这样会十分影响成绩。其实遇到这种情况，我们是有办法让电脑鼠走出死区的。图10方法是在程序运行中，记下传感器交替探测到阻碍的次数。并且关键是程序必须记住每一次探测到阻碍时前一次的探测状态，并和当前的探测状态对比。如果状态相反，就在交替总数上加1。如果这个交替总数的值大于程序中预先给定的阀值，那么就应该令电脑鼠做一个向后转的‘U’形弯。并且把交替计算器复位。图10下面的图11即为死区人工智能决策的流程图，容易知道该决策的代码实现其实也很简单，但是就是难在如何将该进程融合在整个系统中来实现，我们可以用中断前后台来实现，也可以用引入操作系统，用进程之间通信来实现。 图11While(1){ if(两个传感器探测状态不相同){ if(两个传感器探测状态均不和原来自己的状态相同){ Count加1；//交替次数加1 更新两个传感器自身old状态为现在状态； if(Count达到阀值){ Count复位为1； 执行‘U’形转弯；}}else//存在一个传感器状态不变，证明不存在交替了 count=1;} if(左右均有阻碍)then后转； elseif(均无阻碍)then直走； elseif(状态不同，上面判断不是死区时，左边没有阻碍时) then左转 else//状态不同，上面判断不是死区时，右边没有阻碍时 then右转}本算法只适用于逃离死区，具体电脑鼠执行算法很复杂，编写代码时想要加入这一功能时，可以参考这一算法。使用这一算法，可以实现人工智能决策，使电脑鼠能成功的逃离死区。五、算法的实现（一）、无操作系统的前后台实现其实大多电脑鼠的操作都是基于无操作系统来实现的，简单地说就是软件前后台实现的关系，一个主函数和几个中断来实现电脑鼠的运作，在周立功提供的源代码里面，已经有详细的主函数与定时器中断的关系。关于主函数：主函数执行先走一步，然后用MazeSearch()函数在摸索中前进，MazeSearch()提供墙壁信息之后电脑鼠继续走。关于中断服务序：其中的一部分有关于电机驱动程序是这样运行的，首先初始程序设置定时器定时时间，定时时间到，定时器触发中断服务子程序，通过输入驱动步进电机的时序状态、步进电机运动的方向来调节驱动步进电机的时序状态和步进电机运动的方向；所以在这里关键是定时时间的设定，在上面底层算法中已经介绍了电机控制的方法，易知可以查表GuiAccelTable[GmLeft.iSpeed]来执行TimerLoadSet(..)函数，GuiAccelTable关于表的计算在上面已经详细介绍。同理，传感器驱动也是如此，这里就不再介绍了，按照源码改进，我们是可以实现前后台、无操作系统的电脑鼠正常运行的。但是这样，我们就是将ARM体系的处理器当成准单片机使用，有些大材小用，只能编出一些简单的电脑鼠软件，因为没有操作系统，当代码的功能加强时，代码的编写难度会变得很大，比如上文我们提到的数字PID模型的决策算法。我们想利用时虽然可以将代码嵌在中断中，但是无疑加大了代码的难度，并且代码执行的实时性不能保证，因为数字PID算法的决策算法当电脑鼠在直行过程中就要立即被调用，不然不能及时的调整电脑鼠的状态，后果会出乎意料，这种多进程的软件实现最好是利用操作系统来辅助实现。（二）、基于μC/OS-Ⅱ多进程的软件设计一种好的电脑鼠软件设计非常复杂，若像上文采用传统的前后台模式来管理程序会导致很大的开发难度，且程序不易修改。因此我们考虑在LM3S615上移植μC/OS-Ⅱ。作为一种嵌入式实时操作系统，μC/OS-Ⅱ提供了很多系统服务，例如信号量、互斥型信号量、事件标志、消息邮箱、消息队列、块大小固定的内存申请与释放及时间管理等，基于RTOS编程，不仅使系统的实时性