基于IEEE標(biāo)準(zhǔn)的電腦鼠走迷宮的智能算法研究

王斌，張衛(wèi)鋼

（長安大學(xué) 信息工程學(xué)院，陜西 西安 710064）

電腦鼠[1]（Micromouse）是一個(gè)由微控制器、探測器、驅(qū)動(dòng)電機(jī)等構(gòu)成的，集感知、判斷、行走功能于一體，能夠自動(dòng)尋找到達(dá)目的地最佳路徑的小型機(jī)器人。它可以在迷宮中自動(dòng)感知并記憶分析迷宮地圖，在規(guī)定時(shí)間內(nèi)，通過一定的智能算法，尋找一條最優(yōu)路徑，以最快的速度從起點(diǎn)沖刺到終點(diǎn)。IEEE標(biāo)準(zhǔn)規(guī)定，迷宮由16×16個(gè)、18 cm×18 cm大小的正方形單元格組成，隔板沿單元格布設(shè)，形成迷宮通道，起點(diǎn)在迷宮任意一角，終點(diǎn)在迷宮中心。

電腦鼠的基本功能是從起點(diǎn)開始走到終點(diǎn)，該過程稱為1次“運(yùn)行”，花費(fèi)的時(shí)間稱為“運(yùn)行時(shí)間”[1]。從終點(diǎn)回到起點(diǎn)所花費(fèi)的時(shí)間不計(jì)算在運(yùn)行時(shí)間之內(nèi)。從電腦鼠的第1次激活到每次運(yùn)行開始，這期間所花費(fèi)的時(shí)間稱為“迷宮時(shí)間”[1]。若在比賽時(shí)需要手動(dòng)輔助，則稱為“碰觸”[1]。競賽主要采用這3個(gè)參數(shù)來進(jìn)行評分，運(yùn)行時(shí)間最短的電腦鼠獲勝。因此，高效的迷宮搜索算法和轉(zhuǎn)彎算法就顯得至關(guān)重要。基于此對電腦鼠走迷宮的軟件控制算法和轉(zhuǎn)彎算法進(jìn)行深入的探討和研究。

1 電腦鼠探索迷宮

1.1 迷宮探索過程

根據(jù)IEEE標(biāo)準(zhǔn)電腦鼠走迷宮競賽要求[1]，電腦鼠完成整個(gè)走迷宮任務(wù)可分為以下4個(gè)步驟：

1）第一次搜索 電腦鼠按照一定的搜索算法從起點(diǎn)開始搜索直至到達(dá)終點(diǎn)的任意一個(gè)單元格，并記憶走過的路徑信息，該過程為第一次搜索。整個(gè)迷宮用二維坐標(biāo)表示，左下角設(shè)為原點(diǎn)坐標(biāo)（0，0），向上向右依次為Y軸正向和X軸正向。起點(diǎn)為任意一角，坐標(biāo)為（0，0）或（15，0）的單元格，終點(diǎn)在中心，由坐標(biāo)為（7，7）、（7，8）、（8，7）和（8，8）的 4 個(gè)單元格組成。

2）第二次搜索 從第一次搜索完成時(shí)所處的位置開始按照一定的智能算法進(jìn)行搜索直至找到起點(diǎn)，并記憶走過的路徑信息，該過程為第二次搜索。為了在最短時(shí)間內(nèi)搜索到更多路徑信息，此次搜索的路徑盡可能避免和第一次搜索的重復(fù)，以便更加高效地搜索迷宮，增大找到最優(yōu)解的可能性。

3）沖刺 根據(jù)兩次搜索到的迷宮信息，按照一定的智能算法選擇一條從起點(diǎn)到終點(diǎn)的最優(yōu)路徑，然后從起點(diǎn)快速到達(dá)終點(diǎn)，該過程為沖刺。因轉(zhuǎn)彎和走直線耗時(shí)不同，在選擇最優(yōu)路徑時(shí)還要考慮轉(zhuǎn)彎加權(quán)比重問題。

4）回起點(diǎn) 電腦鼠沿原路返回至起點(diǎn)。

