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

1、ieee电脑鼠迷宫路径选择及死区决策ieee电脑鼠路径选择及死区决策一、引言（一）ieee电脑鼠走迷宫竟赛背景嵌入式系统融合了微电了、计算机软硬件、通信和电了工程等多种技术，广泛应川于 航空、航天、仪器仪表、工业控制和3c （computercommunication、consumer）等领 域，是科技集成创新的主要手段。为了培养科技创性意识和动手能力，全国各地在近儿年 纷纷举办“电脑鼠走迷宫“邀请赛。电脑鼠英文名叫做micromouse,是使用嵌入式微控制器、传感器和机电运动部件构成的 一种智能行走装置（微型机器人）。电脑鼠耍在指定的迷宫屮比赛，在迷宫屮探索以找岀 通往终点的路径，并随时掌握

2、自身的位置信息，准确获取墙壁信息并做记录，最终依靠记 忆找出走出迷宫的最佳路径，以最短的时间解开迷宫，赢得比赛。国际电工和电子工程学会（ieee）每年都要举办一次国际性的电脑鼠走迷宫竞赛，自举 办以來参加国踊跃，为此许多大学还开设了 “电脑鼠原理和制作”选修课程。2007年和 2008年，上海市计算机学会率先在国内主办了两次ieee标准电脑鼠走迷宫邀请赛（长三 角地区），有三十多所院校参加。2009年广州致远电了有限公司赞助了全国“ieee标准 电脑鼠走迷宫”邀请赛，共邀请全国9个赛区的52所高校参赛，反响强烈。图1所示为电脑鼠图2所示为比赛迷宫1本文主要以micromouse615为平台，介

3、绍电脑鼠参赛的实现，对有些方而的基本算法提 出改进，并在此基础上加上了一些自c的算法思想，比如说：用数学模型的方法提出了用 改进后的数字pid算法对行进小的电脑鼠进行状态调整，进入死区的电脑鼠的人工智能决 策，参赛时迷宫搜索的易于实现的算法以及植入操作系统的思想。（二）竞赛平台简介micromouse615平台包含了微控制雅、电机、红外线传感器、控制平台。其中最重耍的 微控制器是lm3s615微控制器，如下图3为lm3s615的系统结构图。其中内核用的是arm cortex-m3,外围还有存储器、系统时钟、定时器、输入输出端口、数模转换器等等。arm cortex-m3处理器为高性能、低成木的

4、平台提供了一个能够满足小存储耍求解决方 案、简化管脚数、以及低功耗三方面要求的内核，与此同时，它还提供了出色的让算性能 和优越的系统中断响应能力。其特性如下：1、紧凑的内核2、thumb-2指令集,在与8位和16位器件相关的存储容量中,特别是在微控制器级 应用的儿千字节存储量中，提供了 arm内核所期望的高性能。3、优越的屮断处理能力，通过执行寄存器操作來实现，这些寄存器操作在处理硕件屮 断时使用。4、存储器保护单元（mpu）,为复杂的应用提供特权操作模式5、功能齐全的调试解决方案，包括：串行线jtag调试端口（swj-dp） ； flash修补和 断点（fpb）单-元，用于实现断点操作；数据

5、观察点和触发单-元（dwt）,用于执行观察 点、触发源和系统性能分析等操作；仪表跟踪宏单元（itm）,用于支持printf型调试。2图 3 micromouse615 原理图图4 lm3s615 cpu结构图关于各个部件的接线图如图3,关于系统编程尤为重要；编程时主要注意引脚的链接和 存储器的地址映射等。在具体嵌入式编程方面，可以参照lm3s651微控3制器数据手册，其中提供了存储器、串并口通信时序等全部信息。电机使用的是ba6845fs,它是步进电机,最大输出电流为10a。逻辑输入允许三种输 出模式：前进、反转和节电模式。集成电路具有低输出饱和电压，能以低电压驱动电机。红外传感器使用的型号是

