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

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

一、引言

（一）IEEE电脑鼠走迷宫竞赛背景

嵌入式系统融合了微电子、计算机软\\硬件、通信和电子工程等多种技术，广泛应用于航空、航天、仪器仪表、工业控制和3C（Computer、Communication、Consumer）等领域，是科技集成创新的主要手段。为了培养科技创性意识和动手能力，全国各地在近几年纷纷举办“电脑鼠走迷宫“邀请赛。

电脑鼠英文名叫做MicroMouse，是使用嵌入式微控制器、传感器和机电运动部件构成的一种智能行走装置（微型机器人）。电脑鼠要在指定的迷宫中比赛，在迷宫中探索以找出通往终点的路径，并随时掌握自身的位置信息，准确获取墙壁信息并做记录，最终依靠记忆找出走出迷宫的最佳路径，以最短的时间解开迷宫，赢得比赛。

国际电工和电子工程学会（IEEE）每年都要举办一次国际性的电脑鼠走迷宫竞赛，自举办以来参加国踊跃，为此许多大学还开设了“电脑鼠原理和制作”选修课程。2007 年和2008 年，上海市计算机学会率先在国内主办了两次IEEE 标准电脑鼠走迷宫邀请赛（长三角地区），有三十多所院校参加。2009 年广州致远电子有限公司赞助了全国“IEEE 标准电脑鼠走迷宫” 邀请赛，共邀请全国9 个赛区的52所高校参赛，反响强烈。

图1 所示为电脑鼠 图2 所示为比赛迷宫

1

本文主要以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 型调试。

2

图3 MicroMouse615 原理图

图4 LM3S615 CPU结构图

关于各个部件的接线图如图3，关于系统编程尤为重要；编程时主要注意引脚的链接和存储器的地址映射等。在具体嵌入式编程方面，可以参照LM3S651微控

3

制器数据手册，其中提供了存储器、串并口通信时序等全部信息。

电机使用的是BA6845FS，它是步进电机，最大输出电流为1.0A。逻辑输入允许三种输出模式：前进、反转和节电模式。集成电路具有低输出饱和电压，能以低电压驱动电机。

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

控制台是使用ZLG72B， ZLG72B是广州周立功单片机发展有限公司自行设计的数码管显示驱动及键盘扫描管理芯片，可直接驱动8位共阴式数码管（或 只LED），同时还可以扫描管理多达 只按键。ZLG72B 内部含有显示译码器，可直接接受BCD 码或16 进制码，并同时具有2 种译码方式。此外，还具有多种控制指令，如消隐﹑闪烁﹑左移﹑右移﹑段寻址等。

ZLG72B 采用SPI 串行总线与微控制器接口，仅占用少数几根I/O 口线。利用片选信号，多片ZLG72B 还可以并接在一起使用，能够方便地实现多于8 位的显示或多于 只按键的应用。ZLG72B 可广泛地应用于仪器仪表，工业控制器，条形显示器，控制面板等领域。

二、实时状态采集及更新方法

要想使电脑鼠具备智能选路的本领，必须使其具备记忆迷宫信息的能力，并且电脑鼠还需记忆当前所在迷宫格和前进方向的信息，这些信息将随着电脑鼠在迷宫格中行走而不断被刷新。用CurDir 存储当前方向，用CurPosition[1][1]存储当前坐标，用MazeShape[16][16]存储每个迷宫格的形状，用CurWall存储当前传感器采集到迷宫格墙壁情况。信息采集算法的核心是确定何时刷新信息以及输入参数。为此用三张表格来表示这三个刷新逻辑。当迷宫是以类似于如图5建立座标时：

Y （02） （01） （00） （12） （11） （10） （22） （21） （20） X 图5

4

以下是数据的更新方法：

表1 CurDir更新方法

原始状态 N S W 左转弯 右转弯 后转弯

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-1) (X-1，Y) (X+1，Y) （X,Y+1） (X,Y-1) (X-1，Y) （X,Y+1） (X,Y-1) (X-1，Y) （X,Y+1） (X,Y-1) (X-1，Y)

(X+1，Y) (X+1，Y) (X+1，Y)

其中转弯项代表：准备和刚转完时的小车位置，且用于非连续转弯。

表3 MazeShape[16][16]更新方法

原始状态 N (X,Y) S (X,Y) W (X,Y) 参数 CurWall CurWall CurWall

