于佳維，潘志雄，馬忠梅

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

引 言

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

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

因?yàn)楸疚牡乃惴ɑ陔娔X鼠走迷宮競(jìng)賽，為了方便闡述，現(xiàn)簡(jiǎn)要介紹電腦鼠走迷宮的競(jìng)賽規(guī)則。

1.1 迷宮的規(guī)范

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

圖1 電腦鼠迷宮圖

1.2 競(jìng)賽主要規(guī)則

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

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

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

2 算法概述

2.1 算法提出的背景

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

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

2.2 算法思想

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

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

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

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

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

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

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

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

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

3.2 核心算法

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

3.2.1 信息補(bǔ)全

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

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

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

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

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

3.2.2 預(yù)先搜索

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

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

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

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

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

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

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

3.3 算法實(shí)現(xiàn)

3.3.1 信息補(bǔ)全算法

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

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

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

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

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

3.3.2 預(yù)先搜索

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

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

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

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

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

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

結(jié) 語

本文介紹了一種迷宮電腦鼠在搜索過程中的優(yōu)化算法。通過對(duì)搜索信息的擴(kuò)展和分析達(dá)到對(duì)電腦鼠走迷宮過程中的無用路徑進(jìn)行刪除，從而達(dá)到節(jié)省搜索時(shí)間、提高比賽成績(jī)的目的。該算法已應(yīng)用在2012年全國(guó)電腦鼠走迷宮大賽中，優(yōu)化效果比較明顯。在電腦鼠走迷宮競(jìng)賽的影響力日益擴(kuò)大的今天，提供了一種在算法上對(duì)電腦鼠進(jìn)行優(yōu)化的思路。同時(shí)也歡迎大家對(duì)算法中的問題和可以改進(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è)計(jì)指南［OL］.［2012-09］.http：／／embedtools.com.

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

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