6、trm-8601s,该设备是一种小型红外遥控器系统接收器，开发 和设计利用最新ic技术.pin二极管前置放人器是组装和引线框架，环氧包装被设计成一 个ir过滤雅解调输出信号可直接曲微处理器解码。控制台是使用zlg7289b, zlg7289b是广州周立功单片机发展有限公司自行设计的数码 管显示驱动及键盘扫描管理芯片，可直接驶动8位共阴式数码管（或64只独立led）, 同时还可以扫描管理多达64只按键。zlg7289b内部含有显示译码器，可直接接受bcd 码或16进制码，并同时具有2种译码方式。此外，还具有多种控制指令，如消隐、闪烁 、左移、右移、段寻址等。zlg7289b釆用spi串行总线与微

7、控制器接口,仅占用少数几根i/o 口线。利用片选信 号，多片-zlg7289b还可以并接在一起使用，能够方便地实现多于8位的显示或多于64 只按键的应川。zlg7289b叮广泛地应川于仪器仪表，丁业控制器，条形显示器，控制面 板等领域。二、实时状态采集及更新方法要想使电脑鼠具备智能选路的木领，必须使其具备记忆迷宫信息的能力，并且电脑鼠还 需记忆当前所在迷宫格和前进方向的信息，这些信息将随着电脑鼠在迷宫格屮行走而不断 被刷新。用curdir存储当前方向，用curpositionl 1存储当前坐标，用 mazeshape1616存储每个迷宫格的形状，用curwall存储当前传感器采集到迷宫格墙 壁

8、情况。信息采集算法的核心是确定何时刷新信息以及输入参数。为此用三张表格来表示 这三个刷新逻辑。当迷宫是以类似于如图5建立座标时：图54以下是数据的更新方法：表1 curdir更新方法原始状态nsw左转弯右转弯后转弯w e s e w n e 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-l) (x-l, y) (x+l, y) (x, y+l) (x, y-l) (x-l, y) (x,

9、y+1) (x, y-l) (x-l, y) (x, y+1) (x, 丫-1) (x1, y) (x+l, y) (x+l, y) (x+l, y)其中转弯项代表:准备和刚转完时的小车位置，且用于 非连续转弯。表 3 mazeshape 16 16更新方法原始状态 n (x, y) s (x, y) w (x, y)参数 curwall curwall curwallmazeshape 更新 e (x, y) curwall cur wall 直接 curwall curwa.il curwall 赋给 顺时 针转180°顺吋针转90°逆时针转90°mazesh

10、ape 赋给 mazeshape 赋给 mazeshape 赋给 mazeshape x y x y x yx y需要注意的是出上述三个刷新逻辑表可知，呛llshope需要curposi tion作为参数,而 curposition需要curdir作为输入参数来更新白身。因此当需要同时刷新三个变量的两 个或三个时，应先刷新curdir再刷新curposition最后刷新wallshapeo收集完迷宫状态z后，就是怎么进行电脑鼠的行进过程，我们参考迷宫的整体状态，可 以设计程序如下：(其中等高法在下而介绍)5void objectgoto (int8 x, int8 y)uint8 ucstep

11、 = 1;int8 cnblock = 0, cdirtemp;int8 cx, cy;cx = gmcmouse. cx;cy = gmcmouse. cy;mapstepedit (x, y) ; /* 制作等高图*/*根据等高值向冃标点运动，直到达到冃的地*/while (cx != x) | (cy != y) ucstep = gucmapstepcxcy;/*任选一个等高值比当前口身等高值小的方向前进*/if (gucmapblockecx cy & 0x01) && /* 上方有路*/(gucmapstepcxcy + 1 < ucstep) /*上

12、方等高值较小*/cdirtemp = up; /* 记录方向*/if (cdirtemp = gucmousedir) /*优先选择不需要转弯的方向*/ cnblock卄;/*前 进一个方格*/ cy+;continue; /*跳过木次循环*/if (gucmapblockcxcy&0x02) &&(gucmapstepcx+lcy < ucstep)!cdirtemp = right;if (cdirtemp = gucmousedir) cnblock+;cx+;continue;6if (gucmapblockcxcy & 0x04) &&a

