电脑鼠电路的改进及搜索算法的研究

本科毕业设计

设计题目：电脑鼠电路的改进及搜索算法的研究 学生姓名：陈昱 学号：200600930012 专

业：应用物理学

指导教师：杨济民 学 院： 物理与电子科学学院

1 2010年 5月 5日

毕业设计内容介绍

设 计 题 目 选题时间 电脑鼠电路的改进及搜索算法的研究 2009.12.31 完成时间 2010.5.5 设计 字数 11711 关 键 词 数字PID 迷宫算法 红外测距 电机控制 RTOS设计题目的来源、理论和实践意义： 本论文题目来源于电脑鼠走迷宫竞赛，为了使电脑鼠以更快的速度完成比赛，需对其电路和算法进行研究和改进。本论文应用了电子技术，嵌入式系统，自动控制,动力学等领域 的知识，对其算法进行了较深入的研究并提出了一套操作性较强的硬件改进方案。设计的主要内容及创新点： 提出了对Micromouse615电源电路、传感器电路的改进方案。给出了电机控制算法、用于纠正姿态的数字PID算法、传感器驱动算法、连续转弯算法、迷宫信息采集算法以及迷宫搜索与迷宫最短路径算法等算法模块。用基于RTOS的多进程架构实现了上述各算法模块，并用无线模块与上位机进行通讯实现了算法的实时跟踪与可视化。本文主要的创新点是将数字PID算法应用在姿态修正，用基于RTOS的多进程架构实现实现上述算法模块，以及用远 程桌面调试算法。附：设计 本人签名： 年 月 日 目 录

中文摘要 ????????????????????????4 英文摘要 ????????????????????????4 一、 引言 ???????????????????????5 二、 硬件改进 ?????????????????????7 （一）电源电路的改进 ??????????????????7 1、原电路 ????????????????????7 （1）电机驱动芯片供电 ???????????????7

（2）系统供电 ??????????????????7 （3）传感器供电 ?????????????????7

2、改进方案 ???????????????????8 （二）传感器电路的改进 ?????????????????10 1、工作原理 ???????????????????10

2、原电路 ????????????????????10

3、改进方案 ???????????????????11 三、底层算法的研究 ???????????????????12 （一）传感器驱动 ????????????????????12 （二）电机控制 ?????????????????????14 （三）姿态纠正 ?????????????????????17 （四）信息采集 ?????????????????????19 （五）连续转弯 ?????????????????????21 四、迷宫算法的研究 ???????????????????21 （一）传统算法 ?????????????????????21 （二）本文的迷宫算法 ??????????????????22 五、算法的实现与调试 ??????????????????24 （一）基于 uC/OS-II 多进程的软件设计 ??????????24 （二）软件调试 ?????????????????????34 六、总结 ????????????????????????34 七、致谢 ????????????????????????35 参考文献 ????????????????????????35

电脑鼠电路的改进及搜索算法的研究

陈昱

（山东师范大学 物理与电子科学学院 济南）

摘要: 简要介绍了电脑鼠走迷宫竞赛。分析了MicroMouse615中电源系统和红

外发射系统的不足，提出了改进方案，并给出了电路图。给出了电机控制算法、用于姿态纠正的数字PID算法、传感器驱动算法、连续转弯算法、迷宫信息采集算法以及迷宫搜索与最短路径算法等算法模块。用基于RTOS的多进程架构实现了上述各算法模块，并给出了各个算法的流程图。用无线模块与上位机进行通讯实现了算法的实时跟踪与可视化。

关键词: 数字PID 迷宫算法 红外测距 电机控制 RTOS

中图分类号： TP242.6

Micromouse circuit improvements and search algorithm

Chen yu

（Shandong Normal University Colleges of Physics & Electronics , Jinan）

