智能鼠原理与制作（高级篇）（中英双语版）课件 第二篇 综合篇

项目一学习智能鼠车速控制算法1学习目标（1）学习智能鼠电动机的PID控制算法。智能鼠在迷宫中运行时涉及多种情况的速度控制，如启动和停止时加速度要适中，平稳运行时要保持速度稳定，转弯时也需要对两台电动机的速度做出干预，PID控制算法可以帮助我们轻松实现这些要求。2任务一掌握智能鼠PID车速控制算法任务二掌握智能鼠直流电动机闭环车速控制3任务一掌握智能鼠PID车速控制算法一、经典PID控制思想经典PID控制思想是一门历史悠久的控制理论，时至科技发达的现在，经典PID控制理论凭着其适应性强、鲁棒性高和原理简单的优势，已经成为工业自动化、汽车控制、航天应用中使用率最高的控制算法，同时也被广泛的使用在其他各行各业中。下面将结合电动机的控制对经典PID控制思想进行分析。机器人的电动机驱动是一个控制系统，为了使电动机能够有效、可控的被驱动，电动机的驱动控制应当是一个闭环回路系统，这也意味着驱动控制必须根据一些反馈信息进行调节。图右所示是一个经典的电动机PID控制示意图。将给定速度与实际转速进行比较，其差值E，经过PID控制器调整后输出电压控制信号PWM，驱动直流电动机改变其转速。根据不同的闭环回路，电动机控制系统都会有一个目标设定值s(t)，反馈则需要通过该设定值对真实的调控结果f(t)进行判断，从而得到一个差值e(t)=s(t)-f(t)，PID控制系统就是根据该差值e(t)对电动机进行闭环控制的。在一个连续系统中，系统的输出控制量k(t)可以表示为4任务一掌握智能鼠PID车速控制算法1.比例环节比例环节的控制输出量可被认为是与差值成比例关系。在差值较大的情况下，比例环节具有非常重要的作用，它能大幅度调节系统的输出，从而迅速降低反馈值与设定值之间的差距。当差值变小时，它又可以减少系统的输出，从而不会出现过大的控制超调现象。在无损耗系统中，通过合理的设定比例调节，控制系统是可以达到设定值的，然而在实际的系统中，由于系统存在不断变化的损耗，因此，控制系统在某些状态下，的调节输出仅仅只能够用来抵消这些损耗而无法继续缩小差（比如电动机转速差值较小时，电控的调节输出可能只够用来抵消电动机的摩擦损耗）。即便如此，在控制系统调节的初始阶段，比例调节的作用还是非常明显和重要的。2.积分环节积分环节可被认为是差值对于时间的积分。根据上述得知，当比例调节的输出量被系统的损耗“完全消耗”时，系统输出的与设置值已经非常接近，此时，积分环节将起到推动控制系统继续调节的作用，和调节输出量之和最终会平衡掉系统中的所有损耗，因此积分调节又称为无差调节。注意到，积分环节并不是完全独立于比例环节的。一方面，当积分环节协助系统不断接近设置值时，比例环节的调节输出也因此变得越来越小，另一方面，积分环节非常依赖于其他两个环节的参数设置。3.微分环节微分环节仅仅是在差值出现较大突变时才发生作用，但它极大的拟制了其他两个环节的效果，因此微分环节又称为抑制环节。当差值在变小时，微分环节的调节输出是负的。实际上，在电动机启动过程中，微分环节的作用是非常负面的，因为它会引起电动机在低速下的强烈反应。在具体的控制当中，如果PI调节能达到系统要求，就可以不使用微分环节。即使使用了微分控制环节，也最好对被控量信号进行去噪处理，防止噪声干扰被放大。微分环节的一个重要作用是克服系统的大惯性效应。由上可知，PID是一种线性控制理论，在对电动机的实际控制过程中，需要根据具体的情况对PID的系数进行设定，从而使系统达到控制稳定与动态性能良好之间的平衡状态。5任务一掌握智能鼠PID车速控制算法二、增量式PID控制算法所谓增量式PID是指数字控制器的输出只是控制量的增量。当执行机构需要的控制量是增量，而不是位置量的绝对数值时，可以使用增量式PID控制算法进行控制。增量式PID控制算法可以通过式（2-1-1）推导。由式（2-1-1）可以得到控制器的第k-1个采样时刻的输出值为：（2-1-2）（2-1-3）将式（2-1-2）与式（2-1-3）相减并整理，就可以得到增量式PID控制算法如下:（2-1-4）其中,（2-1-5）由式（2-1-5）可以看出，如果微控制器控制系统采用恒定的采样周期T，一旦确定A、B、C，只要使用前后三次测量的偏差值，就可以由式（2-1-5）求出控制量。6任务一掌握智能鼠PID车速控制算法1.比例-积分作用1）比例(Kp)部分比例部分的数学表达式是e(t)。在PID控制器中，比例环节的作用是对偏差瞬间作出反应。偏差一旦产生，PID控制器立即产生控制作用，使控制量向减小偏差的方向变化。控制作用的强弱取决于比例系数，比例系数越大，控制作用越强，则过渡过程越快，控制过程的静态偏差也就越小。但是，越大，也越容易产生振荡，破坏系统的稳定性。故比例系数Kp选择必须恰当，才能达到过渡时间端、静差小而又稳定的效果。（2）积分（Ki）部分积分部分的数学表达式是

