VB中電腦鼠微型機(jī)器人走迷宮模擬仿真

趙新華，白峻汀，馬忠麗

(哈爾濱工程大學(xué) 自動化學(xué)院，黑龍江 哈爾濱 150001)

電腦鼠是一種具有人工智能的輪式機(jī)器人，是由嵌入式微控制器、傳感器和機(jī)電運(yùn)動部件構(gòu)成的一種智能行走裝置，它結(jié)合了機(jī)械、電子、電機(jī)、控制、光學(xué)、程序設(shè)計、優(yōu)化算法等多方面的科學(xué)知識。因此，電腦鼠的開發(fā)及相關(guān)技術(shù)的研究能夠體現(xiàn)多個電子相關(guān)技術(shù)的水平。研究人員分別從電腦鼠行走的控制算法、迷宮的優(yōu)化算法及硬件實(shí)現(xiàn)等三方面對電腦鼠運(yùn)動的穩(wěn)定性及迷宮搜索的快速性進(jìn)行了研究。電腦鼠行走的控制算法主要有模糊PID控制算法[1]、模糊控制[2]等；電腦鼠迷宮搜索方法有包括轉(zhuǎn)彎算法的改進(jìn)[3]、改進(jìn)蟻群算法在迷宮路徑規(guī)劃中的應(yīng)用[4]、迷宮搜索中心算法[5]、基于向心法則的迷宮算法[6]等；電腦鼠微型機(jī)器人硬件實(shí)現(xiàn)方面主要有基于DSP電腦鼠系統(tǒng)設(shè)計[7]及基于ARM的電腦鼠設(shè)計與實(shí)現(xiàn)[8-9]。可見先進(jìn)的控制方法及迷宮搜索算法的應(yīng)用是電腦鼠走迷宮實(shí)現(xiàn)快速性及穩(wěn)定性的必然趨勢，但是在進(jìn)行先進(jìn)控制方法及優(yōu)化理論應(yīng)用的開發(fā)過程中，直接在電腦鼠硬件系統(tǒng)上進(jìn)行測試，往往因?yàn)樗惴皡?shù)的不合理，導(dǎo)致開發(fā)的失敗，因而耗費(fèi)一定的人力物力。基于以上原因，本文提出了采用VB編程開發(fā)仿真軟件來實(shí)現(xiàn)電腦鼠運(yùn)動的仿真，可以提高相關(guān)算法應(yīng)用開發(fā)的效率。

本文以“IEEE國際電腦鼠競賽”為背景，應(yīng)用VB程序軟件開發(fā)對電腦鼠走迷宮進(jìn)行模擬實(shí)現(xiàn)，該軟件能夠反映電腦鼠迷宮中的運(yùn)行狀態(tài)、顯示電腦鼠的運(yùn)行軌跡、開發(fā)先進(jìn)的搜索算法、記錄采用不同搜索算法的運(yùn)行步數(shù)、最短路徑及搜索效率等，通過比較不同算法的執(zhí)行效率，獲得最佳的優(yōu)化方案。因此，本軟件可以作為電腦鼠工程應(yīng)用開發(fā)的先行軍，為參賽隊(duì)伍節(jié)省人力物力，提高工作效率。

1 迷宮的建立與設(shè)計

IEEE標(biāo)準(zhǔn)迷宮由16×16個的正方形單元所組成。迷宮的起始單元可選設(shè)在迷宮4個角落之中的任何一個。起始單元必須三面有隔墻，只留1個出口。例如，如果沒有隔墻的出口為“北”時，那么迷宮的外墻就構(gòu)成位于 “東”、“西”和“南”的隔墻。電腦鼠競賽的終點(diǎn)設(shè)在迷宮中央，由4個正方形單元構(gòu)成。

圖1 IEEE標(biāo)準(zhǔn)迷宮Fig.1 IEEE standard maze

1.1 迷宮的建立

為使問題簡化，可先對迷宮的每個單元進(jìn)行編號，建立二維數(shù)組A(16，16)(左上角的坐標(biāo)為A(1，1)，右下角為A(16，16))。每個單元有右、上、左、下有4個方向，定義4個常量Rig、Up、Dow、Lef，分別用數(shù)字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文件中，應(yīng)用時讀取txt文件。迷宮四周存在的擋板，可去除這部分迷宮信息。

