电脑鼠走迷宫技术报告.docx

电脑鼠走迷宫技术报告.docx

《电脑鼠走迷宫技术报告.docx》由会员分享，可在线阅读，更多相关《电脑鼠走迷宫技术报告.docx（18页珍藏版）》请在冰点文库上搜索。

电脑鼠走迷宫技术报告

项目编号：

31SZDYKC-090601

全国大学生电子设计竞赛

项目名称：

电脑鼠走迷宫

学生班级：

1104班

学生姓名：

王忆文

所在系（部）：

通信工程系

指导教师：

摘要

“电脑鼠”是使用嵌入式微控制器、传感器和机电运动部件构成的一种微型机器人，可以在“迷宫”中自动记忆和选择路径，快速地达到所设定的目的地。

电脑鼠走迷宫竞赛是一项具有一定难度、富有挑战性和趣味性的比赛。

通过该研究性课程完成电路板测试、算法研究、资料查询与检索、项目管理等学校课程外的知识与技术技能的学习、整合培养科技创新意识和动手设计能力。

通过系统分析、硬件设计、软件设计、整合电路设计、汇编语言、C语言在单片机开发中的应用知识培养运用专业知识解决问题的综合应用能力,激发我们对电脑鼠的研究兴趣。

创新点是提出了对电脑鼠电源电路、传感器电路的改进方案。

给出了电机控制算法、用于纠正姿态的算法、传感器驱动算法、连续转弯算法、迷宫信息采集算法以及迷宫搜索与迷宫最短路径算法等算法模块。

关键词：

嵌入式系统，电脑鼠，智能算法

ABSTRACT

"Computermouse"istheuseofembeddedmicrocontrollers,sensorsandelectromechanicalmovingpartsconsistingofamicro-robotmazememoryandautomaticallyselectthepathtoreachthesetdestination.ComputerMouseMazeCompetitionisacertaindegreeofdifficulty,challengingandfungame.

completionoftheresearchprogramcircuitboardtesting,knowledgeandtechnicalskillsintheschoolcurriculumlearningalgorithm,dataqueryandretrieval,projectmanagement,integrationcultivateawarenessofscientificandtechnologicalinnovationandhands-ondesigncapabilities.Systemanalysis,hardwaredesign,softwaredesign,integratedcircuitdesign,assemblylanguage,ClanguageapplicationofknowledgeinthedevelopmentofSCMcultureintegratedapplicationskills,stimulateourinterestinthestudyofcomputermouseuseourexpertisetosolvetheproblem.

Theinnovationofthecomputermousepowercircuit,sensorcircuitimprovementprogram.Motorcontrolalgorithm,thealgorithmusedtocorrectposture,thesensor-drivenalgorithm,continuousturningalgorithm,themazeinformationcollectionalgorithms,andmazesearchmazeshortestpathalgorithm,algorithmmodule.

Keywords：

EmbeddedSystem，Micromouse，IntellegentAlgorithm

摘要………………………..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.1项目背景

电脑鼠可看作是一种具有人工智能的小型机器人，依照比赛规则，当电脑鼠放入“迷宫”起点，按下启动键之后，它就必须自行决定搜寻法则并且在迷宫中前进、转弯、记忆迷宫墙壁资料、计算最短路径、搜寻终点等功能。

电脑鼠更结合了机械、电机、电子、控制、光学、程序设计和人工智能等多方面的科技知识。

国际电工和电子工程学会（IEEE）每年都要举办一次国际性的电脑鼠走迷宫竞赛。

首场电脑鼠迷宫竞赛1979年于纽约举行，1991年以来，每年都有世界级的比赛。

2007年，国内开始举行IEEE标准电脑鼠走迷宫邀请赛,自举办以来各高校参赛踊跃。

电脑鼠走迷宫竞赛具有一定难度，是一项富有挑战性和趣味性的比赛。

电脑鼠可看作是一个集多项工程学科知识于一体的小型系统，成功的设计者通常都是合作团体，他们必须考虑电子、电气、机械以及计算机各方面的问题，重量、速度、功耗、传感技术、重心以及程序各方面都是设计中需要决定和综合考虑的因素。

