用于迷宮電腦鼠的一種迷宮補(bǔ)全算法

于佳維，潘志雄，馬忠梅

（北京理工大學(xué) 計算機(jī)學(xué)院，北京100081）

引 言

“電腦鼠（MicroMouse）”是一種使用嵌入式微控制器、避障傳感器和機(jī)電運(yùn)動部件構(gòu)成的一種智能行走機(jī)器人。其主要功能為在迷宮中行走，并通過傳感器收集迷宮中的環(huán)境數(shù)據(jù)，通過對數(shù)據(jù)的分析和運(yùn)算找到通往目的點的路徑。國際電工和電子工程學(xué)會每年都要舉辦一次國際性的電腦鼠走迷宮大賽，我國從2009年開始舉辦全國性的電腦鼠走迷宮大賽。比賽的關(guān)鍵在于如何在迷宮中快速找到合適路線并且到達(dá)目標(biāo)點。目前對電腦鼠的改進(jìn)有3個主要的研究方向：硬件上電腦鼠性能的改進(jìn)、搜索算法上的改進(jìn)和比賽策略上的改進(jìn)。本文基于電腦鼠走迷宮大賽的規(guī)則介紹了搜索算法改進(jìn)的一種思想。

1 電腦鼠走迷宮的規(guī)則介紹

因為本文的算法基于電腦鼠走迷宮競賽，為了方便闡述，現(xiàn)簡要介紹電腦鼠走迷宮的競賽規(guī)則。

1.1 迷宮的規(guī)范

電腦鼠比賽用的標(biāo)準(zhǔn)迷宮由16×16個18cm×18cm的正方形單元所組成。迷宮的隔墻高5cm，厚1.2cm，兩個隔墻所構(gòu)成的通道的實際距離為16.8cm。外墻將整個迷宮封閉。迷宮的起始單元可選設(shè)在迷宮4個角落之中的任何一個。起始單元必須3 面有隔墻，只留一個出口。例如，如果沒有隔墻的出口端為“北”時，那么迷宮的外墻就構(gòu)成位于“西”和“南”的隔墻。電腦鼠競賽的終點設(shè)在迷宮中央，由4個正方形單元構(gòu)成。在每個單元的4角可以插上一個小立柱，其截面為正方形。立柱長1.2 cm，寬1.2cm，高5cm。小立柱所處的位置稱為“格點”。除了終點區(qū)域的格點外，每個格點至少要與一面隔墻相接觸。電腦鼠迷宮圖如圖1所示。

圖1 電腦鼠迷宮圖

1.2 競賽主要規(guī)則

電腦鼠的基本功能是從起點開始走到終點，這個過程稱為一次“運(yùn)行”，所花費(fèi)的時間稱為“運(yùn)行時間”。從終點回到起點所花費(fèi)的時間不計算在運(yùn)行時間內(nèi)。從電腦鼠的第一次激活到每次運(yùn)行開始，這段期間所花費(fèi)的時間稱為“迷宮時間”。如果電腦鼠在比賽時需要手動輔助，這個動作稱為“碰觸”。競賽使用這3個參數(shù)，從速度﹑求解迷宮的效率和電腦鼠的可靠性3個方面來進(jìn)行評分。

電腦鼠的得分是通過計算每次運(yùn)行的“排障時間”來衡量的，排障時間越短越好。排障時間是這樣計算的：先將迷宮時間的1／30加上一次運(yùn)行時間，如果這次運(yùn)行結(jié)束以后電腦鼠沒有被碰觸過，那么還要再減去10s的獎勵時間，得到的就是排障時間。每個電腦鼠允許運(yùn)行多次，取其中最短的排障時間作為參賽的計分成績。

例子：一個電腦鼠在迷宮中運(yùn)行時間為4min（240s）沒有碰觸過，迷宮時間使用了20s，這次運(yùn)行的排障時間就是：20s＋（240s×1／30）-10s＝18s。

2 算法概述

2.1 算法提出的背景

電腦鼠走迷宮進(jìn)行迷宮搜索的最基礎(chǔ)算法即為對迷宮進(jìn)行全搜索，也就是將迷宮中的每一個格子都走遍。這種算法可以得知迷宮的全部信息，從而搜索出到達(dá)目的點的每一條路徑，再通過一定的路徑選擇方法得出起點到終點的最短路徑。但是按照上述的競賽規(guī)則，顯然對迷宮進(jìn)行全搜索會使得迷宮時間過長。在特殊迷宮的情況下會使得迷宮時間遠(yuǎn)遠(yuǎn)高于預(yù)期，所以全搜索的搜索方法效率并不高，在現(xiàn)在的比賽中已經(jīng)基本見不到。

所以，如何在最短的時間內(nèi)快速地找到一條基本合適的路徑就變得十分重要。而對于迷宮進(jìn)行部分搜索，如何優(yōu)化使得搜索時間盡量短，是解決上述問題的主要思考方向。下面就此問題提出一種算法。

2.2 算法思想

