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.