基于概率距離的電腦鼠迷宮搜索算法

王磊　董珊　潘洪友

摘 要：效率不高是目前電腦鼠競賽中迷宮搜索算法存在的普遍問題，為此，提出一種基于概率距離的電腦鼠迷宮搜索算法。通過生成靜態(tài)概率距離圖，并結(jié)合對迷宮圖的動態(tài)處理，以達(dá)到提高迷宮搜索效率，縮短迷宮搜索時間的目的。測試結(jié)果表明，基于概率距離的電腦鼠迷宮搜索算法，在迷宮搜索效率、迷宮搜索時間等方面，較左手、中左、中心、中心分區(qū)算法有明顯優(yōu)勢。

關(guān)鍵詞：迷宮搜索算法 電腦鼠 迷宮 概率距離 封閉體算法 搜索效率

中圖分類號：TP242.6 文獻(xiàn)標(biāo)識碼：A 文章編號：1674-098X（2016）01（c）-0093-03

Abstract：Low efficiency is the regular problem in search algorithm of Micromouse maze at present. To solve this problem， proposed the search algorithm based on probability distance. This algorithm creates a static probability distance map， and combines the dynamic handling of the maze map to improve the efficiency and speed of maze search.The results show that search algorithm based on probability distance of Micromouse maze has a big advantage of search efficiency and search time comparing with the left hand， center left， center， center partition algorithm.

Key Words：Maze search algorithm；Micromouse；Maze；Probability distance；Closed body algorithm；Search efficiency

電腦鼠（Micromouse）是使用嵌入式微控制器、傳感器和機電運動部件構(gòu)成的一種智能行走裝置（微型機器人），電腦鼠可以在不同“迷宮”中自動記憶和選擇路徑，采用相應(yīng)的算法，快速地達(dá)到所設(shè)定的目的地。電腦鼠競賽的迷宮[1]由256個迷宮格組成，每個迷宮格的大小為18 cm見方，排成16行16列。電腦鼠走迷宮競賽的目的是設(shè)計制作一個電腦鼠，按照規(guī)則要求以最快的速度完成比賽。

迷宮搜索過程中，電腦鼠除去需要正常記錄迷宮格信息、自身所在位置、方向等數(shù)據(jù)，還需要使用某些迷宮搜索算法，進(jìn)行行進(jìn)路線的抉擇[2]，該過程屬于機器人路徑規(guī)劃的范疇，是基于地圖未知的路徑規(guī)劃方法在電腦鼠走迷宮競賽中的具體運用。當(dāng)前使用的迷宮搜索算法有很多，常見的主要有以下幾種。

（1）左手/右手法則[3]，當(dāng)電腦鼠行進(jìn)中遇到兩條或更多的支路時，優(yōu)先考慮向左/右行進(jìn)，其次考慮向前，最后才考慮向右/左行進(jìn)；（2）中左/中右法則，優(yōu)先考慮前行，其次考慮向左/右行進(jìn)，最后才考慮向右/左行進(jìn)；（3）求心法則，優(yōu)先選擇離中心點最近的方向行進(jìn)，同時有兩個離中心最近的方向供選擇時，選擇直線方向；（4）中心分割法則[4]，將迷宮分為幾個部分，根據(jù)每個部分相對于目標(biāo)區(qū)域的位置和當(dāng)前電腦鼠行進(jìn)的絕對方向，采用不同的法則來控制電腦鼠運行。

以上幾種迷宮搜索算法普遍存在搜索效率不高、搜索時間過長的問題。為此，文章提出基于概率距離的電腦鼠迷宮搜索算法。

1 概率距離算法

概率距離算法，是一種通過生成靜態(tài)概率距離圖，并在電腦鼠運行過程中對迷宮圖進(jìn)行動態(tài)處理，來輔助電腦鼠進(jìn)行路徑抉擇的算法。

1.1 靜態(tài)概率距離圖生成

目標(biāo)區(qū)域為迷宮中心的4個相通的迷宮格，此目標(biāo)區(qū)域同外界相鄰的是8個迷宮格，按照規(guī)則，目標(biāo)區(qū)域必須與外界相通，也即目標(biāo)區(qū)域G周圍至多有7堵墻壁，如圖1中所示，虛線表示可能存在的墻壁，虛線圍成的方格為迷宮格。

假設(shè)初始時其他墻壁均不存在，單元格之間距離記為1，每一個90°轉(zhuǎn)彎所耗時間也等效為距離，記為，每一個180°轉(zhuǎn)彎所耗時間等效為距離b（測試中所使用的電腦鼠a≈1，b≈10）。

圖1中迷宮格A和目標(biāo)區(qū)域G的距離應(yīng)該這樣計算：距離A最近的墻壁不存在的概率為（28-1），A到G的最短距離為，即A到G有的可能距離為；在該墻壁存在的情況下，距離A第二近的墻壁不存在的概率·26/（27-1），此時A到G的最短距離為，即A到G有的可能最短距離為；依此類推，、如表1所示。

最終可得到A到G的距離：

由于上述結(jié)果是一個概率與距離的乘積，表示概率意義上的距離，所以也稱其為“概率距離”。

上述概率距離的計算過程中，并沒有考慮電腦鼠當(dāng)前的方向，這顯然是不合理的，因為每個轉(zhuǎn)彎或調(diào)頭，都會影響電腦鼠與目標(biāo)區(qū)域之間的概率距離，所以電腦鼠當(dāng)前的方向也是影響概率距離的因素之一。以圖1為例，假設(shè)電腦鼠初始方向向上，B到G有的可能最短距離為；有的可能最短距離為；依次類推可以得到、如表2所示。