Abstract : Introduced the Micromouse maze competition.Analysised the power system and infrared emission system of MicroMouse615 , proposed a improvement program, and gived the circuit diagram. Motor control algorithm was given, together with the Digital PID algorithm to correct posture, sensor-driven algorithm, continuous turning algorithms, maze of information acquisition algorithm and a maze search algorithm with the shortest path algorithm module.RTOS-based framework for multi-process mechanism was used to achieve the above algorithm module, and the flow chart of each algorithm was given .Real-time tracking and visualization of algorithm were achieved through communicating with the host computer algorithm by wireless module .

Key words: Digital PID; Maze algorithm; Infrared range; Motor Control; RTOS

CLASSNO: TP242.6

一、引言

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

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

图一 电脑鼠 图二 比赛迷宫

为了更好的普及电脑鼠走迷宫竞赛，广州志公远电子设计生产了一款电脑鼠MicroMouse615,它的元件布局图如图三所示。它的原理图如图四所示。

图三 MicroMouse615元件布局图

图四 MicroMouse615原理图

本文以MicroMouse615为原始硬件平台，结合2009年参加济南赛区电脑鼠走迷宫竞赛中的经验教训，提出了一套硬件改进方案，并对底层算法和迷宫算法进行了一番研究，最后给出了算法的具体实现以及软件调试方法。 二、硬件改进

（一）电源电路的改进 1、原电路

MicroMouse615采取外接锂电池供电，并为整个系统提供三种不同的电压，分别用来驱动电机、给传感器供电和给微控制器供电。 （1）电机驱动芯片供电

MicroMouse615装有两个永磁式步进电机，系统中直接把电池的输出电压连接到电机的驱动芯片上。 （2）系统供电

LM3S615微控制器需要3.3V供电，电路如图五所示，外接电源经过C36、C2滤波，然后通过SPX1117M-3.3将电源稳压至3.3V。SPX1117M-3.3是Exar公司生产的LDO芯片，其特点是输出电流大，输出电压精度高，稳定性高。其输入电压范围为4.7V到12V，输出电流可达800mA。在其输出端的C3、C4用来改善瞬态响应和稳定性。

图五 3.3V电源电路 （3）传感器供电

MicroMouse615使用的红外传感器的工作电压为5V，在一般情况下可以把电池的输出电压经过LDO稳到5V。但若电池电压较低或瞬间被拉低时，系统就不能为传感器提供稳定的电源，这将严重影响传感器的灵敏度。所以原电路把系统中已经较为稳定的3.3V电压升到5V。升压芯片采用Exar公司的低静态电流、高效率的升压芯片SP6641A，升压电路如图六所示。

图六 5V升压电路 2、改进方案

整个系统仍由一个7.2V锂电池供电。电脑鼠在行走过程中，由于需要不停的加减速，电机负载会不停的变化，因此电源电压将在很大范围内变化。比如锂电池充足电时的电压为7.8V，放完电后的电压为5.0V，如果负载大时会更低。为了保证供电电压稳定不变，系统采用三端稳压器供电。原系统采用常见的SPX1117芯片把电压稳到3.3V给微控制器供电，再用SP6641A-5V芯片把3.3V升到5V给传感器接收管供电。由于SPX1117的输入输出电压差为1.4V,因此SPX1117允许的最小输入电压为3.3+1.4=4.7V。当某个时刻电机负载较大时电池电压有可能瞬间被拉到很低(尤其是当电池快没电时)，甚至会低于SPX1117的最低工作电压4.7V，所以SPX1117的输出电压可能会不稳定。为了解决这个问题，笔者选择了支持更低压差且微功耗的三端稳压芯片HT1034，其输出电压为3.3V，且输入输出压差低。HT1034的主要参数如表一所示。

表一 HT1034的主要参数

而且将两路供电改成了三路供电，用两片HT1034分别供给微控制器和传感器，如图五所示，这样进一步保证了传感器和微控制器工作电压的稳定，同时也

减小了每一路的电流。

图五 三路供电