若建立圖1所示迷宮，此迷宮的橫擋板迷宮部分程序?yàn)?/p>

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 隨機(jī)迷宮的設(shè)計

隨機(jī)迷宮就是隨機(jī)產(chǎn)生的一個可以走通(即有解)的迷宮, 隨機(jī)迷宮產(chǎn)生的關(guān)鍵在于如何實(shí)現(xiàn)隨機(jī)[10]。其具體思路為：依照電腦鼠迷宮的特性，首先設(shè)定迷宮的初始狀態(tài)，墻壁都存在，并且迷宮終點(diǎn)的4個單元設(shè)置為不可訪問。為保證電腦鼠迷宮的起始單元必須三面有隔墻，只留1個出口，開始單元只能設(shè)為迷宮四角的一角。從開始單元開始，隨機(jī)地選擇一個沒有訪問過的鄰接單元，并打通與它相鄰的墻壁。此時，此鄰接單元為當(dāng)前單元。如果所有周圍的單元都是訪問過的，則退回上一個單元進(jìn)行挖掘墻壁，如此反復(fù)。當(dāng)開始單元被返回的時候，算法結(jié)束。此時，從開始單元開始能到達(dá)除迷宮終點(diǎn)的4個單元的任何一個單元。最后，再利用隨機(jī)函數(shù)在迷宮終點(diǎn)的4個單元處外圍開一口，并設(shè)置內(nèi)部無擋板。至此電腦鼠迷宮設(shè)計結(jié)束。

VB部分程序如下：

Do

If 當(dāng)前單元周圍的單元有未訪問過 then

A： Suiji=Int(Rnd * 4)

Select Case Suiji

Case 0

If當(dāng)前單元右單元有未訪問過 then

移動到右單元

指針數(shù)+1

右單元訪問過

Else

GotoA

End if

…‘另3個方向進(jìn)行判斷

End Select

Else

指針數(shù)-1‘返回上一單元

End if

Loop until 指針=0

根據(jù)此隨機(jī)迷宮算法，建立的迷宮符合IEEE標(biāo)準(zhǔn)迷宮要求，具體實(shí)現(xiàn)如圖2所示。

圖2 隨機(jī)迷宮示意圖Fig.2 The diagram of random maze

1.3 迷宮的顯示

迷宮的顯示是指讀取擋板的信息，為1時在軟件界面相應(yīng)單元處用Line函數(shù)畫出一段直線。顯示方法有2種：1)以人觀察為視角，迷宮的樣式直接顯示在軟件界面上，2)以電腦鼠的視野為視角，電腦鼠每移動一個單元，顯示此單元的信息。其中，第2種方法加上手動移動電腦鼠在迷宮上搜索，進(jìn)行自身模擬走迷宮，有助于對迷宮算法的探討。此時，未免混亂，可另定義B1(16，17)、C1(17，16)來表示電腦鼠所觀測到的迷宮信息。

2 電腦鼠走迷宮的VB實(shí)現(xiàn)

VB是一套可視化的具有面向?qū)ο蟮某绦蜷_發(fā)工具，是一種非常方便的Windows應(yīng)用程序開發(fā)平臺。它可以實(shí)現(xiàn)Windows的絕大多數(shù)功能(包括大型游戲軟件的開發(fā))，最大的優(yōu)勢就是可快速創(chuàng)建用戶界面，把復(fù)雜而完善的Windows操作系統(tǒng)的使用融于易于學(xué)習(xí)和應(yīng)用的高級程序設(shè)計語言中，使得它具有易學(xué)易懂易用的特點(diǎn)，因而受到初學(xué)者和廣大工程技術(shù)開發(fā)人員的普遍喜歡。

2.1 電腦鼠的顯示