MazeShape更新

E (X,Y) CurWall

CurWall直接 CurWall CurWall CurWall

赋给 顺时针转180° 顺时针转90° 逆时针转90° MazeShape 赋给MazeShape 赋给MazeShape 赋给MazeShape [x][y] [x][y] [x][y] [x][y]

需要注意的是由上述三个刷新逻辑表可知，WallShape 需要CurPosition 作为参数，而CurPosition 需要CurDir作为输入参数来更新自身。因此当需要同时刷新三个变量的两个或三个时，应先刷新CurDir 再刷新CurPosition 最后刷新WallShape。

收集完迷宫状态之后，就是怎么进行电脑鼠的行进过程，我们参考迷宫的整体状态，可以设计程序如下：（其中等高法在下面介绍）

5

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; }

6

}

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();

7

break; case 3:

mouseTurnleft(); break; default: break;

}

}

if (cNBlock) { /*判断任务是否完成，否则继续前进*/ mouseGoahead(cNBlock); } }

三、迷宫算法的研究 （一）传统算法

我们把电脑鼠的迷宫算法分为两个层次，迷宫搜索算法和迷宫最优路径算法。 迷宫搜索算法的目的是在没有预知迷宫路径的情况下从起点迷宫格搜索到终点迷宫格，再从终点迷宫格搜索到起点迷宫格，好的搜索算法要求以更短的时间搜索到更多的迷宫格，所以要尽量避免重复搜索已经搜索过的地方。迷宫最短路径算法要求根据已知的迷宫信息找出一条从入口到出口的最优路径，最优路径不仅要短而且要求弯道尽量少。

在很多地方容易得知常见的迷宫搜索算法有：

1.右手法则: 以右边为优先的前进方向,然后是直线方向、左边方向。 2.左手法则: 以左边为优先的前进方向,然后是直线方向、右边方向。 3.中左法则: 以直线为优先的前进方向,然后是左边方向、右边方向 4.中右法则: 以直线为优先的前进方向,然后是右边方向、左边方向 5.乱数法则: 取随机值作为前进方向。

6.向心法则: 遇有交叉时,以指向迷宫中心的方向为优先的前进方向。 本人倾向于向心算法+中右法则，即当遇有交叉时,以指向迷宫中心的方向为优先的前进方向。但是当向中心方向的路没有时，利用中右法则。以直线为优先的前进方向,然后是右边方向、左边方向。

8

经典的最优路径算法有：

1、深度优先搜索(DFS)

从入口出发，顺着某一方向向前探索，若能走通，则继续往前走；否则沿原路退回(回溯)，换一个方向再继续探索．直至所有可能的通路都探索到为止。如果恰好某一步探索到出口，则就找到了从入口到出口的路径。为了保证在任何位置上都能沿原路退回，防止死循环，需要使用堆栈来保存大量记录。而要求解迷宫最短路径，则必须用深度优先搜索出所有到达出口的路径，通过比较得到最短距离的路径．这样也必然要求增加数据空间来保存搜索过程中当前最短路径．增加了空间复杂度。

2、广度优先搜索(BFS)

从入口出发，离开入口后依次访问与当前位置邻接的单元格(上下左右方向)，然后分别从这些相邻单元格出发依次访问它们的邻接格，并使“先被访问的单元格的邻接格‘先于’后被访问的单元格的邻接格”被访问，直至访问到迷宫出口，则找到了迷宫问题的最优解，即迷宫最短路径。该算法的显著特点是“层层推进”，探索点会随着探索的深入急剧增加，相应地，需要大量的空间用来保存探索过程的记录。空间复杂度大。但是上述两种算法都比较抽象复杂, 编程时由于牵涉到回溯、递归等较复杂的算法，实现起来容易出现问题,非常容易出错，尤其牵涉到复杂数据结构栈( 深度优先搜索) 、队列( 广度优先搜索) 的操作, 调试跟踪比较麻烦，所以本人不认为是一种很好的方法。

（二）适于实践的算法

在比赛中，采用计时的方法计算成绩，本人认为用以上传统方法选择最优路径，是十分费时的，而且实现起来不是很简便。

实现电脑鼠的快速确定最优路径的算法应该利用向心算法+中右法则来回遍历出一部分的迷宫，再利用等高法求出相对于已遍历出的迷宫状态的最短路径，我们把这条路径称之为最优路径。