注意到原红外接收管的工作电压为4.5V至5.5V，HT1034输出的3.3V电压无法提供其工作。因此选择了一块工作电压为3.3V的红外接收管从而避免了使用升压芯片，使电路更加简单高效。 （二）传感器电路的改进 1、工作原理

MicroMouse615使用一体化红外接收头IRM8601S，它内部集成自动增益控制电路、带通滤波电路、解码电路及输出驱动电路。当连续收到38KHz 的红外线信号时，将产生脉宽10ms 左右的低电平，有效电平维持时间TWL的范围为400μs

手册，其调制信号应为周期1000us的方波。IRM8601S内部的带通滤波器的中心频率为38KHz,所以发射红外线的载波信号为38KHz时经过滤波器衰减最小，传感器最灵敏，越是偏离就衰减的越多，这是一体化接收头抗干扰的关键原理。有效发射信号是指接收头所能识别的信号，改变有效发射信号的方法有两种： 1. 改变输出信号的能量，改变输出信号的能量又有两种方法： （1）改变输出信号的幅度 （2）改变输出信号的占空比

2. 改变输出信号的频率，由于一体化接收头是 38KHz 的带通滤波器，所以发射信号

的频率偏离38KHz 越多，能检测到的有效信号就越少。这样也就可以改变有效发射信号的强度。 2、原电路

原电路的红外发射电路如图六所示。通过W4调节红外线发光管的发光强度。

图六 发射电路 图七 接收电路

接收电路如图七所示。U4 为一体式红外线接收传感器IRM8601S，，它内部集成自动增益控制电路、带通滤波电路、解码电路及输出驱动电路。但由于它是

开漏输出，所以输出端需接一个上拉电阻，见图七中的R10。其中R4 是限流电阻。

由图六可知，每个发射二极管接一个电位器后直接接到微控制器的PWM引脚上，在实际调试中发现这个电路虽然简单易行但存在三个问题。第一，由于二级管工作曲线的非线性，实际调节时不能充分利用电位器的调节作用，大大增加了调节的难度和精度。第二，由于五个发射模块彼此独立，故需要调节五次，调节次数多，容易照成调节的不对称。第三，不能通过程序来控制发射电流的大小。

3、改进方案

改进后的电路如图六所示，三级管的作用是作为一个电流源来驱动红外发射二级管。运放LM324作为一个电压跟随器，跟随PWM的输出。通过合理调配各电阻的阻值，使三级管工作在线性区。其中电容C1、C2的作用是滤出电源高频干扰。当调节电位器时相应的改变PWM的占空比从而实现对发射电流大小的控制。

图六 改进后的红外发射电路

三、底层算法的研究

（一）传感器驱动

电脑鼠在迷宫中行进时要随时侦测路面情况。它的左右传感器不但要检测是否存在支路（没有挡板就是一条支路）还要避免和挡板碰触。因此电脑鼠每一侧就需要完成两组参数的检测，一组检测稍微远一点的距离是否有墙，判断是否存在支路，另一组检测稍微近一点的距离，判断是否即将碰触挡板。如果只用一组传感器来完成两组参数的检测的话，若使用非调制的普通红外接收头，可以根据接收到的信号的强弱来计算距离，可是非调制的抗干扰差，但是如果使用调制的一体化接收头，检测信号输出的是数字信号，这样通过检测传感器输出信号的强弱来计算距离的方法肯定行不通。解决的方法是把上面测距的原理反过来，可以通过改变有效发射信号强度，当接收头刚好能接收到信号时，记录下此时发射的强度，这样也就可以大致测算出距离。本文让五个发射头轮流发射38KHz及35KHz

的调制信号，由上文可知这可以改变有效发射信号的强度，从而能够粗略判断障碍物的远近距离，完成两组参数的检测，于是可以指示出没有障碍物、检测到障碍物和障碍物靠的太近三种状态。

