VB中电脑鼠微型机器人走迷宫模拟仿真

赵新华，白峻汀，马忠丽

(哈尔滨工程大学 自动化学院，黑龙江 哈尔滨 150001)

电脑鼠是一种具有人工智能的轮式机器人，是由嵌入式微控制器、传感器和机电运动部件构成的一种智能行走装置，它结合了机械、电子、电机、控制、光学、程序设计、优化算法等多方面的科学知识。因此，电脑鼠的开发及相关技术的研究能够体现多个电子相关技术的水平。研究人员分别从电脑鼠行走的控制算法、迷宫的优化算法及硬件实现等三方面对电脑鼠运动的稳定性及迷宫搜索的快速性进行了研究。电脑鼠行走的控制算法主要有模糊PID控制算法[1]、模糊控制[2]等；电脑鼠迷宫搜索方法有包括转弯算法的改进[3]、改进蚁群算法在迷宫路径规划中的应用[4]、迷宫搜索中心算法[5]、基于向心法则的迷宫算法[6]等；电脑鼠微型机器人硬件实现方面主要有基于DSP电脑鼠系统设计[7]及基于ARM的电脑鼠设计与实现[8-9]。可见先进的控制方法及迷宫搜索算法的应用是电脑鼠走迷宫实现快速性及稳定性的必然趋势，但是在进行先进控制方法及优化理论应用的开发过程中，直接在电脑鼠硬件系统上进行测试，往往因为算法及参数的不合理，导致开发的失败，因而耗费一定的人力物力。基于以上原因，本文提出了采用VB编程开发仿真软件来实现电脑鼠运动的仿真，可以提高相关算法应用开发的效率。

本文以“IEEE国际电脑鼠竞赛”为背景，应用VB程序软件开发对电脑鼠走迷宫进行模拟实现，该软件能够反映电脑鼠迷宫中的运行状态、显示电脑鼠的运行轨迹、开发先进的搜索算法、记录采用不同搜索算法的运行步数、最短路径及搜索效率等，通过比较不同算法的执行效率，获得最佳的优化方案。因此，本软件可以作为电脑鼠工程应用开发的先行军，为参赛队伍节省人力物力，提高工作效率。

1 迷宫的建立与设计

IEEE标准迷宫由16×16个的正方形单元所组成。迷宫的起始单元可选设在迷宫4个角落之中的任何一个。起始单元必须三面有隔墙，只留1个出口。例如，如果没有隔墙的出口为“北”时，那么迷宫的外墙就构成位于 “东”、“西”和“南”的隔墙。电脑鼠竞赛的终点设在迷宫中央，由4个正方形单元构成。

图1 IEEE标准迷宫Fig.1 IEEE standard maze

1.1 迷宫的建立

为使问题简化，可先对迷宫的每个单元进行编号，建立二维数组A(16，16)(左上角的坐标为A(1，1)，右下角为A(16，16))。每个单元有右、上、左、下有4个方向，定义4个常量Rig、Up、Dow、Lef，分别用数字0，1，2，3来表示。每个方向上有有挡板与无挡板之分，分别用1、0表示。定义B(16，17)表示横挡板，C(17，16)表示竖挡板，如迷宫小格A(2，2)的上方横挡板为B(2，2)，下方挡板为B(2，3)，左方挡板为C(2，2)，右方挡板为C(3，2)。到此，迷宫的建立就可以用挡板信息来表示。为了方便，可将挡板信息保存于txt文件中，应用时读取txt文件。迷宫四周存在的挡板，可去除这部分迷宫信息。

若建立图1所示迷宫，此迷宫的横挡板迷宫部分程序为

H(0)=“1111111011111100”

…

H(14)=“0101000001110101”

Forj= 2 To 16

Fori= 1 To 16

B(i,j) = Mid(H(j- 2),i, 1)

Nexti

Nextj

1.2 随机迷宫的设计

随机迷宫就是随机产生的一个可以走通(即有解)的迷宫, 随机迷宫产生的关键在于如何实现随机[10]。其具体思路为：依照电脑鼠迷宫的特性，首先设定迷宫的初始状态，墙壁都存在，并且迷宫终点的4个单元设置为不可访问。为保证电脑鼠迷宫的起始单元必须三面有隔墙，只留1个出口，开始单元只能设为迷宫四角的一角。从开始单元开始，随机地选择一个没有访问过的邻接单元，并打通与它相邻的墙壁。此时，此邻接单元为当前单元。如果所有周围的单元都是访问过的，则退回上一个单元进行挖掘墙壁，如此反复。当开始单元被返回的时候，算法结束。此时，从开始单元开始能到达除迷宫终点的4个单元的任何一个单元。最后，再利用随机函数在迷宫终点的4个单元处外围开一口，并设置内部无挡板。至此电脑鼠迷宫设计结束。