电脑鼠结合了多学科知识，对于提升我们的动手能力、团队协作能力和创新能力，促进课堂知识的消化和扩展自身的知识面都非常有帮助；

1.2项目介绍

本课程将重点研究电脑鼠硬件与改进、迷宫算法分析与改进。

通过对由微处理器控制的、集传感与控制于一体的电脑鼠自动穿越迷宫过程的的研究，综合嵌入式专业的电路设计、传感器控制、单片机程序开发和算法研究等多学科知识，学生可熟悉掌握嵌入式应用开发的全过程，从而具备一定的嵌入式应用开发基础与能力。

另外，该课程可以提高学生专业学习兴趣，锻炼学生独立学习、综合运用专业知识的能力。

通过该研究性课程，我们将要完成电路板测试、算法研究、资料查询与检索、项目管理等学校课程外的知识与技术技能的学习、整合，培养科技创新意识和动手设计能力。

通过系统分析、硬件设计、软件设计、整合电路设计、汇编语言、C语言在单片机开发中的应用知识，培养运用专业知识解决问题的综合应用能力,具体包括:

（1）制定学习计划、项目计划，学会合理安排时间与事先准备的能力；

（2）检索信息，查阅资料，自主学习的能力；

（3）团体合作，与项目组成员以及老师的沟通协调能力；

（4）分析、设计、编程、调试、测试等软件设计的综合能力；

（5）规范编程，整理文档，综合演示，锻炼文字表达、语言表达能力。

（6）通过竞赛，培养责任感、荣誉感、集体观念，锻炼学生在遇到难题与压力的情况下不放弃、迎难而上，树立坚强的自信心。

第二章电脑鼠硬件与软件

2.1电脑鼠硬件

2.1.1电脑鼠硬件组成

电脑鼠的硬件大致分为以下几部分：

传感器、执行部件、微处理器、机械结构，如图3-1所示

1.传感器

传感器是电脑鼠准确获取外部环境信息以做出正确判断的依据，是电脑鼠灵敏快捷的保证。

红外测距方式在电脑鼠上应用最广。

Micromouse615使用5组红外传感器，每组红外传感器由红外发线射器和红外线接收器组成用于检测迷宫墙壁信息，分别用于检测左、左前、前、右前和右五个方向的墙壁信息。

我们用U1-U5表示红外线接收头传感器，RF1-RF5为发送红外线装置，使用5组可调电阻W1-W5控制红外信号发射强度，调整可见距离。

信号采用载波调制，增强抗干扰性。

2.执行部件

电机是电脑鼠的动力源，是电脑鼠的四肢。

只有具备健壮且灵活的四肢的电脑鼠才有可能在比赛中高效的解开迷宫。

电机不但要能输出足够的马力还要便于控制，在此基础上再配以合适的控制算法就能使电脑鼠快速而精确的行走。

电脑鼠中常用的是步进电机和直流电机，步进电机控制容易，但直流电机使电脑鼠控制更加灵敏。

Micromouse615上有两个两相四线制的步进电机，左电机和右电机用来控制电脑鼠前进，左转和右转，停止。

步进电机是一种将电脉冲转化为角位移的执行机构。

当步进驱动器接收到一个脉冲信号，它就驱动步进电机按设定的方向转动一个固定的角度（称为“步距角”），它的旋转是以固定的角度一步一步运行的。

可以通过控制脉冲个数来控制角位移量，从而达到准确定位的目的；同时可以通过控制脉冲频率来控制电机转动的速度和加速度，从而达到调速的目的。

四相步进电机如图3-3所示

3.微处理器

微处理器是电脑鼠的核心部分，是电脑鼠的大脑。

几乎所有的信息，包括墙壁信息，位置信息，角度信息和电机状态信息等都需要经过微处理器处理并做出相应的判断。

所有的数据分析，算法实现和执行指令的发出等都需要由微处理器来完成。

Micromouse615的微控制器是由Luminary公司生产的Cotex-M3内核的ARM处理器——LM3S615，该芯片具有32位RISC性能，带有8KB单周期Flash，2KB单周期SARM，2个定时器（每一个都可配置为一个32位定时器或两个16位定时器，以及高达18个GPIO口。

4.机械结构