，其中。从积分部分的数学表达式可知，只要存在偏差，则它的控制作用就不断的增加；只有在时，积分才能是一个常数，控制作用才是一个不会增加的常数。可见，积分部分可以消除系统的偏差。积分环节的调节作用虽然可以消除静态误差，但也会降低系统的响应速度，增加系统的超调量。积分常数越大，积分的积累作用越弱，这时系统在过渡时不会产生振荡，但是增大积分常数会减慢静态误差的消除过程，消除偏差所需的时间也较长，但可以减少超调量，提高系统的稳定性。当较小时，积分的积累作用较强，这时系统过渡时有可能产生振荡，不过消除偏差所需的时间较短。所以，必须根据实际控制的具体要求确定Ti。7任务一掌握智能鼠PID车速控制算法2.控制器参数的整定控制器参数整定是指决定调节器的比例系数、积分系数的具体数值。整定的实质是通过改变调节器的参数，使其稳定特性和过程特性相匹配，以改善系统的动态和静态指标，取得最佳的控制效果。整定步骤如下：（1）先调整积分系数为0，接着调整比例系数，直到速度反馈信号产生振荡。（2）调整积分系数，直到消除稳态误差。（3）输出结果如果不理想，重复步骤（1）、（2），加大比例系数，让振荡现象更明显，直到输出理想结果为止。8任务二掌握智能鼠直流电动机闭环车速控制一、智能鼠直流电动机闭环控制系统框图智能鼠直流电动机闭环控制系统框图，如下图所示。leftSpeed=xSpeed–wSpeed；rightSpeed=xSpeed+wSpeed；xSpeed=（rightSpeed+leftSpeed）/2;wSpeed=（rightSpeed-leftSpeed）/2;整个速度控制系统由两个PI闭环组成。第一个PI闭环：设定值为给定的直行速度（xSpeed），用左轮速度和右轮速度之和再除以2[即（R+L）/2]作为反馈量，得到偏差xError[xError=xSpeed-（R+L）/2]，再把偏差xError送到PI控制器进行运算得到输出U1。第二个PI闭环：设定值为给定的旋转速度（wSpeed）和位置校正输入之和，用右轮速度减去左轮速度再除以2[即（R-L）/2]作为反馈量，得到偏差wError[wError=wSpeed-（R-L）/2]，再把偏差wError送到PI控制器进行运算得到输出U2。把U1减去U2的值作为左电动机的驱动信号（其实就是控制电动机的PWM占空比），把U1加上U2的值作为右电动机的驱动信号，这样就能通过分别控制两个电动机的转速从而控制智能鼠的运行状态。9任务二掌握智能鼠直流电动机闭环车速控制二、闭环控制程序流程图10

思考与总结（1）在增量式PID控制中，P、I和D各有什么功能？（2）智能鼠在不同的状态下，要使用不同的速度，这就需要PID调速来实现。过大、过小都会造成车姿的摇晃和卡顿，所以合适的PID参数是智能鼠稳定运行的良好保证。11本项目到此结束THANKYOU12

