人工智能电脑鼠搜迷宫实验

北京科技大学实验报告学院：自动化学院专业：智能科学学技术班级：姓名：学号：实验日期：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连接电脑鼠和电脑，打开传感器查询模式，用手逐渐靠近每一个传感器，如果相应的传感器值由小变大，那么此传感器工作正常。

一、实验目的通过本次实验，了解老鼠在迷宫中的运动轨迹，探究其寻找出口的策略，并尝试运用数据结构中的搜索算法来模拟老鼠的行走过程，分析其路径选择的特点。

二、实验原理迷宫问题是一个经典的算法问题，旨在通过模拟老鼠在迷宫中寻找出口的过程，来验证和优化搜索算法。

本实验采用深度优先搜索（DFS）算法来模拟老鼠的运动轨迹，通过堆栈来存储老鼠走过的路径，并记录其最终找到出口的最短路径。

三、实验材料1. 迷宫地图：一个二维数组，表示迷宫的布局，其中0代表无墙、没走过；1代表墙；2代表无墙、已走过。

2. C语言编程环境：用于编写和运行实验代码。

3. 输入设备：用于输入起始点和迷宫地图。

四、实验步骤1. 设计迷宫地图，初始化二维数组map[10][12]。

2. 输入起始点坐标（行列坐标），判断输入是否合法（越界或起始点在墙中）。

3. 初始化一个空堆栈，用于存储老鼠走过的路径。

4. 使用深度优先搜索算法遍历迷宫，寻找出口：a. 将起始点入栈。

b. 标记当前点为已走过。

c. 判断当前点是否为出口，如果是，则输出路径，结束搜索。

d. 找到当前点的后继点（上下左右），如果后继点合法且未走过，则将其入栈并标记为已走过，继续搜索。

e. 如果当前点没有后继点，则回溯，弹出栈顶元素，尝试下一个方向。

5. 输出最短路径，记录老鼠的运动轨迹。

五、实验结果与分析1. 迷宫地图及起始点：```0 1 1 1 1 1 1 1 1 1 1 11 0 0 0 0 0 0 0 0 0 0 11 0 1 1 1 1 1 1 1 1 1 11 0 1 0 0 0 0 0 0 0 0 11 0 1 1 1 1 1 1 1 1 1 11 0 1 0 0 0 0 0 0 0 0 11 0 1 1 1 1 1 1 1 1 1 11 0 0 0 0 0 0 0 0 0 0 11 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1```2. 老鼠起始点坐标：(1, 1)3. 运动轨迹及最短路径：```老鼠运动轨迹：[(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (1, 9), (1, 10), (1, 11), (2, 11), (3, 11), (4, 11), (5, 11), (6, 11), (7, 11), (8, 11), (9, 11), (10, 11), (11, 11)]最短路径：[(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (1, 9), (1, 10), (1, 11), (2, 11), (3, 11), (4, 11), (5, 11), (6, 11), (7, 11), (8, 11), (9, 11), (10, 11), (11, 11)]```4. 分析：通过实验结果可以看出，老鼠在迷宫中寻找出口的过程主要遵循深度优先搜索策略，即优先探索当前路径的深度，直到找到出口。

项目编号：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，是使用嵌入式微控制器、传感器和机电运动部件构成的一种智能行走装置的俗称。

一种人工智能迷宫穿梭电脑鼠作者：龙行杜强王宁杨荃文来源：《现代信息科技》2021年第01期摘要：作為微型轮式机器人，电脑鼠能够自主地求解迷宫。

文章对电脑鼠车身结构进行了研究，通过加入新型双层吸盘装置增大压力，提高电脑鼠在迷宫穿梭时的速度，降低电脑鼠高速运行下打滑的风险;对算法控制等方面的研究与改进，电脑鼠能够在迷宫中找到从起点到终点的最佳路径。

在当今智能社会的发展趋势下，电脑鼠具有广泛的实用价值，其技术可以推广到自动导航和避障机器人等多个行业。

关键词：轮式机器人;电脑鼠;结构设计;算法控制中图分类号：TP301.6;TP242.6 文献标识码：A 文章编号：2096-4706（2021）01-0168-04An Artificial Intelligence Maze of Shuttle MicroMouseLONG Hang，DU Qiang，WANG Ning，YANG Quanwen（School of Information Science and Engineering，Tianshi College，Tianjin 301700，China）Abstract：As a micro-wheeled robot，micromouse can solve maze independently. In this paper，the body structure of the micromouse is studied. By adding a new double-layer sucker device to increase the pressure，the speed of the micromouse in the maze shuttle is improved，and the risk of the micromouse slipping at high speed is reduced;through the research and improvement ofalgorithm control，the micromouse can find the best path from the beginning to the end in the maze. Under the trend of today’s intelligent society，the micromouse has a wide range of practical value，and its technology can be extended to industries such as automatic navigation and obstacle avoidance robots.Keywords：wheeled robot;micromouse;structure design;algorithmic control0 引言电脑鼠是一个基于微处理器控制的、集传感器与控制于一体的、能够自动穿梭迷宫的智能微型机器人[1]。