1.2 軟件設(shè)計(jì)與實(shí)現(xiàn)

電腦鼠走迷宮過程可以分為4個(gè)狀態(tài)：等待狀態(tài)、啟動(dòng)狀態(tài)、搜索狀態(tài)和沖刺狀態(tài)。主程序流程[2]如圖1所示。

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

1）等待狀態(tài) 在該狀態(tài)中，電腦鼠靜止在起點(diǎn)，等待觸發(fā)啟動(dòng)鍵，當(dāng)啟動(dòng)鍵按下后，電腦鼠進(jìn)入啟動(dòng)狀態(tài)。

2）啟動(dòng)狀態(tài) 在該狀態(tài)中，電腦鼠根據(jù)第一次轉(zhuǎn)彎的方向判斷起點(diǎn)的坐標(biāo)是（0，0）還是（15，0），向左轉(zhuǎn)時(shí)起點(diǎn)坐標(biāo)為（15，0），向右轉(zhuǎn)時(shí)起點(diǎn)坐標(biāo)為（0，0）。

3）搜索狀態(tài) 在該狀態(tài)中，電腦鼠的任務(wù)就是探索并記憶迷宮信息。采用基于向心法則和向點(diǎn)法則的深度優(yōu)先搜索算法和洪水填充法相結(jié)合的智能搜索算法，實(shí)現(xiàn)部分迷宮搜索。程序流程如圖2所示。

圖2 搜索程序流程圖Fig.2 Flow chart of searching program

4）沖刺狀態(tài) 迷宮搜索完畢后，補(bǔ)全迷宮信息，根據(jù)洪水填充法找出一條從起點(diǎn)到終點(diǎn)的最佳路徑并沖刺到終點(diǎn)。

2 智能算法設(shè)計(jì)與分析

2.1 迷宮搜索算法

迷宮搜索常用的算法有深度優(yōu)先法[3]、洪水填充法、遺傳算法[4]等，本文提出一種基于向心法則和向點(diǎn)法則的深度優(yōu)先法和洪水填充法相結(jié)合的智能搜索算法?；舅枷耄旱?次搜索采用基于向心法則的深度優(yōu)先搜索算法，逐次搜索直至找到終點(diǎn)，搜索過程中遇到需要回溯到上一節(jié)點(diǎn)的情況時(shí)，采用洪水填充法尋找到達(dá)上一節(jié)點(diǎn)的最短路徑，并快速到達(dá)該節(jié)點(diǎn)。為了第二次搜索時(shí)的“熱區(qū)”定義做準(zhǔn)備，需要備份此次搜索的部分路徑信息作為“熱區(qū)”；第2次搜索采用基于向點(diǎn)法則的深度優(yōu)先搜索算法，逐次搜索直至找到起點(diǎn)，搜索過程中遇到需要回溯到上一節(jié)點(diǎn)的情況時(shí)，采用洪水填充法尋找最優(yōu)路徑，在到達(dá)起點(diǎn)之前必然碰觸“熱區(qū)”，一旦碰觸“熱區(qū)”立即采用洪水填充法找到回起點(diǎn)的最優(yōu)路徑并快速回至起點(diǎn)；沖刺前要進(jìn)行數(shù)據(jù)補(bǔ)全，然后采用洪水填充法根據(jù)已搜索過的迷宮信息找出一條從起點(diǎn)到終點(diǎn)的最優(yōu)路徑[5]，以最快的速度沖刺到終點(diǎn)。

2.1.1 向心法則

向心法則是深度優(yōu)先搜索迷宮過程中遇到叉路口時(shí)采用的一種搜索法則，常用的搜索法則有以下4種，向心法則是對這4種法則的綜合運(yùn)用。

1）左手法則：優(yōu)先左轉(zhuǎn)，其次是直走、右轉(zhuǎn)。2）右手法則：優(yōu)先右轉(zhuǎn)，其次是直走、左轉(zhuǎn)。3）中左法則：優(yōu)先直走，其次是左轉(zhuǎn)、右轉(zhuǎn)。4）中右法則：優(yōu)先直走，其次是右轉(zhuǎn)、左轉(zhuǎn)。