當(dāng)迷宮建立完成，可對電腦鼠進(jìn)行顯示，其關(guān)鍵點(diǎn)是電腦鼠的朝向。VB編程中，可在工程窗口中添加一個圖片控件組，分別加載電腦鼠不同朝向時的圖片，都先將其Visable屬性設(shè)為False。當(dāng)電腦鼠在迷宮前進(jìn)過程中，首先應(yīng)判斷其朝向，再依此把代表其朝向的圖片控件的Visable屬性設(shè)為True。

2.2 電腦鼠的移動

電腦鼠的移動歸根結(jié)底是圖片控件的移動，可根據(jù)電腦鼠所處迷宮單元坐標(biāo)，對圖片控件的Left及Top屬性值進(jìn)行設(shè)定。當(dāng)電腦鼠移動到一單元，首先對其迷宮單元坐標(biāo)進(jìn)行判斷，進(jìn)而設(shè)定圖片控件的Left及Top屬性值，最后顯示相應(yīng)朝向的圖片控件。

2.2.1 電腦鼠主程序的實(shí)現(xiàn)

依照電腦鼠主程序流程，電腦鼠走迷宮過程可以分為4個狀態(tài)：等待狀態(tài)、啟動狀態(tài)、搜索狀態(tài)和沖刺狀態(tài)[11]。主程序流程如圖3所示。

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

從該流程圖中可以看出，電腦鼠軟件主程序主要包括：迷宮子程序、路徑優(yōu)化子程序、沖刺子程序、路口檢測子程序、行走控制子程序、路口控制子程序。每個子程序的功能如下：

1)迷宮子程序。在沒有預(yù)知迷宮路徑的情況下，電腦鼠必須優(yōu)先探索迷宮中的所有單元格，直到抵達(dá)終點(diǎn)為止。為了完成這個功能，電腦鼠要隨時知道自己的位置及姿態(tài)，同時要記錄所有訪問過的方塊四周是否有墻壁，并且在搜索過程中盡量避免重復(fù)搜索它搜索過的地方[12]。

2)路徑優(yōu)化子程序。通過對迷宮環(huán)境進(jìn)行搜索檢測，數(shù)組自動記錄迷宮地圖信息以及迷宮中每一單元格到起始點(diǎn)的路程。運(yùn)行最優(yōu)路徑子程序，就能找到一條從起點(diǎn)到終點(diǎn)的最短路徑。

3)沖刺子程序。此程序可使電腦鼠循著最短路徑從起點(diǎn)以最快的速度沖到終點(diǎn)。

4)路口檢測子程序。由安裝在正前、左前、右前方向的3個紅外發(fā)射管發(fā)射信號完成遠(yuǎn)距檢測，根據(jù)傳感器的讀入值，判斷迷宮中的障礙信息、路口信息。

5)行走控制子程序。根據(jù)左右兩側(cè)紅外傳感器接收的反饋信號來判斷電腦鼠偏離迷宮巷道中軸線的程度，通過調(diào)整步進(jìn)電機(jī)工作脈沖使某一邊電機(jī)減速來修正電腦鼠的行駛方向，使其基本行走在中軸線附近。

6)路口控制子程序。當(dāng)電腦鼠檢測到岔路口，且需要轉(zhuǎn)彎時，調(diào)用該子程序。應(yīng)用VB進(jìn)行仿真模擬時，可在窗口增加一個Timer控件，其Value值用HScroll控件的Value值來表示，以方便觀察電腦鼠的走向。軟件運(yùn)行時，實(shí)時檢測電腦鼠的位置，根據(jù)其不同的狀態(tài)，進(jìn)行不同的控制，其中，狀態(tài)的變化可用Select函數(shù)進(jìn)行選擇。

2.3 迷宮搜索算法的實(shí)現(xiàn)

迷宮搜索算法的實(shí)現(xiàn)關(guān)鍵點(diǎn)是電腦鼠遇到岔路口的處理方式：保存岔路口坐標(biāo)和根據(jù)迷宮搜索算法確定轉(zhuǎn)彎優(yōu)先級。對于岔路口坐標(biāo)的保存，可利用堆棧的方法。電腦鼠每到一個迷宮單元，即需進(jìn)行判斷，是否進(jìn)行坐標(biāo)保存。在VB可定義一個函數(shù)Chalu()，為了方便，可以也把起點(diǎn)用堆棧進(jìn)行保存，作為棧底元素。

