王昕++++袁曉堂++++陳晨++++馬浩++++袁臣虎

摘 要： 一款性能穩(wěn)定，功能全面，算法優(yōu)良的高效智能“電腦鼠”能在短時(shí)間內(nèi)快速穩(wěn)定地完成復(fù)雜迷宮的搜索和沖刺。本文將向心算法和洪水算法融合形成向洪算法，介紹了該算法的工作原理，并對(duì)該算法進(jìn)行優(yōu)化和評(píng)估后完成迷宮搜索、迷宮二次回程搜索。向洪算法在保持向心算法和洪水算法優(yōu)勢(shì)的基礎(chǔ)上減輕了處理器的運(yùn)算負(fù)擔(dān)，使電腦鼠運(yùn)行穩(wěn)定性進(jìn)一步提高。實(shí)驗(yàn)表明，與傳統(tǒng)算法相比，加載該算法的“電腦鼠”可以探尋出更加有利的路徑，獲取更全面的迷宮信息，是一種高效的迷宮搜索算法。

引言

“電腦鼠”是一個(gè)具備自主運(yùn)動(dòng)能力的微型機(jī)器人，它能夠在特定的迷宮中行進(jìn)和搜索，由起點(diǎn)出發(fā)，自行搜索到迷宮的終點(diǎn)，并利用搜索過程中記錄的迷宮墻壁資料尋找出由迷宮起點(diǎn)到達(dá)終點(diǎn)的最短路徑，然后根據(jù)最短路徑規(guī)劃出最快的運(yùn)動(dòng)方式和路徑，并以最快的速度完成由迷宮起點(diǎn)到終點(diǎn)的沖刺。

要在指定的復(fù)雜迷宮中比賽，就像是一個(gè)人置身于未知的環(huán)境中，必須靠自身的判斷力、敏捷的動(dòng)作和正確精準(zhǔn)地探查周遭環(huán)境贏得最終比賽的勝利?！半娔X鼠”必須具備三項(xiàng)基本功能：

（1）穩(wěn)定及快速的行走能力；

（2）正確的預(yù)判能力；

（3）路徑記憶功能；

隨著人工智能的發(fā)展和新興智能算法的突破，迷宮算法革新對(duì)迷宮求解來說相當(dāng)重要，迷宮算法從非圖論（NGT）發(fā)展到圖論（GT）[2]，從簡(jiǎn)單的左右手法則、中左、中右法則發(fā)展到洪水填充法則、深度優(yōu)先探索法則（DFS），且隨著機(jī)器人多路徑規(guī)劃的不斷深入探索，A■和D■等啟發(fā)式算法也開始運(yùn)用其中，甚至新興智能算法如蟻群算法、遺傳算法、粒子群算法應(yīng)運(yùn)而生。以上算法都存在著隨機(jī)性，運(yùn)算結(jié)果也不一定是最優(yōu)解且搜索效率低。很多情況下需要遍歷整個(gè)迷宮才能夠找到終點(diǎn)，針對(duì)以上算法所存在的問題，本文提出一種經(jīng)過改善和優(yōu)化后的融合算法——向洪算法，此算法建立在向心算法和洪水算法的基礎(chǔ)上，對(duì)墻壁信息進(jìn)一步拓展，減少了搜索過程中的盲目性，有效地判別無效路徑。向洪算法結(jié)合了向心法則和洪水算法的各自優(yōu)勢(shì)，既克服了洪水算法頻繁制作等高圖問題，又提高了向心算法對(duì)終點(diǎn)的指向性，此算法減輕了CPU頻繁制作等高圖帶來的數(shù)據(jù)處理負(fù)擔(dān)，同時(shí)減少不必要的路徑搜索，為電腦鼠競(jìng)賽的勝利爭(zhēng)取時(shí)間。

1.電腦鼠走迷宮的理論基礎(chǔ)與迷宮建模

1.1電腦鼠走迷宮的理論基礎(chǔ)

“電腦鼠”走迷宮競(jìng)賽的任務(wù)是電腦鼠在千變?nèi)f化的未知迷宮中從迷宮起點(diǎn)自主探索到迷宮終點(diǎn)的最佳路徑，用時(shí)最短者優(yōu)勝。比賽成績(jī)計(jì)算如式（1）所示。