電腦鼠在起點處第一次運(yùn)行時，對整個迷宮的信息都是未知的。電腦鼠通過在迷宮中行走來獲取迷宮的情況。但是，傳統(tǒng)的電腦鼠搜索算法往往只注重當(dāng)前所在格的信息，而忽略了當(dāng)前格子信息對周圍格子的影響；注重通過小車行走來獲得信息，而忽略了通過算法提前搜索分析行走的可行性。

以往的算法只注重當(dāng)前格子的狀態(tài)，比如電腦鼠所在格子狀態(tài)為上面有墻，下面有墻，左側(cè)無墻，右側(cè)無墻。實際上探測到當(dāng)前格子所能掌握的信息遠(yuǎn)比這多，比如在上面例子的基礎(chǔ)之上還能推測出電腦鼠當(dāng)前位置的上面一格的下面有墻，下面一格的上面有墻，左面一格的右側(cè)無墻，右面一格的左側(cè)無墻。

以往算法在一些格子的部分信息未知的情況下，選擇讓小車行走去獲得信息，這樣有可能陷入“死胡同”。實際上可以讓算法去“行走”，即先用廣度搜索算法預(yù)先搜索去分析可行性，再讓小車行走。

本文提出的算法則利用了已獲得的和補(bǔ)全的信息，從而推測出迷宮中只有一個入口的不規(guī)則形狀死路。將這些死路在記錄信息中進(jìn)行“堵死”處理，從而避免了電腦鼠進(jìn)入死路進(jìn)行搜索，大大節(jié)省了搜索時間，提高了搜索效率。

3 “補(bǔ)全迷宮”算法

3.1 數(shù)據(jù)結(jié)構(gòu)

采用一個字節(jié)的8位來表示一個迷宮格的信息，低4位從左到右分別代表“左”、“下”、“右”、“上”4個方向，1表示沒墻，0表示有墻，方向相當(dāng)于坐標(biāo)的X 與Y 軸；而高4位與低4位的方向一一對應(yīng)，1表示該方向搜索過，0為未搜索過。當(dāng)高4位全為1時候，即當(dāng)前格的4個方向都搜索過，表示當(dāng)前格是小車已經(jīng)走過的。該數(shù)據(jù)結(jié)構(gòu)充分利用了字節(jié)的全部8位信息，減少了不必要的浪費(fèi)。

例如：當(dāng)一個字節(jié)為0100 0000 的時候，高4 位中“下”方向為1，表示當(dāng)前格的“下”方向是搜索過的，即該方向的“墻”是已知的。這時低4位中對應(yīng)位的數(shù)值才有意義，可以看出“下”方向為有墻。

在廣度搜索時，采用隊列數(shù)據(jù)結(jié)構(gòu)存儲有路的方格，不斷取出隊列的頭一個方格進(jìn)行分析，搜索到四周有路的方格加入隊列，直到達(dá)到搜索目的。

3.2 核心算法

算法的核心是“信息補(bǔ)全”和“預(yù)先搜索”。

3.2.1 信息補(bǔ)全

當(dāng)小車走到某一格的時候，不僅要更新當(dāng)前格的全部“墻”信息，還要更新四周格子的部分“墻”信息。

圖2 電腦鼠迷宮信息補(bǔ)全圖

電腦鼠迷宮信息補(bǔ)全圖如圖2所示，初始4格的位置信息都為00000000。當(dāng)小車處在“1”方格中，根據(jù)小車自身探測結(jié)果可得該位置的信息為1111 1010，高4位為4個1，表示當(dāng)前格周圍4個方向都已經(jīng)搜索過，此時低4 位對應(yīng)的信息有效，分別表示“左”方向沒墻，“下”方向有墻，“右”方向有路，“上”方向有墻。

經(jīng)過信息補(bǔ)全，可以更新四周的格子的部分信息，如“2”。雖然“2”格小車還未走過，但是可以通過已經(jīng)走過的“1”格知道“2”格的部分信息為1000 1000，高4位為1000，表示“2”格小車還未走過，但是“左”方向已經(jīng)搜索過，為“左”方向沒墻。而當(dāng)小車走到“2”時，可知“上”方向有路，通過信息補(bǔ)全可得，“3”的“下”方向也有路。

通過信息補(bǔ)全的方法，可以減少小車的搜索，提高小車的搜索效率，為“預(yù)先搜索”提供信息的支持。

3.2.2 預(yù)先搜索

當(dāng)小車處在某一格子的時候，4個方向中有路可走，不是直接讓小車通過法則選擇一條路前進(jìn)，而是先讓小車通過“預(yù)先搜索”算法判斷往該方向前進(jìn)是否有可能到達(dá)終點，如果沒有可能到達(dá)終點，則不往該方向前進(jìn)，將其“堵死”，封鎖整個“死胡同”。

該方法利用之前小車搜索的信息以及補(bǔ)全的部分迷宮信息，其中將還未搜索過的方向全部假設(shè)為沒墻，采取“廣度搜索”策略，對從當(dāng)前格某一方向到終點的路徑進(jìn)行搜索，獲知該方向是否有可能到達(dá)終點，從而達(dá)到目的。而算法執(zhí)行的時間要遠(yuǎn)小于小車行走時間，可忽略不計。