可得到B到G的有向概率距離：

根據(jù)迷宮單元格的物理位置進(jìn)行分類并編號，并按照上述算法進(jìn)行計算，可以得出迷宮中每個單元格到目標(biāo)區(qū)域的概率距離，這樣便可以生成一個方向為上的靜態(tài)概率距離圖，如圖2所示。

同理，其他3個方向的有向概率距離圖，可以由圖2旋轉(zhuǎn)得到，在此不再贅述。

1.2 迷宮圖的動態(tài)處理

隨著電腦鼠的搜索，越來越多的迷宮格數(shù)據(jù)被獲取，根據(jù)獲取的數(shù)據(jù)，使用封閉體算法（Closed body algorithm）對靜態(tài)概率距離圖進(jìn)行修正。封閉體，就是在迷宮搜索過程中經(jīng)常碰到的“死胡同”，是指某一區(qū)域與外界只有一個出入口連接，除非目標(biāo)點在這一區(qū)域內(nèi)，否則，進(jìn)入該區(qū)域是不可能到達(dá)目標(biāo)點的。封閉體算法主要由以下兩個步驟實現(xiàn)。

1.2.1 迷宮格封閉

在電腦鼠搜索過程中，每探明一個迷宮格的墻壁數(shù)據(jù)，更新相鄰迷宮格的墻壁資料，此時對墻壁資料有變動的迷宮格進(jìn)行判斷，若3個方向均為有墻，則對該迷宮格進(jìn)行封閉[5]，即設(shè)置第4個方向為有墻；變更后繼續(xù)對有墻壁數(shù)據(jù)更新的迷宮格進(jìn)行同樣的判斷、操作，直至更新完畢。

1.2.2 迷宮區(qū)域封閉

在電腦鼠搜索過程中，遇到路口或要返回某個路口時，可以參考Flood-Fill[6]算法來進(jìn)行判斷：向該路口的某個方向相鄰迷宮格注入某個數(shù)值，按照廣度優(yōu)先算法[7]，將此數(shù)值賦給所有連通的迷宮格（已探明的迷宮格除外），最終判斷目標(biāo)迷宮格是否也得到了這個值。若得到了，則路口的該方向是個可行路徑，否則，判斷為該方向不可行。

2 基于概率距離的迷宮搜索流程

基于概率距離的迷宮搜索，首先建立靜態(tài)概率距離圖，電腦鼠從起點出發(fā)后，使用“死路”算法更新迷宮格墻壁狀態(tài)。若遇到路口，則使用Flood-Fill算法判斷路口與終點是否存在可達(dá)性，若不存在，則關(guān)閉此方向的墻壁；若存在多個可行的方向，則利用靜態(tài)概率距離圖判斷最優(yōu)路徑，直到電腦鼠到達(dá)目標(biāo)區(qū)域。

3 測試結(jié)果

隨機采用電腦鼠競賽地圖對“概率距離”算法進(jìn)行測試，并使用“左手”“中左”“向心”“中心分割”等算法進(jìn)行對比測試。結(jié)果如表3所示，“路程”表示行進(jìn)距離，“總路程”表示90°轉(zhuǎn)彎、180°轉(zhuǎn)彎量化為路程之后的總和，“探明”表示搜索后已知單元格的總數(shù)，“效率”表示探明單元格數(shù)量與路程總和的比值。對于測試使用的地圖，基于概率距離的迷宮搜索算法，在迷宮搜索效率、迷宮搜索時間（總路程）等方面，較左手、中左、中心、分區(qū)中心等搜索算法有明顯優(yōu)勢。

4 結(jié)語

對于一個完全未知的迷宮，如何進(jìn)行高效率的搜索，是電腦鼠走迷宮競賽中的關(guān)鍵環(huán)節(jié)。文章提出了基于概率距離的迷宮搜索算法，從概率學(xué)的角度出發(fā)生成概率距離圖，并結(jié)合電腦鼠運行過程中所獲取的數(shù)據(jù)，形成了獨特的搜索路徑選擇機制。這是一種迷宮搜索的新方法，測試結(jié)果表明其具有獨特的優(yōu)勢。

參考文獻(xiàn)

[1] MicroMouseInfo.com.Design of a working MicroMouse[EB/OL].[2015-12-27].http：//www.micromouseinfo.com/.

[2] 林國恩.電腦鼠的設(shè)計與制作[D].桃園：臺灣龍華科技大學(xué)，2010.

[3] Mishra S，Bande P.Maze solving algorithms for micro mouse[C]//Signal Image Technology and Internet Based Systems， 2008. SITIS'08. IEEE International Conference on. IEEE， 2008： 86-93.

[4] 周立功.IEEE電腦鼠開發(fā)指南-基于MicroMouse615迷宮智能鼠[M].廣州：廣州致遠(yuǎn)電子有限公司，2010.

[5] Li X， Jia X， Xu X， et al.An improved algorithm of the exploring process in Micromouse Competition[C]//Intelligent Computing and Intelligent Systems （ICIS）， 2010 IEEE International Conference on. IEEE， 2010， 2：324-328.

[6] Mishra S， Bande P.Maze solving algorithms for micro mouse[C]//Signal Image Technology and Internet Based Systems， 2008. SITIS08. IEEE International Conference on. IEEE， 2008： 86-93.

[7] 嚴(yán)蔚敏.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M].北京：清華大學(xué)出版社，2007.