计算机迷宫搜索算法仿真研究摘要：在电脑鼠的设计过程中，往往需要耗费大量的时间在迷宫搜索算法的调试上。

通过研究迷宫地图，采用模块化的设计方法，模拟实现了对迷宫搜索算法的仿真，还设计了迷宫地图的编辑和迷宫搜索算法的导入等功能。

仿真试验结果表明，仿真迷宫搜索算法可提高迷宫搜索算法设计和调试的效率。

关键词：电脑鼠;迷宫搜索算法;仿真;多线程电脑鼠［1］（Micromouse）是一个由微控制器、探测器、驱动电机组成的一种集感知、判断、行走功能于一体，能够在迷宫中自动寻找到达终点最佳路径的微型机器人。

电脑鼠走迷宫比赛集竞赛和趣味性于一体，吸引了大量青年科技人员参加，文献［1］给出了有关迷宫电脑鼠的比赛规则和要求。

在迷宫电脑鼠的设计中，迷宫搜索算法的设计和调试最困难［3-7］。

主要因为迷宫搜索算法的设计和调试过程容易受到周围环境以及电脑鼠底层软硬件的影响而出现运行错误，从而使得调试经常被打断，完成一次完整的调试非常麻烦［8］，需耗费大量时间。

本文针对电脑鼠设计者在迷宫搜索算法设计和调试上所面临的问题，设计了迷宫搜索算法仿真程序，提高迷宫搜索算法设计和调试的效率，减轻设计者的负担。

该算法仿真程序及其实现思路不仅可以推广到电脑鼠走迷宫竞赛中，而且还可以作为电脑鼠迷宫搜索算法研究者的一个理想研究平台。

1仿真模块设计迷宫搜索算法仿真程序的主要功能模块包含动态仿真器、迷宫搜索算法接口、人机交互界面和迷宫地图编辑器。

动态仿真器是整个程序的核心，迷宫搜索算法接口用于连接动态仿真器和迷宫搜索算法，人机交互界面和迷宫地图编辑器，分别负责响应用户的鼠标动作和迷宫地图的设置。

地图编辑器需要接受用户的动作来完成地图的编辑工作，所以将迷宫地图编辑器作为人机交互界面的一个子功能来实现。

图1是迷宫搜索算法仿真程序的系统模块框图。

动态仿真器实现了三个功能，为迷宫搜索算法获取迷宫信息，根据迷宫搜索算法的指令控制模拟电脑鼠运动，显示运行中产生的过程数据。

一、实验背景迷宫实验是心理学和神经科学领域常用的实验方法，用于研究动物的学习和记忆能力。

近年来，随着计算机技术的不断发展，迷宫实验也逐步实现了电脑化。

本实验旨在利用迷宫电脑小鼠实验系统，研究小鼠在迷宫中的行为特征，以及其学习记忆能力。

二、实验目的1. 了解迷宫电脑小鼠实验系统的操作方法和原理。

2. 观察并记录小鼠在迷宫中的行为表现。

3. 分析小鼠的学习记忆能力，探讨影响因素。

三、实验材料1. 迷宫电脑小鼠实验系统：包括迷宫、电脑控制台、摄像头等。

2. 实验小鼠：体重20-25克，性别不限。

四、实验方法1. 迷宫电脑小鼠实验系统操作：将迷宫电脑小鼠实验系统连接到电脑，启动软件，设置实验参数，如迷宫形状、实验次数、时间限制等。

2. 实验步骤：（1）将实验小鼠放入迷宫入口，记录其进入迷宫的时间。

（2）观察并记录小鼠在迷宫中的行为表现，如逃避、探索、犹豫等。

（3）记录小鼠到达迷宫出口的时间，并计算其速度。

（4）重复实验多次，观察小鼠的学习记忆能力。

五、实验结果与分析1. 实验结果（1）实验小鼠在迷宫中的行为表现：在实验初期，小鼠表现出逃避、犹豫等行为，随着实验次数的增加，小鼠逐渐适应迷宫环境，表现出更快的速度和更准确的方向判断。

（2）实验小鼠的学习记忆能力：经过多次实验，小鼠的学习记忆能力得到显著提高。

在后期实验中，小鼠能够快速找到迷宫出口，且速度逐渐提高。

2. 分析（1）迷宫电脑小鼠实验系统能够有效地模拟真实迷宫环境，为研究小鼠的学习记忆能力提供可靠平台。

（2）实验结果表明，小鼠在迷宫中的行为表现与其学习记忆能力密切相关。

逃避、犹豫等行为可能表明小鼠在适应迷宫环境过程中存在困难，而随着实验次数的增加，小鼠逐渐适应迷宫，表现出更好的学习记忆能力。