VB部分程序代碼如下：

Public Sub Chalu()

可前進(jìn)方向數(shù) = 0

If 當(dāng)前迷宮單元上方滿足搜索要求

Then

可前進(jìn)方向數(shù)+ 1

End If

…‘判斷其余各個方向可前進(jìn)的方向數(shù)

If可前進(jìn)方向數(shù)> 1

Then

可前進(jìn)方向數(shù)指針+1

保存當(dāng)前坐標(biāo)

End If

End Sub

應(yīng)用VB進(jìn)行轉(zhuǎn)彎優(yōu)先級模擬時，可利用Select函數(shù)實(shí)現(xiàn)，按照優(yōu)先級順序設(shè)置case元素，當(dāng)不滿足電腦鼠轉(zhuǎn)向的要求時，選擇下一優(yōu)先級。由于VB中，每次執(zhí)行Select函數(shù)時，只能執(zhí)行相應(yīng)選擇的內(nèi)容后跳出，為了提升程序執(zhí)行效率，可以利用Goto函數(shù)，當(dāng)當(dāng)前選擇項(xiàng)不滿足時，跳回到Select函數(shù)開始處。

2.4 等高表的實(shí)現(xiàn)

電腦鼠走迷宮一個關(guān)鍵點(diǎn)在于求解起點(diǎn)到終點(diǎn)的最短距離。同時，在電腦鼠的尋路過程中也存在一個比較特殊的過程，就是在電腦鼠遇到了死胡同時，應(yīng)該讓電腦鼠回到上一個岔路口。這2個問題實(shí)質(zhì)上是等同于求解電腦鼠從一個單元到另一個單元的最短路徑。雖然可以利用堆棧的先入后出的特性來存儲尋路過程中經(jīng)過的單元的坐標(biāo)，但是這不能保證從當(dāng)前的位置移動到岔路口是最短路徑,這就需要用到等高表，利用等高表流程圖可以方便地實(shí)現(xiàn)等高表算法。本文提出了一種新的等高表的算法，其主要思路是將路徑規(guī)劃的思想引入到等高表中，同時利用遞歸：定義一個等高表函數(shù)，若目標(biāo)單元的某一方向上沒有擋板并且此單元的等高表值比目標(biāo)單元的等高表值大1，再以此單元為目標(biāo)單元調(diào)用等高表函數(shù)。

VB部分程序代碼如下：

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

If 上方無擋板And 上方等高值大1

Then

上方等高值=當(dāng)前等高值+1

Call mapEdit(上方單元坐標(biāo))

End If

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

…

End if

…

End Function

與此相似，根據(jù)加權(quán)等高表特性，在注意電腦鼠朝向變化的情況下可方便對其進(jìn)行實(shí)現(xiàn)。

對改進(jìn)的等高表即等高表路徑規(guī)劃與加權(quán)等高表表示的迷宮如圖4所示，采用等高表路徑規(guī)劃方法，電腦鼠在搜索階段的運(yùn)行步數(shù)為496步，轉(zhuǎn)彎次數(shù)為232次，掉頭次數(shù)為19次，而采用第2種等高表方法，搜索階段的運(yùn)行步數(shù)為504步，轉(zhuǎn)彎次數(shù)為232次，掉頭次數(shù)為19次?？梢姷雀弑砺窂揭?guī)劃方法的效率略高。

(a) 等高表路徑規(guī)劃

(b)加權(quán)等高表圖4 等高表路徑規(guī)劃及加權(quán)等高表Fig.4 The path planning of the contour line and the weighting contour line

3 軟件仿真測試

VB實(shí)現(xiàn)的電腦鼠走迷宮模擬軟件最終效果圖如5所示，運(yùn)用右手法則對迷宮進(jìn)行全搜索，步數(shù)為400步，轉(zhuǎn)彎244次，掉頭27次；最短路徑步數(shù)為59步，轉(zhuǎn)彎43次。經(jīng)測試，制作的模擬仿真軟件可以很好地模擬電腦鼠走迷宮競賽，運(yùn)行穩(wěn)定。