VB部分程序如下：

Do

If 当前单元周围的单元有未访问过 then

A： Suiji=Int(Rnd * 4)

Select Case Suiji

Case 0

If当前单元右单元有未访问过 then

移动到右单元

指针数+1

右单元访问过

Else

GotoA

End if

…‘另3个方向进行判断

End Select

Else

指针数-1‘返回上一单元

End if

Loop until 指针=0

根据此随机迷宫算法，建立的迷宫符合IEEE标准迷宫要求，具体实现如图2所示。

图2 随机迷宫示意图Fig.2 The diagram of random maze

1.3 迷宫的显示

迷宫的显示是指读取挡板的信息，为1时在软件界面相应单元处用Line函数画出一段直线。显示方法有2种：1)以人观察为视角，迷宫的样式直接显示在软件界面上，2)以电脑鼠的视野为视角，电脑鼠每移动一个单元，显示此单元的信息。其中，第2种方法加上手动移动电脑鼠在迷宫上搜索，进行自身模拟走迷宫，有助于对迷宫算法的探讨。此时，未免混乱，可另定义B1(16，17)、C1(17，16)来表示电脑鼠所观测到的迷宫信息。

2 电脑鼠走迷宫的VB实现

VB是一套可视化的具有面向对象的程序开发工具，是一种非常方便的Windows应用程序开发平台。它可以实现Windows的绝大多数功能(包括大型游戏软件的开发)，最大的优势就是可快速创建用户界面，把复杂而完善的Windows操作系统的使用融于易于学习和应用的高级程序设计语言中，使得它具有易学易懂易用的特点，因而受到初学者和广大工程技术开发人员的普遍喜欢。

2.1 电脑鼠的显示

当迷宫建立完成，可对电脑鼠进行显示，其关键点是电脑鼠的朝向。VB编程中，可在工程窗口中添加一个图片控件组，分别加载电脑鼠不同朝向时的图片，都先将其Visable属性设为False。当电脑鼠在迷宫前进过程中，首先应判断其朝向，再依此把代表其朝向的图片控件的Visable属性设为True。

2.2 电脑鼠的移动

电脑鼠的移动归根结底是图片控件的移动，可根据电脑鼠所处迷宫单元坐标，对图片控件的Left及Top属性值进行设定。当电脑鼠移动到一单元，首先对其迷宫单元坐标进行判断，进而设定图片控件的Left及Top属性值，最后显示相应朝向的图片控件。

2.2.1 电脑鼠主程序的实现

依照电脑鼠主程序流程，电脑鼠走迷宫过程可以分为4个状态：等待状态、启动状态、搜索状态和冲刺状态[11]。主程序流程如图3所示。

图3 主程序流程图Fig.3 Flow chart of the main program

从该流程图中可以看出，电脑鼠软件主程序主要包括：迷宫子程序、路径优化子程序、冲刺子程序、路口检测子程序、行走控制子程序、路口控制子程序。每个子程序的功能如下：

1)迷宫子程序。在没有预知迷宫路径的情况下，电脑鼠必须优先探索迷宫中的所有单元格，直到抵达终点为止。为了完成这个功能，电脑鼠要随时知道自己的位置及姿态，同时要记录所有访问过的方块四周是否有墙壁，并且在搜索过程中尽量避免重复搜索它搜索过的地方[12]。

2)路径优化子程序。通过对迷宫环境进行搜索检测，数组自动记录迷宫地图信息以及迷宫中每一单元格到起始点的路程。运行最优路径子程序，就能找到一条从起点到终点的最短路径。

3)冲刺子程序。此程序可使电脑鼠循着最短路径从起点以最快的速度冲到终点。

4)路口检测子程序。由安装在正前、左前、右前方向的3个红外发射管发射信号完成远距检测，根据传感器的读入值，判断迷宫中的障碍信息、路口信息。

5)行走控制子程序。根据左右两侧红外传感器接收的反馈信号来判断电脑鼠偏离迷宫巷道中轴线的程度，通过调整步进电机工作脉冲使某一边电机减速来修正电脑鼠的行驶方向，使其基本行走在中轴线附近。

6)路口控制子程序。当电脑鼠检测到岔路口，且需要转弯时，调用该子程序。应用VB进行仿真模拟时，可在窗口增加一个Timer控件，其Value值用HScroll控件的Value值来表示，以方便观察电脑鼠的走向。软件运行时，实时检测电脑鼠的位置，根据其不同的状态，进行不同的控制，其中，状态的变化可用Select函数进行选择。