13、mp;(gucmapstepcxcy - 1 < ucstep) cdirtemp = down;if (cdirtemp = gucmousedir) cnblock+;cy-；cont inue;if (gucmapblockcxcy & 0x08) && (gucmapstepcx - 1cy < ucstep) cdirtemp = left; if (cdirtemp = gucmousedir) cnblock卄；cx-；continue; cdirtemp = (cdirtemp + 4 - gucmousedir)%4;/* 计算方向偏移量*

14、/ if (cnblock) mousogoahead (cnblock) ; /* 前进 cnblock 步*/cnblock 二 0; /* 任务淸零*/*控制电脑鼠转弯*/switch (cdirtemp) case 1:mouseturnright ();break;case 2:mouseturnbacko ;7break;case 3:mouseturnleft ();break;default:break;if (cxblock) /*判断任务是否完成，否则继续前进*/mousegoahcad (cnblock); 三、迷宫算法的研究(%1) 传统算法我们把电脑鼠的迷宫算法分为两

15、个层次，迷宫搜索算法和迷宫最优路径算法。迷宫搜 索算法的目的是在没有预知迷宫路径的情况下从起点迷宫格搜索到终点迷宫格，再从终点 迷宫格搜索到起点迷宫格，好的搜索算法耍求以更短的时间搜索到更多的迷宫格，所以耍 尽量避免重复搜索已经搜索过的地方。迷宫最短路径算法要求根据已知的迷宫信息找岀一 条从入口到出口的最优路径，最优路径不仅要短而月要求弯道尽量少。在很多地方容易得知常见的迷宫搜索算法有：1右手法则：以右边为优先的前进方向，然后是直线方向、左边方向。2. 左手法则：以左边为优先的前进方向，然后是直线方向、右边方向。3. 中左法则：以直线为优先的前进方向，然后是左边方向、右边方向4. 中右法则：以

16、直线为优先的前进方向，然后是右边方向、左边方向5. 乱数法则：取随机值作为前进方向。6. 向心法则：遇有交叉时，以指向迷宫中心的方向为优先的前进方向。本人倾向于向心算法+中右法则，即当遇有交叉时，以指向迷宫中心的方向为优先的前进 方向。但是当向屮心方向的路没有时，利川屮右法则。以玄线为优先的前进方向，然后是 右边方向、左边方向。8经典的最优路径算法有：1、深度优先搜索(dfs)从入口出发，顺着某一方向向前探索，若能走通，则继续往前走；否则沿原路退回(回 溯)，换一个方向再继续探索.直至所有可能的通路都探索到为止。如果恰好某一步探索 到出口，则就找到了从入口到出口的路径。为了保证在任何位置上都能

17、沿原路退回，防上 死循环，需要使用堆栈來保存人量记录。而要求解迷宫最短路径，则必须用深度优先搜索 出所有到达岀口的路径，通过比较得到最短距离的路径.这样也必然耍求增加数据空间來 保存搜索过程中当前最短路径.增加了空间复杂度。2、广度优先搜索(bfs)从入口出发，离开入口后依次访问与当前位置邻接的单元格（上下左右方向），然后分别 从这些相邻单元格出发依次访问它们的邻接格，并使“先被访问的单元格的邻接格'先 于'后被访问的单元格的邻接格”被访问，直至访问到迷宫出口，则找到了迷宫问题的最 优解，即迷宫最短路径。该算法的显著特点是“层层推进”，探索点会随着探索的深入急 剧增加，相应地，

18、需要大量的空间用来保存探索过程的记录。空间复杂度大。但是上述两 种算法都比较抽彖复杂，编程时山于牵涉到回溯、递归等较复杂的算法，实现起來容易出 现问题，非常容易出错，尤其牵涉到复杂数据结构栈（深度优先搜索）、队列（广度优先 搜索）的操作，调试跟踪比较麻烦，所以本人不认为是一种很好的方法。（二）适于实践的算法在比赛中，采用计时的方法计算成绩，本人认为用以上传统方法选择最优路径，是十分 费时的，而且实现起来不是很简便。实现电脑鼠的快速确定最优路径的算法应该利用向心算法+中右法则来凹遍历出一部分 的迷宫，再利用等高法求出相对于已遍丿力出的迷宫状态的最短路径，我们把这条路径称之 为最优路径。首先用上文

