2． 2
迷宫搜索算法的设计
为了讨论方便， 这 里 使 用 位 差 值。 所 谓 位 差 值 就 是 格 子 （ cell） 距离迷宫中点的最小格子数， 目标的位差值是 0 。 每个格 子的位差值如图 2 所示。
图2
每个格子的位差值
当电脑鼠到达一个格子坐标时， 应该根据传感器检测结果 16］ ［ 16］来保 记录下当前格子的隔墙资料， 可以使用 mapblock［ 存整个迷宫隔墙资料， 表 1 所示隔墙信息的存储方式 。 隔墙资 0 ， 即 料全部初始化为 凡是走过的迷宫格至少有一方没有隔墙， 隔墙资料不为 0 。这样就可以通过单元格存储的隔墙资料是否 为 0 来确定该单元格是否走过 。
表2 迷宫类型 Unpar Unpar Unpar ITB ITB 图4 死路示意图 算法性能比较 搜索步数 +∞ 60 56 +∞ 71 41
搜索算法 沿墙 DFS 位差值 沿墙 DFS 位差值
对于一些特殊的迷宫， 电脑鼠在搜索过程中， 若从某点出发 经过一些点又回到了该点则被标记为环 。可以通过算法来判断 该环是否为封闭循环路径 。 当电脑鼠到达某点， 发现该点以前 已经走过则检查前一个格子， 直到发现某个格子有多路选择 。 判断该格子是否为当前格子， 如果是， 则标记封闭循环路径内的 格子为死路； 如果不是， 则表明不是封闭循环路径 。 如图 5 所 B、 C、 D、 E、 F 和 G 组成了封闭循环路径。当电脑鼠从 G 到达 示， B 时， 因为检测到第二次经过 B， 则检测前一个格子 G， 发现格子 G 只有一路可以走， 并且只能移动到 B。重复检测以前的格子， 直到遇到有多路选择的格子， 即本例中是格子 B。 因为该格子 C， D， E， F 和 G） 是 所以可以得到格子（ B， 是电脑鼠的当前位置， 设置这些格子的 marking 为真。 封闭循环路径， 通过标记死路和封闭循环路径， 该算法不会进入死循环或 确保了该算法的可行性 。 重复走过的路径，
表1 变量位 bit0 bit1 bit2 bit3 墙壁资料存储方式 备注 1 ： 有路； 0 ： 有墙 1 ： 有路； 0 ： 有墙 1 ： 有路； 0 ： 有墙 1 ： 有路； 0 ： 有墙 图3 根据位差值产生的一条路径
代表的绝对方向 上方 右方 下方 左方
当有超过一条路可以走时， 则执行多路程序。 多路程序需 准则可以包括格子走过的次数 、 位差 要根据一些准则选择路径， 值、 直走还是拐弯等。 如果电脑鼠有两个或三个可选方向， 首先要判断的准则是 相邻格子是否走过， 这可以通过该格子的隔墙资料来确定 。 一 种可能性是至少有一个格子没有走过 。 这样的话， 电脑鼠选择 的下一个格子应该是没有走过的格子 。但是如果有超过一个格 子未走过， 则需要根据位差值进一步决定 。 位差值准则是通过 选择具有最小位差值的相邻格子作为可选路径的方法 。如果有 两个格子具有相同的最小位差值， 则选择直走。 向前移动比左 右转弯的优先级要高， 这是因为电脑鼠直走比转弯的速度更快 。 另一种情况是所有的格子都走过， 电脑鼠则选择相邻格子中走 过次数最小的格子进入 。若相邻格子走过的次数相同则再判断 位差值， 若还相同的则选择直走 。
Abstract Micromouse is actually an autonomous mobile robot （ AMR） ． The micromouse finds the optimal path to get to the destination area which is located in the center of labyrinth without any information of the layout． The whole process is an automatic search process． In this paper we studied and realised the potential valuebased path searching algorithm and contour mapbased optimal path algorithm，and also made the improvement on the ability of micromouse’ s tasks accomplishment． Keywords Maze solving algorithm Micromouse robot Potential value Contour map Optimal path
2． 6
实验测试搜索算法
为了评估该算法， 我们在同一迷宫里运行了三个不同的算
法， 即 沿 墙 的、 深 度 优 先 探 索 （ DFS ） 和 基 于 位 差 值 的 搜 索 算法
［5 ］
。
在德州仪器 Unpar 迷宫和 ITB 的迷宫测试中。 使用基于位 差值的搜索算法电脑鼠到达了目标点， 而使用其他两个算法会 导致不同的现象。沿墙算法未能使之到达终点， 而深度优先搜 索算法行驶距离更长。如表 2 所示。
［1 ， 2 ］
竞赛的规则
。
电脑鼠的基本功能是从起点开始走到终点所花费的时间称 “ 。 电脑鼠从第一次激活到运行开始所花费的时 为 运行时间 ” “迷宫时间” 。电脑鼠在比赛时手动辅助的动作称为 “碰 间称为 触”
［1 － 3 ］
电脑鼠搜索路径应该是在没有人工干预的情况下自主完成 的， 也就是说， 需要运用搜索算法使电脑鼠自主行走 。搜索算法 根据电脑鼠当前的位置确定下一步， 以迅速到达 的主要目的是， 迷宫的中心并返回， 同时利用搜索迷宫时得到的隔墙信息找出 从起点到终点并返回的最优路径 。
2． 3
移动策略
电脑鼠的主要行为就是能够在各种不同情况的迷宫中作出
分别对应这三种处理程序： 死路程序、 单路 决定。有三种情况， 程序和多路程序。 当电脑鼠面对 3 面墙时， 需要执行死路程序。 死路程序会 marking 将当前所处格子的 标记为真， 表示下次搜索时不可进 并且电脑鼠向后转 180 度。如图 3 中点 G 所示， 电脑 入该格子， 鼠在 G 点面对上、 下和右 3 面墙。 当只有一条路可以走时， 执行单路程序。 单路程序会选择 唯一的可前进路径。如图 3 所示， 从 A 到 D， 从 D 到 E 和从 G 到 F 之前的一个单元格， 执行单路程序。
DESIGNING AND IMPLEMENTING A MAZE SOLVING ALGORITHM FOR MICROMOUSE
Wang Fenglin Wang Yihuai
（ School of Compoochow University，Suzhou 215006 ， Jiangsu， China）
1
1． 1
电脑鼠走迷宫的规则与流程
迷宫、 电脑鼠的规格
。在试跑时， 需要按照一定的算法得到隔墙信息， 并到达终 跑” 点， 即迷宫搜索算法； 在搜索结束后根据搜索所获得的隔墙信 按照最优路径算法确定最佳路径， 并以最快的速度到达目的 息， 。 冲刺后还可以继续多次试跑和 地， 这次运行被称为“冲刺 ” 冲刺。
0
引
言
电脑鼠必须自成独立系统 。 电脑鼠的长和宽限定在 25cm × 25cm。对电脑鼠的高度没有限制 。
1． 2
“电脑鼠” （ micromouse） ， 所谓 是使用嵌入式微控制器 、 传感 器和机电运动部件构成的一种智能行走装置的俗称， 它可以在 “迷宫” 中自动记忆和选择路径， 寻找出口， 最终达到所设的目 的地
迷宫由 256 个方块（ 单元） 组成， 每个方块的大小为 18 厘米 见方， 排成 16 行 × 16 列。迷宫的隔墙板沿方块的四周布设， 形 成迷宫通道。如图 1 所示。
2
迷宫搜索算法
当电脑鼠移动时， 电脑鼠要知道自己所处的位置， 因此首先
需要定义电脑鼠的坐标和方向， 然后设计基于位差值的搜索
收稿日期： 2009 － 04 － 05 。 王凤林， 硕士生， 主研领域： 嵌入式系统 图1 全迷宫结构 应用， 网络技术。
2． 4
死路的标记和封闭循环路径的避免
死胡同程序（ 路 = 0 ） 。 图 4 中 D 点， 只有一条可能的路可 电脑鼠三面都围着墙时 。 单元格 D 被标记为真， 电脑鼠 以走， 向后转 180 度。当遇到死路时， 电脑鼠应该标记所有的属于该 H， J， N。 死路的格子。图 4 中被标记为死路的死路终点是 D， P— O， 属于死路的格子是 E—F， 和 K。一旦格子被标记为死路， 下一次电脑鼠经过该点时， 将不会把该点作为可选路径 。
第 12 期
算法
［4 ］
王凤林等： 一种电脑鼠走迷宫算法的设计与实现
271
。
2． 1
迷宫坐标和方向
达某个格子后， 该格子的 count 变量需要加 1 。 该变量在搜索算 法中选择路径时要用到 。 当电脑鼠处于某个格子时， 需要完成下面的操作： ① 检测是否到达过该格子 。 ② 通过传感器计算该格子可走的方向 。 ③ 根据该格子可走的方向数， 选择下一步走的方向。 ④ 检查封闭的循环路径和死路， 并更新相应的变量。 ⑤ 移动到下一个格子， 更新当前坐标。 ⑥ 根据坐标检测是否到达终点 。
第 27 卷第 12 期 2010 年 12 月
计算机应用与软件 Computer Applications and Software
Vol. 27 No． 12 Dec． 2010
一种电脑鼠走迷宫算法的设计与实现
王凤林 王宜怀
（ 苏州大学计算机科学与技术学院 江苏 苏州 215006 ）
摘 要 电脑鼠是一个自主移动机器人系统 。电脑鼠的任务是到达迷宫中心的目标区域 。 电脑鼠在不知道迷宫的布局情况下， 必须自己找出到达目标的最优路径 。整个过程是一种自主搜索的过程 。研究和实现了基于位差值的搜索算法和基于等高图的最优 并作出改进提高机器人完成任务的能力 。 路径算法， 关键词 迷宫搜索算法 电脑鼠机器人 位差值 等高图 最优路径