式中，T為第一次從起點(diǎn)出發(fā)到第N次到終點(diǎn)所用的總時(shí)間；T為第N次的運(yùn)行時(shí)間，電腦鼠每一次從迷宮起點(diǎn)運(yùn)行到迷宮終點(diǎn)所用的時(shí)間，稱為一次運(yùn)行時(shí)間。T為獎(jiǎng)勵(lì)時(shí)間（一般為負(fù)數(shù)），T為懲罰時(shí)間，二者由比賽規(guī)則確定[1]；T為排障時(shí)間，在每次運(yùn)行結(jié)束后都會(huì)獲得一個(gè)數(shù)值，最終成績(jī)?yōu)閿?shù)值最小的T。

由式（1）可知，“電腦鼠”走迷宮競(jìng)賽的最終成績(jī)由運(yùn)行速度﹑迷宮求解效率和穩(wěn)定性三個(gè)方面確定。搜索階段獲取的迷宮信息量越充分，進(jìn)行路徑的預(yù)判越精準(zhǔn)，選取的路徑越有效，對(duì)沖刺階段最優(yōu)路徑的選擇就越有利，前提是電腦鼠足夠穩(wěn)定。因此迷宮搜索算法的設(shè)計(jì)和優(yōu)化目標(biāo)是使電腦鼠穩(wěn)定的在短時(shí)間內(nèi)探尋到盡可能全面的迷宮墻壁資料，利用搜索的迷宮信息做出準(zhǔn)確的決策分析和最優(yōu)路徑判斷。向洪法則就是針對(duì)以上目標(biāo)的一種迷宮搜索優(yōu)化和實(shí)現(xiàn)算法。

1.2迷宮環(huán)境建模及方向表示

標(biāo)準(zhǔn)電腦鼠比賽迷宮是由16×16格的迷宮墻壁組成，采用16×16的二維數(shù)組對(duì)迷宮格進(jìn)行編號(hào)記錄。數(shù)組的下標(biāo)代表迷宮格位置，數(shù)組的元素代表該迷宮格的墻壁信息。若定義數(shù)組GucMapBlock[MAZETYPE][MAZETYPE]（MAZETYPE=16表示全迷宮），則每一格位置及信息由GucMapBlock[x][y]確定，第一個(gè)下標(biāo)代表X軸坐標(biāo)，第二個(gè)代表Y軸坐標(biāo)。

根據(jù)坐標(biāo)表示及競(jìng)賽規(guī)則看，每個(gè)單元的迷宮起點(diǎn)可以是迷宮的左下角或者右下角，即（0，0）或者（15，0）。電腦鼠開始搜索時(shí)，電腦鼠會(huì)將起點(diǎn)坐標(biāo)設(shè)為（0，0），電腦鼠通過第一個(gè)轉(zhuǎn)彎口方向判斷未知起點(diǎn)位置。若第一個(gè)轉(zhuǎn)彎口為右轉(zhuǎn)，則起點(diǎn)坐標(biāo)為（0，0）點(diǎn)，否則將起點(diǎn)標(biāo)定為（15，0）。若起點(diǎn)坐標(biāo)為后者，則需要進(jìn)行迷宮坐標(biāo)和墻壁資料的轉(zhuǎn)換，將搜索過的迷宮信息的X坐標(biāo)值加上15，并將墻壁資料賦給轉(zhuǎn)換后的坐標(biāo)。

電腦鼠在迷宮中的運(yùn)動(dòng)是以每格為單位，到達(dá)下一格后需要對(duì)坐標(biāo)進(jìn)行更新和墻壁資料的采集，為了方便記錄電腦鼠當(dāng)前位置和坐標(biāo)的更新，需要進(jìn)行絕對(duì)方向和相對(duì)方向的判定和轉(zhuǎn)換。相對(duì)方向是以電腦鼠當(dāng)前行進(jìn)的方向?yàn)閰⒄盏姆较?，將相?duì)于電腦鼠的前、右、后、左的方向定義0、1、2、3；絕對(duì)方向是以迷宮絕對(duì)坐標(biāo)平面為參照的方向，將相對(duì)于迷宮的上、右、下、左的方向定義0、1、2、3；以絕對(duì)方向定義迷宮的墻壁資料，將迷宮的4面墻壁用4個(gè)方向定義，再以數(shù)值代替其名稱，以便于程序的編寫和運(yùn)算處理。將16×16個(gè)迷宮格的墻壁資料存放于數(shù)組GucMapBlock[]中，其中低4位用于迷宮墻壁資料的保存（bit3～bit0分別代表左下右上，0為該方向有墻，1為有路），第4bit用于確定該迷宮是否搜索過。