圖5 軟件最終效果圖(全搜索)Fig.5 The final picture of the soft(full search)

對迷宮的改進(jìn)搜索算法，包括死胡同排除搜索算法、死區(qū)域排除搜索算法、死岔路口排除搜索算法、死區(qū)域結(jié)合死岔路口排除搜索算法進(jìn)行了軟件仿真測試，測試結(jié)果如圖6所示。圖中所用迷宮均為圖5所示中的迷宮，運(yùn)用法則均為右手法則。圖中除終點(diǎn)外，為0的迷宮單元表示電腦鼠排除的單元。

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

(b)死區(qū)域排除搜索算法

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

(d) 死區(qū)域結(jié)合死岔路口排除搜索算法圖6 改進(jìn)的迷宮搜索算法對比Fig.6 The comparison of the maze search algorithm

表1是用仿真軟件實(shí)現(xiàn)的各種迷宮搜索算法執(zhí)行效率的比較，分別從搜索階段、最短路徑、索索空間3個方面進(jìn)行了比較，其中空間為探索區(qū)域/全迷宮×100%。

表1 迷宮搜索算法效率

由表1及以上仿真結(jié)果圖分析可得：死區(qū)域結(jié)合死岔路口排除算法是迷宮搜索3種改進(jìn)算法最好的結(jié)合。分別從未搜索過的迷宮單元和已搜索過的迷宮單元移動策略進(jìn)行優(yōu)化，進(jìn)而對迷宮搜索的效率進(jìn)行了提升。

5 結(jié)束語

依據(jù)電腦鼠走迷宮競賽的規(guī)則，應(yīng)用Visual Basic制作仿真軟件,實(shí)現(xiàn)了迷宮的隨機(jī)生成，電腦鼠的表示及迷宮優(yōu)化算法的對比分析。對軟件的測試表明，該軟件能夠?qū)Ω鞣N迷宮搜索算法進(jìn)行仿真實(shí)現(xiàn)，完成電腦鼠行進(jìn)速度的設(shè)定、搜索法則的選擇、電腦鼠行進(jìn)狀態(tài)的設(shè)定、等高表、最短路徑的顯示及搜索階段關(guān)鍵數(shù)據(jù)的統(tǒng)計等工作。該軟件為實(shí)際電腦鼠(迷宮微型機(jī)器人)的控制及優(yōu)化算法的實(shí)際應(yīng)用提供了有效的測試手段。

參考文獻(xiàn):

[1]薛艷.電腦鼠模糊PID控制算法研究[D].長安大學(xué),2010: 12-15.

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

[2]周亦敏，傅俊華.基于模糊控制的電腦鼠行進(jìn)速度的控制[J].微計算機(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]孫舟,雷斌.電腦鼠走迷宮轉(zhuǎn)彎算法的改進(jìn)與實(shí)現(xiàn)[J].電子元器件應(yīng)用, 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ìn)蟻群算法在迷宮路徑規(guī)劃問題中的研究和應(yīng)用[J].江西理工大學(xué)學(xué)報, 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ī)器人迷宮搜索中心算法的優(yōu)化[J].長春師范學(xué)院學(xué)報：自然科學(xué)版, 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]賀少波,孫克輝.基于向心法則的電腦鼠走迷宮算法設(shè)計與優(yōu)化[J].計算機(jī)系統(tǒng)與應(yīng)用, 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的電腦鼠系統(tǒng)設(shè)計[J].電器電子教學(xué)學(xué)報, 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的電腦鼠的設(shè)計與實(shí)現(xiàn)[J].煤炭技術(shù), 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標(biāo)準(zhǔn)電腦鼠研究與實(shí)現(xiàn)[J].機(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]杜凱，朱澤民.基于圖的深度遍歷產(chǎn)生隨機(jī)迷宮的算法研究[J]. 黃岡師范學(xué)院學(xué)報, 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]朱姍,傅或哲，吳忠麗,等.一種走迷宮電腦鼠的設(shè)計與實(shí)現(xiàn)[J].微型電腦應(yīng)用, 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]. 現(xiàn)代電子技術(shù), 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.