19、所说的搜索迷宫算法（向心算法+中右法则），走到终点，然后从以终点为 起点，以上一次的起点为终点再次利用向心算法+中右法则的算法走回去。这两次走的路 最好满足以前走过的在z后的一次遍历中不再重复，为了实现9这样的要求，对以在第一次从起点到终点的遍历中，在走过的迷宫格上加上flag,标志 已走过，从此电脑鼠只走没有阻碍和没有标志迷宫格，当没有阻碍迷宫格都是标志过的， 那也只能走以前走的路了。就这样利用搜索迷宫算法+迷宫格限制条件就可以快速遍历一 部分迷宫格，并记录迷宫格的状况。将迷宫格的状态存入mazeshape16 16中，然后冋到终点利用等高法确定最优路径。 等高法介绍：假设迷宫状态如图6所示

20、，其中（#）代表的单元格表示此处有阻碍（这些 状态来源是在上一节的mazeshape16 16更新中给出）。假设图中a代表起点,b代表 终点，按照下图用等高法来确定最优路径：图6我们从a点出发，以此为第一个扩展节点，与该扩展节点相邻并且可达的方格成为町行 节点被加入到活节点队列屮，并将这些方格标，忐为1,即从起始方格a到这些方格距离为 1;接着从活动队列屮取出队首节点作为下一个扩展节点，并将与当前扩展节点相邻且为 标志过的节点标志位2,并存入活动队列中。这一过程一直继续到算法搜索到冃标方格b 或活节点队列为空为止。将图6标志如下：图7易知到达终点b时，最短距离为9;则可选择出最优路径如图8：到