5）向心法則：由于終點(diǎn)在迷宮中心，遇叉路口時(shí)，以向迷宮中心方向?yàn)閮?yōu)先的前進(jìn)方向。如下圖3所示，把整個(gè)迷宮均分為A、B、C和D 4個(gè)區(qū)域，每個(gè)區(qū)域使用不同的法則組合，例如，在A區(qū)中，向上搜索時(shí)采用中右法則，向下搜索時(shí)采用左手法則，向左搜索時(shí)采用右手法則，向右搜索時(shí)采用中左法則。

圖3 向心法則示意圖Fig.3 Schematic diagram of the rule towards the center

2.1.2 洪水填充法

洪水填充法[6]可以想象為洪水從迷宮的某一個(gè)單元格涌出，沿所有走過的路徑方向流動(dòng)，每流動(dòng)一格就將該單元格進(jìn)行遞增的數(shù)字編碼，直至到達(dá)目的單元格。實(shí)際在某種程度上洪水填充法運(yùn)用了繪制等高圖的原理，尋找一條從一點(diǎn)到另一點(diǎn)的最優(yōu)路徑。

2.1.3 向點(diǎn)法則

向點(diǎn)法則是把整個(gè)迷宮看成一個(gè)區(qū)域，電腦鼠從迷宮終點(diǎn)出來后繼續(xù)搜索，當(dāng)遇到叉路口時(shí)運(yùn)用向點(diǎn)法則（迷宮起點(diǎn)坐標(biāo)為（15，0）時(shí)）：向上搜索采用右手法則，向下搜索采用中左法則，向左搜索采用左手法則，向右搜索采用中右法則。當(dāng)起點(diǎn)坐標(biāo)為（0，0）時(shí)以此類推。

2.1.4 “熱區(qū)”選擇

從第一次搜索過的迷宮中選取部分合適的迷宮格作為特殊區(qū)域，這個(gè)特殊區(qū)域即為“熱區(qū)”。例如，假設(shè)起點(diǎn)坐標(biāo)為（15，0）， 設(shè) 11＜X≤15 且 0≤Y≤15 區(qū)域?yàn)?S1，0≤X≤15 且0≤Y＜4區(qū)域?yàn)镾2，S1和S2中在第一次搜索過程中被搜索到的所有迷宮格的集合即可設(shè)為“熱區(qū)”。這是為第二次搜索過程中找到一個(gè)合適的位置后快速返回至起點(diǎn)而設(shè)計(jì)的。“熱區(qū)”范圍的定義有多種，本文僅舉其一例，如在2010年電腦鼠走迷宮競賽（西北賽區(qū)）迷宮圖中的“熱區(qū)”選擇如圖4中的黑點(diǎn)所在單元格的集合，箭頭處為發(fā)生碰觸的地方。

圖4 “熱區(qū)”選擇Fig.4 Choices of“hot zone”

2.1.5 數(shù)據(jù)補(bǔ)全

數(shù)據(jù)補(bǔ)全，就是對未探測到的單元格，通過周圍已有的墻壁資料，可進(jìn)行補(bǔ)充的一種方法[6]。由于采用一個(gè)8位二維數(shù)組GucmapBlock[X][Y]存儲(chǔ)迷宮墻壁信息（如表1），迷宮墻壁資料全部初始化為0，凡是已走過的迷宮格至少有一個(gè)方向墻壁資料不為0，根據(jù)未探測到的單元格上下左右4個(gè)相鄰單元格的墻壁資料分析并大膽設(shè)想該單元格的墻壁信息。如圖5（a）為某單元格補(bǔ)全前墻壁信息，圖5（b）為補(bǔ)全后墻壁信息。

表1 墻壁資料存儲(chǔ)方式Tab.1 The storage mode of walls information

圖5 數(shù)據(jù)補(bǔ)全前后對照表Fig.5 Table of data before and after completion