电脑鼠要能够在迷宫里面灵活穿梭，必须有一副好身板，有适合在迷宫中快速运行的身体结构。

首先他必须结实，拥有两只东倒西歪的轮子的电脑鼠是很难不在迷宫中碰壁的，其次身材娇小的电脑鼠在迷宫里是会更灵活的，它有更大的空间用于完成转弯，有更大的空间用于纠正姿，最后体重太大和没有平衡感的老鼠也是不适宜迷宫竞赛的。

基于如此多的考虑，一只学富五车而又娇小玲珑的电脑鼠要求我们从机械上面有更多创新。

电脑鼠的机械结构如图3-4所示，左边是车身电路板，右边是电脑鼠行走的两个车轮及控制车轮的电机。

2.1.2电脑鼠基本动作

电脑鼠基本动作包括路口检测，行走控制和转弯。

路口检测：

由安装在前、右、左的三个红外线发射对管和接收部件实现，利用时钟中断来控制，实现远红外测距功能，探测前、右、左有无障碍。

行走控制：

由左、右45°角的两个红外线发射对管和接收部件实现，利用时钟中断来控制，实现近红外测距功能，保持电脑鼠在中轴线上行走，避免撞墙。

转弯：

由于电机采用的是步进电机，只要对一个电机的步数进行设定，电机采用PWM进行驱动，另外一个电机停止或者反转同样的步数，当然这个步数要自己实际测量。

2.2电脑鼠软件

电脑鼠的软件主要可以分为等高图制作模块、冲刺模块、转弯模块、搜索模块、相对方向与绝对方向转变模块、墙壁资料存储模块和电脑鼠搜索策略模块这七个模块。

如图3-5所示。

下面介绍一下电脑鼠运行中必须要知道的一些参数，及其在程序运行过程中的用途。

电脑鼠在运行中可以划分为四个状态：

等待，启动，搜索迷宫和冲刺状态。

1.等待状态

在该状态中，电脑鼠静止在起点，等待开始命令。

同时实时显示传感器检测结果和电池电压，这样方便调试传感器的灵敏度和更换电池。

当控制启动的按键按下后，电脑鼠进入启动状态。

2.启动状态

在该状态中，电脑鼠根据第一次转弯的方向判断起点是在坐标的（0，0）点还是在（15，0）点。

其程序流程图见图3-6所示：

图3-6判断起点坐标程序流程图

3.搜索迷宫状态

在该状态中，电脑鼠的任务就是搜索并记忆迷宫地图，以采用右手搜索法则为例搜索全迷宫，其流程图如图3-7所示。

图3-7迷宫搜索流程图

4.冲刺状态

迷宫搜索完毕后，根据算法找出一条最优路径冲刺到终点，冲刺结束后返回到起点。

2.2.1等高图制作模块

等高图就是等高线地图的简称，有如一般地图可以标出同一高度的地区范围，或有如气象报告时的等气压的范围和大小。

那么等高图运用在迷宫地图上，可以标出每个迷宫格到起点相等步数的关系，许多封闭路径的逃脱与冲刺的关卡都可以在制作出等高图后迎刃而解，使电脑鼠更容易逃脱，少走一些弯路。

首先开辟一块16*16的二维数组空间（MapStep[16][16]），其中每一个元素代表迷宫的一个方格，用以计算后储存各方格至起点的最短路径步数（所谓步数即为路径中经过的方格数）。

当起点坐标处标识为1时，可以直接达到的相邻方格均为2，再远的方格的等高值依次递增，这样距离越远的地方等高值越大。

2.2.2冲刺模块

冲刺函数的实现是建立在等高图已经建立好的基础上的。

当电脑鼠要进行冲刺的时候，调用冲刺函数时，首先会调用等高图制作函数将等高图制作好。

然后该函数通过等高图和墙壁信息来进行电脑鼠的行进控制。

当然，我们认为电脑鼠在走直道的时候应该会比走弯道的时候，来的更快一点，所以我们没有进行特殊的加权，直接是走直道的。

电脑鼠从起点开始，一直利用等高图信息和墙壁信息进行一格一格的对比，只有当这一格在电脑鼠绝对方向上时，这一格才算记录到进行直道冲刺，同时直道格数加一。