然而，如果五个发射管同时发射红外信号，由于漫反射的作用，信号之间可能发生相互干扰，如图七所示。左前发射头发射的信号错误的被前接收头收到了。

解决这一问题的方法是分组分时发射。所谓分组分时发射是指左、前、右三个传感器为一组同时发射，左前、右前两个传感器为一组同时发射，这样做的目的是使组内各个传感器的发射头彼此垂直，避免相互间的干扰。所谓分时发射是指当第一组发射时，

第二组接收，而当第一组接收时第二组发射。如图八所示，其中PWM1连接斜左、斜右两个传感器，PWM2连接左、前、右三个传感器。

图七 漫反射示意图

图八 分时分组发射示意图

PWM2轮流以38KHz和35KHz驱动第一组发射头（左、前、右），检测左、前和右的远距离和近距离。PWM2发射时PWM1停止发射。而当PWM2停止发射时，PWM1以35KHz或38KHz检测第二组发射头（左前和右前）。这样做的目的是使两组传感器可并行的工作，缩短一倍的采样周期。

红外线在空气中传播和反射受外界的干扰，如果测量距离刚好处在能够检测到信号的临界状态，保持距离不变，传感器输出信号也可能不确定。这样就需要在合适的时机读取接收头输出端的状态。图九为IRM8601S信号处于临界状态时用逻辑分析仪抓到的波形图，Pulse 为38KHz 的输出信号，Send 高电平有效，有效时发送红外线脉冲，OUT 为一体化接收头输出端。由图可知当刚刚结束上次发射时读接收头输出端的状态，此时正处于OUT 有效信号的中间，读能保证正确检测到信号。

图九 传感器检测波形图

综上所述，传感器驱动的流程图如图十所示。

图十 传感器流程图

（二）电机控制

为了减少轮胎的打滑，降低车身的晃动，防止电机的震荡与失步，一种有效地解决方案是对电机进行匀加减速的控制，本系统使用的是步进电机。步进电机不能像直流电机那样自动加减速，它的的加减速需要通过设定节拍的频率来实现。假设每步的平均速度等于中心时间的速度。

Tn?Cnf,Vn?fCn

f??Vn?1?VnTn?12?Tn2?Cn?1Cn?12f??fCnCn2f?2f(Cn?Cn?1)CnCn?1(Cn?1?Cn)2①

电机

ttn为：

n??v(t)dt?0??tdt?0?2t2

转过n步所花的时间tn为:tn?2n?

Cn为：第n步的定时器

Cn?f(tn?1?tn)?f(2(n?1)??2n?)

得C0?f2?②

由①②得

Cn?C0(n?1?n)

但上式需要开平方，不适合没有浮点运算功能的LM3S615处理器，因此还需进一步变换

1??1n?1③1nCnCn?1?C0(n?1?C0(n?n)n?1)1?1?

由泰勒公式

1?1n?1?12n?18n2?o[1n3]...

代入③式可近似得到

CnCn?1(1??12n?118n?)?1218n21?2n12n??18n18n2?24n?14n?1?1?24n?1④1?(1?2n)

Cn?Cn?1?2Cn?14n?1

将n换成i ，得：

Ci?Ci?1?2Ci?14i?1⑤

减速过程是加速过程的逆过程，如果减速过程中要跑m步，同理可得

Ci?Ci?1?2Ci?1(4m?1)?4i⑥

时产生的误差如表二所示。用④式代替③式计算CnCn-1

由表中数据可以看出除C1/C2外其他比值误差都很小，故可单独令C1=0.4142C0，而C2，C3，C4??Cn可由公式⑤或⑥计算出。

n 1 2 3 4 5 10 100 1000 精确的Cn/Cn-1 0.4142 0.7673 0.8430 0.8810 0.9041 0.9511 0.9950 0.9995 近似的Cn/Cn1 0.6000 0.7778 0.8462 0.8824 0.9048 0.9512 0.9950 0.9955 近似值误差 0.4485 0.0136 0.00370 0.00152 7.66×10 9.42×10 9.38×10-8 9.37×10-11 -5-4 表二 近似误差

