软件系统设计与实现毕业设计目录1简介.................................................. 错误！未定义书签。
1.1背景与意义 (1)1.2研究内容与思路 (1)2现有迷宫算法简述 (3)2.1迷宫的数字模型表征 (3)2.2迷宫问题的搜寻准则 (4)2.3迷宫问题的搜寻策略 (5)3硬件系统分析 (6)3.1实验平台与设计工具 (6)3.2硬件控制模块分析 (6)3.3电机选择与分析 (7)3.3.1电机比较 (8)3.3.2电机选择 (8)3.4传感器模块分析 (9)3.5测试赛道 (10)4软件系统设计与实现 (12)4.1路径决策功能的实现 (12)4.1.1迷宫探测算法 (13)4.1.2路径决策功能程序及分析 (14)4.2驱动控制功能的实现 (17)5验证结果与改进方案 (31)5.1实验验证结果 (31)5.2改进方向与研究方案 (32)5.2.1迷宫墙壁信息的记录 (32)5.2.2迷宫路口信息的记录 (33)6结论 (33)6.1结论 (33)附录 (35)1简介1.1 背景与意义电脑鼠（Micro-Mouse）是指采用嵌入式微处理器、传感器、机械电子运动部件为一体的微型智能移动机器人[1]，可实现探测、分析、行走等基本功能控制，且集合传感、机械移动等设计功用[2]。
国际电气和电子工程学会（IEEE）每年都要举办一次国际性的电脑鼠走迷宫竞赛，而对应的赛事要求、设计成果等内容业已成为参与电脑鼠研究的关注点[3]。
目前电脑鼠迷宫竞赛就参与程度、设计水平、发展程度而言，主要集中在美国、日本、英国、新加坡等，例如APEC（美国）、ALL JAPAN MICROMOUSE CONTEST （日本）、Singapore Inter-School Micromouse Competition（新加坡）、Euromouse maze contest（英国）[4]。
我国于2007年开始举办“IEEE 标准电脑鼠走迷宫”邀请赛，而比赛发展至今，比赛规模和参赛质量上均取得了显著的进步[5]。
目前电脑鼠迷宫边塞规定，电脑鼠在按下启动键后将自行选取搜寻法则，并且在迷宫行进过程中实现前行、转弯、往返、记忆迷宫墙壁资料、计算最优路径、探测障碍物、寻找目标终点等功能内容[6]。
1.2 研究内容与思路本文以“IEEE 标准电脑鼠走迷宫”竞赛规则为研究背景，选取电脑鼠MicromouseV3.2作为研究对象和实验工具，以STM32F103R8T6增强型系列微控制器[8]作为电脑鼠主控制器，具体依据课题设计要求分别完成规定部分，包括三个独立部分：（1）往返运动：电脑鼠从起始点A处出发，运行到挡板B处，并原路返回至起始点A处，如图1.1所示。
图1.1“往返运动”示意图（2）连续转弯：电脑鼠从A点出发，先后经B，C，D点之后，到达A处；之后掉头原路返回，如图1.2所示。
图1.2“连续转弯”示意图（3）寻找目标点：电脑鼠从A点出发，寻找到迷宫终点B处，并最终运行到终点B处。
如图1.3所示。
图1.3 “寻找目标点”示意图课题研究具体的研究内容分为以下几个部分：（1）电脑鼠硬件结构研究与分析，包括电脑鼠主控制模块的特征与开发原理、电机选择与驱动模块分析、红外检测模块、迷宫挡板探测模块、电源模块、速度感应与状态调整模块、电动机选取与分析等等。
（2）电脑鼠软件系统实现，包括程序初始化模块、迷宫墙壁记忆模块、红外探测与反馈模块、运动及其驱动控制模块、决策模块等等。
（3）电脑鼠迷宫路径搜寻与避障算法的研究，包括现代典型迷宫算法的分析对比、迷宫数字化表征方式、迷宫路径的数学模型研究、基于硬件语言的迷宫算法实现、记忆与决策功能算法的实现等等。
（4）实现软件系统设计和算法程序载入后，利用电脑鼠MicromouseV3.2在专用比赛跑道进行系统测试和调整，最终使电脑鼠具有基本的运动、探测、控制功能，并完成课题规定的竞赛功能。
2 现有迷宫算法简述迷宫算法的研究属于移动机器人路径规划研究的一部分[9]，是优化与提升移动机器人性能的重要研究环节。
面向不同环境的路径规划决策方式与实时避障功能是当前移动机器人性能研究中表征自主能力的重要检测指标[10]。
针对移动机器人（或面向电脑鼠）的路径规划算法和实时避障算法的研究已经获得众多理论成果，重点分为两类：（1）基于已知地图的路径规划方法，如栅格法[11]、Free Space Approach 、V-Graph 等；（2）基于未知地图的路径规划方法，遗传算法、势场法、模糊逻辑算法[9]、深广结合算法[9]、粒子群算法[10]等等。
各类算法都有针对性的适用范围和使用优势，对电脑鼠迷宫路径算法研究具有重要参考意义。
2.1 迷宫的数字模型表征本次毕业设计面向的迷宫模型如图2.1所示，共有10×10个方格组成。
由于设计中“连续转弯”规定部分的需要，迷宫外围是一个封闭式的挡板。
对应地，电脑鼠的起点位置是封闭挡板内的任意位置单元。
因此，电脑鼠实际的运动范围为8×8个方格。
图2.1 迷宫示意图依据上述分析，迷宫的位置单元，即每一个方格，可以用一个数值属性来表征该位置是否可以通行，而所有位置单元的数值属性的集合可以用一个矩阵来描述。
基于该思想，将迷宫格栅（挡板）表征为数值“1”，迷宫空格表征为数值“0”，据此可以利用一10 108 8个二值的二维矩阵表征迷宫，即将迷宫进行数学化的抽象描述。
图2.2为迷宫中部分区域进行抽象化和数字化之后的表征结果。
1 1 1 1 1 1 1 1 10 0 1 0 0 0 0 0 11 0 1 0 1 1 1 0 11 0 0 0 1 0 0 0 1[,]=1 0 1 1 1 0 0 1 11 0 1 0 0 0 0 0 11 0 1 0 1 1 1 1 11 0 1 0 0 0 0 0 01 1 1 1 1 1 1 1 1x y⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦a b c图2.2 迷宫抽象化、数字化的结果2.2 迷宫问题的搜寻准则结合计算机图形学、图论学、、拓扑学、数据结构等领域对于迷宫问题的解释与解决方法，电脑鼠等移动机器人面对的迷宫路径规划和决策判定问题可以进一步转化为迷宫路径最优化选择问题[12-14]。
在具体的迷宫环境中，以图2.1所示迷宫为例，电脑鼠前进至一个位置单元（假设为一个方格），最多面对三个前进方向（三种选择），最少面对三个挡板（唯一选择退回）。
在迷宫行进过程中，如果出现至少两个方向，即有两个以上的选择，通过设计好的搜寻算法，电脑鼠判定优先行进的方向和顺序。
目前常用的搜寻准则如下所示[1, 4, 12, 15, 16]：（1）左手准则：在迷宫中行进的电脑鼠面对两种以上选择方向时，优先选择向左行进，其次选择向前行进，最后选择向右行进。
（2）右手准则：在迷宫中行进的电脑鼠面对两种以上选择方向时，优先选择向右行进，其次选择向前行进，最后选择向左行进。
（3）中左准则：在迷宫中行进的电脑鼠面对两种以上选择方向时，优先选择向前行进，其次选择向左行进，最后选择向右行进。
（4）中右准则：在迷宫中行进的电脑鼠面对两种以上选择方向时，优先选择向前行进，其次选择向右行进，最后选择向左行进。
（5）乱序准则：或称乱数准则，在迷宫中行进的电脑鼠面对两种以上选择方向时，以随机值（随机方向）作为下一步的行进方向。
（6）向心准则：在迷宫中行进的电脑鼠面对两种以上选择方向时，优先选择距离迷宫中心最近的方向作为行进方向。
上述各类法则基本能够解决迷宫中的路径选择问题。
对于单迷宫(无回路)而言，其“入口”与“出口”的在拓扑学上始终是封闭的，因此，在迷宫中的行进者只需一直沿单一墙壁前进必然抵达目的地；对于复迷宫而言，上述“法则”不能完全解决，但是只考虑本次课题中设计的迷宫问题，可以认为课题中面向的迷宫是由多个单迷宫组成，因此利用上述准则中的任意一种就可以充分解决目标搜寻问题。
2.3 迷宫问题的搜寻策略上述的搜寻准则解决的是电脑鼠在迷宫行进中微观的最优决策问题，即保证目标地点的成功抵达，而搜寻策略（或称搜寻模式[1, 18, 19]）则解决的是迷宫墙壁记忆、等高线绘制、最短路径等问题。
目前的搜寻策略包括两类，如下：（1）全部迷宫路径搜索策略：电脑鼠从出发到终点过程中会进行地毯式搜索，将迷宫中全部道路进行逐一行进，然后选择一条最优路径（根据不同要求选择路径最短，或时间最短），再从起点出发由最优路径抵达终点。
（2）单一迷宫路径搜索策略：电脑鼠在出发后只沿一条路径前进，直至终点，不再搜寻其他迷宫区域，不再返回，结束搜寻任务。
面向全迷宫的搜寻策略可以获得迷宫的全部位置信息，利于未来获取目标最优路径的选取和算法优化，但是对于时间要求较高的任务或比赛，该策略会耗费大量时间而不具有实用性。
面向局部的迷宫搜寻策略可以迅速解决目标搜寻任务，具有时间上的优势。
如果进一步结合最佳路径判定算法，即返回时选取最短路径，则在时间上会具有明显优势。
本次课题中采用单一迷宫路径的搜寻策略和优化算法。
3硬件系统分析3.1 实验平台与设计工具本次毕业设计以“IEEE 标准电脑鼠走迷宫”竞赛规则为研究背景，选取电脑鼠MicromouseV3.2作为研究对象和实验工具，选用基于“IEEE 标准电脑鼠走迷宫”标准的课题测试赛道作为测试环境。
电脑鼠系统可以划分为硬件系统和软件系统。
硬件系统包括[10, 19, 20]：电源模块、红外传感器模块、驱动电机模块、微处理器控制模块、机身模块。
软件系统包括：红外检测模块、控制判断模块、驱动模块、运动调整模块、存储记忆模块（功能性模块）等。
针对本次课题要求，电脑鼠功能系统的设计主要针对于控制模块、驱动模块、传感器模块等。
本次毕设的软件开发平台是基于ARM公司发布的RealView MDK开发工具中集成的Keil uVision4。
Keil uVision4支持目前市场上多种不同的MCS51架构的芯片以及ARM，具有编辑、编译、仿真等一体功能，且操作界面与VC++相类似，形成友好的操作界面[21]。
3.2 硬件控制模块分析本次设计以ST旗下的STM32F103R8T6增强型系列微控制器作为电脑鼠控制系统的控制器。
在实际工程应用中，STM32F103R8T6适用于多种工作场合：电机驱动、探测控制等常规电子设备；可编程控制器、继电器等工业设备等。
STM32F103R8T6核心使用的是ARM® Cortex-M3™处理器。
芯体尺寸32位，速度72MHZ，RAM为20KB，程序存储64KB，存储类型FLASH，数据转换器为A/D16*12B，电压-电源（Vcc/Vdd）为2V-3.6V，工作温度为-40—85摄氏度。