首先用上文所说的搜索迷宫算法（向心算法+中右法则），走到终点，然后从以终点为起点，以上一次的起点为终点再次利用向心算法+中右法则的算法走回去。这两次走的路最好满足以前走过的在之后的一次遍历中不再重复，为了实现

9

这样的要求，可以在第一次从起点到终点的遍历中，在走过的迷宫格上加上flag，标志已走过，从此电脑鼠只走没有阻碍和没有标志迷宫格，当没有阻碍迷宫格都是标志过的，那也只能走以前走的路了。就这样利用搜索迷宫算法+迷宫格条件就可以快速遍历一部分迷宫格，并记录迷宫格的状况。

将迷宫格的状态存入MazeShape[16][16]中，然后回到终点利用等高法确定最优路径。等高法介绍：假设迷宫状态如图6所示，其中（##）代表的单元格表示此处有阻碍（这些状态来源是在上一节的MazeShape[16][16]更新中给出）。假设图中A代表起点，B代表终点，按照下图用等高法来确定最优路径：

## ## ## A ## ## ## ## ## ## ## ## ## ## ## B

图6

我们从A点出发，以此为第一个扩展节点，与该扩展节点相邻并且可达的方格成为可行节点被加入到活节点队列中，并将这些方格标志为1，即从起始方格A到这些方格距离为1；接着从活动队列中取出队首节点作为下一个扩展节点，并将与当前扩展节点相邻且为标志过的节点标志位2，并存入活动队列中。这一过程一直继续到算法搜索到目标方格B或活节点队列为空为止。将图6标志如下：

3 2 1 2 ## ## ## 2 1 A 1 2 ## ## ## ## 1 2 3 ## ## ## ## 4 5 6 ## ## ## 6 7 B 8 7 8 8

图7

10

易知到达终点B时，最短距离为9;则可选择出最优路径如图8：

A ## ## ## ## ## ## B ##

图8

## ## ## ## ## ## ## 到此为止，我们就选择出了一条最优路径，电脑鼠就可以按照这条最有路径向终点冲刺了。

代码如下：

void mapStepEdit (int8 cX, int8 cY) {

uint8 n= 0;/* GmcStack[]下标*/ uint8 ucStep = 1;/* 等高值*/

uint8 ucStat = 0;/* 统计可前进的方向数*/ uint8 i,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) {

11

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++;

12

}

/*任意选择一条可前进的方向前进*/

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; } } } }

这种等高图算法也叫洪泛法求最短路径法。

13

其实这个最优路径并不是最短路径，因为不是所有的迷宫信息都被电脑鼠收集到，我们只是在电脑鼠收集到的已有信息中找出最优的路径。我认为这样的做法是可取的，因为电脑鼠如果想得到所有的迷宫格信息，必然要全部遍历迷宫，但是这样做太花时间了，要走很多重复的路，并且电脑鼠遍历运行的时间越长，很难保证它的偏差足够小，就越容易出现不稳定现象。所以我认为在电脑鼠速度足够快的情况下，最短路径和最优路径所花时间没什么区别，但大大节省了遍历的时间和系统算法的复杂度，同时降低了电脑鼠的不稳定性。

制作完等高图，就要用等高图作为最优路径选择的基础，以存储在数组里面

的等高值作为参照，以上面的思想作为依据开始让电脑属自主选择路径。

（三）基于迷宫范围已知时比赛的算法

在网上我曾看见过一个的电脑鼠竞赛获奖的视频，视频里的电脑鼠跑得异常快，并且小车一开始就好像就“认识”路似的，直接就选择了最优的路径，关于小车跑得快，可能是因为电脑鼠硬件过得去，电机驱动和控制，转弯算法调整得好。但是电脑鼠的路径规划给我很大的启发。因为IEEE电脑鼠竞赛是已知比赛迷宫图的，尽管有很多张，我个人认为光就比赛来说，我们可以用如下的方法，把电脑鼠对应每个迷宫的最优路径存进去（对于基于Cortex-M3 内核LM3S615来说，这点开销是完全可以承受的）。

例如2010年天津赛区的IEEE电脑鼠竞赛之前有九张图，我们在此简单的取出两个迷宫来说明：

图9 比赛用的一二号迷宫图

我们可以让电脑鼠先走一段迷宫探测迷宫开始的状态，如图一号迷宫在（0,4）处有出口，而二号迷宫在（0,2）处有出口，我们在比赛中就可以设置这样的算