2.3 迷宫搜索算法的实现

迷宫搜索算法的实现关键点是电脑鼠遇到岔路口的处理方式：保存岔路口坐标和根据迷宫搜索算法确定转弯优先级。对于岔路口坐标的保存，可利用堆栈的方法。电脑鼠每到一个迷宫单元，即需进行判断，是否进行坐标保存。在VB可定义一个函数Chalu()，为了方便，可以也把起点用堆栈进行保存，作为栈底元素。

VB部分程序代码如下：

Public Sub Chalu()

可前进方向数 = 0

If 当前迷宫单元上方满足搜索要求

Then

可前进方向数+ 1

End If

…‘判断其余各个方向可前进的方向数

If可前进方向数> 1

Then

可前进方向数指针+1

保存当前坐标

End If

End Sub

应用VB进行转弯优先级模拟时，可利用Select函数实现，按照优先级顺序设置case元素，当不满足电脑鼠转向的要求时，选择下一优先级。由于VB中，每次执行Select函数时，只能执行相应选择的内容后跳出，为了提升程序执行效率，可以利用Goto函数，当当前选择项不满足时，跳回到Select函数开始处。

2.4 等高表的实现

电脑鼠走迷宫一个关键点在于求解起点到终点的最短距离。同时，在电脑鼠的寻路过程中也存在一个比较特殊的过程，就是在电脑鼠遇到了死胡同时，应该让电脑鼠回到上一个岔路口。这2个问题实质上是等同于求解电脑鼠从一个单元到另一个单元的最短路径。虽然可以利用堆栈的先入后出的特性来存储寻路过程中经过的单元的坐标，但是这不能保证从当前的位置移动到岔路口是最短路径,这就需要用到等高表，利用等高表流程图可以方便地实现等高表算法。本文提出了一种新的等高表的算法，其主要思路是将路径规划的思想引入到等高表中，同时利用递归：定义一个等高表函数，若目标单元的某一方向上没有挡板并且此单元的等高表值比目标单元的等高表值大1，再以此单元为目标单元调用等高表函数。

VB部分程序代码如下：

Public Function mapEdit(ByVal cx As Integer, ByVal cy As Integer) As String

If 上方无挡板And 上方等高值大1

Then

上方等高值=当前等高值+1

Call mapEdit(上方单元坐标)

End If

If … then‘其他三方向的等高表制作

…

End if

…

End Function

与此相似，根据加权等高表特性，在注意电脑鼠朝向变化的情况下可方便对其进行实现。

对改进的等高表即等高表路径规划与加权等高表表示的迷宫如图4所示，采用等高表路径规划方法，电脑鼠在搜索阶段的运行步数为496步，转弯次数为232次，掉头次数为19次，而采用第2种等高表方法，搜索阶段的运行步数为504步，转弯次数为232次，掉头次数为19次。可见等高表路径规划方法的效率略高。

(a) 等高表路径规划

(b)加权等高表图4 等高表路径规划及加权等高表Fig.4 The path planning of the contour line and the weighting contour line

3 软件仿真测试

VB实现的电脑鼠走迷宫模拟软件最终效果图如5所示，运用右手法则对迷宫进行全搜索，步数为400步，转弯244次，掉头27次；最短路径步数为59步，转弯43次。经测试，制作的模拟仿真软件可以很好地模拟电脑鼠走迷宫竞赛，运行稳定。

图5 软件最终效果图(全搜索)Fig.5 The final picture of the soft(full search)

对迷宫的改进搜索算法，包括死胡同排除搜索算法、死区域排除搜索算法、死岔路口排除搜索算法、死区域结合死岔路口排除搜索算法进行了软件仿真测试，测试结果如图6所示。图中所用迷宫均为图5所示中的迷宫，运用法则均为右手法则。图中除终点外，为0的迷宫单元表示电脑鼠排除的单元。

(a) 死胡同排除搜索算法

(b)死区域排除搜索算法

(c) 死岔路口排除搜索算法

(d) 死区域结合死岔路口排除搜索算法图6 改进的迷宫搜索算法对比Fig.6 The comparison of the maze search algorithm

表1是用仿真软件实现的各种迷宫搜索算法执行效率的比较，分别从搜索阶段、最短路径、索索空间3个方面进行了比较，其中空间为探索区域/全迷宫×100%。

表1 迷宫搜索算法效率

由表1及以上仿真结果图分析可得：死区域结合死岔路口排除算法是迷宫搜索3种改进算法最好的结合。分别从未搜索过的迷宫单元和已搜索过的迷宫单元移动策略进行优化，进而对迷宫搜索的效率进行了提升。

