一种电脑鼠走迷宫的算法

《一种电脑鼠走迷宫的算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一种电脑鼠走迷宫的算法电脑鼠的英文名称为Micromouse，实际上是一个由微处理器控制的，集感知、判断、行走功能于一体，能够自动寻找最佳路径到达目的地的小型机器人。它可以在“迷宫”中自动感知并记忆迷宫地图，通过一定的算法，寻找一条最佳路径，以最快的速度到达目的地。1997年，在美国举办了第一届电脑鼠竞赛，随后，电脑鼠竞赛传入欧洲，首届欧洲电脑鼠竞赛于1980年在伦敦举办，之后英国的电脑鼠比赛便由电子工程协会（IEE）主办。1980年11月日本电脑鼠协会（JMA）在东京举办了第一届竞赛，此后，日本

2、每年都要举办一届电脑鼠竞赛。我国台湾也于1986年10月举办了首届电脑鼠比赛。现在国际电工和电子工程学会（IEEE）每年都要举办一次国际性的电脑鼠走迷宫竞赛，各国选手报名踊跃，主要是大学生，为此部分大学还开设了“电脑鼠原理和制作”选修课程。由于电脑鼠要由参赛选手自己设计制作，不仅要求选手具有嵌入式系统应用﹑传感器﹑控制技术等多方面的知识、经验和实践能力，还要求具有编写寻找最佳路径算法的能力。由于迷宫路径设置是随机的，因而竞赛难度较大，极富挑战性。这对培养和提高学生的创新精神和实践能力，有着深远的意

3、义。2007年5月—8月将举办由我国部分地区（上海及长三角地区）参加的首届电脑鼠邀请赛。1电脑鼠走迷宫的规则有关电脑鼠国际比赛的详细规则，可参阅国际电工和电子工程学会（IEEE）的官方网站：http://www.eece.maine.edu/sc2006/2006MicromouseRules.pdf。迷宫的规格迷宫由256个方块（单元）组成，每个方块的大小为18厘米见方，排成16行×16列。迷宫的隔墙板沿方块的四周布设，形成迷宫通道。隔墙板高5厘米﹑厚1.2厘米，因此迷宫通道的实际宽度是16.8

4、厘米。隔墙板的两个侧面是白色的，顶部是红色的。迷宫的地板由木质材料做成，涂上没有反光的黑漆。隔墙板的侧面和顶部对红外线有反射特性，而地板则对红外线有吸收特性。竞赛起始点可设在迷宫的任何一角，其三面要有隔墙；竞赛的终点设在迷宫的中央，有四个方块那么大小。图一为一个实际的电脑鼠竞赛用的迷宫照片。图一电脑鼠竞赛用的迷宫照片1.2电脑鼠的规格电脑鼠要求由参赛者自制，使用电源为能源，不能使用其它可燃物为能源。电脑鼠结构高出隔墙部分的长宽几何尺寸应不大于25×25厘米，对高度没有限制。一个完整的电脑鼠应包含有

5、机身、电源、传感器、微处理器、马达及驱动等部分。电脑鼠的传感器可分为三组，分别用来感知前、左、右三个方向是否已靠近宫壁，并将所获得信息传送给微处理器进行处理。微处理器要完成多种信息的处理，如路径、迷宫地图、行走距离、马达控制等，并要能够作出判断。在马达的控制下，电脑鼠能够完成直行、转弯、掉头以及加减速等动作。通常采用左右独立的马达驱动和控制，以使微处理器的控制更加灵活。图二为一个实际参加竞赛的电脑鼠样例照片。8图二电脑鼠样例照片。1.3竞赛的规则电脑鼠的基本功能是从起点开始走到终点，这个过程称为一

6、次“运行”，所花费的时间称为“运行时间”。从终点回到起点所花费的时间不计算在运行时间内。电脑鼠从第一次激活到每次运行开始，所花费的时间称为“迷宫时间”。如果电脑鼠在比赛时需要手动辅助，这个动作称为“碰触”。竞赛使用这三个参数，即运行时间﹑迷宫时间和碰触，从速度﹑求解迷宫的效率和电脑鼠可靠性三个方面来进行评分。电脑鼠的得分是通过计算每次运行的“排障时间”来衡量的。所谓排障时间是这样计算的：先将迷宫时间的1/30加上一次运行时间，如果这次运行结束以后电脑鼠没有被碰触过，那么还要再减去10秒的奖励时间，

7、这样得到的就是排障时间。电脑鼠在迷宫中的停留或运行的总时间不可超过15分钟，在限时内允许运行多次，允许取其中最短的排障时间作为参赛的计分成绩。当然，排障时间越短越好例如：一个电脑鼠在迷宫中运行时间为4分钟（240秒）没有碰触过，迷宫时间使用了20秒，这次运行的排障时间就是：20秒+（240秒×1/30）－10秒=18秒。电脑鼠在迷宫通道内行走时不能碰到隔墙板，遇到岔道口时要能够自动作出方向选择。本文规定：如果进入迷宫是为了进行探测和记忆，这次运行就称为“试跑”；如果进入迷宫是根据先前的记忆和经验，

8、按照智能算法确定最佳路径，并以最快的速度到达目的地，这次运行就称为“冲刺”。1电脑鼠走迷宫的算法2.1　探测策略电脑鼠走迷宫可以采用全迷宫探索策略，即将迷宫的所有单元均搜索一次，从中找出最佳的行走路径。这种策略需要有足够的时间或探测次数，但在IEEE竞赛规则中每场竞赛只有15分钟的时间，因此是不可能的。另一种方法是部分迷宫探索策略，即在有限的时间或探测次数下，只探测迷宫的一部分，从中找出次最佳的路径，显然只能采用这种策略。电脑鼠在一巷道内行走，如果最后无路可走，则该巷为死巷。电脑鼠