当遇到电脑鼠要转弯的时候，已经将要走的步数记录下来了，接下来直接调用行进函数，控制电脑鼠走完记录好的步数后，即走到电脑鼠要转弯的地方后，再进行转弯，然后接着继续进行上一步的动作。

2.2.3转弯模块

转弯也是电脑鼠运行时必不可少一部分，同时转弯也分为静止转弯和行进中转弯。

静止转弯要求电脑鼠首先要停止，主要用在电脑鼠进行搜索中，这时要求电脑鼠要绝对的稳定，所以采用静止转弯比较好。

行进中转弯的特点是消除了静止转弯的要求电脑鼠停止的弊端，可以节省一些时间，主要用在电脑鼠进行冲刺时，这时要求电脑鼠要以竟可能短的时间从起点到达终点，所以行进中转弯可以节省不少的时间。

静止转弯时，对两个电机设置走相同的步数，如当要转左转90°时，设置左电机向后走40步，右电机向前走40步。

通过两个电机走的方位不同，来实现静止转弯，但静止转弯的缺点就是，在转弯前首先要让电机停止，然后再对电机的要走的步数进行赋值，这样会浪费一点时间。

行进中转弯时，让一个轮子停止，一个轮子进行运转来实现。

如当要左转90°时，设置左电机停止转动，右电机转动80步。

与静止转弯区别开来的是，电机的步数在其他的函数中赋值好了，在转弯函数中只要一开始将一个电机停止转动就可以了，而不用一开始就将两个电机都停止，然后对电机的步数进行赋值，这样的话，就可以节省一些不必要的时间。

2.2.4搜索模块

电脑鼠一开始进行迷宫搜索时必须要用到这个模块。

通过这个模块电脑鼠进行迷宫的墙壁信息的采集，电脑鼠所走过的每个坐标都会有一个相应的墙壁信息，这些墙壁信息是电脑鼠后来进行等高图制作和冲刺的基础。

在进行搜索时，电脑鼠的红外是在时钟中断下，不停地被驱动的，这一连串的动作有发射短波红外，发射长波红外，和接受红外。

处理器通过读取红外接收器对应引脚的信息来判断四周的情况，同时将迷宫的信息进行编码后存储在对应坐标的一个迷宫情况数组中。

当遇到岔路时，程序跳出搜索函数，回到主函数中将岔路坐标进行处理，将这个坐标进行入栈，再回到搜索函数中，根据所选用的搜索法则选择好一条路后，继续搜索，并这样一直下去直到电脑鼠运行到终点。

2.2.5迷宫地图相对方向与绝对方向的建立

迷宫是用18cm×18cm大小的方格组成的，其行列各有16个方格。

为了让电脑鼠记住所走过的各个迷宫格的信息，我们就坐标的方法来对256个迷宫格进行编号。

根据坐标的的定义和比赛规则，也为了把上下左右这四个方向参数转换为微控制器能够识别的符号，在本文中，将向上的方向定义为0、向右为1、向下为2、向左为3，如图3-8所示。

图3-1迷宫方向值定义

只要有了迷宫的坐标和方向后，电脑鼠在迷宫行走就可以随时知道自己所处的位置和方位了。

然而，对于电脑鼠而言，红外线传感器的位置和方向是固定不变的，但是对于迷宫，红外线传感器的位置和方向是随着老鼠前进方向的变化而一起变化的。

这是由于选择参照物的不同而引起的，由此引出了两个方向的问题：

相对方向和绝对方向。

相对方向：

以电脑鼠当前行走方向为参照的方向。

绝对方向：

以迷宫绝对坐标平面为参照的方向。

那么传感器所检测到的信息如何才能更便于处理呢？

周立功提到了如果以相对方向存储的资料将是混乱的，不仅要存储麻烦，而且要记录起检测时电脑鼠所处的方向，存储量比较大，处理起来也非常麻烦。

而以绝对方向存储就不需要考虑当前电脑鼠的方向。

这样就会经常遇到相对方向和绝对方向的互换。

在本文中采取了以变量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的值落在0～3的范围内，计算式进行式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所示。