实际使用公式求每步定时器初值时，可以把事先计算好的加速和减速表存储在微控制器的ROM中，需要时直接查表即可。例如下面这个数组，存储了加速度为1200步/s的加速度表。

const unsigned int AccelTable1200[120] = {

2041241,845482,657598,556430,490968,444210,408674,380490,357430,338110,321617,307323,294780,283657,273705,264732,256587,249150,242324,236030,230203,224787,219736,215011,210578,206409,202478,198763,195246,191909,188737,185718,182839,180090,177461,174944,172531,170216,167991,165851,163791,161806,159892,158044,156259,154533,152863,151246,149679,148160,146686,145255,143865,142515,141202,139925,138682,137471,136291,135141,134020,132926,131859,130817,129799,128805,127833,126883,125954,125045,124155,123284,122431,121596,120778,119976,119190,118419,117663,116921,116193,115478,114777,114088,113411,112746,112093,111451,110820,110200,109590,108990,108400,107819,107248,106686,106132,105587,105050,104521,104000,103487,102981,102483,101992,101508,101031,100560,100096,99638,99187,98742,98303,97869,97441,97019,96602,96191,95785,95384};

2

（三）姿态纠正

由于左右轮摩擦以及初始位置方向不正，要使电脑鼠在直线的迷宫中正常运行，需要电脑鼠在前进的过程中不断调整姿势，以免碰到挡板。电脑鼠在迷宫中理想的姿势是处于迷宫格的中央，且前进方向平行于挡板，如图七所示。图中箭头为左前右前传感器能够检测到的大致距离。

图七 正确姿势 图八 偏左 图九 偏右

图十 斜左 图十一 斜右

在实践中发现电脑鼠在迷宫格中姿态不需要时时刻刻调整，只需当两侧都有挡板时对电脑鼠姿态进行纠正，这样可以使算法更加简洁高效。当且仅当电脑鼠处在如图八、九、十、十一所示位置时才需要执行纠正。仔细观察这四种姿势可发现一个共同点，即当发现左边信号强于右边时应向右转，当发现右边信号强于左边时应向左转。姿态纠正算法的核心是当发现需要对姿态进行纠正时，如何合理控制其左转右转的快慢。理想的姿态修正算法应该使电脑鼠不仅可以很快的回到中心线上而且在中心线附近的震荡越小越好。为了同时满足以上两个要求，策略是采用数字PID算法，比例控制具有快速对现状进行纠正的特性，是系统纠正更加灵敏快速，积分控制具有利用历史状态进行修正的特性，可以提高系统的稳态性能，微分控制具有利用系统未来状态进行修正的特性，可以改善系统的动态性能。数字PID控制的结构图如图十二所示。

图十二 数字PID控制结构图 由图可知：

u?kp(e?1Ti?edt?Td?kp(1?dedt1Tis)D(s)?U(s)E(s)?Tds)

将模拟量转换为数字量：

t?kTe(t)?e(kT)?e(k)

kk?e(t)dt??e(jT)Tj?0?T?e(j)j?0

de(t)dt?e(kT)?e[(k?1)T]T?e(k)?e(k?1)T

则：

u(k)?Kp{e(k)?TTik?j?0e(j)?TdT[e(k)?e(k?1)]}