2.1.6 最優(yōu)路徑

電腦鼠要在最短的時(shí)間內(nèi)完成由起點(diǎn)到終點(diǎn)的沖剌，最優(yōu)路徑的選擇至關(guān)重要，步數(shù)少的路徑是最佳路徑的條件之一，但不是唯一條件。考慮到電腦鼠在拐彎時(shí)也要耗時(shí)，所以要對拐彎次數(shù)加權(quán)后加到步數(shù)中得到加權(quán)步數(shù)[6]。

加權(quán)步數(shù)=實(shí)際步數(shù)+拐彎次數(shù)×拐彎權(quán)重

拐彎次數(shù)：一個(gè)90°的拐彎算一次，一個(gè)180°的拐彎算二次（可根據(jù)實(shí)際測試情況而定）。

拐彎權(quán)重：需要結(jié)合電腦鼠的機(jī)械結(jié)構(gòu)、直道速度、轉(zhuǎn)彎速度等因素來確定。實(shí)際測試計(jì)算出拐彎權(quán)重大約為0.5。迷宮圖4中的最優(yōu)路徑選擇如圖6中的粗實(shí)線路徑所示，路徑A的加權(quán)步數(shù)N1=55+24×0.5=67；路徑B的加權(quán)步數(shù)N2=59+22×0.5=70；路徑 C 的加權(quán)步數(shù) N3=59+20×0.5=69；因此，最優(yōu)路徑為路徑A。

圖6 最優(yōu)路徑的選擇Fig.6 Choices of the optimal path

該智能算法的關(guān)鍵點(diǎn)如下：1）向心法則和向點(diǎn)法則使深度優(yōu)先法在迷宮搜索中的運(yùn)用更加合理。2）在第二次搜索過程中搜索到某一節(jié)點(diǎn)時(shí)檢測到該節(jié)點(diǎn)的臨格已搜索過且在“熱區(qū)”內(nèi)，那么電腦鼠立即根據(jù)洪水填充法快速回至起點(diǎn)，目的是為了避免搜索過多路徑而耗費(fèi)更多時(shí)間。此外，一旦碰觸“熱區(qū)”也就意味著搜索到至少有兩條以上的路徑可到達(dá)終點(diǎn)，路徑具有可選擇性和可比性。3）墻壁資料補(bǔ)全和加權(quán)步數(shù)的設(shè)計(jì)大大增加尋找到最優(yōu)路徑的可能性。

2.2 轉(zhuǎn)彎算法

2.2.1 停轉(zhuǎn)算法

停轉(zhuǎn)算法思想：電腦鼠在前進(jìn)中遇到叉路口需要轉(zhuǎn)彎時(shí)，兩輪同時(shí)停轉(zhuǎn)，一輪正轉(zhuǎn)若干步，一輪反轉(zhuǎn)若干步，然后繼續(xù)前進(jìn)。每次轉(zhuǎn)完后，小車必在格子中心，實(shí)現(xiàn)準(zhǔn)確定位。以左轉(zhuǎn)為例如圖7（a）所示，電腦鼠在行進(jìn)中不斷檢測墻壁信息，當(dāng)左面的傳感器檢測到無墻時(shí)，再前進(jìn)若干步停止，然后左輪反轉(zhuǎn)若干步，右輪正轉(zhuǎn)相同的若干步，這樣保證電腦鼠轉(zhuǎn)90°后安穩(wěn)的停在格子中心，隨后賦新的任務(wù)量，準(zhǔn)備進(jìn)行下一個(gè)動(dòng)作。實(shí)驗(yàn)證明，該算法轉(zhuǎn)彎準(zhǔn)確率高，安全系數(shù)大，適合前期路徑搜索，缺點(diǎn)是速度慢，嚴(yán)重影響解迷宮效率。

2.2.2 連續(xù)轉(zhuǎn)彎算法