2.向心法則與洪水算法的求解原理

2.1向心法則迷宮求解原理

此算法會(huì)把迷宮分成4個(gè)對(duì)等的部分（如圖1所示），根據(jù)前方是否存在可行走方向并結(jié)合傳統(tǒng)的左手法則、中左法則、右手法則和中右法則使搜索的目標(biāo)始終指向中心點(diǎn)，根據(jù)分區(qū)轉(zhuǎn)換法則（如圖2所示）選擇路徑進(jìn)行搜索。電腦鼠在此算法的引導(dǎo)下優(yōu)先選擇了更靠近中心的點(diǎn)進(jìn)行搜索，可以使搜索更加偏向迷宮的中心點(diǎn)，提高了搜索效率，但是并未考慮接下來搜索的迷宮格及其附近迷宮格的墻壁情況，可以說向心算法只是機(jī)械地選取更“靠近”中心的格子。

圖3所示即為向心法則的迷宮搜索路徑示意圖，電腦鼠目標(biāo)指向非常明確，向心法則在這個(gè)地圖上的搜索效率十分高效，但是在進(jìn)入圖中標(biāo)注的“死胡同”后，判定當(dāng)前電腦鼠所在迷宮右下角區(qū)域，當(dāng)前行進(jìn)方向?yàn)槊詫m絕對(duì)方向的上方，此時(shí)采用中左法則進(jìn)行路徑搜索，根據(jù)圖中標(biāo)注的路徑可知電腦鼠錯(cuò)失到達(dá)終點(diǎn)的機(jī)會(huì)，又進(jìn)行左上角未知迷宮的探尋，增加迷宮時(shí)間，對(duì)優(yōu)先取得一次最好成績(jī)產(chǎn)生影響，所以向心法則需要優(yōu)化，它在特殊路徑?jīng)Q策上還存在改進(jìn)方面。

2.2洪水算法迷宮求解原理

以8×8的迷宮舉例說明洪水算法的基本思想，先進(jìn)行迷宮墻壁的初始化，認(rèn)定四面迷宮邊界有墻，其余迷宮單元格都沒有墻，如圖5所示圖中標(biāo)注的數(shù)值為在迷宮無墻壁時(shí)各個(gè)單元格到終點(diǎn)的等高值即步數(shù)值，電腦鼠在迷宮中搜尋路徑時(shí)朝著等高值小的迷宮格行進(jìn)，若發(fā)現(xiàn)墻壁資料與之前設(shè)置有所不同時(shí)，如遇到岔路口、“死胡同”（當(dāng)前單元格無可前行方向）和前方單元格等高值比當(dāng)前單元格高時(shí)會(huì)更新并記錄墻壁資料，等高圖也會(huì)重新制作，依次規(guī)劃各個(gè)單元格可能存在及可到達(dá)迷宮終點(diǎn)的等高值，整個(gè)過程都在反復(fù)制作等高圖和更新等高值，根據(jù)等高值探索路線直至終點(diǎn)。

純洪水算法相較其他搜索算法相比，不會(huì)再機(jī)械性地向終點(diǎn)邁進(jìn)，而是在搜索過程中邊搜索邊進(jìn)行推演和步數(shù)計(jì)算，圖6為在洪水算法下規(guī)劃出的等高值和最短路徑，可以看出洪水算法在迷宮中的搜索效率較高。