项目二学习智能鼠基本运动控制13学习目标（1）学习智能鼠的基本运动控制。（2）掌握多种智能鼠转弯算法。智能鼠在迷宫中的行走，可以简化为直行和转弯两部分。直行是指智能鼠在迷宫中通过检测两侧挡板，校正车姿，避免碰触，转弯是指智能鼠精确地转弯180°和90°，配合直行最终到达目的地。14任务一学习智能鼠基本运动的实现15任务一学习智能鼠基本运动的实现基本运动是指智能鼠在迷宫中进行搜索和冲刺时需要执行的运动，主要包括智能鼠的直线行进、制动回转以及连续转弯等。智能鼠直线行进是所有动作的基础。在迷宫中，智能鼠不仅需要依靠编码反馈进行直线前进，同时也需要红外反馈对自身姿态进行调整。这里主要介绍制动回转以及连续转弯。一、制动回转制动是智能鼠在迷宫中运动的一个必要动作，当智能鼠进入到迷宫死路的时候，需要进行及时的制动回转从而退出该路段，此外，制动对调整智能鼠的姿态误差是也能起到一定的作用。制动回转的实现：当前方发现挡板且左右方向均没有可行进的之路时，智能鼠需要制动回转返回上一个节点继续搜索。为了减小行进方向的纵向误差，智能鼠需要向前减速行进约4cm再进行制动。制动后进行原地回转操作，原地回转过程中，需要使用编码器进行控制，即：二、提高制动性能在制动回转动作中，紧急制动是一种非常容易实现的方法，即瞬间将轮胎刹住并锁住轮胎，但在调试过程中，紧急制动也暴露出一些问题；（1）对高速行进中的智能鼠进行紧急制动，是车身制动加速过大，轮胎和迷宫底板之间极有可能出打滑现象，严重的情况下，智能鼠可能被强大的惯性甩离地面。（2）对低速行进的智能鼠进行紧急制动，虽然出现打滑现象的概率不大，但是由于左、右轮制动加速度不同，会在制动停止后出现姿态错误。为了改善刹车性能，一方面对制动情况进行提前预测，对搜索阶段有可能制动的情况进行提前减速，另一方面，采用了一种类似汽车ABS（防抱死制动）点制动的制动方式，即制动过程中进行若干次制动力的快速释放，释放的瞬间，轮胎并没有被锁住，此时有效降低了轮胎和地面的静摩擦力。实践结果表明，这种类汽车ABS的制动方式不仅有效的解决了车轮打滑的问题，而且制动效果良好。16任务一学习智能鼠基本运动的实现三、连续转弯目前大多数智能鼠系统都是采用了原地转弯。原地转弯可靠度高，编程容易，但是极大的降低了智能鼠的行进速度。针对以上情况，下面介绍连续转弯的实现。1.90°弧形转弯曲线与直行的要求不同，转弯过程需要智能鼠左、右轮的速度保持一定的比例，90°弧形转弯曲线如图2-2-1所示，图中OA为弧形转弯起始处，OB为弧形转弯的终点。根据编码器闭环反馈控制的算法，当智能鼠在进行直线行进的时候，在任意时刻左、右轮的行进距离应该满足以下不等式：式中，S△应当取一个较小的合理的正数。因此，在对弧形转弯进行编码反馈控制的时候，编码反馈控制的被控量应该满足以下不等式：17任务一学习智能鼠基本运动的实现2.连接转弯的动作分解上述的圆弧转弯曲线是理想状态下的，在具体的实践中是无法做到的，原因在于当智能鼠从OA进入弧形转弯时，左、右轮速比n无法从直线行驶的n=1突变到n=r2/r1，同样，在智能鼠从OB退出弧形转弯时，也同样面临一样的问题。在具体的转弯过程中，将转弯动作分解成三部分进行，即：S1:n=1→n=r2：r1差速阶段；S2:n=r2：r1维持阶段；S3:n=r2：r1→n=1同步阶段。S1：假设智能鼠在t=0时刻进入转弯运动时，左、右轮的速度为vc(0)=v2(0)=v1(0)，在进入圆弧运动的差速阶段时，左、右轮之间的速度差逐渐拉大，直到左、右轮速比为n，有：式中，a2、a1分别为左、右轮在差速阶段的加速度，t1为差速阶段的结束时间。S2：在维持阶段下（t1＜t≤t2)，左、右轮的速度比n不变，有：S3：进入圆弧运动的同步阶段后，左、右轮之间的速度差在逐步减小，最后恢复到左、右轮同速状态，有：18任务一学习智能鼠基本运动的实现3.连续转弯的控制方法根据上述理论，将连续转弯的实现也分成了三个阶段进行，实验证明，这种方法在中、低速下都具有非常好的效果。实际调试过程中需要注意的是：（1）在上面运动方程组中，加速度a1、a2，a1t