連續(xù)轉(zhuǎn)彎算法思想：電腦鼠在前進(jìn)中遇到叉路口需要轉(zhuǎn)彎時(shí)，一輪低于直道速度前進(jìn)若干步，一輪速度突然提高到某一值前進(jìn)另一若干步，保證在最短的時(shí)間內(nèi)實(shí)現(xiàn)快速轉(zhuǎn)90°，然后兩輪同時(shí)恢復(fù)到直道速度繼續(xù)前進(jìn)。這種方法轉(zhuǎn)彎迅速且不失坐標(biāo)，相對于停轉(zhuǎn)速度快幾倍。以左轉(zhuǎn)為例如圖7（b）所示，電腦鼠在行進(jìn)中不斷檢測墻壁信息，當(dāng)左面的傳感器檢測到無墻時(shí)，兩輪同時(shí)前進(jìn)相同合適的步數(shù)之后，左輪以低于直道速度前進(jìn)若干步，右輪通過人為修改定時(shí)器頻率使其速度突變并前進(jìn)另一若干步，實(shí)現(xiàn)左右兩輪行進(jìn)中連續(xù)轉(zhuǎn)彎，具有轉(zhuǎn)彎速度快，求解迷宮效率高的優(yōu)點(diǎn)。

圖7 電腦鼠轉(zhuǎn)彎Fig.7 Micromouse turning

3 結(jié)束語

本文提出的算法可以大大避免了重復(fù)搜索、“孤島”[7]等問題，實(shí)現(xiàn)了搜索部分迷宮即可找出從起點(diǎn)到終點(diǎn)的最優(yōu)路徑。由圖6可以看出搜索過的單元格占整個(gè)迷宮單元格的比例近2/3，且四角基本未進(jìn)行搜索，該智能算法搜索迷宮效率高，比較科學(xué)合理。此外，采用連續(xù)轉(zhuǎn)彎算法也在一定程度上縮短了運(yùn)行時(shí)間。另外，該智能算法在2010電腦鼠走迷宮（西北賽區(qū)）競賽中也得到了驗(yàn)證，并取得了優(yōu)異的成績。電腦鼠的歷史已經(jīng)超過了50年，但迄今為止幾乎沒有一種智能算法能保證在任意未知迷宮中都比其他算法好，因此對電腦鼠走迷宮智能算法的研究仍任重道遠(yuǎn)。

[1]周立功.IEEE電腦鼠開發(fā)指南[M].廣州：廣州致遠(yuǎn)電子有限公司，2008.

[2]朱姍，傅或哲，吳忠麗，等.一種走迷宮電腦鼠的設(shè)計(jì)與實(shí)現(xiàn)[J].微型電腦應(yīng)用，2008，24（9）：59-62.ZHU Shan，F(xiàn)U Huo-zhe，WU Zhong-li，et al.Research and realization on micromouse for maze searching[J].Microcomputer Applications，2008 24（9）：59-62.

[3]嚴(yán)蔚敏，陳文博.數(shù)據(jù)結(jié)構(gòu)及算法應(yīng)用教程[M].北京：清華大學(xué)出版社，2001.

[4]徐守江.迷宮算法綜述[J].信息與電腦，2009（10）：91-92.XU Shou-jiang.Labyrinth algorithm[J].China Computer&Communication，2009（10）：91-92.

[5]楊新.礦區(qū)中一種走迷宮電腦鼠的研究與實(shí)現(xiàn)[J].煤炭技術(shù)，2010，29（6）：168-171.YANG Xin.Research and realization on micromouse for maze searching in coalmine[J].Coal Technology，2010，29（6）：168-171.

[6]張新誼.一種電腦鼠走迷宮的算法[J].單片機(jī)與嵌入式系統(tǒng)應(yīng)用，2007（5）：84-85.ZHANG Xin-yi.Analgorithm ofmicromousemaze[J].Microcontrollers&Embedded System，2007（5）：84-85.

[7]朱聞達(dá).IEEE迷宮電腦鼠的迷宮搜索算法研究[J].科技博覽，2009（27）：7-8.ZHU Wen-da.Maze search algorithm research of IEEE maze micromouse[J].China Science and Technology Review，2009（27）：7-8.