洪水算法雖然在迷宮搜索過程中效率較高，但比賽前迷宮地圖都是未知的，若遇到較復(fù)雜的地形，在探索過程中則會(huì)經(jīng)常性地制作等高圖和更新等高值，這期間處理的數(shù)據(jù)量較大，然而頻繁地制作等高圖勢(shì)必會(huì)占用CPU處理和計(jì)算數(shù)據(jù)的時(shí)間。電腦鼠在運(yùn)行過程中需要存儲(chǔ)的信息量較大，處理的數(shù)據(jù)量較多，對(duì)電腦鼠控制精度要求較高，這些都需要控制系統(tǒng)保證高實(shí)時(shí)性，所以控制器的性能對(duì)能否高效地完成算法設(shè)計(jì)起到至關(guān)重要的作用，而在實(shí)際算法設(shè)計(jì)時(shí)發(fā)現(xiàn)電腦鼠往往會(huì)因?yàn)樽鴺?biāo)存儲(chǔ)及轉(zhuǎn)換，墻壁資料保存等多信息的處理及高頻率的制作等高圖而出現(xiàn)控制器處理能力不足，因此路徑搜索出錯(cuò)，發(fā)生撞墻現(xiàn)象就在所難免。

3.向洪算法的基本思想與實(shí)現(xiàn)過程

3.1向洪算法的基本思想

向洪算法是向心法則和洪水算法的融合算法，此算法有以下幾點(diǎn)優(yōu)勢(shì)：首先，此算法不再使已知的迷宮墻壁資料受到局限，擴(kuò)展并充分利用已知墻壁信息剔除無效路徑。其次，電腦鼠利用此算法進(jìn)行搜索時(shí)，遇到分支路口將使用向心法則進(jìn)行路徑探索，直至電腦鼠進(jìn)入“死胡同”后將之前選擇的路徑進(jìn)行預(yù)推演，預(yù)推演的過程包括路徑選擇，等高圖的制作和等高值的更新，在完成推演后會(huì)判定是否可到達(dá)終點(diǎn)，若能到達(dá)，轉(zhuǎn)換搜索法則繼續(xù)行進(jìn)，若不能到達(dá)，則將此支路及通過此支路的路徑標(biāo)記為死路，下次搜索回到附近處直接避開此支路。如圖7所示為向洪算法的搜索路徑示意圖，為了展示向洪算法的優(yōu)勢(shì)，采用與圖3所示相同的地圖進(jìn)行實(shí)驗(yàn)，我們會(huì)直觀地發(fā)現(xiàn)電腦鼠前期一直采用向心法則進(jìn)行搜索，直至到達(dá)圖中標(biāo)注的“死胡同”時(shí)進(jìn)行路徑信息的更新和預(yù)推演，填入新的等高值后直接沿等高值小的方向成功搜索到終點(diǎn)，解決圖3所示存在的問題。改進(jìn)后的算法不僅提高向心法則對(duì)終點(diǎn)的指向性，而且克服洪水算法頻繁地制作等高圖，對(duì)搜索路徑進(jìn)行優(yōu)化，篩除無效路徑，明確搜索范圍，使電腦鼠在搜索過程中保有快速性的前提下作出更精準(zhǔn)的路徑判斷。

3.2向洪算法的求解步驟

步驟1：定義三個(gè)16×16的二維數(shù)組GucMapBlock[x][y]，GucMapBlock0[x][y]，GucMapBlock1[x][y]，GucMapBlock[x][y]是在向心法則的路徑搜索下儲(chǔ)存的墻壁資料，GucMapBlock1[x][y]是在洪水算法的路徑搜索下儲(chǔ)存的墻壁資料，GucMapBlock0[x][y]儲(chǔ)存的是已探尋過的墻壁信息和進(jìn)行預(yù)推演的墻壁資料（bit3～bit0分別代表左下右上，0表示此方向無路，1為有路，第4bit用于確定該迷宮是否搜索過）；