TdT[e(k?1)?e(k?2)]}u(k?1)?Kp{e(k?1)?TTik?1?j?0e(j)?

?u(k)?KP{e(k)?e(k?1)?TTie(k)?TdT[e(k)?2e(k?1)?e(k?2)]}

?KP[e(k)?e(k?1)]?KIe(k)?KD[e(k)?2e(k?1)?e(k?2)]TTi其中KI?KPKD?KPTdT

令u(k)?u(k?1)??u(k)实际的控制系统中，存在着饱和特性。当控制变量达到一定值后，系统的输出变量不再增长，系统进入饱和区。这就要求系统的控制变量必须限制在某个范围之内，即

采用积分分离法：

?u(k)?KP[e(k)?e(k?1)]?aKIe(k)?KD[e(k)?2e(k?1)?e(k?2)]

当e(k)?emax时,a?1;当e(k)?emax时，a?0.

有关比例系数Kp，积分系数Ti，微分系数Td的调节可参照以下口诀： 参数整定找最佳，从小到大顺序查 先是比例后积分，最后再把微分加 曲线震荡很频繁，比例增益要减小 曲线漂浮绕大弯，比例增益要增大 曲线偏离回复慢，积分时间往下降 曲线波动周期长，积分时间再加长 曲线震荡频率快，先把微分降下来 动差大来波动慢，微分时间应加长

当确定了全部参数后，可定义一个数字PID函数，如下:

unsigned int PID(unsigned int e1,unsigned int e2,unsigned int e3){

return P*(e3-e2)+I*e3+D*(e3-2*e2-e1); }

其中P=KP I=KI D=KD

该函数在下文介绍姿态纠正进程时会被用到。姿态纠正算法的实现可参照30页图十五。

（四）信息采集算法

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

触发事件j件 参数 左转执行完 右转执行完 后转执行完 W E S E W N S N E N S W N S W E 表三 CurDir刷新逻辑

触发事件 参数 直行（N/2+Nc）+nN步 准备直行左转 准备直行右转 刚执行完左转 刚执行完右转 刚执行完后转 触发事件 参数

N，（X,Y） S,（X,Y） W,（X,Y） E,（X,Y） (X,Y+1) (X,Y-1) (X-1,Y) (X+1,Y) 表四 CurPosition刷新逻辑

N,(X,Y) CurEye S,(X,Y) CurEye W,(X,Y) CurEye E,(X,Y) CurEye CurPosition赋新值 CurEye直接赋CurEye顺时针旋CurEye顺时针CurEye逆时针给转180°赋给旋转90°赋给旋转90°赋给Cellshape[X][Y] Cellshape[X][Y] Cellshape[X][YCellshape[X][Y]

] 表五 Cellshape刷新逻辑

注：式中Nc表示当MicroMouse处在迷宫格中心位置时，其左右传感器发射头离该迷宫格前沿的距离所对应的步数，N表示迷宫格的边长所对应的步数，n取0,1,2,3...迷宫格的坐标系如图十三所示。 (0,3) (1,3) (2,3) (3,3) （0,2（1,2(2,2) (3,3) ） ） （0,1（1,1（2,1（3,1） ） ） ） （0,0（1,0（2,0（3,0） ） ） ） 图十 迷宫坐标系

由上述三个刷新逻辑表可知：Cellshape需要CurPosition作为触发事件，而CurPosition需要CurDir作为输入参数。因此当需要同时刷新三个变量的两个或三个时，应先刷新CurDir 再刷新CurPosition最后刷新Cellshape。

（五）连续转弯

转弯共有两种方式：一种是在前进中转弯，即一个电机快转，一个电机慢转。另外一种方式是在原地转弯，即车体先停在转弯口，然后一个轮正转，另一个轮反转。前进中转弯节约时间，效率高，原地转弯控制较为简单。由于原地转弯需要减速停下来，转完后再加速，非常浪费时间，严重影响比赛成绩，故选取连续转弯方法。R1表示内侧轮胎划出的轨道半径，R2表示外侧轮胎划出的轨道半径。当需要转弯时，外侧轮保持当前速度不变，而内测轮的速度降至外侧轮的K=R1/R2 倍，电脑鼠便开始转弯，直到走过一定步数或内侧传感器检测到有墙时，此次转弯便结束。由于摩擦和惯性，实际的K值可能不等于R1/R2,需要在实验中反复调试才能获得。连续转弯算法的实现可参照32页图十七。

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

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

常见的迷宫搜索算法有：

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

6.向心法则: 遇有交叉时,以指向迷宫中心的方向为优先的前进方向。 实际应用时应采用上述搜索法则混合的搜索策略。因为当电脑鼠在迷宫中遇到“孤岛”时，如果采取的是单一搜索法则，则电脑鼠很容易陷入死循环。 经典的最优路径算法有：

1.深度优先搜索(DFS)：从入口出发，顺着某一方向向前探索，若能走通，则继续往前走；否则沿原路退回(回溯)，换一个方向再继续探索．直至所有可能的通路都探索到为止。如果恰好某一步探索到出口，则就找到了从入口到出口的路径。为了保证在任何位置上都能沿原路退回，防止死循环，需要使用堆栈来保存大量记录。而要求解迷宫最短路径，则必须用深度优先搜索出所有到达出口的路径，

通过比较得到最短距离的路径．这样也必然要求增加数据空间来保存搜索过程中当前最短路径．增加了空间复杂度。

2.广度优先搜索(BFS)：从入口出发，离开入口后依次访问与当前位置邻接的单元格(上下左右方向)，然后分别从这些相邻单元格出发依次访问它们的邻接格，并使“先被访问的单元格的邻接格‘先于’后被访问的单元格的邻接格”被访问，直至访问到迷宫出口，则找到了迷宫问题的最优解，即迷宫最短路径。该算法的显著特点是“层层推进”，探索点会随着探索的深入急剧增加，相应地，需要大量的空间用来保存探索过程的记录。空间复杂度大。

但是上述两种算法都比较抽象复杂, 编程时由于牵涉到回溯、递归等较复杂 的算法，实现起来容易出现问题,非常容易出错，尤其牵涉到复杂数据结构栈( 深度优先搜索) 、队列( 广度优先搜索) 的操作, 调试跟踪比较麻烦。 （二）本文的迷宫算法

本文算法思想：想象你站在一个迷宫里，迷宫格之间的隔板由不透水的材料制成。你手中有一个带开关的水管。当你想找出通往迷宫出口的最短路径时，你可以打开水管开关，此时水便从你所在的迷宫格向四周漫出，第一支到达出口的水流所代表的路径便是你想找的最短路径。

算法改进：上述算法成立的前提条件是你已经掌握了迷宫格的墙壁资料。当你站在入口处还没进行迷宫格搜索时迷宫情况是未知的，因而不能直接用上述算法得到最短路径，但是如果将该算法用在已经探索过的迷宫格上，并且每当探索到一个新的迷宫格就用该算法刷新一下地图，同样可以找到最短路径。 以16*16迷宫为例，用数组CellOrder[16][16]存储迷宫格序号，迷宫格序号表示从入口到此迷宫格的距离。用数组Cellshape[16][16]存储迷宫格墙壁信息。函数LowestNeighbouringcelll(x,y)返回与（x,y）相邻的赋过值的且没

有隔板隔开的迷宫格序号最大的迷宫格的序号，若周围迷宫格未被赋值则返回-1。每次刷新地图前除了入口处迷宫格序号赋0外，其余迷宫格均赋-1。每次刷新按照从（0,0）开始从下到上从左到右的顺序遍历每一个迷宫格，若该迷宫格未被赋值且周围有已赋值的迷宫格则将函数LowestNeighbouringcelll(x,y)的返回值加1后赋予它。如果未能给出口迷宫格赋值则再次重复上述顺序遍历一遍直至给出口迷宫格赋值后才结束本次刷新。具体代码如下：

while(1){ for(x=0;x<=15;x++){

for(y=0;y<=15;y++){ //按从下向上从左到右的顺序遍历迷宫格 if(CellOrder[x][y]!=-1) //若该格已被赋值则跳过不予处理

continue;

if(LowestNeighbouringCell(x,y)!=-1) CellOrder[x][y]==LowestNeighbouringCell(x,y)+1;

//若相邻最小序号格存在，则将此序号加1后赋给该格

}

} } if(CellOrder[dist_x][dist_y]!=-1) //若出口迷宫格已被赋值，结束此处刷新，否则再遍历一次 }

break;

当刷新完序号图后，从出口迷宫格为起点沿序号值递减的顺序绘出一条路径，老鼠每按此路径行走一步，刷新序号图一次。

本算法将迷宫搜索算法和迷宫最优路径算法合二为一，且只用到数组这个简单形象的数据结构, 算法简单, 相应的编程代码短小高效, 在迷宫规模较小时, 完全可以进行人工纸上模拟运行，不足之处的是此算法找出的是最短路径但不一定是最优路径，因为本算法没有考虑弯道因素，但是在转弯速度快的情况下（例如采取连续转弯）最短路径近与最优路径效果差距不大。

五、算法的实现与调试

（一）基于 uC/OS-II 多进程的软件设计

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

整个系统分为四个进程（>比较的是优先级的大小）：总线进程 >姿态纠正进程>控制进程>决策进程，以及四个中断（>比较的是中断优先级的大小）：无线ISR>传感器ISR>左电机ISR>右电机ISR。系统的总体关联图如图十一所示。

图十一 系统的总体关联图

全局变量中的Permit1和Permit2的作用是控制是否允许姿态纠正进程进行姿态纠正。具体当Permit1与Permit2都等于1时允许纠正，否则为不允许。当左电机执行非直走任务时Permit1被赋0，当发现斜左或斜右远距离无墙时Permit2被赋0。

图中消息队列的作用是接收各进程发来的报文，报文的格式如图十二所示。 目的进程 源进程 控制\\数据 报文内容 图十二 报文格式

报文中“控制/数据”部分表达了该条消息是作为控制信息还是作为数据信息。

从系统的总体关联图可以看出每个进程配有一个控制邮箱和一个数据邮箱，控制邮箱接收总线进程发来的控制信息，数据邮箱接收总线进程发来的数据信息。 总线进程负责接收消息邮箱中的报文，根据报头中的信息，将报文分发到正确的邮箱中。

传感器中断负责驱动五对传感器工作，并刷新全局变量CurEye. 无线进程负责驱动无线收发模块发送与接收报文。

决策进程负责从宏观上完成搜索迷宫、返回起点、冲刺三个任务。28页图十三为决策进程流程图。红色箭头表示信号流，蓝色箭头表示控制流。平行四边形表示全局变量，云朵表示其它进程。

控制进程负责利用全局变量CellShape,CurDir,CurPosition得到下一步的操作（直走，左转，右转，后转），并将该操作交给左、右电机中断完成。29页图十四为控制进程流程图。

姿态纠正进程负责根据左、右传感器信号的差值由PID函数给出纠正量，具体PID函数的实现前文已有介绍。30页图十五为姿态纠正流程图。

左电机中断与右电机中断共同负责根据控制进程下达的操作（直走，左转，右转，后转）控制步进电机转动。左电机机中断还负责刷新电脑鼠的状态和迷宫格形状等全局变量。

图十六为直走任务左电机流程图。

直走任务右电机流程图与直走任务左电机流程图类似，CurDir,CurPosition,CellShaped的刷新。

图十七为右转任务左电机流程图。 图十八为右转任务右电机流程图。 图十九为后转任务左电机流程图。

后转任务右电机流程图与后转任务左电机流程图类似，CurDir,CurPosition,CellShaped的刷新。

只是少了对只是少了对

图十三 决策进程流程图

图十四 控制进程流程图。

图十五 姿态纠正进程流程图

本文来源：https://www.bwwdw.com/article/t6t7.html