、a2t的绝对值应当控制在一定范围之内，如果拥速度过大，则容易出现打滑现象。（2）连续转弯的难点在于转弯结束时，左、右轮的行进路程差|△S|和左、右轮速差|△v|之间的矛盾，即:在具体的转向控制上有两种方法：一种是对左、右轮的速度比n进行控制，另一种是对左、右轮的行进路程|△S|进行控制。在实际运行中，选用第一种方法则容易在转弯结束时出现转弯不到位或者转过头的情况，选用第二种方法则容易出现左、右轮速度没有达到同步就结束了转弯动作。为了解决路程和速度上的矛盾，从两个方面进行完善：一是通过调试对不同速度下的转向参数进行标定，二是在转弯结束后使用红外反馈对误差进行修正。而在高速转弯中，为了防止过大的误差出现，可以使用陀螺仪进行辅助。19任务一学习智能鼠基本运动的实现4.连续转弯的流程图及参考代码核心函数1：mazeSearch/******************************************************************************Functionname:mazeSearch**Descriptions:转弯前脉冲***************************************************************************/voidmazeSearch(void){

……if((__GucMouseState==__TURNRIGHT)||(__GucMouseState==__TURNLEFT)){__GmLeft.uiPulseCtr=8000;__GmRight.uiPulseCtr=8000;

……}核心函数2：mouseTurnright/**************************************************************************Functionname:mouseTurnright**Descriptions:右转函数**************************************************************************/voidmouseTurnright(void){while((__GmRight.uiPulseCtr+200)<=__GmRight.uiPulse);while((__GmLeft.uiPulseCtr+200)<=__GmLeft.uiPulse);__GmLeft.uiPulse=3000;__GmLeft.uiPulseCtr=0;__GmRight.uiPulse=3000;__GmRight.uiPulseCtr=0;__GmSPID.sRef=35;__GmWPID.sRef=-25;GW=0;__GucMouseState=__TURNRIGHT;//智能鼠状态__GmRight.cState=__MOTORRUN;//电动机状态__GmLeft.cState=__MOTORRUN;GucMouseDir=(GucMouseDir+1)%4;/*方向转换*/while(1){if(GW>55500)//调用陀螺仪数据{break;}} __mazeInfDebug();__GmWPID.sRef=0;__GucMouseState=__GOAHEAD;GuiSpeedCtr=3;__GmLeft.uiPulse=3800;//转弯后电动机转动的脉冲__GmLeft.uiPulseCtr=0;__GmRight.uiPulse=3800;__GmRight.uiPulseCtr=0;while((__GmRight.uiPulseCtr+200)<=__GmRight.uiPulse);while((__GmLeft.uiPulseCtr+200)<=__GmLeft.uiPulse);__GucMouseState=__TURNRIGHT;GuiSpeedCtr=__SPEEDUP;__GmRight.cState=__MOTORSTOP;__GmLeft.cState=__MOTORSTOP;__GmRight.uiPulseCtr=0;__GmLeft.uiPulseCtr=0;}20思考与总结（1）智能鼠如何实现转弯？（2）左转180°和右转180°有何区别？（3）直流电动机在使用时需要注意直线速度和旋转速度的大小，前者表示运行的快慢，后者决定了转弯半径的大小。21本项目到此结束THANKYOU22

项目三掌握经典迷宫搜索算法23学习目标（1）学习等高图的制作及优化。（2）学习智能鼠的左手、右手、中心法则。（3）学习多种智能鼠的程序设计算法。等高图就是等高线地图的简称，有如一般地图可以标出同一高度的地区范围，或有如气象报告时的等气压图，可以标出相等气压的范围及大小。那么等高图运用在迷宫地图上，可以标出每个迷宫格到起点相等（对等）步数的关系。许多封闭路径的逃脱与冲刺的关卡都可在制作出等高图后迎刃而解，使智能鼠更容易逃脱，少走一些弯路。24任务一掌握等高图的制作及优化任务二掌握智能鼠的右手法则任务三掌握智能鼠的左手法则任务四掌握智能鼠的优化算法——中心法则及优化任务五了解Flood扩散算法任务六了解几种重要的智能鼠逻辑算法25任务一掌握等高图的制作及优化一、墙壁资料当智能鼠达到一方格坐标时，应根据传感器检测结果记录下当前方格的墙壁资料。为了方便管理和节省存储空间，每一个字节变量的低四位分别用来存储一个方格四周的墙壁资料，见右表，迷宫共有16×16个方格，所以可以定义一个16×16的二维数组变量来保存整个迷宫墙壁资料。迷宫墙壁资料全部初始化为0，凡是走过的迷宫格至少有一方没有墙壁，即墙壁资料不为0，这样就可以通过单元格存储的墙壁资料是否为0来确定该单元格是否曾搜索过。变量位绝对方向相对方向bit0上方01：有路，0：有墙壁bit1右方11：有路，0：有墙壁bit2下方21：有路，0：有墙壁bit3左方31：有路，0：有墙壁Bit4～bit7

保留位26任务一掌握等高图的制作及优化核心函数：__wallCheck/************************************************************************************Functionname:__wallCheck**Descriptions:根据传感器检测结果判断是否存在墙壁**Returnedvalue:低三位从左到右依次表示左、前、右是否有墙壁，1有墙，0无墙。**********************************************************************************/void__wallCheck(void){uint8ucMap=0;uint8uctemp=0;ucMap|=MOUSEWAY_B;if(__GucDistance[__LEFT]&0x01){ucMap&=~MOUSEWAY_L;uctemp|=0x06;}else{ucMap|=MOUSEWAY_L;}if(__GucDistance[__FRONT]&0x01){ucMap&=~MOUSEWAY_F;uctemp|=0x40;}else{ucMap|=MOUSEWAY_F;}if(__GucDistance[__RIGHT]&0x01){ucMap&=~MOUSEWAY_R;uctemp|=0x30;}else{ucMap|=MOUSEWAY_R;}GucMapBlock0[GmcMouse.cX][GmcMouse.cY]=ucMap;GucMapBlock[GmcMouse.cX][GmcMouse.cY]=ucMap;GucMapBlock1[GmcMouse.cX][GmcMouse.cY]=ucMap;if(GmcMouse.cY<(MAZETYPE-1)){GucMapBlock1[GmcMouse.cX][GmcMouse.cY+1]&=~(((~ucMap)&0x01)*4);}if(GmcMouse.cX<(MAZETYPE-1)){GucMapBlock1[GmcMouse.cX+1][GmcMouse.cY]&=~(((~ucMap)&0x02)*4);}if(GmcMouse.cY>0){GucMapBlock1[GmcMouse.cX][GmcMouse.cY-1]&=~(((~ucMap)&0x04)/4);}if(GmcMouse.cX>0){GucMapBlock1[GmcMouse.cX-1][GmcMouse.cY]&=~(((~ucMap)&0x08)/4);}

if(GmcMouse.cY<(MAZETYPE-1)){GucMapBlock[GmcMouse.cX][GmcMouse.cY+1]|=((ucMap&0x01)*4);}if(GmcMouse.cX<(MAZETYPE-1)){GucMapBlock[GmcMouse.cX+1][GmcMouse.cY]|=((ucMap&0x02)*4);}if(GmcMouse.cY>0){GucMapBlock[GmcMouse.cX][GmcMouse.cY-1]|=((ucMap&0x04)/4);}if(GmcMouse.cX>0){GucMapBlock[GmcMouse.cX-1][GmcMouse.cY]|=((ucMap&0x08)/4);}zlg7289Download(2,2,0,uctemp);}27任务一掌握等高图的制作及优化二、等高图制作及优化1.等高图制作首先开辟一块16×16的二维数组空间（MapStep[16][16]），其中每一个元素代表迷宫中的一个方格，用以计算后储存各方格至起点的最短路径步数（所谓步数即为路径中经过的方格数）。当起点坐标处标识为1时，可以直接达到的相邻方格均为2，再远的方格的等高值依次递增。这样距离越远的地方等高值越大。2.等高图转弯优化由于智能鼠转弯要浪费一定时间，虽然(0，2)点和(1，1)点的等高值都为3，但肯定会认为等高图从(0，2)点到起点比从(1，1)点到起点要快。因此，为了寻找一条最优的路径(也就是能最快达到路径)，可以给转弯点加权。假设权值为1，即经过转变前进的坐标的等高值是由当前等高值加2得到的。转弯加权后的等高图如图2-3-1所示，加权值可以根据自己智能鼠转弯性能来决定，这里设置为1。28任务一掌握等高图的制作及优化核心函数：mapStepEdit/********************************************************************************Functionname:mapStepEdit**Descriptions:制作等高图**uiX:目的地横坐标**uiY:目的地纵坐标**outputparameters:GucMapStep[][]:各坐标上的等高值******************************************************************************/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))){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;GmcStack[n].cY=cY;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;}}}}29任务二掌握智能鼠的右手法则当智能鼠在前进时，如果在前进的方向上存在两条和两条以上的支路时，它需要选择向哪个方向转弯，转弯的方向不同导致智能鼠的运动路径也不同。可以使智能鼠优先考虑向右转弯，其次向前直行，最后才考虑向左转弯，这种策略方法称为右手法则。如右图所示，图中坐标（0，0）为智能鼠出发点，虚线为智能鼠运动路径，可以很清楚的看到，每当智能鼠遇到分支路口时，它都会选择优先向右转弯，不能右转弯时智能鼠会选择向前直行，当它既不能右转弯也不能直行时才会向左转弯。以右手法则示意图中的几个关键点为例进行解释，决策对应如右表所示。在坐标（0，4）处，智能鼠可以选择前进或右转，那么依据右手法则最终会选择右转；在坐标（2，0）处，智能鼠可以选择左转或右转，依据右手法则最终会选择右转；在坐标（4，0）处，智能鼠可以选择左转或前进，依据右手法则最终会选择前进。坐标点方向选择项最终策略选择（0，4）前进、右转右转（2，0）左转、右转右转（4，0）左转、前进前进30任务三掌握智能鼠的左手法则与右手法则相似，在迷宫搜索方法策略上，智能鼠优先考虑向左转弯，其次是向前直行，最后考虑向右转弯，这种策略称为左手法则。示意图如右图所示，图中智能鼠出发点依然是坐标（0，0），虚线依然为智能鼠运动路径，不同的是，每当智能鼠遇到分支路口时，它都会选择优先向左转弯；不能左转弯时，智能鼠会选择向前直行；当它既不能左转弯也不能直行时才会向右转弯。以左手法则示意图中的几个关键点为例进行解释，决策对应如右表所示。在坐标（2，6）处，智能鼠可以选择左转或右转，那么依据左手法则最终会选择左转；在坐标（1，8）处，智能鼠可以选择前进或右转，依据左手法则最终会选择前进；在坐标（2，F）处，智能鼠可以选择右转或前进，依据左手法则最终会选择右转。坐标点方向选择项最终策略选择（2，6）左转、右转左转（1，8）前进、右转前进（2，F）右转、前进右转31任务四掌握智能鼠的优化算法——中心法则及优化一、中心法则中心法则是指：当智能鼠在前进的方向上遇到两条或两条以上的支路时，优先选离中心点最近的方向行进。同时有两个离中心最近的方向供选择时，选择直线方向。把迷宫分为四个对等的区域(1、2、3、4)，通过观察可得到，各个区域中智能鼠向哪个方向上运动更能接近中心，如右图所示中箭头所指。如果智能鼠前进的方向上遇到两系支路方向都是离迷宫中心最近的方向，优先选择可以直线前进的方向，其次选择只用转弯90°的方向。如果可前进的支路方向都是远离中心的方向时，优先选择直线运行方向，其次选择转弯90°的方向，其搜索示意图如右图所示。32任务四掌握智能鼠的优化算法——中心法则及优化二、中心分割法则中心分割法则是中心算法的优化，是指将迷宫分为几个部分，根据每个部分相对于目标区域的位置和当前智能鼠行进的绝对方向，采用不同的法则来控制智能鼠运行。如图2-3-6所示中右上角区域，当智能鼠向上行进时，采用左手法则；当智能鼠向右行进时，采用右手法则；当智能鼠向下行进时，采用中右法则：当智能鼠向左行进时，采用中左法则。33任务五了解Flood扩散算法一、Flood-Fill算法概述Flood-Fill算法又称为洪水扩散算法，是当前智能鼠中使用最为广泛的一种算法，其思路来源于水往低处流的自然现象。洪水扩散算法的基本思想是将迷宫终点看成是数值为1的低洼，并且从终点开始，相邻的单元格的数值依次递增1。单元格数值一方面表明了其距离终点的距离，另一方面说明了该单元格的高度，最终起点处的智能鼠按照拱水填充的方法，沿着逐渐变低的地势〈单元格数值）流动就可以到达迷宫终点。Flood扩散算法可以在搜索迷宫中使用，也可以在迷宫冲剌阶段中使用。在搜索中使用时，由于迷宫信息并不全，此时可以将未知的迷宫单元格全部看成是无挡板通路，即最优状况，通过迷宫信息的不断扩充，单元格中的数字也将发生变化，直到智能鼠找到出口为止。如图2-3-7所示，结合直行优先对Flood扩散算法进行阐述。34任务五了解Flood扩散算法Flood扩散算法是一个不断对行进单元格进行重新赋值的过程。在以上的算法详述中，使用了直行优先法则。但是如果使用右手法则进行Flood扩散算法，则找到的终点通道并不是迷宫最佳通道，因此，如果系统使用Flood扩散算法得到最优路径，则需要对迷宫进行完全搜索。35任务五了解Flood扩散算法二、基于Flood扩散算法的等高图制作三、Flood扩散算法优化—迷宫补全迷宫补全是利用获得的信息，对某些只有一个入口的死路迷宫通道进行预测，并将这些处于死路的通道区域进行“封锁”，从而避免智能鼠进入这些无关紧要的死区进行搜索，在某些地图中大大节省了搜索时间。该补全算法要求智能鼠在对当前单元格进行坐标挡板更新的同时，也将该单元格相邻的单元格信息进行更新，比如对于坐标（3，3）的挡板信息为右侧有挡饭，则可以同时对左边坐标（3，4）的信息添加为左侧有挡板，并对确定的死区区城添加虚拟墙壁，以阻止算法的扩散，减少算法的运算量。迷宫补全和Flood扩散相结合可以减少对死区的搜索。这对于需要进行完全搜索的Flood扩散算法是非常有利的。如图所示，图中阴影部分为在右手法则下，通过迷宫补全算法对“死区”的判断，从中可以看出大量减少了智能鼠的搜索时间（图中灰色底纹部分不会再行走了）。36任务六了解几种重要的智能鼠逻辑算法一、搜索算法智能鼠采用基于曼哈顿距离的A-Star搜索方法。智能鼠在每一步都会计算下一格到终点的曼哈顿距离，然后选择距离终点最近的方向前进，当两个方向与终点距离相同时，智能鼠优先直行。路径选择程序如下：核心算法：RightPathcharRightPath(intXX,intYY){charBlockNow;BlockNow=GucMapBlock[XX][YY];intDis[4]={99,99,99,99};charGoDer=GOAHEAD;intMinDis=99;if((!(BlockNow&0x01))&&(!(GucMapBlock[XX][YY+1]&0x10)))//判断前方是否可行{Dis[0]=abs(YY+1-DEST_Y)+abs(XX-DEST_X);//计算曼哈顿距离}if((!(BlockNow&0x02))&&(!(GucMapBlock[XX+1][YY]&0x10)))//判断右方是否可行{Dis[1]=abs(YY-DEST_Y)+abs(XX+1-DEST_X);//计算曼哈顿距离}if((!(BlockNow&0x04))&&(!(GucMapBlock[XX][YY-1]&0x10)))//判断后方是否可行{Dis[2]=abs(YY-1-DEST_Y)+abs(XX-DEST_X);//计算曼哈顿距离}if((!(BlockNow&0x08))&&(!(GucMapBlock[XX-1][YY]&0x10)))//判断左方是否可行{Dis[3]=abs(YY-DEST_Y)+abs(XX-1-DEST_X);//计算曼哈顿距离}

intDire=GucMouseDir/2;MinDis=Dis[Dire];

Dire=(Dire+1)%4;if(Dis[Dire]<MinDis){MinDis=Dis[Dire];GoDer=TURNRIGHT;}

Dire=(Dire+1)%4;if(Dis[Dire]<MinDis){MinDis=Dis[Dire];GoDer=TURNBACK;}

Dire=(Dire+1)%4;if(Dis[Dire]<MinDis){MinDis=Dis[Dire];GoDer=TURNLEFT;}returnGoDer;}37任务六了解几种重要的智能鼠逻辑算法二、洪水算法智能鼠采用洪水算法制作等高图。程序如下：核心算法：mapStepEditvoidmapStepEdit(intcX,intcY){intn=0;/*GmcStack[]下标*/intucStep=1;/*等高值*/charucStat=0;/*统计可前进的方向数*/chari,j;

GmcStack[n].cX=cX;/*起点X值入栈*/GmcStack[n].cY=cY;/*起点Y值入栈*/n++;/*初始化各坐标等高值*/for(i=0;i<MAZETYPE_X;i++){for(j=0;j<MAZETYPE_Y;j++){GucMapStep[i][j]=9999;}}/*制作等高图，直到堆栈中所有数据处理完毕*/while(n){if(er==1)break;GucMapStep[cX][cY]=ucStep++;/*填入等高值*//*对当前坐标格里可前进的方向统计*/ucStat=0;if(GucMapBlock[cX][cY]&0x10){if(GucMapBlock[cX][cY]&0x01){}else/*前方有路*/{if(GucMapStep[cX][cY+1]>ucStep){/*上方等高值大于计划设定值*/ucStat++;}}if(GucMapBlock[cX][cY]&0x02){}else/*右方有路*/{if(GucMapStep[cX+1][cY]>ucStep){/*右方等高值大于计划设定值*/ucStat++;}}if(GucMapBlock[cX][cY]&0x04){}else/*后方有路*/{if(GucMapStep[cX][cY-1]>ucStep){/*下方等高值大于计划设定值*/ucStat++;}}if(GucMapBlock[cX][cY]&0x08){}else/*左方有路*/{if(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]&0x10){if(GucMapBlock[cX][cY]&0x01){}else{if(GucMapStep[cX][cY+1]>ucStep){/*上方等高值大于计划设定值*/cY++;/*修改坐标*/continue;}}if(GucMapBlock[cX][cY]&0x02){}else{if(GucMapStep[cX+1][cY]>ucStep){/*右等高值大于计划设定值*/cX++;/*修改坐标*/continue;}}if(GucMapBlock[cX][cY]&0x04){}else{if(GucMapStep[cX][cY-1]>ucStep){/*下方等高值大于计划设定值*/cY--;/*修改坐标*/continue;}}if(GucMapBlock[cX][cY]&0x08){}else{if(GucMapStep[cX-1][cY]>ucStep){/*左方等高值大于计划设定值*/cX--;/*修改坐标*/continue;}}}}}}38任务六了解几种重要的智能鼠逻辑算法三、直接到指定坐标程序设计该程序块的目的是实现控制智能鼠能够以最短路径前进到指定坐标点。当然该功能实现的前提是目的地是智能鼠已经走过且记录下来的方格。设计该程序的步骤如下：（1）制作以目的地为起点的等高图。（2）检查算法是否已搜索到目的地，如果是则跳到第（6）步，否则继续顺序执行。（3）获取当前坐标的等高值。（4）寻找比当前坐标等高值小的支路方向，且优先选择不需要转弯的方向前进。如果选择的方向就是正前方，则前进步数cNBlock加1并返回第（2）步，否则继续执行。（5）根据目标方向记录智能鼠转弯，完成后返回第（2）步。（6）智能鼠依次执行记录记录的操作。（7）按搜索法则选择下一步动作。核心函数1：objectGoTocharobjectGoTo(intcXdst,intcYdst,charOK){intucStep=1;charNEXTS=0xFF;charcNBlock=0,cDirTemp;charMouseDir=GucMouseDir;intcX,cY;Step=0;cX=GmcMouseCoor.cX;cY=GmcMouseCoor.cY;mapStepEdit(cXdst,cYdst);/*制作等高图*//**根据等高值向目标点运动，直到达到目的地*/while(er==0){ucStep=GucMapStep[cX][cY];

if((cX==cXdst)&&(cY==cYdst)){SpurtStep[Step].NumCoorUpdate=cNBlock;SpurtStep[Step++].nextrad=(cDirTemp+8-MouseDir)%8;break;}/**任选一个等高值比当前自身等高值小的方向前进*/if(GucMapBlock[cX][cY]&0x10){if(GucMapBlock[cX][cY]&0x01){}else/*上方有路*/{if(GucMapStep[cX][cY+1]<ucStep){/*上方等高值较小*/cDirTemp=UP;/*记录方向*/if(cDirTemp==MouseDir){/*优先选择不需要转弯的方向*/cNBlock++;/*前进一个方格*/cY++;continue;/*跳过本次循环*/}}}if(GucMapBlock[cX][cY]&0x08){}else/*左方有路*/{if(GucMapStep[cX-1][cY]<ucStep){/*左方等高值较小*/cDirTemp=LEFT;/*记录方向*/if(cDirTemp==MouseDir){/*优先选择不需要转弯的方向*/cNBlock++;/*前进一个方格*/cX--;continue;/*跳过本次循环*/}}}if(GucMapBlock[cX][cY]&0x02){}else{/*右方有路*/if(GucMapStep[cX+1][cY]<ucStep){/*右方等高值较小*/cDirTemp=RIGHT;/*记录方向*/if(cDirTemp==MouseDir){/*优先选择不需要转弯的方向*/cNBlock++;/*前进一个方格*/cX++;continue;/*跳过本次循环*/}}}if(GucMapBlock[cX][cY]&0x04){}else{/*下方有路*/if(GucMapStep[cX][cY-1]<ucStep){/*下方等高值较小*/cDirTemp=DOWN;/*记录方向*/if(cDirTemp==MouseDir){/*优先选择不需要转弯的方向*/cNBlock++;/*前进一个方格*/cY--;continue;/*跳过本次循环*/}}}}SpurtStep[Step].NumCoorUpdate=cNBlock;SpurtStep[Step++].nextrad=(cDirTemp+8-MouseDir)%8;MouseDir=cDirTemp;cNBlock=0;}for(inti=0;i<Step;i++)//依次执行动作{Micromouse_SearchGoAhead(i);if(SpurtStep[i].nextrad==2){Turn_Right90();}elseif(SpurtStep[i].nextrad==4){Turn_Back();GmLeft.ucState=MOTORRUN;GmRight.ucState=MOTORRUN;GucMouseState=GOAHEAD;}elseif(SpurtStep[i].nextrad==6){Turn_Left90();}}GmcMouseCoor.cX=cX;GmcMouseCoor.cY=cY;if(OK==0){NEXTS=RightPath(GmcMouseCoor.cX,GmcMouseCoor.cY);//继续搜索}returnNEXTS;}39任务六了解几种重要的智能鼠逻辑算法核心函数2：objectGoTovoidobjectGoTo(int8cXdst,int8cYdst){uint8ucStep=1;int8cNBlock=0,cDirTemp;int8cX,cY;GucCrossroad=0;cX=GmcMouse.cX;cY=GmcMouse.cY;mapStepEdit(cXdst,cYdst);/*首先制作等高图*//*根据等高值向目标点运动*/while((cX!=cXdst)||(cY!=cYdst)){ucStep=GucMapStep[cX][cY];/*选一个等高值比自身小的方向前进*/if((GucMapBlock[cX][cY]&0x01)&&(GucMapStep[cX][cY+1]<ucStep))//上方有路且等高值较小{cDirTemp=UP;//记录方向

if(cDirTemp==GucMouseDir){/*优先选择不需要转弯的方向*/cNBlock++;/*前进一格*/

cY++;if((GucMapBlock[cX][cY]&0x0f)==0x