logo资料库

电脑鼠算法电脑鼠算法.doc

发布时间：2022-05-29 发布人：admin 分类：说明书 资料大小：0.40M 资料格式：doc 举报 版权申诉
第1页 / 共8页
第2页 / 共8页
第3页 / 共8页
第4页 / 共8页
第5页 / 共8页
第6页 / 共8页
第7页 / 共8页
第8页 / 共8页
资料共8页，全文预览结束
    一种电脑鼠走迷宫的算法 ■ 上海商学院 张新谊 ───────────────────────────────────────────────────────────────── 电脑鼠（Micromouse）实际上是一个由微处理器控制的，集感知、判断、行走功 能于一体，能够自动寻找最佳路径到达目的地的小型机器人。国际电工和电子工 程学会（IEEE）每年都要举办一次国际性的电脑鼠走迷宫竞赛。本文介绍一种能 满足 IEEE 学会颁布规则的电脑鼠走迷宫算法。 摘 要摘 要 ───────────────────────────────────────────────────────────────── 关键词 ───────────────────────────────────────────────────────────────── 运行时间 迷宫时间 碰触 排障时间 电脑鼠的英文名称为 Micromouse，实际上是一个由微处理器控制的，集感知、判断、 行走功能于一体，能够自动寻找最佳路径到达目的地的小型机器人。它可以在“迷宫”中自 动感知并记忆迷宫地图，通过一定的算法，寻找一条最佳路径，以最快的速度到达目的地。 1997 年，在美国举办了第一届电脑鼠竞赛，随后，电脑鼠竞赛传入欧洲，首届欧洲电脑鼠 竞赛于 1980 年在伦敦举办，之后英国的电脑鼠比赛便由电子工程协会（IEE）主办。1980 年 11 月日本电脑鼠协会（JMA）在东京举办了第一届竞赛，此后，日本每年都要举办一届 电脑鼠竞赛。我国台湾也于 1986 年 10 月举办了首届电脑鼠比赛。现在国际电工和电子工程 学会（IEEE）每年都要举办一次国际性的电脑鼠走迷宫竞赛，各国选手报名踊跃，主要是大 学生，为此部分大学还开设了“电脑鼠原理和制作”选修课程。 由于电脑鼠要由参赛选手自己设计制作，不仅要求选手具有嵌入式系统应用﹑传感器﹑ 控制技术等多方面的知识、经验和实践能力，还要求具有编写寻找最佳路径算法的能力。由 于迷宫路径设置是随机的，因而竞赛难度较大，极富挑战性。这对培养和提高学生的创新精 神和实践能力，有着深远的意义。2007 年 5 月— 8 月将举办由我国部分地区（上海及长三 角地区）参加的首届电脑鼠邀请赛。 1 电脑鼠走迷宫的规则 有关电脑鼠国际比赛的详细规则，可参阅国际电工和电子工程学会（IEEE）的官方网 站：http://www.eece.maine.edu/sc2006/2006MicromouseRules.pdf 。 迷宫的规格 迷宫由 256 个方块（单元）组成，每个方块的大小为 18 厘米见方，排成 16 行×16 列。 迷宫的隔墙板沿方块的四周布设，形成迷宫通道。隔墙板高 5 厘米﹑厚 1.2 厘米，因此迷宫 通道的实际宽度是 16.8 厘米。隔墙板的两个侧面是白色的，顶部是红色的。迷宫的地板由 木质材料做成，涂上没有反光的黑漆。隔墙板的侧面和顶部对红外线有反射特性，而地板则 对红外线有吸收特性。竞赛起始点可设在迷宫的任何一角，其三面要有隔墙；竞赛的终点设 在迷宫的中央，有四个方块那么大小。图一为一个实际的电脑鼠竞赛用的迷宫照片。 图一 电脑鼠竞赛用的迷宫照片 1
    1.2 电脑鼠的规格 电脑鼠要求由参赛者自制，使用电源为能源，不能使用其它可燃物为能源。电脑鼠结构 高出隔墙部分的长宽几何尺寸应不大于 25×25 厘米，对高度没有限制。一个完整的电脑鼠 应包含有机身、电源、传感器、微处理器、马达及驱动等部分。电脑鼠的传感器可分为三组， 分别用来感知前、左、右三个方向是否已靠近宫壁，并将所获得信息传送给微处理器进行处 理。微处理器要完成多种信息的处理，如路径、迷宫地图、行走距离、马达控制等，并要能 够作出判断。在马达的控制下，电脑鼠能够完成直行、转弯、掉头以及加减速等动作。通常 采用左右独立的马达驱动和控制，以使微处理器的控制更加灵活。图二为一个实际参加竞赛 的电脑鼠样例照片。 1.3 竞赛的规则 图二 电脑鼠样例照片。 电脑鼠的基本功能是从起点开始走到终点，这个过程称为一次“运行”，所花费的时间 称为“运行时间”。从终点回到起点所花费的时间不计算在运行时间内。电脑鼠从第一次激 活到每次运行开始，所花费的时间称为“迷宫时间”。如果电脑鼠在比赛时需要手动辅助， 这个动作称为“碰触”。竞赛使用这三个参数，即运行时间﹑迷宫时间和碰触，从速度﹑求 解迷宫的效率和电脑鼠可靠性三个方面来进行评分。 电脑鼠的得分是通过计算每次运行的“排障时间”来衡量的。所谓排障时间是这样计算 的：先将迷宫时间的 1/30 加上一次运行时间，如果这次运行结束以后电脑鼠没有被碰触过， 那么还要再减去 10 秒的奖励时间，这样得到的就是排障时间。电脑鼠在迷宫中的停留或运 行的总时间不可超过 15 分钟，在限时内允许运行多次，允许取其中最短的排障时间作为参 赛的计分成绩。当然，排障时间越短越好 例如：一个电脑鼠在迷宫中运行时间为 4 分钟（240 秒）没有碰触过，迷宫时间使用了 20 秒，这次运行的排障时间就是：20 秒+（240 秒×1/30）－ 10 秒 = 18 秒。 电脑鼠在迷宫通道内行走时不能碰到隔墙板，遇到岔道口时要能够自动作出方向选择。 本文规定：如果进入迷宫是为了进行探测和记忆，这次运行就称为“试跑”；如果进入迷宫 是根据先前的记忆和经验，按照智能算法确定最佳路径，并以最快的速度到达目的地，这次 运行就称为“冲刺”。 2 电脑鼠走迷宫的算法 2.1 探测策略 电脑鼠走迷宫可以采用全迷宫探索策略，即将迷宫的所有单元均搜索一次，从中找出最 佳的行走路径。这种策略需要有足够的时间或探测次数，但在 IEEE 竞赛规则中每场竞赛只 有 15 分钟的时间，因此是不可能的。另一种方法是部分迷宫探索策略，即在有限的时间或 探测次数下，只探测迷宫的一部分，从中找出次最佳的路径，显然只能采用这种策略。 电脑鼠在一巷道内行走，如果最后无路可走，则该巷为死巷。电脑鼠在任一单元内，可 能的行走方向最多只有三个（前、左、右），如果有二个或二个以上的可能行走方向，称为 交叉，遇有交叉时，由于有多个可以行走的方向，在行走方向的选择上，可有下面的几种选 择法则： 2
     右手法则：遇有交叉时，以右边为优先的前进方向，然后是直线方向、左边方向。  左手法则：遇有交叉时，以左边为优先的前进方向，然后是直线方向、右边方向。  中左法则：遇有交叉时，以直线为优先的前进方向，然后是左边方向、右边方向。 与此类似的还有中右法则。  乱数法则：遇有交叉时，取随机值作为前进方向。  向心法则：由于终点在迷宫的中心，遇有交叉时，以向迷宫中心的方向为优先的前 进方向。 2.2 标记 为了记忆迷宫的详细信息，需要对迷宫单元的位置进行线路标记。全迷宫共有 16×16 个单元组成，可采用二维坐标方式标记，即用每个单元的 XY 坐标表示，如起点可标记为（0， 0），终点为（7，7）。此外，还需要对迷宫单元的可行进方向进行标记，可采用绝对方位或 相对方位二种方式。 绝对方位：这是一种与电脑鼠行进方向无关的标记方式，以一个四位的二进制数，分别 表示“东”﹑“西”﹑“南”和“北”四个方向。以 1 表示允许行进（无墙壁），0 表示不 允许行进（有墙壁）。 相对方位：这是一种与电脑鼠行进方向有关的标记方式，以一个三位的二进制数即可实 现标记，分别表示“前”“左”“右”， 以 1 表示允许（无墙壁），0 表示不允许（有墙壁）。 2.3 阻断 在电脑鼠试跑过程中或在最后冲刺时，需要对部分路径进行“阻断”，即在发现某条路 径是死路（只有入口而无出口）时，在该路径的入口处（一般是交叉点）设置标记，即将入 口的线路标记由 1 改为 0。 2.4 试跑 试跑是获得迷宫地图（各单元路线标记）的唯一方法，因而应在规则允许的情况下，尽 可能多的获得迷宫信息，为最后的冲刺准备尽可能多的信息。在试跑过程中，要对经过的单 元进行线路标记，同时还要选择一个合适的探测策略。 下面以 1/4 迷宫为例进行说明。假设迷宫图布局如图三所示，共有 8×8=64 个单元，起 点在左下角（Start），终点在右上角（End）。选用一个 8×8 的矩阵 map 保存迷宫地图信息， 矩阵的每个元素为 1 个字节，高 4 位表示探测到的可行进路径，以绝对方位标记，次序为“北” ﹑“东”﹑“西”﹑“南”。低 4 位记录自起点的交叉点的个数。探测策略采用右手法则， 在初始状态，矩阵 map 各元素的值均为 FFH，00H 表示死巷。 在探测过程中，如果下一个可行进的单元已经探测过（对应的矩阵元素值非 00H 或非 FFH），只有在发现死巷时，才对 map 中的数据进行修改。对于其它情况，无论探测结果与 矩阵中对应元素存储的信息是否一致，均不修改存储的信息。对于复杂的迷宫，往往不能仅 图三 1/4 迷宫 3
    使用一种探测策略，而要综合考虑，如增加向心法则。当发现交叉点时，应将该单元坐标和 线路特征保存（如入栈），再分析可行的下一个单元是否已经探测过，如果均未探测过，则 根据探测策略，选择一方向进行探测。如果部分单元已经探测，则选择未被探测的单元进行 探测。遇有死巷，应返回最近的交叉点，同时将死巷阻断，修改入口单元的相应数值。 图四为首次探测时电脑鼠的行走路线示意，电脑鼠在探测过程中，将获得行走过的各单 元的线路特征，表一为电脑鼠探测到（5，0）单元时的二维表（以十六进制表示，高 4 位为 线路标记，低 4 位为交叉点数）。 图四 首次探测行走路线 7 6 5 4 3 2 1 0 FFH FFH FFH FFH FFH FFH FFH end FFH FFH FFH FFH FFH FFH FFH FFH 30H 50H FFH FFH FFH FFH FFH FFH 90H 90H FFH FFH FFH FFH FFH FFH 90H D1H FFH FFH FFH FFH FFH FFH 90H 90H FFH FFH FFH FFH FFH FFH 90H B2H FFH FFH FFH FFH FFH FFH 80H C0H 60H 60H 60H 60H FFH FFH 0 7 1 6 表一 探测到（5，0）时的 map 二维表 2 3 4 5 从图四可以看出，该巷为一死巷，当电脑鼠探测到（7，0）时，发现是死巷，将按原路 返回到最近的交叉点（1，1），进行阻断，即将向“南”修改为不可行，并修改交叉点的数 据，由原值 B2H 改为 90H，死巷中的数据全写零，并继续完成探测，最后得表二 。 7 6 5 4 3 2 1 0 FFH FFH FFH FFH FFH FFH FFH end FFH FFH FFH FFH FFH FFH FFH B0H 30H 50H FFH FFH FFH FFH FFH B0H 90H 90H FFH FFH FFH FFH FFH 90H 90H D1H FFH FFH FFH FFH FFH 90H 90H 90H FFH FFH FFH FFH FFH A2H 90H C0H 60H 60H 60H 60H 60H 90H 80H 00H 00H 00H 00H 00H 00H 00H 0 7 4 6 1 3 2 5 表二 执行阻断后的二维表 4
    根据 IEEE 电脑鼠竞赛规定，当电脑鼠到达终点后，可进行返回探测，从而获得更多的 迷宫地图信息。图五为返回探测时的行走路径。在返回探测中，未发现死巷，返回起点，探 测后的结果如表三。 图五 返回时的探测路径 7 6 5 4 3 2 1 0 50H 60H 60H 60H 60H 60H 30H end C0H 60H 70H FFH FFH FFH C0H B4H 30H 50H D2H FFH FFH FFH FFH B3H 90H 90H C0H 60H 30H FFH FFH 90H 90H D1H 60H 71H A0H FFH FFH 90H 90H 90H FFH FFH FFH FFH FFH A2H 90H C0H 60H 60H 60H 60H 60H 90H 80H 00H 00H 00H 00H 00H 00H 00H 7 2 3 0 1 4 5 6 表三 返回探测后的二维表 图六 第二次探测路径 第二次探测如图六，在（3，3）和（2，5）分别执行阻断，将获得二维表四 5
    7 6 5 4 3 2 1 0 60H 60H 60H 30H end 50H 60H 60H 72H 60H 30H C0H B4H C0H 60H 70H 30H 50H 90H 00H 00H D3H HHH B3H 90H 90H C0H 60H 30H 90H HHH 90H 30H A0H 90H HHH 90H 90H D1H 60H A2H 90H 90H HHH 00H 00H C0H 60H 90H C0H 60H 60H 60H 60H 60H 90H 00H 00H 00H 00H 00H 80H 00H 00H 2 3 6 7 表四 第二次探测后的二维表 4 5 0 1 2.5 数据补全 由于不可能将所有的单元均探测到，在有了一定的数据基础上，就可以实现数据补全了。 数据补全，就是对未探测到的单元，通过周围已有的相数据，可进行补充的一种方法。方法 是寻找单元数据为 FFH 的单元，如果该单元的“东”﹑“西”﹑“南”﹑“北”四个相邻 的单元均为非 00H 或 FFH，分析“东”﹑“西”和“南”﹑“北”四个单元的二组数据， 看是否有指向该单元的可行方向，如果有，在该方向是相通的，可对数据进行大胆的假设。 对照表四，（6，5）是未探测过的，其值为 FFH，分析与之相邻的（5，5）（7，5）和 （6，6）（6，4）二组数据，（6，4）的数据为 FFH，放弃在南北方向上的补全，考虑东西 方向，（5，5）向东是可行的，（7，5）向西是可行的，因而可以大胆设想，（6，5）是东西 可行的，数据可设为 60H，将 60H 填入表四，就得到补全后的表五。 7 6 5 4 3 2 1 0 60H 60H 60H 30H end 50H 60H 60H 72H 60H 30H C0H B4H C0H 60H 70H 00H 00H D3H 60H B3H 30H 50H 90H 90H 90H C0H 60H 30H 90H HHH 90H 30H A0H 90H HHH 90H 90H D1H 60H A2H 90H 90H HHH 00H 00H C0H 60H 90H C0H 60H 60H 60H 60H 60H 90H 00H 00H 00H 00H 00H 80H 00H 00H 2 3 6 7 表五 补全后的二维表 4 5 0 1 2.6 等高表 经过有限次的探测、阻断与补全后，已经可以得到描述迷宫图线路的二维表，虽然不 是全部，但已经是部分或大部分，其中可能包含了若干条可以到达终点的路径，为了寻找到 达终点的路径，需要制作等高表。等高表是指已探测的各单元距离起点的步数（一个单元为 一步），起点的步数为 0，表六为通过表五所获得的等高表。等高值以十进制数表示。 19 18 5 4 3 2 1 0 20 17 6 7 8 9 10 21 16 15 14 9 11 22 17 13 10 12 23 18 12 11 13 24 19 20 21 22 23 14 25 26 21 24 15 28 27 22 19 18 17 16 表六 等高表 6
    2.7 可行路径 在等高表中，可行路径上任一单元到起点的步数都是已知的，按从大到小的次序，可以 返回起点。按从小到大的次序，可到达终点，这样的可行路径可能不止一个，而是多个。可 行路径的查找，从起点开始，在允许前进的方向上，按比当前等高值高 1 的方向前进，直到 终点。有时可能会遇到下一单元的等高值小于当前值（如（6，2）点）或比当前值高 1 以上 的情况，如果当前单元不是交叉点，可以不予理会，进入下一个单元，按等高值增加的方向 查找。如果是交叉点，则要进行趋势分析，找出等高值就增加的方向。舍弃等高值减少的方 向。 图七 是根据表六得到的所有可行路径，共有 A、B、C、D 四条。 2.8 可行路径的步数 图七 所有的可行路径 可行路径的步数，指由起点到达终点，所经过的单元数，可由等高表计算得出。 线路 A：由（0，0）到（7，4），19 步，（7，4）到（7，5）1 步，（7，5）到（7，6）1 步，（7，6）到（7，7），28-27=1 步。总计=19+1+1+1=22 步。 线路 B：由（0，0）到（6，2），24 步，（6，2）到（7，2）1 步，（7，2）到（7，4）,19-17=2 步，（7，4）到（7，5），1 步, （7，5）到（7，6），1 步。（7，6）到（7，7），28-27=1 步, 总计=24+1+2+1+1+1=30 步。 同理可得线路 C：22+1+1=24。线路 D：28。 2.9 最佳路径 电脑鼠要在最短的时间内完成由起点到终点的冲剌，路径的选择至关重要，步数少的路 径，是最佳路径的条件之一，但不是唯一条件。考虑电脑鼠在拐弯时，同样需要时间，所以 要对拐弯次数加权后加到步数中得到加权步数。 加权步数=步数+拐弯次数×拐弯权重 拐弯次数：一个 90 度的拐弯算一次，一个 180 度的拐弯算二次。 拐弯权重：这是一个对结果有重要影响的参数，要结合电脑鼠的结构和试跑确定。如果 电脑鼠无加速功能，是以恒速前进，其值可选 0.4~1.0 之间，如果电脑鼠有变速功能，可根 据变速的范围，其最值可适当增加。表 7 与表 8，分别列出了不同的拐弯权重，对加权步数 的影响。 拐弯次数 拐弯权重 加权步数 线路 A B C D 步数 24 22 35 30 29 24 34 28 表七 拐弯权重为 0.5 时，各线路的加权步数 0.5 0.5 0.5 0.5 4 10 10 12 名次 1 4 2 3 7
    线路 A B C D 4 10 10 12 拐弯次数 拐弯权重 加权步数 步数 28 22 45 30 39 24 46 28 表八 拐弯权重为 1.5 时，各线路的加权步数 1.5 1.5 1.5 1.5 名次 1 3 2 4 从表七与表八中，已经明显看出了拐弯权重对加权步数的影响，线路 B 与线路 D 的排 名次序发生了逆转。 3 结论 本文详细介绍了一种电脑鼠走迷宫的算法，实践表明该算法可以基本满足电脑鼠走迷宫 竞赛的要求。电脑鼠走迷宫已有的算法很多，新算法也层出不穷。本文仅为抛砖引玉，以供 同行参考。 参考文献 1. 林家德 詹耀仁 电脑鼠制作宝典 台湾益众资讯有限公司 2. 吴一农 林家德 快速穿越 8051 单晶片 台湾益众资讯有限公司 3. http://www.eece.maine.edu/sc2006/2006MicromouseRules.pdf ，2006 年 IEEE 学会 公布 2006 年电脑鼠走迷宫竞赛规则的网址 8
    分享到：
    赞 收藏

    相关推荐

    资料库

    开发技术

    共收录19306份资料，累计14个分类，关注成员有19位，主要包括：Actionscript,Javascript,PHP,VB,Perl,Delphi,Python,C#,C,Java,C++,Web开发,硬件开发,其它

    热门标签

    Actionscript Javascript PHP VB Perl Delphi Python C# C Java C++ Web开发 硬件开发 其它

    最新资料