下载文档原格式
2016年度天津市高职高专院校学生技能大赛“电脑鼠走迷宫”赛项规程天津渤海职业技术学院2016年10月2016年天津市职业院校技能大赛赛项规程一、赛项名称赛项编号：赛项名称：“启诚杯”电脑鼠走迷宫竞赛英语翻译：“QiCheng Cup”Micromouse Contest赛项组别：高职学生组赛项归属产业：电子信息产业二、竞赛目的“启诚杯”电脑鼠走迷宫竞赛项目，从技术上涵盖了物联网应用技术、电子信息工程技术、嵌入式技术、通信技术、软件技术、计算机网络技术、信息安全技术、移动通信技术、计算机应用技术、应用电子技术、计算机控制技术、机电一体技术、自动化技术等多个专业技术，涉及:传感器检测、人工智能、自动控制和机电运动部件应用等技能和综合职业素养。
全面展现高职教育的发展水平，提高电子信息类高素质、高技能应用型人才的培养质量。
通过竞赛，推动电子信息行业企业人才能力需求，顺应科技发展将嵌入式技术开发，智能算法优化等前端先进技术融入竞赛内容中，进一步深化校企合作，引导高职电子信息类专业开展单片机应用、嵌入技术应用、物联网技术应用等，课程建设和教学改革，促进创新型人才培养模式的改革与发展，增强高职电子类专业学生就业竞争力，推进创新创业教育，强化创业指导和服务，提高就业水平。
三、竞赛内容比赛分理论考试和实际操作两大环节，其中理论考试占总成绩的20%，实际操作考核占80%，实际操作分“迷宫赛部分”占总成绩的50%，“创新赛部分”占总成绩的30%。
1、理论考试部分：主要考核高职各专业课程中所涉及的电子技术、单片机技术、嵌入式技术及程序设计基础知识，与工程实践创新类-电脑鼠竞赛相关的基本知识及基本能力。
以理论知识笔答方式进行，考试题型由主观题与客观题组成。
考核知识点如下：1）比赛通过理论考试和走迷宫竞赛，综合考查学生对嵌入式系统、软件编程、传感器理论、程序算法等掌握情况，主要技能点与知识点如下：2）嵌入式硬件知识：电脑鼠通过ARM处理器的软硬结合编程调试，要求学生掌握IAR编程环境的配置与使用、ARM处理器工作方式与程序编写及下载运行的操作流程、嵌入式技术的相关理论。
项目编号：31SZDYKC-090601 全国大学生电子设计竞赛项目名称：电脑鼠走迷宫学生班级：1104班学生姓名：王忆文所在系（部）：通信工程系指导教师：摘要“电脑鼠”是使用嵌入式微控制器、传感器和机电运动部件构成的一种微型机器人，可以在“迷宫”中自动记忆和选择路径，快速地达到所设定的目的地。
电脑鼠走迷宫竞赛是一项具有一定难度、富有挑战性和趣味性的比赛。
能力。
通过系统分析、硬件设计、软件设计、整合电路设计、汇编语言、C语言专业知识解决问题的综合应用能力,激发我们对电脑鼠的研究兴趣。
创新点是提出了对电脑鼠电源电路、传感器电路的改进方案。
给出了电机控制算法、用于纠正姿态的算法、传感器驱动算法、连续转弯算法、迷宫信息采集算法以及迷宫搜索与迷宫最短路径算法等算法模块。
关键词：嵌入式系统，电脑鼠，智能算法ABSTRACT"Computer mouse" is the use of embedded microcontrollers, sensors and electromechanical moving parts consisting of a micro-robot maze memory and automatically select the path to reach the set destination. Computer Mouse Maze Competition is a certain degree of difficulty, challenging and fun game.completion of the research program circuit board testing, knowledge and technical skills in the school curriculum learning algorithm, data query and retrieval, project management, integration cultivate awareness of scientific and technological innovation and hands-on design capabilities. System analysis, hardware design, software design, integrated circuit design, assembly language, C language application of knowledge in the development of SCM culture integrated application skills, stimulate our interest in the study of computer mouse use our expertise to solve the problem.The innovation of the computer mouse power circuit, sensor circuit improvement program. Motor control algorithm, the algorithm used to correct posture, the sensor-driven algorithm, continuous turning algorithm, the maze information collection algorithms, and maze search maze shortest path algorithm, algorithm module.Keywords：Embedded System，Micromouse，Intellegent Algorithm目录摘要 (2)第一章前言 (2)1.1项目背景 (2)1.2项目介绍第三章电脑鼠硬件与软件 (2)第二章电脑鼠硬件及软件 (4)2.1电脑鼠的硬件 (4)2.1.1 电脑鼠硬件组成 (4)2.1.2电脑鼠基本动作 (6)2.2电脑鼠软件 (7)2.2.1等高图制作模块 (9)2.2.2冲刺模块 (10)2.2.3转弯模块 (10)2.2.4搜索模块 (11)2.2.5迷宫地图相对方向与绝对方向的建立 (11)2.2.6墙壁资料存储 (13)2.2.7电脑鼠搜索策略第四章问题总结及改进 (14)第三章问题总结及改进 (15)总结 (19)参考文献 (20)第一章前言所谓“电脑鼠”，英文名叫做MicroMouse，是使用嵌入式微控制器、传感器和机电运动部件构成的一种智能行走装置的俗称。
一种电脑鼠走迷宫的算法电脑鼠走迷宫的算法1探测策略电脑鼠走迷宫可以采用全迷宫探索策略，即将迷宫的所有单元均搜索一次，从中找出最佳的行走路径。
这种策略需要有足够的时间或探测次数，但在IEEE竞赛规则中每场竞赛只有15分钟的时间，因此是不可能的。
另一种方法是部分迷宫探索策略，即在有限的时间或探测次数下，只探测迷宫的一部分，从中找出次最佳的路径，显然只能采用这种策略。
电脑鼠在一巷道内行走，如果最后无路可走，则该巷为死巷。
电脑鼠在任一单元内，可能的行走方向最多只有三个（前、左、右），如果有二个或二个以上的可能行走方向，称为交叉，遇有交叉时，由于有多个可以行走的方向，在行走方向的选择上，可有下面的几种选择法则：•右手法则：遇有交叉时，以右边为优先的前进方向，然后是直线方向、左边方向。
•左手法则：遇有交叉时，以左边为优先的前进方向，然后是直线方向、右边方向。
•中左法则：遇有交叉时，以直线为优先的前进方向，然后是左边方向、右边方向。
与此类似的还有中右法则。
•乱数法则：遇有交叉时，取随机值作为前进方向。
•向心法则：由于终点在迷宫的中心，遇有交叉时，以向迷宫中心的方向为优先的前进方向。
2标记为了记忆迷宫的详细信息，需要对迷宫单元的位置进行线路标记。
全迷宫共有16×16个单元组成，可采用二维坐标方式标记，即用每个单元的XY坐标表示，如起点可标记为（0，0），终点为（7，7）。
此外，还需要对迷宫单元的可行进方向进行标记，可采用绝对方位或相对方位二种方式。
绝对方位：这是一种与电脑鼠行进方向无关的标记方式，以一个四位的二进制数，分别表示“东”﹑“西”﹑“南”和“北”四个方向。
以1表示允许行进（无墙壁），0表示不允许行进（有墙壁）。
相对方位：这是一种与电脑鼠行进方向有关的标记方式，以一个三位的二进制数即可实现标记，分别表示“前”“左”“右”，以1表示允许（无墙壁），0表示不允许（有墙壁）。
3阻断在电脑鼠试跑过程中或在最后冲刺时，需要对部分路径进行“阻断”，即在发现某条路径是死路（只有入口而无出口）时，在该路径的入口处（一般是交叉点）设置标记，即将入口的线路标记由1改为0。
电脑⿏⾛迷宫电脑⿏⾛迷宫算法改进及仿真测试（部分）2.3.5 迷宫算法改进迷宫最优路径是指从迷宫的⼊⼝到达迷宫出⼝的最短通路。
传统求解迷宫路径问题的算法⼤多采⽤⼴度优先搜索(BFS)或深度优先搜索(DFS)。
由于需要全迷宫搜索，随着迷宫规模的增⼤和复杂性的增加，上述两种算法的空间和时间复杂性将呈指数增加。
针对以上问题，本论⽂对传统算法进⾏优化改进讨论，核⼼思想是利⽤已经探索得知的迷宫信息排除不包含最短路径信息的迷宫格，不予探索。
1、单⾏、单列死点的死胡同排除算法该算法核⼼内容是进⾏数据补全，减少电脑⿏进⼊“死胡同”的次数。
其实迷宫单元的信息并不是只有访问过才能够得到，通过推断的⽅法也是可以得到的。
利⽤某个单元四周的⽅格的信息，就可以推断出此单元的信息，⽽并不需要每⼀个单元都进⾏访问。
如果⼀个迷宫单元三个⽅向有挡板，并且当该迷宫格不是终点时，那么电脑⿏进⼊该迷宫格后必然返回，这对于寻找最短路径信息⽆⽤，此时将该迷宫格第四个⽅向⼀同标记，亦即将迷宫格封闭，不让电脑⿏进⼊该迷宫格，以达到缩短探索时间的⽬的。
如图2.10中圆圈区域，当其四周搜索过时，电脑⿏不应对此区域进⾏访问。
图2.10 死胡同实例根据电脑⿏迷宫特性，迷宫四周的挡板是肯定存在的，可先进⾏预先处理。
⽽且终点四个单元的周围的⼋块挡板有且仅有⼀个是不存在的。
当电脑⿏到达终点，在明确哪个挡板不存在的同时，⽆论其它挡板是否进⾏探测过，都可将它视为挡板存在。
2、多⾏、多列死点的死区域排除算法传统搜索算法中电脑⿏从当前单元移动到下⼀单元的依据是有⽆挡板的存在及是否访问过，⽽未考虑从下⼀单元是否可以在不经过当前单元的情况下到达终点。
形象的说，此种搜索只着眼于当前电脑⿏的移动，⽽不考虑实际效果。
当电脑⿏不能从下⼀单元在不经过当前单元到达终点时，电脑⿏的运⾏就做了“⽆⽤功”，这对于迷宫搜索的执⾏效率产⽣很⼤的副作⽤。
如图2.11所⽰，⽅形区域内即是这种情况，也就是死区域。
第四届青少年机器人活动暨亚洲机器人锦标赛中国区选拔赛电脑鼠机器人迷宫竞赛规则竞赛要求使用东莞市博思电子数码科技有限公司的电脑鼠机器人器材。
如下图所示：（一）场地尺寸及环境要求1.迷宫场地由8×8个边长为180.00×180.00mm 的正方形单元组成（见图1）。
电脑鼠机器人迷宫竞赛是一种利用嵌入式微控制器、传感器和机电运动部件构成的一种智能的小型机器人比赛，它要求机器人在指定的迷宫中自动探索并找出通往终点的路径，赛中机器人需随时掌握自身的位置信息，准确获取墙壁信息并做记录，最终依靠记忆找出最佳路径并以最短的时间走出迷宫，赢得比赛。
一、简述二、规则2.图2示例场地图3.四周的隔墙将整个迷宫封闭，迷宫隔墙的侧面为白色，顶部为红色。
迷宫的地面为木质，用于隔开每个单元格的围板称为墙壁，迷宫场地的墙壁高50.00mm，厚12.00mm，因此两堵隔墙所构成的通道其实际宽度为168.00mm（示例场地图见图2）使用油漆漆成黑色。
迷宫地面上印有墙壁的定位线，作组装场地时定位墙壁的标记，隔墙侧面和顶部的涂料需能反射红外线，地板的涂料需能吸收红外线。
4.迷宫的起始单元必须有三面隔墙，余下一个出口。
例如，若没有隔墙的出口端为“北”向时，那么迷宫的外墙就构成“东”、“南”、“西”方位的隔墙。
5.6.迷宫场地中，将每个正方形单元的四角每两边相交的位置的点我们定义为“格点”。
除了停泊区域中心的格点外，其余每个格点至少要延伸出一面隔墙或与一面隔墙相接触。
由格点延伸出去的墙壁的组合方式多种多样，以迷宫左下角的一个格点为例，如下图中黑色部分为格点，示例场地图见图2A、从格点处延伸出一块墙壁后，与该节点有关的墙壁的几种布置位置如下：B、从格点处延伸出两块墙壁后，与该节点有关的墙壁的几种布置位置如下：符合本规则的迷宫场地设计方案数量众多，但迷宫的格数始终是8×8格，四边的围墙不变，变化的是围墙内部的各个墙壁，比赛时具体使用场地,由比赛现场公布。
附录IEEE电脑鼠走迷宫竞赛规则1．目的电脑鼠走迷宫竞赛的目的是制作一个微型机器人，它能在最短的时间内穿越迷宫到达终点。
参赛的机器人称为“电脑鼠”，将电脑鼠放入迷宫并启动操作的人称为“操作员”。
2．迷宫的规范(1)迷宫由16×16个﹑18cm×18cm大小的正方形单元所组成。
(2)迷宫的隔墙高5cm，厚1.2cm，因此两个隔墙所构成的通道的实际距离为16.8cm。
隔墙将整个迷宫封闭。
(3)迷宫隔墙的侧面为白色，顶部为红色。
迷宫的地面为木质，使用油漆漆成黑色。
隔墙侧面和顶部的涂料能够反射红外线，地板的涂料则能够吸收红外线。
(4)迷宫的起始单元可选设在迷宫四个角落之中的任何一个。
起始单元必须三面有隔墙，只留一个出口。
例如，如果没有隔墙的出口端为“北”时，那么迷宫的外墙就构成位于“西”和“南”的隔墙。
电脑鼠竞赛的终点设在迷宫中央，由四个的正方形单元构成。
(5)在每个单元的四角可以插上一个小立柱，其截面为正方形。
立柱长1.2cm，宽1.2cm，高5cm。
小立柱所处的位置称为“格点”。
除了终点区域的格点外，每个格点至少要与一面隔墙相接触。
(6)迷宫制作的尺寸精度误差应不大于5%，或小于2cm。
迷宫地板的接缝不能大于0.5mm，接合点的坡度变化不超过4度。
隔墙和之间的空隙不大于1mm。
3．电脑鼠的规范(1)电脑鼠必须自成独立系统，不能使用可燃物为能源。
(2)电脑鼠的长和宽限定在25cm×25cm。
每次运行中电脑鼠几何尺寸的变化不能超过25cm×25cm。
对电脑鼠的高度没有限制。
(3)电脑鼠穿越迷宫时不能在其身后留下任何东西。
(4)电脑鼠不能跳越、攀爬、钻挖和损毁迷宫隔墙。
4．竞赛规则(1)电脑鼠的基本功能是从起点开始走到终点，这个过程称为一次“运行”，所花费的时间称为“运行时间”。
从终点回到起点所花费的时间不计算在运行时间内。
从电脑鼠的第一次激活到每次运行开始，这段期间所花费的时间称为“迷宫时间”。
