2022年迷宫搜索 .pdf

第六章迷宫搜索为了找到火焰，我们要让机器人做迷宫搜索，不管使用什么策略，左手法则和右手法则都是迷宫搜索的基础，我们至少要实现其中一种行走方法。在这里作者向大家推荐的方案是机器人左右手法则都会走，这样机器人灭火和回家的效率就比较高，在这里中间朝前的红外传感器是左右手法则共用的传感器。本章我们只是简单介绍一下迷宫算法，关于迷宫法则的深入讨论，作者把它放在第九章再作论述。61 左手法则所谓左手法则就是机器人把左边的障碍物看成是参照物，机器人贴迷宫左侧的墙壁实现行走。要实现左手法则需要用到红外避障传感器，最常见的是用两个或三个传感器的实现方法，两个传感器来实现左手法则调试最简单。三个传感器的实现方法调试比较难，三个以上传感器的用法行走速度不一定就快，传感器之间相互干扰很难解决，在这里我们不作介绍。一个传感器的实现方法稳定性低，实战中很少有人使用。611 三个传感器实现左手法则的算法三个传感器实现左手法则可以使用两个传感器类似的方法，就是“看到墙壁，往外走，看不到墙壁往里走。”在这里我们给出比较典型的算法，下面的算法调试比较难，调试得不好，机器人容易做出自向矛盾的微动作，表现为停步不前，或者在某处发抖。在这里提供的算法原理是：前面看到右转，左45度看到右转，左边看到前进，什么也没有看到转左弧。图 6-1 图 6-1 是三个传感器走左手常见的安装方法，根据调试经验，左传感器也向前偏转一定角度，这样设计，机器人走迷宫的速度会快一些。前红外传感器观察范围20cm 左右，左传感器观察范围 20cm 左右，左 45 度传感器观察范围10cm 左右，红外的观察范围、角度和下面面的马达参数一样，都需要调节以适应自己的机器人。假设纳英特机器人前面传感器接13 口，左 45 度接 12 口，左红外接 11口。具体参考代码如下：Void migong_left()If(digital(13)=1)/前面看到，原地右转 名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 10 页 -motor(0,40);Motor(1,-70);elseIf(digital(12)=1)/左上角 45 度看到，原地右转 motor(0,40);Motor(1,-70);elseIf(digital(11)=1)/左边看到，前进 motor(0,60);Motor(1,60);)Else/什么也没有看到，转左弧 motor(0,-80);Motor(1,80);motor(0,80);Motor(1,80);612 两个传感器实现左手法则的算法不管你使用那个公司的产品，左手法则都可以用两个传感器实现，如图6-2 是两个传感器走左手的常见安装方法。一个传感器在机器人前面中间位置，另一个装在机器人中间位置，朝左前45 度偏转，观察距离10-15 厘米。左手法则的基本原理是看到墙壁，往外走，看不到墙壁往里走。假设纳英特机器人前面传感器接13 口，左 45 度接 11口。则具体参考代码如下：图 6-2 Void migong_left()名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 10 页 -If(digital(13)=1)/前面有墙原地右转。Motor(0,40);/右转时间长，前面有墙壁不前进，否则要撞墙。Motor(1,-100);Sleep(0.05);Else If(digital(11)=1)/左边有墙原地右转并前进。Motor(0,40);/右转时间长。Motor(1,-100);Sleep(0.05);Motor(0,70);/前进无延时，否则要撞墙。Motor(1,70);Else/什么也看不见，划左弧。Motor(0,-80);Motor(1,80);Motor(0,80);Motor(1,80);上面我们给出了两个传感器实现左手法则的一种算法，给出这种算法是为了说明两个传感器走左手的原理，在第二章我们论述了把迷宫行走和地面检测结合起来的算法，为无火不进房间的实现提供了基础。613 一个传感器实现左手法则的算法一个传感器走左手法则的算法本身意义不大，我们在这里提供算法只想说明一个问题，就算是到了很困难的程度，我们也要有解决问题的信心。实现的原理和 2 个传感器一样，这里的算法我们把一个传感器当做两个来用，传感器安装在机器人前左45 度角，接 12 号口,红外的观察距离是10-15 厘米左右。图 6-3 名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 10 页 -int m=0;void main()/主程序 while(1)migong_left();void migong_left()/左手法则 if(digital(12)=1)/如果传感器看到墙壁 m+;if(m30000)m=0;if(m%3)30000)m=0;if(m%3)2)/3 个时间片内 2 个时间片左转 motor(0,-70);motor(1,40);sleep(0.03);else/3个时间片内 1 个时间片左转并前进 motor(0,-70);motor(1,40);sleep(0.03);motor(0,50);motor(1,50);名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 10 页 -else/如果传感器没有看到墙壁 motor(0,40);/向右转弧线motor(1,-40);motor(0,80);motor(1,80);63 常用搜索策略介绍搜索策略一般可以分为两大类，一类是常规的搜索法，使用左手法则和右手法则为基础，一般搜索的顺序是1-2-3-4 房间或按照 4-3-2-1 的房间顺序搜索。另一类非常规的搜索法，主要有一技必杀和固定路线两种。以下所讲的方法不存在哪种最好的问题，如果世界上有最好的算法，也就没有人用其他方法了，比赛也没有意义了。4.3.1 常规搜索法431.1 进房间搜索法进房间搜索法就是左手法则或右手法则的简单应用，是入门阶段的常用方法，算法简单易学，速度慢，多出现在刚开始开始机器人活动的地方，现在使用的人已经很少，适合刚入门的小学生使用。如左手法则在起点朝前启动，只能搜索到 1、2、3 号房间，朝右启动，只能搜索到4 号房间，但它是一切算法的基础，是所有灭火机器人学习者必须掌握的一种方法。431.2 不进房间搜索法简单搜索法不管房间内有没有火都要进去绕，所以速度慢，无火不进房间是对简单搜索法的改进。它结合白线检测，按照房间把迷宫搜索分为几阶段，到了房间门口就停止脚步，检测里面是否有火焰，如果有火进去灭火，否则，顺序搜索下一个房间。不进房间搜索法实际上是对简单迷宫法则的改进，简单的迷宫法则把墙壁当作参照物来决定下一步的动作，而不进房间搜索法实际上是利用墙壁和门口白线参照物来决定下一步的动作。根据利用门口白线的方法不同，右可以分为退房法和旋转法两大类。名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 10 页 -(1)退房法对无火不进房间的机器人来说，又存在两种实现策略，比较容易的是退房法，机器人在房间门口如果判断出房间内没有火焰，就后退出房门，然后到其他房间搜索。例如从4 号房间出来，后退一定时间或后退到后面的传感器看到墙壁，然后走右手法则进3 号。退房法根据后退的方法不同，又可以分为时间法和条件法两类，时间法就是后退一定的时间，然后转动一定角度，接下去搜索其他房间。时间法比较容易掌握，但很难把握后退时间的长短，如果后退时间太长，有撞墙的可能，会降低迷宫行走的速度。后退时间太短，机器人找不到参照物，会出现转圈的现象。条件法就是在机器人后面安装1-2个传感器，在传感器看到墙壁时，就停止后退。我们也可以结合使用2 种方法，先后退一段时间，然后后退到传感器看到墙壁，这种方法稳定性很高，我们在下面的例子中就有这一方法的介绍。(2)旋转法旋转法是利用门口白线和墙壁作为迷宫行走参照物的实现方法，旋转法的实现要比退房法难，速度也更快。旋转法可以在旋转的同时检测火焰，节省了检测时间，由于机器人在转动的过程中容易发现火焰，所以检测火焰的效率更高。旋转法速度比退房法快点，但调试难度大。根据旋转的角度，旋转法有半旋法和全旋法两类。机器人进行 90 度旋转的方法叫半旋法，180度旋转的方法叫全旋法，我们在后面的章节向大家介绍的是半旋法实现的方案。根据旋转方向不同可以分为同向旋转法和反向旋转法。机器人进门时处于旋转状态，如果旋转法旋转的方向和进门旋转的方向相同，我们称之为同向旋转法。如果旋转法旋转的方向和进门旋转的方向相反，我们称之为反向旋转法。4.3.2 特殊搜索法特殊搜索法是用的人比较少的方法,所有特殊搜索法共同特点是速度快,调试难度大,稳定性低.。这类方法中著名的方法有一技必杀法和时间法两种。(1)一技必杀法一技必杀法并非主流算法，具体实现也有很多方法，共同特点是直接进入有火房间灭火，给人一种速度很快的感觉。但由于有房间系数的存在，该方法不见得能提高多少成绩，根据现在的教育部规则，对中学组根本就不合适。作者是反对该方法的应用，认为该方法阻碍了算法的发展。该方法适合小学组应用，但中学组应用的人也不少，可能是上一届的同学根据规则发现该方法简单有效，规则修改后，下一届同学还去参考的缘故。既然用的人比较多，我们在这里也介绍其中的一种算法。由于规则并没有规定机器人的高度（实际上规则上已经考虑到一技必杀的效果不可能很好），在机器人中间竖一根比墙壁高的天线，上面安装 3 个火焰传感器，机器人在起点朝前启动，1 个传感器朝 1 号房间方向，另 1 个传感器朝 4号房间方向，第三个传感器朝前，如果朝 1 号房间方向的传感器发现火焰，走左手灭 1 号，如果朝 4 号房间方向的传感器发现火焰，走右手灭4 号，1、4 号都没有，机器人朝前走到2 号房间墙壁，如果第 3 个朝前的传感器发现火焰，走右手灭 2 号，否则走左手灭 3 号。本方法由于直接奔向火焰，给人很快的感觉，所名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 10 页 -以学生特别喜欢.。目前国内灭火速度最快的一些队，如宋诏桥小学现在也应用该方法，1、4号的灭火时间都是2 秒多，2、3 号的灭火时间是3 秒多。但该方法的调试很难，在2006 年全国比赛上，宋诏桥小学的学生就是调试时间超过2分钟，错过了 2 轮比赛，从而名落孙山。作者认为现在的规则不合理是导致部分强队使用一技必杀法的原因，如果把房间系数改为1 0.6 0.4 0.3 可能更加合适。(2)时间法时间法又叫固定路线走法,是所有搜索策略中速度最快的一种，也是调试最难，成功率最低的一种方法。固定路线走法的特点是不用或少用红外避障传感器来走迷宫。根据红外避障传感器接受到的信号，机器人可以随时调整身体姿态，所以用红外避障传感器走迷宫的方法比较稳定，是主流走法。红外避障传感器的优点正是它的缺点，如果调试不好，机器人就会作出自相矛盾的微动作，表现为机器人在某处（特别是角落）发抖，情况严重的甚至会30 秒静止不动。角落容易出问题是因为红外传感器发出红外线，在角落处多次反射后被其他红外收到，干扰了机器人的判断，这种情况随传感器数量的增加会越来越严重，我们向大家推荐2个传感器的迷宫走法也是这个道理。固定路线走法很容易受内外环境变化的干扰，特别是电池电量的多少和地面光滑程度对成功率影响很大。有的机器人在自己实验室里每次成功，到了比赛场地就每次失败，多半是使用了固定路线走法。该方法并非主流算法，作者是坚决反对该方法的应用，认为该方法稳定性太低，阻碍了算法的发展。虽然该方法稳定性低，但也有高手应用，如2006 年浙江省中学组灭火冠军启新学校就是用这种方法。他们用指南针来引导机器人行走，速度很快，但稳定性低，拿冠军一半靠运气，到了全国赛就无所作为。名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 10 页 -