步驟2：首先進(jìn)行數(shù)組的初始化，GucMapBlock[x][y]的全部元素值填0，墻壁資料初始化使GucMapBlock1[x][y]中利用循環(huán)迭代使x=0時(shí)的所有元素的bit2值為0（此時(shí)對(duì)應(yīng)迷宮絕對(duì)方向的下邊界），同理可得x=15的所有元素的bit0值為0（對(duì)應(yīng)迷宮上邊界），y=0的所有元素的bit3值為0（對(duì)應(yīng)迷宮左邊界），y=15的所有元素的bit1值為0（對(duì)應(yīng)迷宮右邊界），這表示只有迷宮四周邊界處有墻，其余地方無墻，靠后期搜索及推演的過程進(jìn)行隔墻添加。GucMouseTask表示電腦鼠的狀態(tài)處理，GucMouseTask=START開始進(jìn)行搜索過程，此時(shí)可根據(jù)第一個(gè)轉(zhuǎn)彎口方向判定起始點(diǎn)坐標(biāo)來決定是否進(jìn)行坐標(biāo)轉(zhuǎn)換，先利用洪水算法對(duì)迷宮單元格進(jìn)行等高值的填寫，再根據(jù)等高值的由大到小進(jìn)行路徑探索，遇到支路口時(shí)，程序會(huì)先行統(tǒng)計(jì)可前進(jìn)的支路數(shù)，若可前行支路數(shù)大于0，則利用向心法則進(jìn)行搜索直至進(jìn)入“死胡同”后進(jìn)行等高圖的制作和路徑推演；

步驟3：電腦鼠在搜索時(shí)利用已知迷宮單元格的墻壁信息可推斷出其余相鄰迷宮單元格的信息，兩個(gè)數(shù)組在進(jìn)行等高圖制作時(shí)會(huì)同步更新內(nèi)容，GucMapBlock1[x][y]保存實(shí)際探尋過的迷宮墻壁資料，GucMapBlock0[x][y]保存實(shí)際迷宮信息及推演后的墻壁資料，當(dāng)電腦鼠已探尋出GucMapBlock1[x][y]的bit1為0（表示當(dāng)前單元格坐標(biāo)（x，y）右方有墻壁，無可前進(jìn)方向），可通過推演法推斷GucMapBlock0[x-1][y]的bit3為0（表示當(dāng)前單元格坐標(biāo)（x-1，y）左方有墻壁，無可前進(jìn)方向），以此類推可知已知地圖信息的單元格四個(gè)方向的各個(gè)坐標(biāo)處的墻壁信息。當(dāng)再次探尋到支路口時(shí)又將轉(zhuǎn)換成向心法則進(jìn)行路徑搜尋，如此循環(huán)上述過程，直至當(dāng)前目標(biāo)點(diǎn)為終點(diǎn)結(jié)束操作；

下圖8所示為本論文所提的向洪融合算法軟件流程圖。此向洪融合算法不僅解決了向心法則對(duì)特殊路徑的搜尋問題，減少了沒有必要的路徑搜索，而且大大減輕了CPU的運(yùn)算負(fù)擔(dān)，大幅度提高了指令的執(zhí)行效率。本實(shí)驗(yàn)室成員已參加了四屆天津市電腦鼠競(jìng)賽及全國性電腦鼠比賽，從整體效果說，本融合算法對(duì)迷宮的適應(yīng)性廣，對(duì)策略的嵌入性好，相較其他算法來說較為高效，適合進(jìn)行推廣應(yīng)用。

4.向洪算法實(shí)驗(yàn)測(cè)試

4.1測(cè)試平臺(tái)簡(jiǎn)介

為了檢驗(yàn)文中所提算法的合理性及有效性，需要搭載一個(gè)硬件平臺(tái)方便算法的驗(yàn)證和測(cè)試。本文實(shí)驗(yàn)所用的電腦鼠硬件是實(shí)驗(yàn)室開發(fā)的第三代MicroMouse3，其微處理器是意法公司生產(chǎn)的基于Cortex-M3內(nèi)核的ARM處理器—STM32F103。采用IEEE國際標(biāo)準(zhǔn)電腦鼠走迷宮競(jìng)賽迷宮作為測(cè)試迷宮。

4.2算法測(cè)試過程及結(jié)果

為了便于算法的測(cè)試和實(shí)驗(yàn)結(jié)果的對(duì)比，我們隨機(jī)選取5幅往年天津市電腦鼠競(jìng)賽的迷宮圖進(jìn)行測(cè)試，同時(shí)為了使算法得到充分的驗(yàn)證，選取相同的迷宮環(huán)境、相同的硬件架構(gòu)和同一運(yùn)行策略進(jìn)行實(shí)驗(yàn)，有且僅在迷宮算法上有所不同。