因为迷宫共有8×8个方格，所以可以定义一个16×16的二维数组变量来保存整个迷宫墙壁资料。

表3-4墙壁资料存储方式

变量位

代表的绝对方向

备注

bit0

上方（0）

1：

有路，0：

有墙壁

bit1

右方

（1）

1：

有路，0：

有墙壁

bit2

下方

（2）

1：

有路，0：

有墙壁

bit3

左方（3）

1：

有路，0：

有墙壁

bit7～bit4

保留位

迷宫墙壁资料全部初始化为0，表示走过迷宫格至少有一方没墙壁，即墙壁资料不为0。

这样就可以通过单元格存储的墙壁资料是否为0来确定该单元格是否曾搜索过。

2.2.6　墙壁资料存储

为了记忆迷宫的详细信息，需要对迷宫单元的位置进行线路标记。

全迷宫共有16×16个单元组成，可采用二维坐标方式标记，即用每个单元的XY坐标表示，如起点可标记为（0，0），终点为（7，7）。

此外，还需要对迷宫单元的可行进方向进行标记，可采用绝对方位或相对方位二种方式。

绝对方位：

这是一种与电脑鼠行进方向无关的标记方式，以一个四位的二进制数，分别表示“东”﹑“西”﹑“南”和“北”四个方向。

以1表示允许行进（无墙壁），0表示不允许行进（有墙壁）。

相对方位：

这是一种与电脑鼠行进方向有关的标记方式，以一个三位的二进制数即可实现标记，分别表示“前”“左”“右”，以1表示允许（无墙壁），0表示不允许（有墙壁）。

2.2.7电脑鼠搜索策略

电脑鼠走迷宫可以采用全迷宫探索策略，即将迷宫的所有单元均搜索一次，从中找出最佳的行走路径。

这种策略需要有足够的时间或探测次数，但在IEEE竞赛规则中每场竞赛只有15分钟的时间，因此是不可能的。

另一种方法是部分迷宫探索策略，即在有限的时间或探测次数下，只探测迷宫的一部分，从中找出次最佳的路径，显然只能采用这种策略。

电脑鼠在一巷道内行走，如果最后无路可走，则该巷为死巷。

电脑鼠在任一单元内，可能的行走方向最多只有三个（前、左、右），如果有二个或二个以上的可能行走方向，称为交叉，遇有交叉时，由于有多个可以行走的方向，在行走方向的选择上，可有下面的几种选择法则：

（1）右手法则：

遇有交叉时，以右边为优先的前进方向，然后是直线方向、左边方向。

（2）左手法则：

遇有交叉时，以左边为优先的前进方向，然后是直线方向、右边方向。

（3）中左法则：

遇有交叉时，以直线为优先的前进方向，然后是左边方向、右边方向。

与此类似的还有中右法则。

（4）乱数法则：

遇有交叉时，取随机值作为前进方向。

（5）向心法则：

由于终点在迷宫的中心，遇有交叉时，以向迷宫中心的方向为优先的前进方向。

第三章问题总结及改进

1.底层驱动中步进电机的加减速控制

控制步进电机的加减速实际上就是控制每次换相的时间间隔。

如果利用定时器中断方式来控制电机变速，可以不断地改变定时器装载值的大小。

步进电机的输入信号包括步进脉冲信号和方向电平信号。

每接收一个脉冲信号系统将驱动步进电机旋转一个步距角，细分时为一个细分步距角。

步进电机的转速和脉冲信号的频率成正比。

下表所列为步进电机三种驱动方式的比较。

驱动方式

步进角度

功率损耗

特性

单拍驱动

7.5°

P

1功率损耗小

2步进时容易产生错乱

整步驱动

7.5°

2P

1功率损耗最大

2温度上升快

3转矩较大

4步进时较稳定

半步驱动

3.75°

1.5P

1特性介于单拍驱动和整步驱动之间

2步进角度是原步进角的一半

3最高的极速度减小

试验表明，如果脉冲信号变化太快，步进电机由于惯性跟不上电信号的变化就会产生失步现象，故在选择驱动方式时可选择半步驱动，即步进电机在启动时必须有升速过程，而在停止时则必须有减速过程。

如图所示为步进电机在运行过程中的速度变化曲线。