下载文档原格式
一种电脑鼠走迷宫算法作者：周杰来源：《电脑知识与技术》2018年第03期摘要：该文通过对电脑鼠走迷宫算法的研究，提出了一种电脑鼠走迷宫算法，该算法引用了斜线K和Z用以更新期望坐标，并将迷宫分割为多个部分，以斜线K上的点为起点坐标，下一条斜线K上的点为期望终点坐标，找到起点坐标和终点坐标的最优解，以局部最优，引出全局最优找到最佳路径，并与传统走迷宫算法进行比较，提高了迷宫搜索效率。
关键词：迷宫；斜线；局部最优；最佳路径中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2018）03-0053-031 概述电脑鼠是一种机电一体化装置，是由单片机、传感器、机电运动部件组成的一种能在迷宫行走的小型机器人可以通过预先设定的算法，探索迷宫，可以找到一条从预设的起点到终点的最佳路径，运行环境是由一个16X16正方形单元格所组成的迷宫，其中单元格的大小为18cmX18cm，文献[1][2]给出了电脑鼠走迷宫的相关规则，每一个单元格有相应的挡板组成，电脑鼠的目的是在最短的时间内找到出口，在整个电脑鼠中最重要的是硬件的可靠性和算法的优劣，在当今单片机迅速发展的时代，硬件稳定性上已经趋于稳定，本文主要研究和设计搜索迷宫算法，并提出了一种电脑鼠搜索迷宫的算法。
2 迷宫环境建模电脑鼠不具有思维能力，它只能按照我们设定的算法运行，因此需要模拟现场运行环境[6][7].构建一个16X16的迷宫，迷宫的水平方向为Y轴，垂直方向为X轴，第一个坐标为（1，1），那么依次下去最上角的坐标为（16，16）。
迷宫构建图，如图1 所示，迷宫内的挡板信息未知。
假设起点为（1，1）终点为（16，16），现在规定，X方向为地理北，Y方向为地理南，如图2所示。
对于当前坐标，和下一步目标，两个坐标的差值比如（X1，Y1）-（X2，Y2）。
（1，0）表示电脑鼠向北前进一步。
其中差值（0，1）表示向东前进一步，（-1，0）表示向南前进一步，（0，-1）表示向西前进一步。
北京科技大学实验报告学院：自动化学院专业：智能科学学技术班级：姓名：学号：实验日期：2017年11月6日实验名称：人工智能电脑鼠搜迷宫实验实验目的：掌握电脑鼠的基本操作及智能搜索算法操作。
实验仪器：KEIL MDK、电脑鼠、J-Link、VS实验原理：所谓“电脑鼠”，英文名叫做Micromouse，是一种具有人工智能的轮式机器人，是由嵌入式微控制器、传感器和机电运动部件构成的一种智能行走装置的俗称。
当电脑鼠放入起点，按下启动键之后，他就必须自行决定搜索法则并且在迷宫中前进，转弯，记忆迷宫墙壁资料，计算最短路径，搜索终点等功能。
电脑鼠更结合了机械、电机、电子、控制、光学、程序设计和人工智能等多方面的科技知识。
本实验中，通过红外传感器检测电脑鼠所处位置状态，通过智能算法保存地图并实现地图的搜索，通过pid等控制算法控制电机，达到电脑鼠搜索迷宫并计算最短路径等功能。
实验内容与步骤：实验内容1）KEIL MDK的安装2）电脑鼠硬件的检查及调整3）智能搜索算法的编写4）算法的调试与优化5）实验结果实验步骤（一）KEIL MDK的安装1双击运行Ke i l MDK 4.12 安装程序，出现软件安装界面，如图所示：2点击Next，勾选安装协议；3选择安装路径，建议安装在C 盘，运行速度快些4 填入用户信息，个人用户随意填入即可；点击Next 就进入实质的安装过程了，Wait for a Whle…5点击Finish，Keil MDK 就完成安装了，可以发现桌面上生成了名为“Keil uVis ion4”的可执行文件快捷方式。
（二）检查和调整电脑鼠的硬件1.电机检查：在电脑鼠程序文件中找到Motor.c文件，直接为两侧电机赋相同的速度值，用G-link连接电脑鼠和电脑，传入程序，打开电脑鼠放在地面上，如果电脑鼠能正常直线行进，即证明两侧电机正常工作。
如果有电机有问题，拆下原来的电机换新的再次进行电机检查即可。
2.传感器检查：用G-link连接电脑鼠和电脑，打开传感器查询模式，用手逐渐靠近每一个传感器，如果相应的传感器值由小变大，那么此传感器工作正常。
电脑鼠百科名片本词条主要介绍电脑鼠所谓“电脑鼠”，英文名叫做MicroMouse，是使用嵌入式微控制器、传感器和机电运动部件构成的一种智能行走装置的俗称，它可以在“迷宫”中自动记忆和选择路径，寻找出口，最终达到所设定的目的地。
国际电工和电子工程学会（IEEE）每年都要举办一次国际性的电脑鼠走迷宫竞赛，自举办以来参加国踊跃，为此许多大学还开设了“电脑鼠原理和制作”选修课程。
电脑鼠可谓是一种具有人工智能的小型机器人，依照新制的比赛规则，当电脑鼠放入起点，按下启动键之后，它就必须自行决定搜寻法则并且在迷宫中前进、转弯、记忆迷宫墙壁资料、计算最短路径、搜寻终点等功能。
电脑鼠更结合了机械、电机、电子、控制、光学、程序设计和人工智能等多方面的科技知识。
人类在科技的发展史上，一直在尝试着想要创造出一个具有肢体、感官、脑力等综合一体的智能机器人，而电脑鼠就是一个很能够用来诠释肢体、感官及脑力综合工作的基本实例，这也是当初电脑鼠被发明的理由，希望能够借助电脑鼠的创作来进而研究与发明更加复杂的机械。
电脑鼠走迷宫一只电脑鼠是具有机电知识整合的基本架构，本身就像是一个智能的机器人。
要在指定的迷宫中比赛，就像是一个人置身于竞赛中，必须要靠本身的判断力、敏捷动作及正确探查周边环境，来赢得胜利。
一般来说，一只电脑鼠需具备有下列三件基本能力：(1) 拥有稳定且快速的行走能力；(2) 能正确判断能力；(3) 记忆路径的能力。
行走能力指的就是电机，当电机收到讯号时，系统必须判断是否能同步行走，遇到转角时，转弯的角度是否得当，一个好的电机驱动程序，可以减少行走时所需要做的校正时间。
判断能力的关键就在于传感器，它的地位如同人类的双眼，一个好的传感器驱动程序，可避免一些不必要的错误动作，如撞壁、行走路线的偏移等等。
而记忆能力就像是大脑，它的功能并没有因为看不见而遭到忽视，相反地，它的地位在整场比赛中是最重要的，他必须把所走过的路都能一一记下来，并将其资料送给系统，让系统整理出最佳路径以避开不必要的路段。
电脑鼠控制系统工作原理及设计方案1电脑鼠工作原理电脑鼠周围安装六组红外传感器，分别感知左方、左前方、前方、右前方、右方，发射端发射一定频率的红外线，接收端通过六个方向的反射波来判断是否有障碍物，实时地储存单元格的资料，通过六组红外传感器反馈的迷宫信息，控制电脑鼠完成避障、转弯、加速等动作，运用智能算法对迷宫的部分单元格或全部单元格进行遍历，并将迷宫的信息以有效的数据结构存储，微控制器根据这些记录信息运用迷宫高效算法找到一条最优化路径，从而实现从起点到终点的最大化冲刺。
2 硬件电路设计为完成迷宫探测和冲刺任务，电脑鼠需具备以下各功能模块：ARM微处理器作为控制核心协调各功能模块正常工作;电机及驱动模块实时控制电机启动、制动;红外检测模块负责红外线探测感知;电源为整个系统供电稳定电压，陀螺仪及指南针模块确定电脑鼠方位，根据走过的距离，从而解析出所在坐标。
硬件组成如图1所示。
2.1 电源模块电源调节器件通常使用线性稳压器件(如LM7805)，具有输出电压可调、稳压精度高的优点，但是其线性调整工作方式在工作有较大的热损耗，导致电源利用率不高、满足不了便携低功耗需求。
开关电源调节器，不同于线性稳压器件，以完全导通或关断的方式工作，通过控制开关管的导通与截止时间，有效的减少工作中的热损耗，提高了电源利用率。
本设计中电源模块为系统提供三种不同的电压，12V电源用于驱动电机，使用开关式电源LM2596将12V直流电压降到5V给红外模块、人机交互模块供电，再通过AMS1117将5V降到3.3V，供ARM处理器及其他模块使用。
2.2 微处理器模块微处理器是整个控制系统的核心，它完成从红外检测模块获取路径信息，采集瞬时速度，进行数据处理，控制算法运算，输出实时控制量等功能。
为了保证系统的实用性和易扩展性，本控制系统采用意法半导体推出的增强型系列STFM32F103RCT6，STM32F103xx增强型系列使用高性能的ARM Correx-M3 32位的RISC内核，工作频率为72MHz，内置高。