相同的迷宮環(huán)境：是指排除迷宮板，迷宮地面的縫隙及外界燈光環(huán)境對(duì)電腦鼠的影響；

相同的硬件架構(gòu)：是指所用的電腦鼠采用相同的底層驅(qū)動(dòng)，速度參數(shù)和紅外閾值設(shè)定；

同一運(yùn)行策略：是指起點(diǎn)到終點(diǎn)的搜索→原路徑返回起點(diǎn)→起點(diǎn)到終點(diǎn)的沖刺→終點(diǎn)到起點(diǎn)的迷宮二次搜索→第二次沖刺→第三次沖刺；

結(jié)果分析：算法測(cè)試結(jié)果如上表所示，每幅迷宮圖我們進(jìn)行了5次測(cè)試，然后將搜索時(shí)間、排障時(shí)間進(jìn)行均值計(jì)算后記錄比對(duì)，只要按照預(yù)設(shè)的策略完整地運(yùn)行下來即算成功一次，計(jì)算成功率并記錄。從上表可知，向洪算法的搜索時(shí)間和排障時(shí)間相對(duì)向心法則都有不同幅度的減少，比起洪水法則最好成績(jī)相近。在第2幅和第4幅的迷宮測(cè)試過程中，我們發(fā)現(xiàn)向洪融合算法的成功率比洪水算法成功率高，原因在于在迷宮二次回程中向洪算法信息處理得較合理，使電腦鼠在快速運(yùn)行時(shí)保證高穩(wěn)定性。綜合評(píng)價(jià)向洪算法的高效性更便于電腦鼠的穩(wěn)定運(yùn)行。

結(jié)語

本文針對(duì)傳統(tǒng)迷宮搜索算法低效和處理器的局限性問題研究和實(shí)現(xiàn)了基于向心法則和洪水算法的電腦鼠走迷宮的向洪融合算法，并結(jié)合實(shí)驗(yàn)測(cè)試了優(yōu)化后的算法，提出了一些能提高比賽效率的策略。通過與現(xiàn)有的常用算法比較后發(fā)現(xiàn)，本文所提算法在搜索步數(shù)、轉(zhuǎn)彎次數(shù)及成功率方面具有一定優(yōu)勢(shì)。實(shí)驗(yàn)測(cè)試結(jié)果表明，改進(jìn)后的搜索向洪融合算法在保證原有兩種算法高效的前提下，能更好地處理一些特殊迷宮信息，總體提高算法效率和實(shí)用價(jià)值。

參考文獻(xiàn)：

[1]王鳳林，王宜懷.一種電腦鼠走迷宮算法的設(shè)計(jì)與實(shí)現(xiàn).計(jì)算機(jī)應(yīng)用與軟件，2010，27（12）：270-273.

[2]王磊.基于IEEE電腦鼠走迷宮競(jìng)賽的迷宮算法分析與實(shí)現(xiàn).山東大學(xué)，2013.

[3]Jong-Kwon Lee，Sang Kim，IEEE.Student Activities Conference-Micromouse Competition Rules[J/OL]. IEEE，2007.http：//www.ieee.uc.edu/main/files/sac2007/mm_rules.pdf.

[4]王斌，張衛(wèi)鋼.基于IEEE標(biāo)準(zhǔn)的電腦鼠走迷宮的智能算法研究[J].電子設(shè)計(jì)工程，2011，19（12）：42-45.

[5]賀少波，孫克輝.基于向心法則的電腦鼠走迷宮算法設(shè)計(jì)與優(yōu)化.計(jì)算機(jī)系統(tǒng)應(yīng)用，2012，21（9）.

[6]Manoj Sharma， Kaizen Robeonics Algorithms for Micro-mouse. International Conference on future Computer and Communication， 2009，（38）：581-585.

[7]蔣雄，任化龍，馬忠麗.基于ARM的電腦鼠走迷宮研究.現(xiàn)代電子技術(shù)，2011，34（8）.

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

[9]徐守江.迷宮算法綜述[J].信息與電腦：理論版，2009，10（9）.