5 结束语

依据电脑鼠走迷宫竞赛的规则，应用Visual Basic制作仿真软件,实现了迷宫的随机生成，电脑鼠的表示及迷宫优化算法的对比分析。对软件的测试表明，该软件能够对各种迷宫搜索算法进行仿真实现，完成电脑鼠行进速度的设定、搜索法则的选择、电脑鼠行进状态的设定、等高表、最短路径的显示及搜索阶段关键数据的统计等工作。该软件为实际电脑鼠(迷宫微型机器人)的控制及优化算法的实际应用提供了有效的测试手段。

参考文献:

[1]薛艳.电脑鼠模糊PID控制算法研究[D].长安大学,2010: 12-15.

XUE Yan. Fuzzy PID control algorithm research of the micromouse[D]. Chang’an University, 2010: 12-15.

[2]周亦敏，傅俊华.基于模糊控制的电脑鼠行进速度的控制[J].微计算机信息, 2010, 26(5): 79-81.

ZHOU Yimin, FU Junhua. Speed control of miciro-mouse based on fuzzy control[J]. Micro Computer Information, 2010, 26(5): 79-81.

[3]孙舟,雷斌.电脑鼠走迷宫转弯算法的改进与实现[J].电子元器件应用, 2011, 13(1): 54-57.

SUN Zhou, LEI Bin. Improvement and implementation of the turn algorithm of the micro mouse maze[J]. Electronic Component & Device Applications, 2011, 13(1): 54-57.

[4]温如春,许樱, 王祖麟. 改进蚁群算法在迷宫路径规划问题中的研究和应用[J].江西理工大学学报, 2010, 31(2): 26-28.

WEN ruchun, XU Ying, WANG Zulin. Study and application on Maze path planning based on improved ant colony algorithm[J]. Journal of Jiangxi University of Science and Technology, 2010, 31(2): 26-28.

[5]康冰,梁艳磊.基于机器人迷宫搜索中心算法的优化[J].长春师范学院学报：自然科学版, 2011, 30(4): 25-29.

KANG Bing, LIANG Yanlei. The optimization of central algorithm based on robot maze searching[J]. Journal of Changchun Normal University: Natural science, 2011, 30(4): 25-29.

[6]贺少波,孙克辉.基于向心法则的电脑鼠走迷宫算法设计与优化[J].计算机系统与应用, 2012, 21(9): 79-82.

HE Shaobo, SUN Kehui. Design and optimization of micro-mouse solving the maze algorithm based on central method[J]. Computer Systems and Applications, 2012, 21(9): 79-82.

[7]屈传坤,徐国政,崔建伟,等.基于DSP的电脑鼠系统设计[J].电器电子教学学报, 2008, 30(4): 32-34.

QU Chuankun, XU Guozheng, CUI Jianwei, et al. Design of a micro-mouse system based on DSP[J]. Journal of Electrical and Electronic Education, 2008, 30(4): 32-34.

[8]夏炎.基于ARM7的电脑鼠的设计与实现[J].煤炭技术, 2010, 29(12): 188-189.

XIA Yan. Design and implementation of micromouse based on ARM7[J]. Coal Technology, 2010, 29(12): 188-189.

[9]方金亮, 谈英姿, 周怡君.基于ARM的IEEE标准电脑鼠研究与实现[J].机械制造与自动化, 2008, 37(5): 99-101.

FANG Jinliang, TAN Yingzi, ZHOU Yijun. Micro mouse based on ARM of IEEE standard[J]. Machine Building and Automation, 2008, 37(5): 99-101.

[10]杜凯，朱泽民.基于图的深度遍历产生随机迷宫的算法研究[J]. 黄冈师范学院学报, 2008, 28: 68-71.

DU Kai, ZHU Zemin. Algorithm research based on traversal depth for the random maze[J]. Journal of Huanggang Normal University, 2008, 28: 68-71.

[11]朱姗,傅或哲，吴忠丽,等.一种走迷宫电脑鼠的设计与实现[J].微型电脑应用, 2008, 24(9): 59-62.

ZHU SAN, FU Yuzhe, WU Zhongli, et al. Design and realization of micro mouse maze[J]. Microcomputer Applications, 2008, 24(9): 59-62.

[12]蒋雄, 任化龙, 马忠丽. 基于ARM的电脑鼠走迷宫的研究[J]. 现代电子技术, 2011, 34(8): 14-16.

JIANG Xiong, REN Hualong, MA Zhongli. Research on how ARM-based micromouse gets out of maze[J]. Modern Electronics Technique, 2011, 34(8): 14-16.