电脑鼠走迷宫路径规划及控制方法的研究
电脑鼠走迷宫路径规划及控制方法的研究
2011年 6 月2 日
摘要
电脑鼠是使用嵌入式微控制器、传感器和机电运动部件构成的一种微型机器人，可以在迷宫中自动记忆和选择路径，快速地达到所设定的目的地。电脑鼠走迷宫竞赛是一项具有一定难度、富有挑战性和趣味性的比赛。
本论文首先介绍了电脑鼠的起源与发展，分析了电脑鼠的硬件组成和工作原理，在此基础上重点讨论了电脑鼠软件的设计与实现，具体包括：等高图制作、电脑鼠冲刺、电脑鼠转弯、电脑鼠搜索、相对方向与绝对方向转变、墙壁资料存储和电脑鼠搜索策略。通过对电脑鼠自动穿越迷宫过程，综合嵌入式专业的电路设计，传感器控制，单片机程序开发和算法研究等多学科知识的研究，使我熟悉掌握嵌入式应用开发的全过程。最后对电脑鼠研究过程中遇到的问题进行了讨论与总结。
关键词：电脑鼠；迷宫的算法；路径规划；电机；红外感应器
ABSTRACT
The micromouse is a typical micro robot, which inclueds embedded microcontroller, sensors and mechanical motion. The micromouse can choose a best and fast way to the destination in the maze, with automatic memory. The contest of micromouse go through a maze is a difficult but challenging and interesting game. This Research-based Curriculum focuses on the hardware design of micromouse and the maze algorithm. The research includes the knowledge of circuit design, the embedded microcontroller program and algorithms such.
This paper firstly introduces the origin and development of micromouse. Then it analyzses the micromouse's hardware composition and working principles. After that we discuss the design and implementation of the software. It includes the maze map, absolute orientation, search strategy and optimal path method of the research. At last, the problems during the studying process are discussed and summarized.
Keywords: Micromouse,；Flood Algorithm；Path Planning；Motor；Infrared
目录
第一章绪论 (1)
1.1电脑鼠介绍 (1)
1.2电脑鼠的国内外现状 (2)
1.3电脑鼠比赛简述 (3)
第二章迷宫的算法 (4)
2.1迷宫坐标和方向 (4)
2.2迷宫搜寻法则 (5)
2.2.1基础的搜寻法则 (6)
2.2.2中心搜寻法则 (7)
2.3洪水算法简介 (8)
2.4最优路径算法 (8)
2.4.1等高图的制作原理 (9)
2.4.2转弯加权的等高图 (10)
2.5模拟最佳路径 (10)
第三章运动控制 (12)
3.1电脑鼠原理 (12)
3.2底层驱动程序及顶层算法程序 (13)
3.2.1两相四线制步进电机驱动时序 (13)
3.2.2步进电机的加减速控制 (14)
3.3电脑鼠转弯 (15)
3.4电脑鼠运动状态的控制 (18)
3.4.1电脑鼠姿势修正 (18)
第四章软硬件原理 (21)
4.1电脑鼠的硬件构造和特点 (21)
4.2原理说明 (23)
4.2.1电机驱动电路 (23)
4.2.2红外线接收传感器 (24)
4.2.3按键电路 (26)
4.2.4处理器 (27)
4.2.5机械结构 (29)
4.3软件设计 (30)
4.3.1软件开发环境 (30)
4.3.2电脑鼠的主要程序 (33)
第五章总结与展望 (34)
参考文献 (36)
附件 (38)
附件1程序 (38)
附件2英文文献 (43)
附件3中文翻译 (54)
谢辞 ............................................................................................ 错误！未定义书签。
第一章绪论
1.1电脑鼠介绍
1956年，―信息论之父‖克劳德?埃尔伍德?香农(Claude Elwood Shannon)参与发起了达特默斯人工智能会议，成为这一新学科的开山鼻祖之一。他不仅率先把人工智能运用于电脑下棋方面，而且发明了一个能自动穿越迷宫的―电老鼠‖，以此证明计算机可以通过学习提高智能。电脑鼠(Micromouse)是一个具备自主运动能力的机器人，它能在一个16×16方块组成的迷宫中，有起点出发，自行搜寻到迷宫的终点，并利用搜寻过程中所记录的迷宫资讯找出有起点到终点的最短路径，再进一步规划出最快的运动方式，并以最快的速度的来完成从起点到终点的移动。迷宫中的每一个方块的边长18公分，迷宫墙壁高5公分、厚度1.2公分，地面是黑色，而墙壁是白色。
图1.1 16x16标准迷宫示意图
图1.2 8x8标准迷宫示意图
虽然电脑鼠的开发和与他相关的国际竞赛已经开展了将近三十年，但是中国在电脑鼠上的发展基本是一片空白，只停留在很基础的层面上，而且市面上出售的电脑鼠不但结构复杂，体积大质量大，转弯也很不稳定，因此无法拥有流畅的动作，而且所提供的范例大都是能完成走迷宫的最基础的程序，需要进行大量的修改以优化现有的程序。
因为微控制器和感测器的快速发展，使得电脑鼠的大小、资讯处理得速度以及运动速度的提升比较大，发达国的积极投入，使其电脑鼠的性能远远领先于其他国家。另外电脑鼠的制作其实包含了软件程序编写、硬件设施的设计，是一个非常好的嵌入式整合机电系统。因此本论文是想研究电脑鼠在迷宫中从起点到终点的路径规划以及优化算法的应用，还有是对电机的有效控制，使电脑鼠可以快速的从起点跑到终点。
图1.3 本论文所使用的电脑
1.2电脑鼠的国内外现状
我国电脑鼠发展起步的比较晚，国内比赛从2007年才开始。2008 年长三角
嵌入式系统创新设计应用竞赛暨IEEE标准电脑鼠走迷宫邀请赛在华东师范大学举行，50支队伍参加了电脑鼠走迷宫竞赛。比赛的规模和质量都比往年有很大的提高。
2009年全国电脑鼠走迷宫邀请赛先分别于长三角、北京、天津、山东、四川、湖北、陕西和山西等赛区进行分区预赛，再有各赛区荣获一等奖的队伍参加北京的总决赛。11月8日全国电脑鼠走迷宫总决赛在北京航空航天大学首享科技大厦举行，其中曾在国际上荣获第三名的台湾龙华科技大学的电脑鼠也受邀参加了本次决赛。
2009年，在美国APEC2009电脑鼠竞赛中新加坡南洋理工工院电脑鼠队以11.81秒的综合计算时间，技压群―鼠‖，击退美国麻省理工学院(Massachusetts Institute of Technology，MIT)等强劲对手三度夺得冠军。台湾龙华科技大学夺得第三名。速度最快的电脑鼠是由来自位于华盛顿的BattelLe Northwest实验室的Art Boland，Phil Stover和Ron Dilbeck制造的。根据Boland的观点，他们围绕一个微型计算机构建作品，这个微型算机具有足够大的存储器，可存储需要在迷宫中99个不同位置做决定时所需的信息。通常采用的策略是，第一次通过时(允许有三次通过机会)，允许电脑鼠在每个拐弯处随机选择。第二次通过时，电脑鼠尝试它―知道‖在第一次没有尝试的新路线。然后用收集到的消息计算最佳路线，用于第三次通过。
1.3电脑鼠比赛简述
电脑鼠的基本功能是从起点开始走到终点，这个过程称为一次―运行‖，所花费的时间称为―运行时间‖。从终点回到起点所花费的时间不计算在运行时间内。电脑鼠从第一次激活到每次运行开始，所花费的时间称为―迷宫时间‖。如果电脑鼠在比赛时需要手动辅助，这个动作称为―碰触‖。竞赛使用这三个参数，即运行时间、迷宫时间和碰触，从速度、求解迷宫的效率和电脑鼠可靠性三个方面来进行评分。电脑鼠的得分是通过计算每次运行的―排障时间‖来衡量的。所谓排障时间是这样计算的：先将迷宫时间的1/30加上一次运行时间，如果这次运行结束以后电脑鼠没有被碰触过，那么还要再减去10秒的奖励时间，这样得到的就是排障时间。电脑鼠在迷宫中的停留或运行的总时间不可超过15分钟，在限时内允许运行多次，允许取其中最短的排障时间作为参赛的计分成绩。当然，排障时间越短越好例如：一个电脑鼠在迷宫中运行时间为4分钟(240秒)没有碰触过，迷宫时间使用了20秒，这次运行的排障时间就是：20秒+(240秒×1/30)－10秒=18秒。
第二章迷宫的算法
2.1迷宫坐标和方向
为了让电脑鼠记住所走过的各个迷宫格的信息，需要使用坐标对256 个迷宫格进行编号。
规定以电脑鼠放到起点时的方向为参照，此时电脑鼠的正前方为Y 轴正方向。迷宫格与坐标的对应关系如图2.1所示。
根据坐标的定义和比赛规则可知，电脑鼠的起点可在迷宫的四个角落的点上，但是无法确定起点的具体坐标。解决方法是根据电脑鼠第一次检测到的转弯口是在右方还是左方判断。如果电脑鼠第一个检测到的拐弯口是在它的右方( 迷宫的四个角落中有两个角落是这种情况) ，那么它从(0，0) 点出发; 如果第一个检测到的拐弯口在它的左边(迷宫的四个角落中有两个角落是这种情况) ，那么它从(15，0) 出发。图2.2是判断起点流程图。
图2.1 全迷宫结构图
图2.2 判断起点坐标流程图
2.2迷宫搜寻法则
在电脑鼠的竞赛中，事前并不会知道迷宫的墙壁资讯，所以电脑鼠需要拥有一个具有记忆迷宫资讯和在迷宫中找到从起点到终点的最短路径的迷宫算法。一个好的迷宫算法可以大大的缩短电脑鼠在迷宫中的搜索时间，以达到最快找出最短路径的目的，那么就需要事先搜索迷宫的墙壁资讯。
为了讨论方便，这里使用距离值。所谓距离值就是迷宫格距离迷宫终点的最小格子数，目标的距离值是0。每个格子的距离值如图2.3所示。
当电脑鼠处于某个格子时，需要完成下面的操作:
①检测是否到达过该格子。
②通过传感器计算该格子可走的方向。
③根据该格子可走的方向数，选择下一步走的方向。
④检查封闭的循环路径和死路，并更新相应的变量。
⑤移动到下一个格子，更新当前坐标。
⑥根据坐标检测是否到达终点。
图2.3 迷宫格的距离值
2.2.1基础的搜寻法则
基础的搜寻法则有右手搜寻法则、左手搜寻法则、中左搜寻法则、中右搜
寻法则等。
右手搜寻法则是当电脑鼠行进时，如果碰到有两个或者两个以上的方向可以选择时，优先选择右手方向转弯。左手搜寻法则就是优先选择左手方向转弯(如图2.4所示)。
a右手法则b左手法则
图2.4 左右手搜寻法则
中左和中右搜寻法则就是碰到有两个或者两个以上的方向可以选择时，有一个选择的顺序，先保持原先的方向行进，如果原先的方向被搜寻过或是没有路可走时，就会选择左手方向或右手方向转弯行驶。
2.2.2中心搜寻法则
中心搜寻法则的应用则更加的优化，首先是电脑鼠在迷宫的起点，它会记忆终点的坐标，一直去向中心的方向行驶，就免去了选择方向的麻烦，如果电脑鼠可供选择前进的方向包含了两个都有可能是离迷宫中心最近的方向时，它将优先选择可以直线前进的方向，其次选择只用转90度的方向前进(如图2.5所示)。它会自己选择最优路线，去无限的接近终点，就不会去搜索迷宫的一些没有用的路，直到到达终点，这样就省去了去搜索迷宫全图的时间，大大缩短了搜索的时间。中心搜索法则有可能不是最佳的，大师整体而言，中心搜索法则还是最有效的。
图2.5 中心法则
2.3洪水算法简介
洪水算法的基本概念就好像洪水流动一样。一开始先不考虑直行或转弯对洪水流的影响。假设迷宫的终点的距离值是0，每流过一个迷宫格相对于前一个迷宫格到终点的距离就加1，利用这个想法来计算每一个迷宫格与迷宫终点的距离值，持续到计算出迷宫起点与迷宫终点的距离值为止，根据每个迷宫格与终点的距离值，再由大到小的方式排列，这样就能在迷宫中找出一条最短路径。
由中心搜寻法则和洪水算法结合，每一个迷宫格都会执行洪水算法，这样在时间允许的情况下，每个迷宫格都会朝着终点行进，那么会很有效率的找到一条最短路径。但是洪水算法还要考虑到转弯流动和直行流动，转弯流动会大大降低水流的速度，而直行则会最快的到达终点。如果考虑直行流动和转弯流动的影响，那么假设迷宫终点的距离是0，每流过一个直行迷宫格，该迷宫格与终点的距离差为1，每流过一个转弯流动的迷宫格，该迷宫格与上一个迷宫格的距离值为2，按照这样的想法去计算，最后再依据每一个迷宫格与迷宫终点的距离值，由大到小的排列即可找到此迷宫的最短路径，因此洪水算法找出的路径会是一条直行行驶比转弯要多的最短路径，也是最有效的方法。
2.4最优路径算法
电脑鼠当到达起点后，则需要根据搜索获得的信息，选择最优路径进行冲刺。经过有限次的探测、死路标记后，可以得到描述迷宫图线路的二维表。虽然不是
全部，但其中可能包含了若干条可以到达终点的路径。通过制作等高图找到到达终点的路径。等高图是等高线地图的简称，有如一般地图标出同一高度的地区范围。等高图运用在迷宫地图上可以标出每个迷宫格到终点相等步数的关系。等高值为某个迷宫格距离起点格子的路径中经过的最少格子数。最大值为0xff，表示无法到达。
图2.6 洪水算法最优路径
2.4.1等高图的制作原理
首先开辟一块16×16的二维数组空间(MapStep[16][16])，其中每一个元素代表一个迷宫格，用以计算每个迷宫格与重点之间的最短路径步数。
将所有的等高值初始化为0xff，终点坐标处标识为1。
制作等高图的方法如下:
1. 若所处点只有一个方向可前进(可前进的定义是指等高值比当前坐标的等高值大2 以上的相邻坐标)，进入该方向的迷宫格。
2. 若有两个或两个以上可前进的方向，则将该点坐标存入堆栈。任选一个方向进入。
3. 若四周无可前进的方向，则从堆栈中取出最后入栈的坐标，并跳到该坐标。
4. 直到当前坐标没有可前进方向，并且堆栈中没有未处理完的分岔点时结束。
2.4.2转弯加权的等高图
要使电脑鼠在最短的时间内完成冲刺，路径的选择至关重要。选择步数少的路径是确定最佳路径的条件之一，但不是唯一条件。考虑到电脑鼠在拐弯时，要更多时间，所以可将拐弯次数加权后再加到步数中，以确定加权步数。
加权步数= 步数+拐弯次数×拐弯权重。
可以将一个90 度的拐弯算一次拐弯，一个180 度的拐弯算两次拐弯。拐弯权重是一个对结果有重要影响的参数，这要结合电脑鼠的转弯性能确定，而且要考虑到转弯速度与直道速度的不同。图中给出了在4×4 的小迷宫在两种等高图方法所得到的等高图，图2.7(a)为未改进的等高图，图2.7(b) 为转弯加权的等高图。
图2.7 等高图
2.5模拟最佳路径
利用迷宫编辑器可以模拟出电脑鼠在16X16的迷宫中所走的路线，可以帮助我们直观的算出迷宫的最短路径，方便我们验证电脑鼠在真正的迷宫中的行进路径，是否是最短路径。图2.8就是由起点到终点的最短路径。
图2.8 模拟的最佳路径
第三章运动控制
3.1电脑鼠原理
电脑鼠是通过控制左右步进电机的不同运动状态和选择合适的传感器测量距离以及合适的路径选择法则，可实现电脑鼠的避障、身姿调整和方向转向等。在智能老鼠稳定运行的基础上，它可对整个迷宫进行全遍历，并将迷宫信息绘制成等高表，然后进行数据存储，再通过微控制器根据数据进行出栈入栈，以找到目标最短的路径，从而实现智能老鼠快速高效的到达迷宫的终点。
图3.1 运行原理流程图
3.2底层驱动程序及顶层算法程序
电脑鼠是一个智能机器老鼠，其灵活性和智能程度不仅取决于硬件的结构和性能，还取决于软件设计的优良程度。越是智能的电脑鼠，其软件设计就越不简单。电脑鼠程序设计的整体结构可分为两层：顶层驱动程序和顶层算法程序。
底层驱动程序主要实现电脑鼠的一些基本功能，比如至极限控制其前进N个单位坐标格，测量它前进的距离，向右或者向左转90度、向后转、迷宫格四周墙壁信息的检测等。
顶层算法程序主要是一些电脑鼠的智能算法，比如根据迷宫信息决定电脑鼠的动作，记住走过迷宫的地图，寻找到达目的地的最优路径等。
3.2.1两相四线制步进电机驱动时序
驱动步进电机的时序主要有单拍驱动、整步驱动、半步驱动(如图3.2所示)。
a 单拍驱动
b 整步驱动
c 半步驱动
图3.2 步进电机驱动时序图
3.2.2步进电机的加减速控制
控制步进电机的加减速，实际上就是控制每次换相的时间间隔。如果利用定时器中断方式来控制电机变速，可以不断地改变定时器装载值的大小。步进电机的输入信号包括步进脉冲信号和方向电平信号。每接收一个脉冲型号，系统将驱动步进电机旋转一个步距角，步进电机的转速和脉冲信号的频率成正比。
表3.1 步进电机三种驱动方式比较
试验表明，如果脉冲信号变化太快，步进电机由于惯性跟不上电信号的变化，就会产生失步现象，故在选择驱动方式时，可选择半步驱动，即步进电机在启动时，必须有升速过程；而在停止时，则必须有减速过程。图3.3所示为步进电机在运行过程中的速度变化曲线。加减速实时算法的核心是使用定时器中断。当定
时器发生超时中断时，中断服务函数会推动电机走下一步，然后计算出下一步将要维持的时间，并以其设置定时器下一次的中断时间。当下一次中断来临时，再推动一步，并设置再下一步的时间。电机转过的步数通常可由n表示(ω为电机的加速度)：
(3-1) 这样，电机转过n步所花的时间为：
(3-2)
位置
图3.3 步进电机运动时速度的变化曲线
3.3电脑鼠转弯
电脑鼠的转弯分为90度转弯和180度转弯两种(如图3.4所示)。90度转弯又分为前进中转弯和原地转弯两种。前进中转弯可节约时间，效率高，转弯半径相对于原地转弯要小，速度快，但控制相对于原地转弯要困难。所以前进中转弯就成了必不可少的一项。