（3）实验结果还表明，迷宫电脑小鼠实验系统具有良好的重复性和可靠性，可用于研究小鼠的学习记忆能力。

六、结论本实验通过迷宫电脑小鼠实验系统，研究了小鼠在迷宫中的行为表现和学习记忆能力。

电脑⿏⾛迷宫电脑⿏⾛迷宫算法改进及仿真测试（部分）2.3.5 迷宫算法改进迷宫最优路径是指从迷宫的⼊⼝到达迷宫出⼝的最短通路。

传统求解迷宫路径问题的算法⼤多采⽤⼴度优先搜索(BFS)或深度优先搜索(DFS)。

由于需要全迷宫搜索，随着迷宫规模的增⼤和复杂性的增加，上述两种算法的空间和时间复杂性将呈指数增加。

针对以上问题，本论⽂对传统算法进⾏优化改进讨论，核⼼思想是利⽤已经探索得知的迷宫信息排除不包含最短路径信息的迷宫格，不予探索。

1、单⾏、单列死点的死胡同排除算法该算法核⼼内容是进⾏数据补全，减少电脑⿏进⼊“死胡同”的次数。

其实迷宫单元的信息并不是只有访问过才能够得到，通过推断的⽅法也是可以得到的。

利⽤某个单元四周的⽅格的信息，就可以推断出此单元的信息，⽽并不需要每⼀个单元都进⾏访问。

如果⼀个迷宫单元三个⽅向有挡板，并且当该迷宫格不是终点时，那么电脑⿏进⼊该迷宫格后必然返回，这对于寻找最短路径信息⽆⽤，此时将该迷宫格第四个⽅向⼀同标记，亦即将迷宫格封闭，不让电脑⿏进⼊该迷宫格，以达到缩短探索时间的⽬的。

如图2.10中圆圈区域，当其四周搜索过时，电脑⿏不应对此区域进⾏访问。

图2.10 死胡同实例根据电脑⿏迷宫特性，迷宫四周的挡板是肯定存在的，可先进⾏预先处理。

⽽且终点四个单元的周围的⼋块挡板有且仅有⼀个是不存在的。

当电脑⿏到达终点，在明确哪个挡板不存在的同时，⽆论其它挡板是否进⾏探测过，都可将它视为挡板存在。

2、多⾏、多列死点的死区域排除算法传统搜索算法中电脑⿏从当前单元移动到下⼀单元的依据是有⽆挡板的存在及是否访问过，⽽未考虑从下⼀单元是否可以在不经过当前单元的情况下到达终点。

形象的说，此种搜索只着眼于当前电脑⿏的移动，⽽不考虑实际效果。

当电脑⿏不能从下⼀单元在不经过当前单元到达终点时，电脑⿏的运⾏就做了“⽆⽤功”，这对于迷宫搜索的执⾏效率产⽣很⼤的副作⽤。

如图2.11所⽰，⽅形区域内即是这种情况，也就是死区域。

东南大学第二届IEEE标准电脑鼠走迷宫竞赛电脑鼠原理及其应用机电动力试验平台第二届IEEE标准电脑鼠走迷宫竞赛论文东南大学第二届IEEE标准电脑鼠走迷宫竞赛电脑鼠原理及其应用机电动力试验平台目录一．软件程序框图 (3)二．参赛软件研发过程 (4)三．软硬件调试过程 (4)四．各组员分工 (4)五．体会心得 (5)附录 (6)参考书目 (9)软件程序框图东南大学第二届IEEE标准电脑鼠走迷宫竞赛电脑鼠原理及其应用机电动力试验平台参赛软件研发过程在void main()函数中，采用压栈的方式进行电脑鼠搜索，数组uint8 GmcCrossway[MAZETYPE*MAZETYPE]用于暂存未走过支路坐标。

数组uint8 GucMapBlock[MAZETYPE][MAZETYPE]记录每个点的地图信息，初始化为0x00。

函数void mouseGoahead(int8 cNBlock)、void mazeSearch(void)、void mouseTurnleft(void)、东南大学第二届IEEE标准电脑鼠走迷宫竞赛电脑鼠原理及其应用机电动力试验平台void mouseTurnright(void)、void mouseTurnback(void)和void objectGoTo(int8 cXdst, int8 cYdst)控制电脑鼠的运动状态。

void mapStepEdit(int8 cX, int8 cY)为制作等高图函数，它把记录等高值的数组uint8 GucMapStep[MAZETYPE][MAZETYPE]（初始化为0xff）赋值。

当电脑鼠搜索时无方向可走时就按照这个等高图的信息退回上个点，冲刺时也是一样的道理。

另外，为了缩短转弯时间，并且保证电脑鼠的稳定性，采取转弯时整步，直走时半步。

我们在Mouse_Drive.c文件中，加入全局变量int8 maincheck，初始化为0（其中0为不转弯，1为转弯）。