電腦鼠迷宮預(yù)先搜索圖如圖3所示，“1”為起點，“2”為終點，而“a”“b”“c”都是沒必要走的“死胡同”，“3”“4”“5”為即將走入“死胡同”的前一格?？梢钥闯觯?dāng)小車在搜索時，要是進(jìn)入這些“死胡同”，將做大量的無用功，在里面繞來繞去卻無法通往終點，還需出來，浪費(fèi)時間。

當(dāng)小車搜索到“5”方格處時，有“左”和“上”兩個方向可以選擇，可以采取“預(yù)先搜索”的方法，對“左”方向進(jìn)行分析，雖然“c”中的單元格小車還未搜索過，但是其四周的單元格都已經(jīng)搜索過，根據(jù)四周方格搜索的信息對其補(bǔ)全，將未搜索的方向全部假設(shè)為沒墻，可得“c”的補(bǔ)全圖如圖4所示，運(yùn)用廣度搜索方法分析判斷，若往“左”方向進(jìn)去，無論如何走，都到達(dá)不了終點，所以在“5”方格出的“左”方向是不可行的，繼續(xù)用算法對其他有路的方向進(jìn)行分析。

圖3 電腦鼠迷宮預(yù)先搜索圖

圖4 電腦鼠迷宮“死胡同”補(bǔ)全圖

“預(yù)先搜索”算法可以阻斷“死胡同”這種耗費(fèi)大量搜索時間的路徑，減少了沒必要的搜索，大量減少搜索量，提高競賽成績。

3.3 算法實現(xiàn)

3.3.1 信息補(bǔ)全算法

信息補(bǔ)全算法的程序流程圖如圖5所示。

用Car［16］［16］數(shù)組存儲每個方格的“墻”信息，初始化全部為00000000。小車每搜索到一格時，更新當(dāng)前方格的信息，接著補(bǔ)全四周方格的信息。

圖5 信息補(bǔ)全程序流程圖

對四周方格信息的補(bǔ)全，可直接采用位運(yùn)算進(jìn)行“與”“或”求得。低4位中1為沒墻，0為有墻；高4位中1表示該方向搜索過，0為未搜索過。

其中核心代碼實現(xiàn)：

3.3.2 預(yù)先搜索

預(yù)先搜索的程序流程如圖6所示。

“預(yù)先”，即在小車行走前分析小車往某一有路方向前進(jìn)的可行性；“搜索”，即采用廣度搜索策略，對已有的搜索信息以及補(bǔ)全的信息進(jìn)行分析，判斷小車是否有可能從該方向到達(dá)終點。

廣度搜索，即首先將根節(jié)點放入隊列中，從隊列中取出第一個節(jié)點，驗證其是否為目標(biāo)，在迷宮中搜索即為驗證其是否為終點。如果是，則結(jié)束搜索并返回結(jié)果；否則將符合條件的子節(jié)點加入隊列中，即將4個方向有路的節(jié)點加入隊列中，重復(fù)取頭節(jié)點，直到隊列為空，返回分析結(jié)果。

由于一般微控制器的可用棧大小是有限制的，如果用深度搜索的話，在全迷宮中會造成棧溢出，所以采用動態(tài)隊列，進(jìn)行廣度搜索。

圖6 預(yù)先搜索流程圖

在廣度搜索中，將那些未搜索的方向全部假設(shè)為沒墻。核心代碼如下：

結(jié) 語

本文介紹了一種迷宮電腦鼠在搜索過程中的優(yōu)化算法。通過對搜索信息的擴(kuò)展和分析達(dá)到對電腦鼠走迷宮過程中的無用路徑進(jìn)行刪除，從而達(dá)到節(jié)省搜索時間、提高比賽成績的目的。該算法已應(yīng)用在2012年全國電腦鼠走迷宮大賽中，優(yōu)化效果比較明顯。在電腦鼠走迷宮競賽的影響力日益擴(kuò)大的今天，提供了一種在算法上對電腦鼠進(jìn)行優(yōu)化的思路。同時也歡迎大家對算法中的問題和可以改進(jìn)的地方進(jìn)行討論，提出寶貴意見。

［1］Mark Allen Weiss.Data Structures and Algorithm Analysis in C［M］.北京：人民郵電出版社，2005.

［2］嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)［M］.北京：清華大學(xué)出版社，2007.

［3］廣州致遠(yuǎn)電子有限公司.電腦鼠開發(fā)設(shè)計指南［OL］.［2012-09］.http：／／embedtools.com.

［4］張萌，和湘，姜斌.單片機(jī)應(yīng)用系統(tǒng)開發(fā)綜合實例［M］.北京：清華大學(xué)出版社，2003.

［5］賀利軍.智能老鼠走迷宮算法的設(shè)計［J］.電腦與電信，2008（10）：44- 45.