浅谈机器人在线迷宫中的控制策略问题.doc

线迷宫如下图所示，存在一些直道、弯道、丁字路口、十字路口、死胡同等多种情况。在“左手法则”下，如何合理的处理每种道路情况，以让机器人能以最快时间或最短路程从起点走到终点，是我们探讨的主要内容。文中内容结合了自己在机器人开发中的一些体验，并重点参考了国外Richard T-Vannoy教授有关机器人控制材料而完成这篇文章的。好，下面就让我们进入机器人的迷宫世界吧。1、线迷宫简介1.1 线迷宫的类型线迷宫从结构上看一般又可以分为赛道式和迷宫式，如下图所示：p1.0 赛道式线迷宫p1.1 迷宫式线迷宫赛道式由不同形状的曲线组合而成。这类迷宫的特点是，赛道连贯性强，岔道少（或没有岔道），方便机器人对赛道的判断。但赛道方向不规则的变化也为机器人寻迹增加了很多难度。迷宫式则是由不同长度的直线组合而成。这类迷宫的特点是，赛道复杂、赛道岔道多、机器人运动路线不唯一。如何准确判断岔道类型，并作出合理判断，是走这类迷宫时机器人遇到的难题。从颜色看，线迷宫一般又可分为白底黑线和黑底白线两种类型（但鉴于很多赛道采用电胶带粘贴而成，所以白底黑线的情况较为多见）。但无论是哪种类型的线迷宫，都有一个共同特点就是：要有起点和终点。机器人从起点开始，沿着赛道前进，在终点停止。整个过程中，最快的速度或最短的时间是每位机器人设计者追求的目标，也是迷宫机器人比赛的评判标准。1.2 线迷宫的技术难点对于赛道式的线迷宫，技术难点在于如何让机器人在高速运动的状态下，能事先判断赛道变化趋势，以更好的沿着赛道运动；尤其是在弯道上，不会出现偏离或冲出赛道的情况。这里面除了赛道探测传感器的选用外，控制方法也是不可或缺的因素。现在国内的“飞思卡尔智能车比赛”重点考核的就是这个技术难点。对于迷宫式的线迷宫，机器人如何准确的判断赛道岔路类型，是技术难点。在这类线迷宫中，赛道岔道一般可以分为左转路口、右转路口、丁字路口、十字路口、前进或左转路口、前进或右转路口、死胡同、赛道终点等八种类型。还有些线迷宫带有封闭赛道，更增添了机器人判断的难度。如何让机器人具备自我学习能力，能够发现并记住不能通行的岔道，以期使机器人在第二次穿越时，可以用最短的距离走完线迷宫，是机器人设计的难点。p1.2 线迷宫机机器人可能遇到的八种情形p1.3 带有封闭赛道的线迷宫我们这片文章就重点就这第二类迷宫式线迷宫做探讨。2、机器人控制策略2.1 左手法则（Left Hand Rule） 机器人执行左转的优先级高于直行或右转； 机器人执行直行的优先级高于右转； 即机器人在线迷宫中，如果遇到“十字路口”（即有左转、直行和右转），机器人会左转；如果遇到“直行或右转路口”，机器人会直行；只有遇到“右转路口”，机器人才右转。一句话就是，执行左手法则的机器人永远是沿着左侧走。如果线迷宫不存在向p1.3图所示的封闭赛道，都可以顺利的从起点走到终点。2.2 右手法则（Right Hand Rule） 机器人执行右转的优先级高于直行或左转； 机器人执行直行的优先级高于左转； 即机器人在线迷宫中，遇到右转路口，一定右转。如果遇到“十字路口”（即有左转、直行和右转），机器人会右转；如果遇到“直行或左转路口”，机器人会直行；只有遇到“左转路口”，机器人才左转。一句话就是，执行右手法则的机器人永远是沿着右侧走。2.3 我们的选择很多初学者在机器人控制时，会为是选择“左手法则”还是选择“右手法则”而矛盾。这没有任何关系！无论是左手法则还是右手法则都可以让你的机器人顺利的从起点走到终点，完成迷宫穿越。选用哪种方法纯粹是个人爱好问题。3、寻线传感器3.1 寻线传感器类型这个小节我们介绍一下寻线传感器。可以说机器人的最终走迷宫效果如何，很大程度和寻线传感器有关系。机器人只有通过寻线传感器准确的判断了当前所处赛道的位置，机器人控制机构才可以根据赛道状况做出准确的反应。寻线传感器模块是多个传感器阵列。从组合方式上主要有两种类型：一字型和八字型（具体看下图所示）。八字形和一字型相比较，前部突出的传感器，让机器人具有了预判断功能。（如果赛道具有丁字路口、十字路口，八字型寻线传感器模块将会使机器人判断工作变得简单）p3.1八字型寻线传感器p3.2 一字型寻线传感器从数量上来说，有3个、4个、5个，乃至更多传感器组合。一般说，3个的寻线传感器适合做赛道式线迷宫寻线（如图p1.0），不适合迷宫式寻线场合；传感器数量多于3个时，则可以做迷宫式寻线。数量越多越便于机器人对线路做出预判（这也是为什么我们在看飞思卡尔智能车比赛时，很多小车前头都加了长长一排的寻线传感器，十多个之多的原因）。从输出信号类型分类，又有模拟信号输出传感器模组和开关量输出传感器模组。这些由于对我们后续的介绍没有太大关系，就不多做分析（当然在我们实际控制上，开关量传感器模组相对简单一些。传感器信号直接送给单片机IO即可；如果是模拟量输出，则还要通过AD模数转换后才可以。但模拟量输出传感器也有其自身的好处，那就是可以准确判断场地灰度值，可以做防坠落功能）。在我们接下来介绍的机器人走迷宫的内容中，为了介绍方便，我们选用“一字型5通道寻线传感器模组”作为讲解对象。3.2 寻线传感器工作原理寻线传感器一般是由光电对管组成，一个发射，一个接收。根据发射光（分可见光和红外光）对赛道介质的反射参数的差别，来判断传感器下面是赛道还是场地。我们都在物理课本中学过，颜色越深的物体，吸收光线的能力就越强；颜色越浅的物体，发射光线的能力就越强。当光电对管通过深颜色物体时，由于发射光被吸收很多，能反射出来的光线就小，能被接收管收到的光线就更少；反之，当光电滴灌通过浅颜色物体时，由于发射光被吸收较少，能反射出来的光线就多，能被接收管接收到的光线也随之增多。而光电接收管会随着接收光线的多少而发生电压或电流变化，我们根据这些电参数变化就可以知道传感器碰到的是深颜色物体还是浅颜色物体。赛道之所以要做成黑底白线，或白底黑线，就是为了让电参数变化差异增大，更便于我们判断。为了方便介绍，在机器人走迷宫时，我们这里设定，遇到黑色，传感器输出“1”高电平；遇到白线，传感器输出“0”低电平。3.3 寻线传感器的使用p3.3 机器人在寻线时的传感器的显示当机器人沿着线走时（在图中自下向上行驶），处于不同情形时，传感器会有不同的显示。这里列出了5种常见情形： 10000=机器人严重向右偏离赛道（在控制上我们就要让机器人在前进的同时向左做大幅度转动） 01000=机器人轻微向右偏离赛道（在控制上我们就要让机器人在前进的同时向左做轻微转动） 00100=机器人正处在赛道上（在控制上我们就要让机器人继续直线前进） 00010=机器人轻微向左偏离赛道（在控制上我们就要让机器人在前进的同时向右做轻微转动） 00001=机器人严重向左偏离赛道（在控制上我们就要让机器人在前进的同时向右做大幅度转动） 通过传感器对不同情形的反馈，就可以确保机器人准确的沿着赛道前进。4、机器人对岔路口的处理方法4.1 机器人走迷宫过程分析机器人在走线迷宫时，常用的控制方法无非是以下几个步骤：(1)、机器人沿着当前赛道前进（following the line）；前进同时检测前方是否有岔路口。(2)、一旦检测到岔路口，机器人要判断岔路口的类型；(3)、确定岔路口类型后，在一定的控制法则下完成转弯。整个流程在机器人走迷宫时将会循环作用，直到机器人到达迷宫重点。简单用流程图示意一下就是下图：p4.1 机器人走迷宫示意图PS.当然上面的流程图中并没有涉及到后面我们所要讲到的“机器人自主学习功能”。这块功能将单拉出来讲解。4.2 机器人寻线方法（following the line）机器人寻线相对而言还是比较简单的，我们只需根据传感器数调整机器人左右转速就可以了。这里提供一个简单的控制代码范例：Select Case Pattern /选择可能的模式；请参考3.3寻线传感器的使用；Case Pattern = %00100 /这种模式表示机器人处于赛道正上方，则全速前进；leftMotor=fast; rightMotor=fast /即左侧电机和右侧电机都快速前进；Case Pattern = %01000 /这种模式表示机器人轻微向右偏离赛道；leftMotor=medium; rightMotor=fast /针对这种状况，左侧电机中速转动，右侧电机快递转动，/通过两侧轮子转速差减少机器人向右偏移；Case Pattern= %10000 /这种模式表示机器人已经严重向右偏离赛道；leftMotor=slow; rightMotor=fast /针对这种状况，左侧电机慢速转动，右侧电机快速转动，/以快速纠正机器人。and so on以上范例代码中，慢速、中速和快速只是根据机器人偏离赛道程度大小而使用的描述词语。在实践中，机器人电机转动的速度需要你不断实验、尝试，才能使机器人有更好的寻线效果。（在控制上，这加入了反馈，属于闭环控制。建议去尝试着了解一下闭环控制理论中PID算法的介绍，这将对机器人的速度控制有很大帮助）4.3 赛道路口的识别和处理。有了4.2中介绍的内容，我们的机器人就可以沿着赛道走了，但这个时候它还不会判断岔路口，更不知道遇到岔路口应该如何操作。这一小节就重点介绍岔路口的识别和对应操作。让我们再次去回顾一下1.2小节中“P1.2线迷宫机机器人可能遇到的八种情形”的图片，我们就对图中的八种状况做分析。说到这里，我们要重点强调一个概念：岔路口。至少到现在为止，岔路口的概念还不会对我们介绍的内容造成理解上的偏差。但后面小节要介绍“机器人的自主学习能力”，如果不对这一概念做澄清，会影响后续内容的开展：岔道口：机器人可以有一个以上行进方向的路口。按照上面的定义，下图中的两个路口就不能再成为岔路口了。虽然在这两个路口，机器人要执行转向的操作，但在方向选择，显然机器人不必要思考的，左转或右转时他们唯一的选择。同样不能作为岔路口的还有“死胡同”。p4.2 不是岔路口的路口弄明白了这个概念对下一小节的内容就容易理解了。下面就切入本小节的正题：路口的识别和处理。4.3.1 死胡同的识别和处理死胡同是8种路口中最简单的一个。当寻线传感器数值从“00100”变化为“00000”时，我们就可以认为机器人是遇到了死胡同。p4.3 死胡同当机器人遇到死胡同时，机器人的动作应该是掉头（make a U-turn）。示意程序代码为：If Pattern = %00000 then gosub U-Turn /当遇到死胡同，机器人直行掉头的子函数。4.3.2 “右转路口”和“右转或直行路口”识别和处理当机器人遇到这两种路口时，传感器输出模式都是“00111”。这个时候机器人如何做选择呢？p4.4 右转路口和右转或直行路口解决方式是，我们编写一个子程序，假设名字是inch（），执行的操作是让机器人再前进一点（一英寸）。当传感器越过赛道后，如果寻线传感器显示数值为“00000”，那么这个路口就一定是“右转路口”；如果寻线传感器显示数值为“00100”，那么这个路口就一定是“右转或直行路口”。那接下来机器人该如果动作呢？如果机器人使用的是“左手法则”，在“右转路口”只能有一种选择右转；在“右转或直行路口”，机器人就要执行“直行”的动作；如果机器人使用的是“右手法则”，在“右转路口”显然要右转；在“右转或直行路口”，机器人就要执行“右转”的动作；4.3.3 “左转路口”和“左转或直行路口”识别和处理当机器人遇到这两种路口时，传感器输出模式都是“11100”。这个时候机器人如何做选择呢？p4.5 左转路口和左转或直行路口同样我们也是借助子函数inch（），让机器人再前进一点（一英寸）。当传感器越过赛道后，如果寻线传感器显示数值为“00000”，那么这个路口就一定是“左转路口”；如果寻线传感器显示数值为“00100”，那么这个路口就一定是“左转或直行路口”。那接下来机器人该如果动作呢？如果机器人使用的是“左手法则”，在“左转路口”显然要左转；在“左转或直行路口”，机器人就要执行“左转”的动作；如果机器人使用的是“右手法则”，在“左转路口”只能左转；在“左转或直行路口”，机器人就要执行“直行”的动作；4.3.4 “丁字路口”、“十字路口”和“终点路口”识别和处理当机器人遇到这三种路口时，传感器输出模式都是“11111”。这个时候机器人如何做选择呢？p4.6 其他路口我们还是利用inch（）函数，让机器人再前进一点距离，这将帮助我们分辨这三种路口：如果寻线传感器数值是“00000”，那么这个路口就是丁字路口；如果寻线传感器数值是“00100”，那么这个路口就是十字路口；如果寻线传感器数值是“11111”，那么这个路口就是迷宫终点了。针对不同路口的判断，我们这里提供一个程序范例：Gosub inch() /机器人再前进一点的子函数（距离越过赛道宽度就可以）ReadSensors() /读取寻线传感器数值If Pattern = “00000” then?Found the T intersection /如果数值是“00000”，遇到丁字路口Elseif Pattern = “11111” then?Found the end of the maze STOP! /如果数值是“11111”，到达了迷宫重点；Else?At a four-way intersection /如果是其他情况，则是遇到了十字路口。EndifPS.在这篇文章中，我们使用的是一字型寻线传感器。如果我们使用八字型寻线传感器的话，由于传感器是分前后两排分布的，这样在判断岔路口方面就非常方便，无需借助inch()函数，就可以直接识别。八字型传感器的识别方法，留给读者自己解决。当我们准确的判断出每个路口的类型后，机器人就可以在一定的走迷宫法则指导下完成走迷宫任务。但我们发现，在线迷宫中，有很多死胡同是不必要走的，有些弯路也是可以省略的，对于机器人，它们应该如何选择一条最短的距离呢？下一小节我们就重点介绍机器人的自学习能力。5、机器人自主学习算法5.1 机器人自主学习功能介绍下面我们通过一个简易线迷宫来介绍机器人的自主学习功能。在这个迷宫中，有十字路口、直行或右转路口、直行或左转路口、死胡同等，从图中可以看出，有些线路是无效线路，如死胡同，就是可以绕过的。但机器人并不知道那些路口时有效路口，哪些路口是无效的。我们使用“左手法则”进行穿越线迷宫，图中的蓝色的线，就是其穿越路径。可以看出绕了很大的圈。机器人的自主学习功能就是机器人在经过第一次穿越后，能够发现并记住所经过的无效线路，从而在第二次穿越时，自动绕过那些无效路口，实现最短距离穿越线迷宫，如图中绿线所示路径。p5.1 机器人穿越线迷宫路径5.3 机器人自主学习算法不要嫌作者啰嗦，这里我们再次强调一下上小节中介绍的“岔路口”的概念：机器人可以有一个以上行进方向的路口称之为岔路口。好了，有了这个概念，就容易了。当机器人穿越线迷宫时，每穿越一个“岔路口”，我们就让机器人在存储器中记录一个字符：如果是直行就保存一个“S”；如果是左转就保存一个“L”；如果是右转就保存一个“R”；如果是掉头，就保存一个“U”。只要是岔路口，就要记录一次。PS.右转路口和左转路口不属于我们所说的岔路口概念，机器人经过时不要记录。有了这个共识，我们就开始下面的算法介绍！p5.2 第一个转弯我们就借助上面的建议线迷宫，分步介绍机器人的自主学习过程的。机器人第一次穿越线迷宫时，我们采用“左手法则”来进行。沿途将有一些“岔路口”，我们需要记录。机器人开始从起点出发了，然后就遇到了第一个“岔路口”直行或右转路口。根据“左手法则”，机器人将直行。这时候，机器人将在存储器中记录一个直行的标示符“S”，如p5.2所示。p5.3 第二个转弯机器人继续前进，这时就遇到第二个“岔路口”死胡同。这个时候机器人需要掉头回来。这时候，机器人将在存储器中记录一个掉头的标示符“U”，如图p5.3所示。这样存储器中的标示符就变成了“SU”PS.从图中可以看出机器人每记录一个死胡同类型的岔路口，就意味着机器人走了错误路线。在任何线迷宫中，最佳或最短路线都不包括死胡同线路。所以遇到死胡同类型的岔路口就是告诉我们在前一个路口的转向时不正确的，我们需要更正。当机器人掉头回到第一个岔道口（也是机器人行进过程中的第三个岔路口），根据左手法则，机器人将会左转，如图p5.4所示。这时候，机器人将在存储器中记录一个左转的标示符“L”。这样存储器中的标示符就变成了“SUL”。从上面的介绍中可以知道死胡同类型的岔路口将不会在机器人穿越迷宫的路径中，所以机器人应该在第一个岔路口向右转“R”，才可以避免经过死胡同。从以上分析我们就可以得出：SUL=R（即机器人直行、掉头、左转就相当于机器人直接右转）。这样在存储器中”SUL”就被标示符“R”取代。这就代表着当机器人再次穿越这个线迷宫时，遇到第一个岔路口直接右转。p5.4 第三个转弯机器人继续前进，就遇到了十字路口类型的岔路口，根据左手法则，机器人将会左转，如图p5.5所示。这时候，机器人将在存储器中记录一个左转的标示符”L”。这样存储器中的标示符就变成了“RL”。p5.5 第四个转弯机器人继续前进将遇到“右转路口”，前面介绍过，这种只有一种方向选择的路口不属于我们定义的“岔路口”，所以这里机器人不记录转弯标示符“R”。接下来又是死胡同类型的岔路口，机器人仍旧做掉头动作。同时在存储器中记录一个掉头标示符“U”，这个时候存储器中的标示符就变成了“RLU”。如图p5.6所示。p5.6 第四个转弯机器人掉头回来，