14

法：小车开始出发如果探测到（0,2）格处有出口，我们立刻执行存在微控制器中的2号路径。否则执行1号路径。

当有很多迷宫图时，基本思想一样，就是先走一段路，当电脑鼠彻底区分现在行走的到底是哪个迷宫时，用switch开关来控制选择的最短路径。

虽然这种算法能很快的是电脑鼠到达终点，取得成绩，但是这样的算法只适用于比赛，却没有什么研究的价值。

四、进入死区的人工智能决策

在比赛参观了一次天津赛区的电脑鼠比赛中，我发现有些代表队电脑鼠在行进中状态不好（路线不再迷宫跑道中间、行进方向有偏差），常常会出现电脑鼠进入一个死区（如图10），首先左边的传感器探测到阻碍，于是电脑鼠右转；但是右转一定角度后右边的传感器也探测到阻碍，于是电脑鼠再左转；左转后右边

的传感器又会探测到阻碍„„此时电脑鼠就会困在墙角里出不来，选手被迫重新返回起点继续开始，这样会十分影响成绩。其实遇到这种情况，我们是有办法让电脑鼠走出死区的。

方法是在程序运行中，记下传感器交替探测到阻碍的次数。并且关键是程序必须记住每一次探测到阻

图10

碍时前一次的探测状态，并和当前的探测状态对比。

如果状态相反，就在交替总数上加1。如果这个交替总数的值大于程序中预先给定的阀值，那么就应该令电脑鼠做一个向后转的‘U’形弯。并且把交替计算器复位。

下面的图11即为死区人工智能决策的流程图，容易知道该决策的代码实现其实也很简单，但是就是难在如何将该进程融合在整个系统中来实现，我们可以用中断前后台来实现，也可以用引入操作系统，用进程之间通信来实现。

15

开始 两个传感器状态相同 交替次数复位 N 两个传感器均为原来状态 Y 交替次数加1 N Y 更新旧状态 N 交替次数>阀值 Y 交替次数复位 U型转弯 图11

