Micromouse615电脑鼠项目报告技术研究报告毕业论文.doc

项目编号：31SZDYKC-090601 职业大学研究性课题教学项目学 生 研 究 论 文项目名称： IEEE标准电脑鼠走迷宫研究论文题目：Micromouse615电脑鼠项目报告摘 要“电脑鼠”是使用嵌入式微控制器、传感器和机电运动部件构成的一种微型机器人，可以在 “迷宫”中自动记忆和选择路径，快速地达到所设定的目的地。电脑鼠走迷宫竞赛是一项具有一定难度、富有挑战性和趣味性的比赛。本研究性课程重点对电脑鼠硬件、迷宫算法进行分析研究。本研究性课程通过对电脑鼠自动穿越迷宫过程的研究，综合嵌入式专业的电路设计、传感器控制、单片机程序开发和算法研究等多学科知识，熟悉掌握嵌入式应用开发的全过程。本文首先介绍了电脑鼠的起源与发展，分析了电脑鼠的硬件组成和工作原理，在此基础上重点讨论了电脑鼠软件的设计与实现，具体包括：等高图制作、电脑鼠冲刺、电脑鼠转弯、电脑鼠搜索、相对方向与绝对方向转变、墙壁资料存储和电脑鼠搜索策略，最后对研究性课程教学过程中遇到的问题进行了讨论与总结。关键词：嵌入式系统，电脑鼠，智能算法ABSTRACTThe 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. The students can know how to design and implement an embedded application through the curriculum.This paper firstly introduces the origin and development of micromouse。Then it analyzses the micromouses 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：Embedded System，Micromouse，Intellegent Algorithm目录摘 要2第一章前言21.1项目背景21.2项目介绍31.3项目成员及分工3第二章 电脑鼠项目介绍52.1 电脑鼠的起源与发展52.1.1电脑鼠的起源52.1.2国际电脑鼠的发展52.1.3我国电脑鼠的发展情况72.2 电脑鼠走迷宫比赛72.2.1电脑鼠Micromouse61572.2.2 电脑鼠迷宫Micromouse Maze82.2.3 电脑鼠比赛简述9第三章 电脑鼠硬件与软件103. 1相关开发工具103.2电脑鼠硬件103.2.1 电脑鼠硬件组成103.2.2电脑鼠基本动作133.3电脑鼠软件143.3.1等高图制作模块163.3.2冲刺模块173.3.3转弯模块173.3.4搜索模块183.3.5迷宫地图相对方向与绝对方向的建立183.3.6墙壁资料存储203.3.7电脑鼠搜索策略21第四章 问题总结及改进224.1硬件方面的问题及解决方法224.2 软件方面的问题及解决方法22第五章 项目总结与展望255.1 课程学习过程255.2 课程总结275.3项目展望29致谢30参考文献31附录 IEEE电脑鼠走迷宫竞赛规则32第一章 前言所谓“电脑鼠”，英文名叫做MicroMouse，是使用嵌入式微控制器、传感器和机电运动部件构成的一种智能行走装置的俗称。它可以在“迷宫”中自动记忆和选择路径，寻找出口，最终达到所设定的目的地。1.1项目背景电脑鼠可看作是一种具有人工智能的小型机器人，依照比赛规则，当电脑鼠放入“迷宫”起点，按下启动键之后，它就必须自行决定搜寻法则并且在迷宫中前进、转弯、记忆迷宫墙壁资料、计算最短路径、搜寻终点等功能。电脑鼠更结合了机械、电机、电子、控制、光学、程序设计和人工智能等多方面的科技知识。国际电工和电子工程学会（IEEE）每年都要举办一次国际性的电脑鼠走迷宫竞赛。首场电脑鼠迷宫竞赛1979年于纽约举行，1991年以来，每年都有世界级的比赛。2007年，国内开始举行IEEE标准电脑鼠走迷宫邀请赛,自举办以来各高校参赛踊跃，许多大学还开设了“电脑鼠原理和制作”选修课程。电脑鼠走迷宫竞赛具有一定难度，是一项富有挑战性和趣味性的比赛。电脑鼠可看作是一个集多项工程学科知识于一体的小型系统，成功的设计者通常都是合作团体，他们必须考虑电子、电气、机械以及计算机各方面的问题，重量、速度、功耗、传感技术、重心以及程序各方面都是设计中需要决定和综合考虑的因素。电脑鼠结合了多学科知识，对于提升我们的动手能力、团队协作能力和创新能力，促进课堂知识的消化和扩展自身的知识面都非常有帮助；另外成立小组合作参赛，不仅使我们学到了知识，而且加强了同学之间的交流，交际能力语言表达能力等也得到了锻炼和提升；最后电脑鼠走迷宫竞赛极具趣味性，容易得到学生的认同及参与，并能很好的激发和引导学生这方面的兴趣和爱好，为继续参加比赛和深入学习提供了良好的条件。研究性课程是我校根据高等职业技术教育人才培养目标和学校课程改革的需要而开设的校本课程。IEEE标准电脑鼠走迷宫研究研究性课程教学项目于2009年4月申请并获立项审批，为期一年，至2010年3月底结束。1.2项目介绍本课程将重点研究电脑鼠硬件与改进、迷宫算法分析与改进。通过对由微处理器控制的、集传感与控制于一体的电脑鼠自动穿越迷宫过程的的研究，综合嵌入式专业的电路设计、传感器控制、单片机程序开发和算法研究等多学科知识，学生可熟悉掌握嵌入式应用开发的全过程，从而具备一定的嵌入式应用开发基础与能力。另外，该课程可以提高学生专业学习兴趣，锻炼学生独立学习、综合运用专业知识的能力，最后，在项目研究基础上组织学生报名参加2009全国电脑鼠走迷宫竞赛验证研究成果，通过竞赛锻炼学生应对挑战，超越自我，肯定自我的自信和精神。通过该研究性课程，我们将要完成电路板测试、算法研究、资料查询与检索、项目管理等学校课程外的知识与技术技能的学习、整合，培养科技创新意识和动手设计能力。通过系统分析、硬件设计、软件设计、整合电路设计、汇编语言、C语言在单片机开发中的应用知识，培养运用专业知识解决问题的综合应用能力,具体包括:(1) 制定学习计划、项目计划，学会合理安排时间与事先准备的能力；(2) 检索信息，查阅资料，自主学习的能力；(3) 团体合作，与项目组成员以及老师的沟通协调能力；(4) 分析、设计、编程、调试、测试等软件设计的综合能力；(5) 规范编程，整理文档，综合演示，锻炼文字表达、语言表达能力。（6）通过竞赛，培养责任感、荣誉感、集体观念，锻炼学生在遇到难题与压力的情况下不放弃、迎难而上，树立坚强的自信心。1.3项目成员及分工本课程项目以小组为单位，指导老师是徐丽华老师,项目开展过程中郑洪静老师也给予了很多帮助。小组共4位学生成员，他们是：组长陈高娟，组员沈伟华，仇高源，张扬。人员的安排及分工情况如下：徐丽华:指导老师,项目总体负责人,项目设计,项目管理与控制。细化任务目标，指导学生按教学预案的计划实施。郑洪静：辅助指导老师。指导硬件设计与调试。陈高娟：学生组长,女。专业课成绩优异，理解与沟通能力较强，细心，责任心强。具体负责与指导教师及队员的沟通,参加项目实施，项目文档整理负责人。沈伟华：队员,男。专业课成绩优异，有较强逻辑思维，编程基本功扎实。具体负责硬件分析与调试,迷宫算法分析与改进。仇高源：队员,男。硬件基本功好，钻研精神强。具体负责硬件分析与改进。张扬：队员，男。头脑灵活，然自控能力不强，负责迷宫算法分析与改进。本项目最终分别针对电脑鼠项目情况、电脑鼠程序算法及分析和电脑鼠硬件分析及改进完成了3篇研究性论文。本文重点讨论电脑鼠走迷宫项目的整体情况，具体介绍项目背景、项目组成及项目开展当中遇到的一些问题，对整个项目进行总结。本文由陈高娟和张扬共同撰写。其中，陈高娟主要负责第一章项目背景，第四章项目组成部分和第五章项目总结，张扬主要负责第二章电脑鼠项目介绍第三章电脑鼠软件和硬件 。第二章 电脑鼠项目介绍2.1 电脑鼠的起源与发展2.1.1电脑鼠的起源1956年，“信息论之父”克劳德埃尔伍德香农（Claude Elwood Shannon）参与发起了达特默斯人工智能会议，成为这一新学科的开山鼻祖之一。他不仅率先把人工智能运用于电脑下棋方面，而且发明了一个能自动穿越迷宫的“电老鼠”，以此证明计算机可以通过学习提高智能。最初，电脑鼠是机械的。1972年，机械设计杂志发起了一场比赛。在比赛中，仅由捕鼠器弹簧驱动的机械鼠不停地与其它参赛鼠竞赛，以判断哪个机械鼠能够沿着跑道跑出最长的距离。冠军是“Mousemobile”，它跑了825.3英尺。1977年，IEEE Spectrum杂志提出电脑鼠的观念。电脑鼠是一个小型的由微处理器控制的机器人车辆，在复杂迷宫中具有译码和导航的功能和能力。2.1.2国际电脑鼠的发展1979年，电子和电气工程师协会（IEEE）通过其Spectrum and Computer杂志发起了一场竞赛，比赛项目是为制造出能够在最短时间内自主走出迷宫的电脑鼠的人奖励$1000美元。尽管没有人知道会是什么结果，但Spectrum的Roger Allan宣称全世界约有6000人对该比赛有兴趣，并于3月份的截至时期前付了$3.95美元参赛费。竞赛给每只电脑鼠多次试运行机会，只要在试运行期间顺利完成了一次就可以参加6月在纽约的国际计算机会议进行的决赛。有6只电脑鼠进入了决赛，其中两只电脑鼠最终完成了比赛。1980年，在伦敦Euromicro80举办了一场欧洲版的比赛，但是18个参赛鼠都没能成功地完成这个迷宫赛。比赛的观众当中，有五位来自日本新科学基金会的代表，他们将此比赛规则带回了东京，后来还在1980年11月举办了首场全日本电脑鼠比赛。1985年8月，在日本Tsukuba举行了首场世界电脑鼠大赛。电脑鼠来自整个欧洲和美国，使用的传感器有红外的、超声波的和CCD的，驱动装置有步进电机的和DC伺服电机的。所有最高奖项均由日本的电脑鼠Noriko-1赢得，一举成为世界冠军。1987年工程协会（IEE）在伦敦举办了一场电脑鼠锦标赛，13个电脑鼠角逐冠军。来自美国麻省理工学院（MIT）的DavidOtten带着他的两个参赛鼠MiteeMouseI和MiteeMouseII获得了一等奖和二等奖。比赛采用新的得分体制，以奖励那些能够智能、高效地解开迷宫的方案和能够独立运行的电脑鼠。在1989年10月21日，IES邀请澳大利亚、日本、台湾、UK和美国最好的电脑鼠来参加新加坡首场国际电脑鼠大赛。来自美国和台湾的电脑鼠等待着复仇的时机，因为他们在7月份的伦敦大赛曾一度被新加坡打败。13个来自当地的和外国的参赛者的电脑鼠在3个小时的比赛中，表演出来的速度和敏捷程度使得观众叹为观止。新加坡获得第2名、第4名、第5名和第7名的事实出乎了很多人的意外。1994年举行的第十五届全日本电脑鼠竞赛已经具有相当大的规模，超过80只电脑鼠参加了此次比赛，其中有三只来自其他国家（美国、韩国新加坡）的电脑鼠，最终美国麻省理工学院David Otten的电脑鼠MITEE 7以11秒81的成绩夺得冠军。1996年举行的第十七届全日本电脑鼠竞赛中，日本电脑鼠NORIKO-FINAL以1274的成绩击败来自美国，韩国和新加坡的电脑鼠夺得冠军。2006年，The UK Micromouse 2006 competition伯明翰举行，比赛包括maze solver, non-contact wall follower, contact wall follower, and drag race events四类，除了英国的入围者还有来自新加坡的最优秀电脑鼠参加，最终COOL Y以5.6秒的成绩夺maze solver比赛的冠军。2006年第二十七届全日本电脑鼠竞赛中，来自新加坡南洋理工工院黃明吉教授的电脑鼠MIN4a夺得冠军。2008年，第二十九届全日本电脑鼠竞赛中，来自新加坡的电脑鼠南洋理工工院黃明吉教授凭借MIN5再次夺得冠军。2009年，在美国APEC2009电脑鼠竞赛中新加坡南洋理工工院电脑鼠队以11.81秒的综合计算时间，技压群“鼠”，击退美国麻省理工学院（Massachusetts Institute of Technology，MIT）等强劲对手三度夺得冠军。台湾龙华科技大学夺得第三名。速度最快的电脑鼠是由来自位于华盛顿的 BattelLe Northwest实验室的Art Boland，Phil Stover，和Ron Dilbeck制造的。根据Boland的观点，他们围绕一个微型计算机构建作品，这个微型计算机具有足够大的存储器，可存储需要在迷宫中99个不同位置做决定时所需的信息。通常采用的策略是，第一次通过时（允许有三次通过机会），允许电脑鼠在每个拐弯处随机选择。第二次通过时，电脑鼠尝试它“知道”在第一次没有尝试的新路线。然后用收集到的消息计算最佳路线，用于第三次通过。2.1.3我国电脑鼠的发展情况我国电脑鼠发展起步的比较晚，国内比赛从前年才开始。2008年长三角嵌入式系统创新设计应用竞赛暨IEEE标准电脑鼠走迷宫邀请赛在华东师范大学举行，50支队伍参加了电脑鼠走迷宫竞赛。比赛的规模和质量都比往年有很大的提高。2009年全国电脑鼠走迷宫邀请赛先分别于长三角、北京、天津、山东、四川、湖北、陕西和山西等赛区进行分区预赛，再有各赛区荣获一等奖的队伍参加北京的总决赛。11月8日全国电脑鼠走迷宫总决赛在北京航空航天大学首享科技大厦举行，其中曾在国际上荣获第三名的台湾龙华科技大学的电脑鼠也受邀参加了本次决赛。2.2 电脑鼠走迷宫比赛2.2.1电脑鼠Micromouse615我们采用的是由广州周立功单片机发展有限公司设计和生产的标准套件。该套件包含电脑鼠Micromouse615（电脑鼠）、IEEE标准迷宫及丰富的配套资料。Micromouse615采用铝制车架，重量轻，散热性能好。采用双步进电机，车轮直接安装在电机轴上，机械结构简单安装方便。Micromouse615车身长12cm，宽9cm，短小精悍，可灵活的在迷宫格中完成90度和180度转弯。如图Error! Reference source not found.所示图2-1 Micromouse6152.2.2 电脑鼠迷宫Micromouse Maze迷宫由256个方块（单元）组成，每个方块的大小为18 cm见方，排成16行16列。迷宫的隔墙板沿方块的四周布设，形成迷宫通道。隔墙板的两个侧面是白色的，顶部是红色的。迷宫的地板由木质材料做成，涂上不反光的黑漆。隔墙板的侧面和顶部对红外线有反射特性，而地板则对红外线有吸收特性。全迷宫四分之一迷宫图2-2该开发套件中提供2个迷宫，一个16x16的标准迷宫和一个8x8的四分之一迷宫，如图2-3所示。对于16x16的标准迷宫，迷宫的起始单元可选设在迷宫四个角落之中的任何一个。起始单元必须三面有隔墙，只留一个出口。终点设在迷宫中央，由四个的正方形单元构成。如果是四分之一迷宫，终点与起点就是迷宫的对角线上的两个拐角处。两个迷宫所有参数都符合IEEE电脑鼠竞赛标准， 16x16标准迷宫可用于正式比赛，8x8四分之一迷宫仅大小和标准迷宫不同，可在日常练习和小规模竞赛时使用。2.2.3 电脑鼠比赛简述最初举办电脑鼠走迷宫竞赛有两个目的，一是为公众提供一个了解微电子学发展及IEEE协会的窗口，其次是为工程师们提供一个发挥聪明才智的空间，激发他们的创造力，最终带动相关领域的技术发展。这一想法最初是由Spectrum的编辑，Donald Christiansen提出的。最新的电脑鼠比赛规则是2006年国际电工和电子工程学会（IEEE）制定的电脑鼠走迷宫竞赛规则1，这个规则将会对我们制作电脑鼠具体方案的设计提供依据。电脑鼠的基本功能是从起点开始走到终点，这个过程称为一次“运行”，所花费的时间称为“运行时间”。从终点回到起点所花费的时间不计算在运行时间内。电脑鼠从第一次激活到每次运行开始，所花费的时间称为“迷宫时间”。如果电脑鼠在比赛时需要手动辅助，这个动作称为“碰触”。竞赛使用这三个参数，即运行时间迷宫时间和碰触，从速度求解迷宫的效率和电脑鼠可靠性三个方面来进行评分。电脑鼠的得分是通过计算每次运行的“排障时间”来衡量的。所谓排障时间是这样计算的：先将迷宫时间的1/30加上一次运行时间，如果这次运行结束以后电脑鼠没有被碰触过，那么还要再减去10秒的奖励时间，这样得到的就是排障时间。电脑鼠在迷宫中的停留或运行的总时间不可超过15分钟，在限时内允许运行多次，允许取其中最短的排障时间作为参赛的计分成绩。当然，排障时间越短越好例如：一个电脑鼠在迷宫中运行时间为4分钟（240秒）没有碰触过，迷宫时间使用了20秒，这次运行的排障时间就是：20秒+（240秒1/30）10秒=18秒。第三章 电脑鼠硬件与软件3. 1相关开发工具我们采用广州周立功单片机发展有限公司提供的相关开发套件。开发环境采用IAR EWARM，调试工具包括LM LINK USB JTAG调试器和SPI接口的键盘显示模块。在开发过程中采用调试工具，使调试过程更为方便。1. IAR EWARM开发环境简介 IAR Embeded Workbench for ARM(下面简称IAR EWARM)是一个针对ARM处理器的集成开发环境，它包含项目管理器、编辑器、C/C+编译器和ARM汇编器、连接器XLINK和支持RTOS的调试工具C-SPY。在EWARM环境下可以使用C/C+和汇编语言方便的开发嵌入式应用程序。比较其它的ARM开发环境，IAR EWARM 具有开发容易、使用方便和代码紧凑等特点。 目前IAR EWARM 支持ARM Cortex-M3内核的最新版本是4.42a,该版本支持Luninary全系列的MCU.2. LM LINK调试器简介LM LINK 是由广州致远电子有限公司开发的低成本高性能USB JTAG调试区，它专门用于对Luninary系列单片机程序的调试和卸载。该调试器结合IAR EWARM 集成开发环境，可支持所有LM3S系列MCU的程序的下载与调试。LM LINK采用USB接口与电脑连接，打破传统的并口和串口下载程序的方式，无论是台式电脑还是笔记本电脑都应用自如。透明外壳封装、设计小巧、晶莹剔透、价格低廉、性价比高、调试下载更快、使用更加方便。3.2电脑鼠硬件3.2.1 电脑鼠硬件组成电脑鼠的硬件大致分为以下几部分：传感器、执行部件、微处理器、机械结构，如图3-1所示电脑鼠传感器执行部件微处理器机械结构红外传感器车身设计步进电机LM3S615图3-1电脑鼠硬件结构图1.传感器它是电脑鼠感知外界环境的窗口，是电脑鼠的双眼。好的传感器是电脑鼠准确获取外部环境信息以做出正确判断的依据，是电脑鼠灵敏快捷的保证。红外测距方式在电脑鼠上应用最广。常见的红外如图3-2所示Micromouse615使用5组红外传感器，每组红外传感器由红外发线射器和红外线接收器组成用于检测迷宫墙壁信息，分别用于检测左、左前、前、右前和右五个方向的墙壁信息。我们用U1-U5表示红外线接收头传感器，RF1-RF5为发送红外线装置，使用5组可调电阻W1-W5控制红外信号发射强度，调整可见距离。信号采用载波调制，增强抗干扰性。图3-2 红外传感器2.执行部件电机是电脑鼠的动力源，是电脑鼠的四肢。只有具备健壮且灵活的四肢的电脑鼠才有可能在比赛中高效的解开迷宫。电机不但要能输出足够的马力还要便于控制，在此基础上再配以合适的控制算法就能使电脑鼠快速而精确的行走。电脑鼠中常用的是步进电机和直流电机，步进电机控制容易，但直流电机使电脑鼠控制更加灵敏。Micromouse615上有两个两相四线制的步进电机，左电机和右电机用来控制电脑鼠前进，左转和右转，停止。步进电机是一种将电脉冲转化为角位移的执行机构。当步进驱动器接收到一个脉冲信号，它就驱动步进电机按设定的方向转动一个固定的角度(称为“步距角”)，它的旋转是以固定的角度一步一步运行的。可以通过控制脉冲个数来控制角位移量，从而达到准确定位的目的；同时可以通过控制脉冲频率来控制电机转动的速度和加速度，从而达到调速的目的。四相步进电机如图3-3所示图3-3 四相步进电机3.微处理器微处理器是电脑鼠的核心部分，是电脑鼠的大脑。几乎所有的信息，包括墙壁信息，位置信息，角度信息和电机状态信息等都需要经过微处理器处理并做出相应的判断。所有的数据分析，算法实现和执行指令的发出等都需要由微处理器来完成。Micromouse615的微控制器是由Luminary 公司生产的Cotex-M3内核的ARM处理器LM3S615，该芯片具有32位RISC性能，带有8KB单周期Flash，2KB单周期SARM，2个定时器(每一个都可配置为一个32位定时器或两个16位定时器，以及高达18个GPIO口。4.机械结构电脑鼠要能够在迷宫里面灵活穿梭，必须有一副好身板，有适合在迷宫中快速运行的身体结构。首先他必须结实，拥有两只东倒西歪的轮子的电脑鼠是很难不在迷宫中碰壁的，其次身材娇小的电脑鼠在迷宫里是会更灵活的，它有更大的空间用于完成转弯，有更大的空间用于纠正姿，最后体重太大和没有平衡感的老鼠也是不适宜迷宫竞赛的。基于如此多的考虑，一只学富五车而又娇小玲珑的电脑鼠要求我们从机械上面有更多创新。电脑鼠的机械结构如图3-4所示，左边是车身电路板，右边是电脑鼠行走的两个车轮及控制车轮的电机。图3-4 电脑鼠的机械结构3.2.2电脑鼠基本动作电脑鼠基本动作包括路口检测，行走控制和转弯。路口检测：由安装在前、右、左的三个红外线发射对管和接收部件实现，利用时钟中断来控制，实现远红外测距功能，探测前、右、左有无障碍。行走控制：由左、右45角的两个红外线发射对管和接收部件实现，利用时钟中断来控制，实现近红外测距功能，保持电脑鼠在中轴线上行走，避免撞墙。转弯：由于电机采用的是步进电机，只要对一个电机的步数进行设定，电机采用PWM进行驱动，另外一个电机停止或者反转同样的步数，当然这个步数要自己实际测量。3.3电脑鼠软件电脑鼠的软件主要可以分为等高图制作模块、冲刺模块、转弯模块、搜索模块、相对方向与绝对方向转变模块、墙壁资料存储模块和电脑鼠搜索策略模块这七个模块。如图3-5所示。图3-5 软件主要模块图电脑鼠软件主要模块等高图制作模块冲刺模块转弯模块搜索模块相对方向与绝对方向转变模块墙壁资料存储模块电脑鼠搜索策略模块下面介绍一下电脑鼠运行中必须要知道的一些参数，及其在程序运行过程中的用途。电脑鼠在运行中可以划分为四个状态：等待，启动，搜索迷宫和冲刺状态。1.等待状态在该状态中，电脑鼠静止在起点，等待开始命令。同时实时显示传感器检测结果和电池电压，这样方便调试传感器的灵敏度和更换电池。当控制启动的按键按下后，电脑鼠进入启动状态。2.启动状态在该状态中，电脑鼠根据第一次转弯的方向判断起点是在坐标的（0，0）点还是在（15，0）点。其程序流程图见图3-6所示：图3-6判断起点坐标程序流程图3. 搜索迷宫状态 在该状态中，电脑鼠的任务就是搜索并记忆迷宫地图，以采用右手搜索法则为例搜索全迷宫，其流程图如图3-7所示。图3-7 迷宫搜索流程图4.冲刺状态迷宫搜索完毕后，根据算法找出一条最优路径冲刺到终点，冲刺结束后返回到起点。3.3.1等高图制作模块等高图就是等高线地图的简称，有如一般地图可以标出同一高度的地区范围，或有如气象报告时的等气压的范围和大小。那么等高图运用在迷宫地图上，可以标出每个迷宫格到起点相等步数的关系，许多封闭路径的逃脱与冲刺的关卡都可以在制作出等高图后迎刃而解，使电脑鼠更容易逃脱，少走一些弯路。首先开辟一块16*16的二维数组空间(MapStep1616)，其中每一个元素代表迷宫的一个方格，用以计算后储存各方格至起点的最短路径步数（所谓步数即为路径中经过的方格数）。当起点坐标处标识为1时，可以直接达到的相邻方格均为2，再远的方格的等高值依次递增，这样距离越远的地方等高值越大。具体的实现方法可以参照电脑鼠研究性课题的*研究性论文。3.3.2冲刺模块冲刺函数的实现是建立在等高图已经建立好的基础上的。当电脑鼠要进行冲刺的时候，调用冲刺函数时，首先会调用等高图制作函数将等高图制作好。然后该函数通过等高图和墙壁信息来进行电脑鼠的行进控制。当然，我们认为电脑鼠在走直道的时候应该会比走弯道的时候，来的更快一点，所以我们没有进行特殊的加权，直接是走直道的。电脑鼠从起点开始，一直利用等高图信息和墙壁信息进行一格一格的对比，只有当这一格在电脑鼠绝对方向上时，这一格才算记录到进行直道冲刺，同时直道格数加一。当遇到电脑鼠要转弯的时候，已经将要走的步数记录下来了，接下来直接调用行进函数，控制电脑鼠走完记录好的步数后，即走到电脑鼠要转弯的地方后，再进行转弯，然后接着继续进行上一步的动作。具体的实现方法可以参照电脑鼠研究性课题的*研究性论文。3.3.3转弯模块转弯也是电脑鼠运行时必不可少一部分，同时转弯也分为静止转弯和行进中转弯。静止转弯要求电脑鼠首先要停止，主要用在电脑鼠进行搜索中，这时要求电脑鼠要绝对的稳定，所以采用静止转弯比较好。行进中转弯的特点是消除了静止转弯的要求电脑鼠停止的弊端，可以节省一些时间，主要用在电脑鼠进行冲刺时，这时要求电脑鼠要以竟可能短的时间从起点到达终点，所以行进中转弯可以节省不少的时间。静止转弯时，对两个电机设置走相同的步数，如当要转左转90时，设置左电机向后走40步，右电机向前走40步。通过两个电机走的方位不同，来实现静止转弯，但静止转弯的缺点就是，在转弯前首先要让电机停止，然后再对电机的要走的步数进行赋值，这样会浪费一点时间。行进中转弯时，让一个轮子停止，一个轮子进行运转来实现。如当要左转90时，设置左电机停止转动，右电机转动80步。与静止转弯区别开来的是，电机的步数在其他的函数中赋值好了，在转弯函数中只要一开始将一个电机停止转动就可以了，而不用一开始就将两个电机都停止，然后对电机的步数进行赋值，这样的话，就可以节省一些不必要的时间。3.3.4搜索模块电脑鼠一开始进行迷宫搜索时必须要用到这个模块。通过这个模块电脑鼠进行迷宫的墙壁信息的采集，电脑鼠所走过的每个坐标都会有一个相应的墙壁信息，这些墙壁信息是电脑鼠后来进行等高图制作和冲刺的基础。在进行搜索时，电脑鼠的红外是在时钟中断下，不停地被驱动的，这一连串的动作有发射短波红外，发射长波红外，和接受红外。处理器通过读取红外接收器对应引脚的信息来判断四周的情况，同时将迷宫的信息进行编码后存储在对应坐标的一个迷宫情况数组中。当遇到岔路时，程序跳出搜索函数，回到主函数中将岔路坐标进行处理，具体参见*主函数。将这个坐标进行入栈，再回到搜索函数中，根据所选用的搜索法则选择好一条路后，继续搜索，并这样一直下去直到电脑鼠运行到终点。3.3.5迷宫地图相对方向与绝对方向的建立迷宫是用18cm18cm大小的方格组成的，其行列各有16个方格。为了让电脑鼠记住所走过的各个迷宫格的信息，我们就坐标的方法来对256个迷宫格进行编号。根据坐标的的定义和比赛规则，也为了把上下左右这四个方向参数转换为微控制器能够识别的符号，在本文中，将向上的方向定义为0、向右为1、向下为2、向左为3，如图3-8所示。图3-1 迷宫方向值定义图3-8 迷宫方向值定义只要有了迷宫的坐标和方向后，电脑鼠在迷宫行走就可以随时知道自己所处的位置和方位了。然而，对于电脑鼠而言，红外线传感器的位置和方向是固定不变的，但是对于迷宫，红外线传感器的位置和方向是随着老鼠前进方向的变化而一起变化的。这是由于选择参照物的不同而引起的，由此引出了两个方向的问题：相对方向和绝对方向。相对方向：以电脑鼠当前行走方向为参照的方向。绝对方向：以迷宫绝对坐标平面为参照的方向。那么传感器所检测到的信息如何才能更便于处理呢？周立功提到了如果以相对方向存储的资料将是混乱的，不仅要存储麻烦，而且要记录起检测时电脑鼠所处的方向，存储量比较大，处理起来也非常麻烦。而以绝对方向存储就不需要考虑当前电脑鼠的方向。这样就会经常遇到相对方向和绝对方向的互换。在本文中采取了以变量Dir记录电脑鼠前进方向上的绝对方向值，即前方的绝对方向值始终为Dir。这样电脑鼠的相对方向转换成绝对方向如表3-1所示。表3-1 相对方向转换成绝对方向相对方向绝对方向电脑鼠前方Dir+1电脑鼠右方（Dir+1）%4电脑鼠后方（Dir+2）%4电脑鼠左方（Dir+3）%4有时候系统还需要根据绝对方向（Dir_dst）和当前的绝对方向（Dir）求出方向偏差值（Dir），如式3-1所示。Dir = Dir_dst Dir 式3-1为了使Dir的值落在03的范围内，计算式进行式3-2的转换如下：Dir =（Dir_dst + 4 Dir）%4 式3-2这时就可以根据方向偏差值求出电脑鼠的相对方向，如表3.2所示。表3-2 绝对方向转换成相对方向绝对方向差值（Dir）相对方向 0电脑鼠前方 1电脑鼠右方 2电脑鼠后方 3电脑鼠左方假设电脑鼠已知当前位置坐标（X，Y），那么就可以求出在其某绝对方向上的相邻坐标值，如表3.3所示。该表是可逆的，即可以根据坐标值的变化求出绝对方向。表3-3 坐标转换绝对方向坐标当前位置（X，Y）上方（0）（X，Y+1）右方（1）（X+1，Y）下方（2）（X，Y-1）左方（3）（X-1，y）当电脑鼠达到一方格坐标时，应根据传感器检测结果记录下当前方格的墙壁资料，为了方便管理和节省存储空间，每一个字节变量的低四位分别用来存储一个方格四周的墙壁资料，如表3.4所示。因为迷宫共有88个方格，所以可以定义一个1616的二维数组变量来保存整个迷宫墙壁资料。表3-4 墙壁资料存储方式变量位代表的绝对方向备注bit0上方（0）1：有路，0：有墙壁bit1右方（1）1：有路，0：有墙壁bit2下方（2）1：有路，0：有墙壁bit3左方（3）1：有路，0：有墙壁bit7bit4保留位迷宫墙壁资料全部初始化为0，表示走过迷宫格至少有一方没墙壁，即墙壁资料不为0。这样就可以通过单元格存储的墙壁资料是否为0来确定该单元格是否曾搜索过。3.3.6墙壁资料存储为了记忆迷宫的详细信息，需要对迷宫单元的位置进行线路标记。全迷宫共有1616个单元组成，可采用二维坐标方式标记，即用每个单元的XY坐标表示，如起点可标记为（0，0），终点为（7，7）。此外，还需要对迷宫单元的可行进方向进行标记，可采用绝对方位或相对方位二种方式。绝对方位：这是一种与电脑鼠行进方向无关的标记方式，以一个四位的二进制数，分别表示“东”“西”“南”和“北”四个方向。以1表示允许行进（无墙壁），0表示不允许行进（有墙壁）。相对方位：这是一种与电脑鼠行进方向有关的标记方式，以一个三位的二进制数即可实现标记，分别表示“前”“左”“右”， 以1表示允许（无墙壁），0表示不允许（有墙壁）。3.3.7电脑鼠搜索策略电脑鼠走迷宫可以采用全迷宫探索策略，即将迷宫的所有单元均搜索一次，从中找出最佳的行走路径。这种策略需要有足够的时间或探测次数，但在IEEE竞赛规则中每场竞赛只有15分钟的时间，因此是不可能的。另一种方法是部分迷宫探索策略，即在有限的时间或探测次数下，只探测迷宫的一部分，从中找出次最佳的路径，显然只能采用这种策略。电脑鼠在一巷道内行走，如果最后无路可走，则该巷为死巷。电脑鼠在任一单元内，可能的行走方向最多只有三个(前、左、右)，如果有二个或二个以上的可能行走方向，称为交叉，遇有交叉时，由于有多个可以行走的方向，在行走方向的选择上，可有下面的几种选择法则：(1)右手法则：遇有交叉时，以右边为优先的前进方向，然后是直线方向、左边方向。(2)左手法则：遇有交叉时，以左边为优先的前进方向，然后是直线方向、右边方向。(3)中左法则：遇有交叉时，以直线为优先的前进方向，然后是左边方向、右边方向。与此类似的还有中右法则。(4)乱数法则：遇有交叉时，取随机值作为前进方向。(5)向心法则：由于终点在迷宫的中心，遇有交叉时，以向迷宫中心的方向为优先的前进方向。第四章 问题总结及改进经过大家几个月的奋斗，电脑鼠项目结束了，在这个过程中也遇到过不少问题，下面简单的介绍一下我们遇到的问题及解决方案：4.1硬件方面的问题及解决方法问题1：芯片的一些封装的定义，以及其的引脚的用途。解决方案：在给的光盘资料里面，有一个PDF文件是专门介绍这个芯片的一些封装形式，以及其引脚的一些用途，以及它的使用方式。问题2：电机的驱动程序。解决方案：在所给的源码中，有一个是关于电机的驱动，电脑鼠所用的电机是步进电机，它的驱动方式是通过PWM打脉冲给电机来驱动的，但是电机转动的状态有很多种，这是由于电机是用磁性来转动的，当电压分配到不同的位置并连续不断时，电机会跑动起来，当顺序相反的时候，电机会反转。问题3：红外的调试。解决方案：红外相当于电脑鼠的“眼睛”，它的灵敏度十分的重要，所以在电脑鼠开始要跑动的时候，一定要先把红外调好，假如手边有7289这个板子的时候，调试工作会相当的轻松，但是，假如手边没有7289这个板子的时候，这时你也要有方法去应付，这时只能靠设定断点来进行监控，并设置监控的变量来进行随时的跟踪，了解好电脑鼠的运行情况，这也是一样相当好的调试手段。4.2 软件方面的问题及解决方法问题1：等高图的制作解决方案：等高图的制作是通过电脑鼠已经搜索的基础上的，由起点到我们所设定的终点，像波浪一样层层推进，当碰到交叉的地方的时候，它也会相应的分叉开来，每条路径都会算到，直到电脑鼠没有搜索到的地方或者到达了设定的终点。问题2：冲刺函数的实现解决方案：冲刺函数的实现方式是建立在等高图已经建立好的基础上的，然后该函数利用等高值和迷宫信息来进行行进，当遇到转弯的时候，电脑鼠就会调用相应的转弯函数来让电脑鼠进行转弯。问题3：电脑鼠搜索的时候，是如何进行迷宫的情况的采集。解决方案：当电脑鼠进行迷宫搜索的时候，每隔一个系统时钟中断，MCU就会对红外进行一次变动，或者发射红外，或者采集接受情况，每个时钟中断做一次动作，然后将这个挡板信息告知在行进中的电脑鼠，然后再将对应的挡板信息中相应的位和某个字符做与运算，将结果保存至一个数组中，连续这样3次，将左，前，右都过一遍，后面永远设为没抢来处理。问题4：绝对方向和相对方向的转换。解决方案：电脑鼠在行进的时候，难免会出现转弯这个情况，当电脑鼠在转弯的时候，系统要预先判断电脑鼠是左转还是右转，这个就是电脑鼠的相对方向，但是电脑鼠在迷宫中行进的时候还会有一个绝对方向，这个绝对方向是不允许有差错的，一旦弄混了以后，电脑鼠行进就会出现错误，所以，电脑鼠在进行转弯的时候，当判断出是左转还是右转以后，还要将电脑鼠的绝对方向也进行改变一下，这个左边才不会被打乱。问题5：行进中转弯的实现。解决方案：行进中转弯是我们工作的重点，是我们最花时间的地方，王凤林学长写的程序中，出现了太多的停止代码，这样会影响电脑鼠转弯时候的速度，以及其转过的方位难以判定，所以这个方案感觉不怎么好，我认为的方式是，在转弯行进中程序中，停止电机的代码不要太多，尽量的进行避免，这样的话可以让电脑鼠跑起来的时候更加的流畅，也更加的美观，所以我的方案是在转弯程序中，代码不多，就是让一个电机停止而已，直到另外一个电机把步数走完为止，而步数的设定也在另外一个函数中，而不是在转弯程序中，转弯程序从而变得相当的简单。问题6：搜索策略的改变。解决方案：搜索策略在电脑鼠比赛中，也占了相当大的取胜比例，如何有更好的搜索策略就意味着你将比别人少走不少的弯路，这样也可以大大的节省了时间，特别是在16*16这样大的迷宫中，即使你的搜索时间要除30，但是也会浪费不少的时间，所以高效地搜索策略是很有用的，我们的策略是，电脑鼠采用中心法则不变，但是我们有在回搜的时候，当发现一条路比原来搜索出来的路更短的时候，我们马上进行再次的冲刺，一般第一条路不是最短的，第二次找到的路才是，这样的方法可以在一定的程度上弥补一些时间，而不是在浪费在接下来漫无边际的搜路上。第五章 项目总结与展望5.1 课程学习过程我们的项目围绕竞赛展开，整个课程的学习阶段可以分成竞赛准备、参加竞赛、竞赛后的交流三个阶段。5.1.1 竞赛准备阶段前期准备阶段。从2009年5月研究性课程立项获批开始到暑假前。项目组制定了教学预案和实施计划，每个人在清楚了各自的任务目标后都制定了个人的学习计划。学习阶段。 我们的课程学习从09年6月份真正开始。每个人在清楚了各自的任务目标后都制定了学习计划。小组成员一起利用课余时间和晚自习时间做一些电脑鼠相关基础知识的学习，从暑假开始，徐老师为我们联系了苏大的实验室作我们的学习环境，那里有迷宫可供调试运行，还有学长为我们解答疑难，但因为住宿等因素的限制，我们组只有两位同学留下来学习。09年7月、8月，他们先一起研究和讨论电脑鼠数据手册，在明白所用芯片的封装、引脚的用途、电机的驱动程序、等高图的制作等基本知识后学会调试红外，并试着修改程序。我们的程序基础是王凤林学长去年参加比赛的程序，但是他的程序出现太多的停止代码，所以修改程序把电脑鼠的静止转弯改成行进中转弯，这对电脑鼠的速度有了很大提高，但是对电脑鼠的稳定性却有了很高的要求，因此这成了他们暑假的工作重点。9月份开学，我们聚在一起讲述各自暑假的生活经历及收获，之后便在留在苏大学习的成员的带领下一起学习，因为有他们的指导，我们的学习比较轻松，周末我们也会轮流到苏大实验室去学习，这时候的重点是算法研究。期间我们购买了自己的电脑鼠，方便了程序的调试运行，并确定了通过预赛能参加全国决赛的目标。5.1.2参加竞赛阶段预赛于11月1日在上海第二工业大学举行，因为电脑鼠的红外对环境要求比较高，所以我们参赛安排了三个成员和徐老师提前到赛点做一些准备工作，其他成员带着参观的学弟学妹门次日到达。因为参赛队伍有三十多个，分预赛和决赛，预赛我们抽到第五组和第十六组出场，第五组以7.4秒排在了第七位，上海交大以4.4秒排在了第一位，我们的另一组小车因为出现碰撞跑了20.15秒，最后因规定成绩在20秒以内进入决赛遗憾出局，决赛我们的电脑鼠发挥的比较好，最终以4.4秒的成绩列第四名，上海交大仍以3.1秒的成绩列第一所以我们顺利的完成了初期目标，进入了全国决赛。全国决赛定于11月8日在北京航空航天大学举行，两次比赛的时间比较接近，所以我们也没有太多的时间去准备，从上海回来我们主要对电脑鼠的直线速度做了改进，希望能提高总体成绩，因为流感，我们的决赛在北航附近的首享科技大厦举行，当天比赛抽取的迷宫比较复杂，对电脑鼠的稳定性要求特别高，所以速度比较快的电脑鼠发生碰撞的概率特别大，由于一旦碰撞就失去奖励10秒的机会，所以发生碰撞对成绩无疑有很大影响。结果有很多队伍没能完成比赛，我们的电脑鼠在比赛过程中发生了碰撞，最终以76.5秒的成绩排在了十八名，陕西科技大学在来自25所高校的37支队伍中以15.7秒获得全国电脑鼠走迷宫的冠军，来自台湾龙华科技大学的小车也意外