下载文档原格式
电脑鼠走迷宫大赛探索过程算法优化研究——死路排除算法——死区域算法0摘要电脑鼠走迷宫大赛是由国际电工和电子工程学会（IEEE）举办的人工智能领域的一项国际性赛事，集机械、电子、控制、光学、程序设计和人工智能等多方面科技知识于一体[1]，具有很高的知名度。
迷宫算法的优劣直接影响比赛的最终成绩。
本文从经典迷宫算法入手，先后提出了能排除单行当列死路的“死路排除算法”和能够排除任意形状死区域的“渗透法”，然后通过测试验证两种改进算法的优越性。
改进算法的核心思想是通过已经获得的迷宫信息排除不包含最短路径信息的死区域。
同时，文中创造性的将“渗透思想”用于迷宫算法当中，很好的实现了死区域的判定与排除。
与经典算法相比，改进算法在时间、空间方面都有良好的优化效果。
1背景简介电脑鼠走迷宫大赛是国际电工和电子工程学会（IEEE）每年都会举办的一项国际性赛事，于1972年由美国机械杂志发起。
比赛中的电脑鼠是一个小型的由微处理器控制的机器人车辆，在复杂迷宫中具有译码和导航功能。
该比赛自推出以来，受到了世界各国师生的青睐。
2007年和2008年，上海市计算机学会率先在中国主办了两次IEEE标准电脑鼠走迷宫邀请赛（长三角地区），有三十多所院校参加，反响强烈。
2009年比赛范围扩展到全国，共有9个赛区的52所高校参赛[2]。
1.1电脑鼠走迷宫大赛规则[3]电脑鼠的基本功能是从起点开始走到终点，这个过程称为一次“运行”，所花费的时间称为“运行时间”；电脑鼠从第一次激活到每次运行开始所花费的时间称为“迷宫时间”；电脑鼠在比赛时手动辅助的动作称为“碰触”。
竞赛使用这3个参数，从速度、求解迷宫的效率和电脑鼠的可靠性三个方面来进行评判。
电脑鼠的得分是通过计算每次运行的“排障时间”来衡量的，即将迷宫时间的1/30加一次运行时间；如果未被碰触过，则再减去10s（奖励时间），这样得到的就是排障时间。
电脑鼠在迷宫中停留或运行的总时间不可超过15min，在限时内允许运行多次。
电脑鼠走迷宫作者：陈敬作者单位：省杭州市青少年科技活动中心1.期刊论文曾璐.周贤娟迷宫电脑鼠控制系统设计-自动化博览2009,26(7)电脑鼠实际上是集传感与控制于一体的,能够自动穿越迷宫的微型机器人.本课题结合模拟电路、数字电路知识以及传感器知识,制作出一个性能优良的电脑鼠,在迷宫中找到一条最优路径,走出迷宫.根据国际标准迷宫电脑鼠的比赛规则,通过各种方案的对比,确定在本文中采用NXP公司ARM7LPC2138作为控制核心,将新兴的群智能算法运用到迷宫电脑鼠中.2.期刊论文朱闻达IEEE迷宫电脑鼠的迷宫搜索算法研究-中国科技博览2009,""(27)迷宫电脑鼠的概念最早由IEEE Spectrum杂志在七十年代提出,随后这项比赛先后在英国、美国、日本、新加坡等国家开展,现在已成为世界级的电子机器人竞赛.电脑鼠是一个能够自主搜索一个16×16单元格的迷宫中心机器人小车.本文总结了常见的搜索算法,吸收现有算法的思想,提出一个适用于电脑鼠竞赛的实用算法.为了测试所设计的算法的性能,用Visual Studio制作测试环境,编程实现上述算法,设置了数个正式比赛使用的迷宫来进行算法测试,并且借助图形界面展示算法仿真的效果,测试结果表明算法具有较好的实时性和鲁棒性.3.期刊论文吴曼晨迷宫电脑鼠的硬件设计简介-中国科技博览2009,""(27)人工智能技术是一门融合了众多学科的新星科学,它被广泛地应用于勘探、侦察、医疗救援、抢险以及日常生活的各个方面.智能机器人竞赛则是一项旨在开发人工智能技术而举行的比赛,它集科学、娱乐和比赛于一体,在各国引起了广泛关注和极大兴趣.目前国际上有很多针对机器人技术的比赛,而IEEE迷宫鼠竞赛则是其中的一个典型代表.本文首先对近年来在国际上迅速开展的迷宫机器人竞赛作了简要介绍,简要说明了迷宫鼠竞赛的竞赛规则以及发展历史,同时也分析了国内外关于此课题的研究现状.其次,本文对迷宫鼠的硬件设计作了一个整体规划,将迷宫鼠的设计分为微控制器模块、马达驱动模块、传感器模块、人工智能模块和数据存储及传输模块.最后还对参加IEEE迷宫鼠竞赛的智能机器人作了一些测试.4.期刊论文朱姗.傅或哲.吴忠丽.王伟.仇润鹤一种走迷宫电脑鼠的设计与实现-微型电脑应用2008,24(9)该文介绍了一种基于ARM嵌入式的电脑鼠,主要由电源、传感子系统、电机控制子系统、微控制器单元等功能模块组成,文中对各个模块的工作原理,分别从硬件结构、软件流程二个主要环节对走迷宫的电脑鼠实现过程进行深入的说明,并在算法方面对传统的中左法则进行了改进,基于泛洪算法的思想,结合向心法则,提出了一种简单的电脑鼠走迷宫的算法,仅用一个一维数组就可以记录迷宫的全部信息,具有较低的复杂度,易于实现编程,本设计有较广泛的发展应用前景.5.期刊论文屈传坤.徐国政.崔建伟.宋爱国.QU Chuan-kun.XU Guo-zheng.CUIJian-wei.SONG Ai-guo基于DSP的电脑鼠系统设计-电气电子教学学报2008,30(4)本文设计了一种基于DSP的微型机器人一电脑鼠系统.通过对车体速度和方向进行控制,使电脑鼠顺利穿越迷宫到达终点并顺利返回起点.实践证明,该系统能完全实现自主控制,抗干扰能力强,稳定性好.6.会议论文张晋嵌入式电脑鼠运行算法的研究2009本文阐述了电脑鼠设计的构思和实现的过程，主要从算法上分析如何使电脑鼠寻找最佳路径快速的找到迷宫终点。
计算机迷宫搜索算法仿真研究摘要：在电脑鼠的设计过程中，往往需要耗费大量的时间在迷宫搜索算法的调试上。
通过研究迷宫地图，采用模块化的设计方法，模拟实现了对迷宫搜索算法的仿真，还设计了迷宫地图的编辑和迷宫搜索算法的导入等功能。
仿真试验结果表明，仿真迷宫搜索算法可提高迷宫搜索算法设计和调试的效率。
关键词：电脑鼠;迷宫搜索算法;仿真;多线程电脑鼠［1］（Micromouse）是一个由微控制器、探测器、驱动电机组成的一种集感知、判断、行走功能于一体，能够在迷宫中自动寻找到达终点最佳路径的微型机器人。
电脑鼠走迷宫比赛集竞赛和趣味性于一体，吸引了大量青年科技人员参加，文献［1］给出了有关迷宫电脑鼠的比赛规则和要求。
在迷宫电脑鼠的设计中，迷宫搜索算法的设计和调试最困难［3-7］。
主要因为迷宫搜索算法的设计和调试过程容易受到周围环境以及电脑鼠底层软硬件的影响而出现运行错误，从而使得调试经常被打断，完成一次完整的调试非常麻烦［8］，需耗费大量时间。
本文针对电脑鼠设计者在迷宫搜索算法设计和调试上所面临的问题，设计了迷宫搜索算法仿真程序，提高迷宫搜索算法设计和调试的效率，减轻设计者的负担。
该算法仿真程序及其实现思路不仅可以推广到电脑鼠走迷宫竞赛中，而且还可以作为电脑鼠迷宫搜索算法研究者的一个理想研究平台。
1仿真模块设计迷宫搜索算法仿真程序的主要功能模块包含动态仿真器、迷宫搜索算法接口、人机交互界面和迷宫地图编辑器。
动态仿真器是整个程序的核心，迷宫搜索算法接口用于连接动态仿真器和迷宫搜索算法，人机交互界面和迷宫地图编辑器，分别负责响应用户的鼠标动作和迷宫地图的设置。
地图编辑器需要接受用户的动作来完成地图的编辑工作，所以将迷宫地图编辑器作为人机交互界面的一个子功能来实现。
图1是迷宫搜索算法仿真程序的系统模块框图。
动态仿真器实现了三个功能，为迷宫搜索算法获取迷宫信息，根据迷宫搜索算法的指令控制模拟电脑鼠运动，显示运行中产生的过程数据。
一种电脑鼠走迷宫的算法电脑鼠走迷宫的算法1探测策略电脑鼠走迷宫可以采用全迷宫探索策略，即将迷宫的所有单元均搜索一次，从中找出最佳的行走路径。
这种策略需要有足够的时间或探测次数，但在IEEE竞赛规则中每场竞赛只有15分钟的时间，因此是不可能的。
另一种方法是部分迷宫探索策略，即在有限的时间或探测次数下，只探测迷宫的一部分，从中找出次最佳的路径，显然只能采用这种策略。
电脑鼠在一巷道内行走，如果最后无路可走，则该巷为死巷。
电脑鼠在任一单元内，可能的行走方向最多只有三个（前、左、右），如果有二个或二个以上的可能行走方向，称为交叉，遇有交叉时，由于有多个可以行走的方向，在行走方向的选择上，可有下面的几种选择法则：•右手法则：遇有交叉时，以右边为优先的前进方向，然后是直线方向、左边方向。
•左手法则：遇有交叉时，以左边为优先的前进方向，然后是直线方向、右边方向。
•中左法则：遇有交叉时，以直线为优先的前进方向，然后是左边方向、右边方向。
与此类似的还有中右法则。
•乱数法则：遇有交叉时，取随机值作为前进方向。
•向心法则：由于终点在迷宫的中心，遇有交叉时，以向迷宫中心的方向为优先的前进方向。
2标记为了记忆迷宫的详细信息，需要对迷宫单元的位置进行线路标记。
全迷宫共有16×16个单元组成，可采用二维坐标方式标记，即用每个单元的XY坐标表示，如起点可标记为（0，0），终点为（7，7）。
此外，还需要对迷宫单元的可行进方向进行标记，可采用绝对方位或相对方位二种方式。
绝对方位：这是一种与电脑鼠行进方向无关的标记方式，以一个四位的二进制数，分别表示“东”﹑“西”﹑“南”和“北”四个方向。
以1表示允许行进（无墙壁），0表示不允许行进（有墙壁）。
相对方位：这是一种与电脑鼠行进方向有关的标记方式，以一个三位的二进制数即可实现标记，分别表示“前”“左”“右”，以1表示允许（无墙壁），0表示不允许（有墙壁）。
3阻断在电脑鼠试跑过程中或在最后冲刺时，需要对部分路径进行“阻断”，即在发现某条路径是死路（只有入口而无出口）时，在该路径的入口处（一般是交叉点）设置标记，即将入口的线路标记由1改为0。
走迷宫电脑鼠的算法分析与研究收稿日期:2010-03-30;修订日期:2010-11-08作者简介:夏炎（1984-），男，南京人，硕士研究生，研究方向：基于ARM 的嵌入式系统的设计与开发。
夏炎（南京工业大学电子与信息工程学院，南京210013）摘要:电脑鼠的灵活性和智能程度不但取决于硬件的结构和性能，还取决于软件设计的好坏，越是智能的电脑鼠，其软件设计就越不简单。
对走迷宫电脑鼠的算法做了总结和比较，并对各算法的优缺点进行了阐述。
关键词:电脑鼠；迷宫；算法中图分类号:TP18文献标识码:A 文章编号:1008-8725（2011）01-0194-03Analyzing and Researching on Maze-runningMicromouse AlgorithmXIA Yan（School of Electronics and Information Engineering,Nanjing University of Technology,Nanjing 210013,China ）Abstract:The flexibility and intelligence degree of Micromouse depended on not only structure and properties of hardware,but also whether software design was good or bad.The more intelligent the Micromouse was,the more difficult software design was.This paper concluded and compared the algorithms of maze -running micromouse,and discribed advantages and disadvantages of different algorithms.Key words:Micromouse;maze;algorithm0引言人类在科技的发展史上，一直在尝试着想要创造出一个具有肢体、感官、脑力等综合一体的智能机器人，而电脑鼠就是一个能够用来诠释肢体、感官及脑力综合工作的基本实例，这也是当初电脑鼠被发明的理由，希望能够借助电脑鼠的创作来进而研究与发明更加复杂的机械。
“IEEE标准电脑鼠走迷宫”竞赛套件简介及竞赛规则为降低电脑鼠走迷宫竞赛难度，方便在校学生和电脑鼠新手快速入门，广州致远电子有限公司开发了一款IEEE国际标准电脑鼠走迷宫竞赛套件。
该套件包含电脑鼠Micromouse615（电脑鼠）、IEEE标准迷宫及丰富的配套资料。
1．Micromouse615Micromouse615采用铝制车架，重量轻，散热性能好。
采用双步进电机，车轮直接安装在电机轴上，机械结构简单安装方便。
Micromouse615车身长12cm，宽9cm，短小精悍，可灵活的在迷宫格中完成90度和180度转弯，如图0.1所示。
图0.1 Micromouse615Micromouse615微处理器采用LM3S615。
LM3S615是美国Luminay公司开发的32位单片机，基于ARM Cortex-M3内核。
LM3S615具有运算速度快，中断响应快，外设丰富等优点，保证了Micromouse615可以具有很高的智商。
另外Luminay公司提供了丰富的函数库，只要懂C就能开发，大大降低了Micromouse615的使用难度。
Micromouse615使用5组红外传感器用于检测迷宫墙壁信息，分别用于检测左、左前、前、右前和右五个方向的墙壁信息。
左前和右前传感器用于调整电脑鼠姿态，使电脑鼠走时行走在迷宫格中心。
使用5组可调电阻控制红外信号发射强度，调整可见距离。
信号采用载波调制，增强抗干扰性。
Micromouse615采用双步进电机驱动。
使用步进电机不需要减速装置等，可简化机械结构。
步进电机控制简单，运行平稳。
Micromouse615板上一个按键，一个复位按键和一个10针JTAG调试接口，并预留了一个6个JPIO、一个串口和一个SPI接口，方便扩展。
在配套光盘中配有一个能够用于参赛的程序，可稳定而快速的完成竞赛。
Micromouse615具有高度可扩展性，领用预留的接口可根据需要扩展其他部件，进行硬件升级。
电脑鼠走迷宫智能算法的研究与优化
王艺宁;蒋涵;王博;于娜
【期刊名称】《科技创新导报》
【年(卷),期】2015(000)032
【摘要】电脑鼠(Micromouse)是智能机电鼠的简称,实际上是一个由微处理器控制的,集感知、判断、行走功能于一体,能够自动寻找最佳路径到达目的地的微型机器人.该文简要分析了电脑鼠的硬件组成和工作原理,在此基础上重点对电脑鼠软件部分的探测策略模块、等高图制作模块、冲刺模块进行了分析研究与优化,并通过大量实验进行了验证.实验结果表明优化后的算法能够在一定程度上有效地提高电脑鼠走迷宫的运行速度、减少电脑鼠的搜索时间.
【总页数】3页(P129-130,132)
【作者】王艺宁;蒋涵;王博;于娜
【作者单位】天津农学院计算机与信息工程学院天津 300384;天津农学院计算机与信息工程学院天津 300384;天津农学院计算机与信息工程学院天津 300384;天津农学院计算机与信息工程学院天津 300384
【正文语种】中文
【中图分类】TP36
【相关文献】
1.基于IEEE标准电脑鼠走迷宫控制算法研究与优化 [J], 郑伟;张永飞
2.基于IEEE标准的电脑鼠走迷宫的智能算法研究 [J], 王斌;张卫钢
3.基于ARM的电脑鼠走迷宫的研究 [J], 蒋雄;任化龙;马忠丽
4.基于向心法则的电脑鼠走迷宫算法设计与优化 [J], 贺少波;孙克辉
5.基于概率距离的电脑鼠走迷宫融合算法研究 [J], 袁臣虎;路亮;王岁;李海杰;刘奇因版权原因，仅展示原文概要，查看原文内容请购买。
电脑⿏⾛迷宫电脑⿏⾛迷宫算法改进及仿真测试（部分）2.3.5 迷宫算法改进迷宫最优路径是指从迷宫的⼊⼝到达迷宫出⼝的最短通路。
传统求解迷宫路径问题的算法⼤多采⽤⼴度优先搜索(BFS)或深度优先搜索(DFS)。
由于需要全迷宫搜索，随着迷宫规模的增⼤和复杂性的增加，上述两种算法的空间和时间复杂性将呈指数增加。
针对以上问题，本论⽂对传统算法进⾏优化改进讨论，核⼼思想是利⽤已经探索得知的迷宫信息排除不包含最短路径信息的迷宫格，不予探索。
1、单⾏、单列死点的死胡同排除算法该算法核⼼内容是进⾏数据补全，减少电脑⿏进⼊“死胡同”的次数。
其实迷宫单元的信息并不是只有访问过才能够得到，通过推断的⽅法也是可以得到的。
利⽤某个单元四周的⽅格的信息，就可以推断出此单元的信息，⽽并不需要每⼀个单元都进⾏访问。
如果⼀个迷宫单元三个⽅向有挡板，并且当该迷宫格不是终点时，那么电脑⿏进⼊该迷宫格后必然返回，这对于寻找最短路径信息⽆⽤，此时将该迷宫格第四个⽅向⼀同标记，亦即将迷宫格封闭，不让电脑⿏进⼊该迷宫格，以达到缩短探索时间的⽬的。
如图2.10中圆圈区域，当其四周搜索过时，电脑⿏不应对此区域进⾏访问。
图2.10 死胡同实例根据电脑⿏迷宫特性，迷宫四周的挡板是肯定存在的，可先进⾏预先处理。
⽽且终点四个单元的周围的⼋块挡板有且仅有⼀个是不存在的。
当电脑⿏到达终点，在明确哪个挡板不存在的同时，⽆论其它挡板是否进⾏探测过，都可将它视为挡板存在。
2、多⾏、多列死点的死区域排除算法传统搜索算法中电脑⿏从当前单元移动到下⼀单元的依据是有⽆挡板的存在及是否访问过，⽽未考虑从下⼀单元是否可以在不经过当前单元的情况下到达终点。
形象的说，此种搜索只着眼于当前电脑⿏的移动，⽽不考虑实际效果。
当电脑⿏不能从下⼀单元在不经过当前单元到达终点时，电脑⿏的运⾏就做了“⽆⽤功”，这对于迷宫搜索的执⾏效率产⽣很⼤的副作⽤。
如图2.11所⽰，⽅形区域内即是这种情况，也就是死区域。