21、此为止，我们就选择出了一条最优路径，电脑鼠就町以按照这条最有路径向终点冲刺 了。代码如下：void mapstepedit (int8 cx, int8 cy) uint8 n= 0;/* gmcstack下标*/ uint8 ucstep = 1;/* 等高值*/uint8 ucstat = 0;/*统计可前进的方向数*/ uint8 i, j;gmcstackn.cx = cx;/* 起点 x 值入栈*/ gmcstackn. cy = cy;/* 起点 y 值入栈*/ n+;/*初始化各坐标等高值*/ for (i = 0; i < mazetype; i+) for (j = 0

22、; j < mazetype; j+) gucmapstepij = oxff; /*制作等高图，直到堆栈中所有数据处理完毕*/ while (n) 11gucmapstepecx cy二 ucstep+; /* 填入等高值*/*对当前坐标格里可前进的方向统计*/ucstat = 0;if(gucmapblockcxcy&0x01)&&(gucmapstepcxcy+l> (ucstep) /*前方有路前方等高值人于计划设定值*/ucstat +; /*可前进方向数加1*/；if(gucmapblockcxcy&0x02)&&(guc

23、mapstepcx+lcy >(ucstep)/*右方有路,右方等高值人于计划设定值，可前进方向数加1*/ucstat+;if (gucmapblocktcxcy & 0x04) &&(gucmapstepcxcy - 1 > (ucstep) ucstat卄；if (gucmapblockcxcy & 0x08) &&(gucmapstepcx - 1cy > (ucstep) ucstat+;/*没有可前进的方向，则跳转到最近保存的分支点否则任选可前进方向前进*/if (ucstat = 0) cx = gmcstacknc

24、x;cy = gmcstackn .cy;ucstep = gucmapste讥cxcy; else if (ucstat > 1) /*有多个可前进方向，保存坐标*/gmcstackn. cx = cx; /* 横坐标 x 值入栈 */gnicstackn. cy = cy; /* 纵坐标 y 值入栈 */n+;12/*任意选择一条对前进的方向前进*/if(gucmapblockcxcy&0x01)&&(gucmapstepcxcy+l>(ucstep) /*前方冇路，前方等高值大于计划设定值，修改处标*/cy+;continue;iif (gucmapb

25、lockcxcy&0x02)&&(gucmapstepcx+ 1cy >(ucstep) /*右方冇路右方等高值大丁计划设定值修改坐标*/cx+;continuc;if (gucmapblockcxcy&0x04)&& (gucmapstepcxcy-1>(ucstep)/*后方有路后方等高值大于计划设定值修改坐标*/!cy-；continue;if (gucmapblockcxcy & 0x08) &&(gucmapstepcx-1cy > (ucstep)/*左方有路左方等高值大于计划设定值修改坐标*

26、/cx;continue;这种等高图算法也叫洪泛法求最短路径法。13其实这个最优路径并不是最短路径，因为不是所有的迷宫信息都被电脑鼠收集到，我们 只是在电脑鼠收集到的已冇信息中找出最优的路径。我认为这样的做法是可取的，因为电 脑鼠如果想得到所有的迷宫格信息，必然要全部遍历迷宫，但是这样做太花吋间了，要走 很多重复的路，并且电脑鼠遍历运行的时间越长，很难保证它的偏差足够小，就越容易出 现不稳定现象.所以我认为在电脑鼠速度足够快的情况下，最短路径和最优路径所花时间 没什么区別，但大大节省了遍历的时间和系统算法的复杂度，同时降低了电脑鼠的不稳定 性。制作完等高图，就要用等高图作为最优路径选择的基础，

27、以存储在数组里而的等高值作 为参照，以上面的思想作为依据开始让电脑属自主选择路径。（三）棊于迷宫范围已知时比赛的算法在网上我曾看见过一个台湾的电脑鼠竞赛获奖的视频，视频里的电脑鼠跑得异常快，并 且小车一开始就好像就“认识”路似的，直接就选择了最优的路径，关于小车跑得快，可 能是因为电脑鼠硬件过得去，电机驱动和控制，转弯算法调整得好。但是电脑鼠的路径规 划给我很人的启发。因为ieee电脑鼠竟赛是己知比赛迷宫图的，尽管有很多张，我个人 认为光就比赛来说，我们可以用如下的方法，把电脑鼠对应每个迷宫的最优路径存进左 （对于基于cortex-m3内核lm3s615來说，这点开销是完全对以承受的）。例如2

28、010年天津赛区的ieee电脑鼠竞赛z前有九张图，我们在此简单的取出两个迷宫 来说明：图9比赛用的一二号迷宫图我们对以让电脑鼠先走一段迷宫探测迷宫开始的状态，如图一号迷宫在（0,4）处有出 口，而二号迷宫在（0,2）处有出口，我们在比赛中就口j以设置这样的算14法：小车开始出发如果探测到（0,2）格处有出口，我们立刻执行存在微控制器中的2 号路径。否则执行1号路径。当有很多迷宫图时，基本思想一样，就是先走一段路，当电脑鼠彻底区分现在行走的到 底是哪个迷宫时，用switch开关來控制选择的最短路径。虽然这种算法能很快的是电脑鼠到达终点，取得成绩，但是这样的算法只适用于比赛， 却没冇什么研究的价值

29、。四、进入死区的人工智能决策在比赛参观了一次天津赛区的电脑鼠比赛屮，我发现有些代表队电脑鼠在行进中状态不 好（路线不再迷宫跑道中间、行进方向有偏差）,常估会出现电脑鼠进入一个死区（如图 10）,首先左边的传感器探测到阻碍，于是电脑鼠右转；但是右转一定角度后右边的传感 器也探测到阻碍，于是电脑鼠再左转；左转后右边的传感器又会探测到阻碍,此时电脑鼠就会困在墙角里出不来，选手被迫重新返回起点继续开始，这样会十分影响成绩。其实遇到这种情况，我们是有办法让电脑鼠定出死区的。方法是在程序运行中，记下传感器交替探测到阻碍的次数。并且关键是程序必须记住每一次探测到阻图10碍时前一次的探测状态，并和当前的探测状

30、态对比。如果状态相反，就在交替总数上加1。如果这个交替总数的值大于程序中预先给定的阀 值，那么就应该令电脑鼠做一个向后转的'it形弯。并且把交替计算器复位。下面的图11即为死区人丁智能决策的流程图，容易知道该决策的代码实现其实也很简 单，但是就是难在如何将该进程融介在整个系统中來实现，我们可以川中断前后台來实 现，也可以用引入操作系统，用进程z间通信來实现。15图 11 while（l）if （两个传感器探测状态不相同）if （两个传感器探测状态均不和原來自己的状态相同）count加1； 交替次数加1更新 两个传感器自身old状态为现在状态；if （count达到阀值）count复位为

31、1；执行'u' 形转弯；else /存在一个传感器状态不变，证明不存在交替了本算法只适用于逃离死区，具体电脑鼠执行算法很复杂，编写代码时想要加入这一功能 时，可以参考这一算法。使用这一算法，可以实现人工智能决策，使电脑鼠能成功的逃离 死区。if（左右均有阻碍）then后转；else if（均无阻碍）then直走；else if（状态 不同，上面判断不是死区时，左边没有阻碍时）then左转else /状态不同，上面判断 不是死区时，右边没有阻碍时then右转count=l;五、算法的实现（一）、无操作系统的前后台实现其实大多电脑鼠的操作都是基于无操作系统來实现的，简单地说就是软件

32、前后台实现的 关系，一个主函数和儿个中断来实现电脑鼠的运作，在周立功提供的源代码里而，已经有 详细的主函数与定时器中断的关系。关于主函数：主函数执行先走一步，然后用mazesearch（） 数在摸索中前进， mazesearch （）提供墙壁信息之后电脑鼠继续走。关于中断服务序：其中的-部分有关于电机驱动程序是这样运行的，首先初始程序设置 定时器定时时间，处时时间到，定时器触发中断服务子程序，通过输入驱动步进电机的时 序状态、步进电机运动的方向来调节驱动步进电机的时序状态和步进电机运动的方向；所 以在这里关键是定时时间的设定，在上而底层算法中己经介绍了电机控制的方法，易知对 以查表 guiac

33、celtable gmleft. ispeed来执彳亍 timerloadset （.）函数,guiacceltable 关于表的计算在上而已经详细介绍。同理，传感器驱动也是如此，这里就不再介绍了，按 照源码改进，我们是对以实现前后台、无操作系统的电脑鼠正常运行的。但是这样，我们就是将arm体系的处理器当成准单片机使用，有些人材小用，17只能编出一些简单的电脑鼠软件，因为没有操作系统，当代码的功能加强时，代码的编 写难度会变得很人，比如上文我们提到的数字pii）模型的决策算法。我们想利用时虽然可 以将代码嵌在中断中，但是无疑加大了代码的难度，并且代码执行的实时性不能保证，因 为数字pid算法的

34、决策算法当电脑鼠在直行过程中就要立即被调川，不然不能及时的调整 电脑鼠的状态，后果会出乎意料，这种多进程的软件实现最好是利用操作系统來辅助实 现。（二）、基于uc/0s-1i多进程的软件设计一种好的电脑鼠软件设计非常复杂，若像上文采川传统的前后台模式來管理程序会导致 很大的开发难度，且程序不易修改。因此我们考虑在lm3s615上移植u c/os-ii o作为一 种嵌入式实时操作系统，u c/os-ii提供了很多系统服务，例如信号量、互斥型信号量、 事件标志、消息邮箱、消息队列、块大小固左的内存川请与释放及时间管理等，基于rtos 编程，不仅使系统的实时性、稳定性和可靠性有很高的保障，而11为设计者与cpu之间建 立了桥梁，使设计者考虑的问题会人人的减少，同时也便于修改与维护。在硬件上覆盖一 层操作系统，虽然增加了代码的长度，占用了系统史多的时间和空间资源，但是对于基于 cortex-m3内核的lm3s615來说，这点开销是完全可以承受的。首先我们把整个系统分为四个进程和四个中断。四个进程的