While(1) {

if(两个传感器探测状态不相同){ {

{

} }

16

if(两个传感器探测状态均不和原来自己的状态相同)

Count加1；//交替次数加1

更新两个传感器自身old状态为现在状态； if(Count达到阀值)

Count复位为1； 执行‘U’形转弯；

else //存在一个传感器状态不变，证明不存在交替了 } }

本算法只适用于逃离死区，具体电脑鼠执行算法很复杂，编写代码时想要加入这一功能时，可以参考这一算法。使用这一算法，可以实现人工智能决策，使电脑鼠能成功的逃离死区。

if(左右均有阻碍) then 后转； else if(均无阻碍) then 直走；

else if(状态不同，上面判断不是死区时，左边没有阻碍时) then 左转

else //状态不同，上面判断不是死区时，右边没有阻碍时 then 右转

count=1;

五、算法的实现

（一）、无操作系统的前后台实现

其实大多电脑鼠的操作都是基于无操作系统来实现的，简单地说就是软件前后台实现的关系，一个主函数和几个中断来实现电脑鼠的运作，在周立功提供的源代码里面，已经有详细的主函数与定时器中断的关系。

关于主函数：主函数执行先走一步，然后用MazeSearch()函数在摸索中前进，MazeSearch()提供墙壁信息之后电脑鼠继续走。

关于中断服务序：其中的一部分有关于电机驱动程序是这样运行的，首先初始程序设置定时器定时时间，定时时间到，定时器触发中断服务子程序，通过输入驱动步进电机的时序状态、步进电机运动的方向来调节驱动步进电机的时序状态和步进电机运动的方向；所以在这里关键是定时时间的设定，在上面底层算法中已经介绍了电机控制的方法，易知可以查表GuiAccelTable[GmLeft.iSpeed] 来执行TimerLoadSet(..)函数，GuiAccelTable关于表的计算在上面已经详细介绍。同理，传感器驱动也是如此，这里就不再介绍了，按照源码改进，我们是可以实现前后台、无操作系统的电脑鼠正常运行的。

但是这样，我们就是将ARM体系的处理器当成准单片机使用，有些大材小用，

17

只能编出一些简单的电脑鼠软件，因为没有操作系统，当代码的功能加强时，代码的编写难度会变得很大，比如上文我们提到的数字PID模型的决策算法。我们想利用时虽然可以将代码嵌在中断中，但是无疑加大了代码的难度，并且代码执行的实时性不能保证，因为数字PID算法的决策算法当电脑鼠在直行过程中就要立即被调用，不然不能及时的调整电脑鼠的状态，后果会出乎意料，这种多进程的软件实现最好是利用操作系统来辅助实现。

（二）、基于μC/OS-Ⅱ多进程的软件设计

一种好的电脑鼠软件设计非常复杂，若像上文采用传统的前后台模式来管理程序会导致很大的开发难度，且程序不易修改。因此我们考虑在LM3S615 上移植μC/OS-Ⅱ。作为一种嵌入式实时操作系统，μC/OS-Ⅱ提供了很多系统服务，例如信号量、互斥型信号量、事件标志、消息邮箱、消息队列、块大小固定的内存申请与释放及时间管理等，基于RTOS 编程，不仅使系统的实时性、稳定性和可靠性有很高的保障，而且为设计者与CPU 之间建立了桥梁，使设计者考虑的问题会大大的减少，同时也便于修改与维护。在硬件上覆盖一层操作系统，虽然增加了代码的长度，占用了系统更多的时间和空间资源，但是对于基于Cortex-M3 内核的LM3S615来说，这点开销是完全可以承受的。

首先我们把整个系统分为四个进程和四个中断。四个进程的优先级的大小标注如下：总线进程>姿态纠正进程>控制进程>决策进程；以及四个中断的中断服务程序优先级的大小标注如下：红外发射器ISR>传感器ISR>左电机ISR>右电机ISR。

我们可以利用μC/OS-Ⅱ的进程间通信方式来解决程序实时性的控制。可以设两个全局变量Permit1，Permit2，全局变量中的Permit1 和Permit2 的作用是控制是否允许姿态纠正进程进行姿态纠正。具体当Permit1 与Permit2 都等于1 时允许纠正，否则为不允许。当左电机执行非直走任务时Permit1 被赋0，当发现斜左或斜右远距离无墙时Permit2 被赋0。这样就能实现多进程的控制。

因为我们还未在电脑鼠上面移植并实现，并且对μC/OS-Ⅱ没有太深刻的理解，所以在这里只是提出想法，如果有精力，我们会继续往下实现。

六、总结

对于现今的计算机技术，学习嵌入式很重要，从控制意义上来说，嵌入式系

18

统涉及系统中底层的，芯片级的信息处理与控制。在某种意义上，对这些“微观”世界的了解与驾驭正是控制的真正目的。嵌入式系统与通常意义上的控制系统在设计思路和总体架构方面有许多不同之处。在当今信息化社会中，嵌入式系统在人们的日常工作和生活中所占的份额，可能已超过传统意义的控制系统，这就是为什么我们感到学的没有用，而有用的又没有学的原因。

文中首先对于平台进行简单介绍，深刻研究了多种路径遍历和最优路径选择

算法，并对此进行比较，得出最适合比赛的实践中可行的算法。在此基础上解决比赛中电脑鼠所容易出现的进入死区无法出来的情况。

19

参 考 文 献

[1] 秦志强. 《C51单片机应用与c语言程序设计》 [M]. 北京: 电子工业出版社，2009.9， [2] 王晓东. 《计算机算法与分析》[M]. 北京:电子工业出版社,2007.5，201～206页. [3] 徐莺. 基于间接PID的智能车控制算法研究 [J]. 湖北广播电视大学学报, 2008.5:

第5期.

[4] 陈昱. 电脑鼠电路的改进及搜索算法的研究 [J]. 山东:山东师范大学,2010. [5] 周立功.Cortex-M3开发指南 [M]. 广州：致远电子有限公司. [6] 严蔚敏，吴伟明. 《数据结构》. 北京:清华大学出版社, 2007.3.

[7] 邵贝贝（译）.《嵌入式实时操作系统μC/OS-Ⅱ》（第二版）[M]. 北京：北京航空航 天出版社，2003.

[8] 陈理壁. 《步进电机机器应用》[M]. 上海：上海科学技术出版社，19.

[9] V. Yu. Teplov, A. V. Anisimov. Thermostatting System Using a Single-Chip Microcomputer

and Thermoelectric Modules Based on the Peltier Effect[J] ,2002

20