一種新穎的電腦鼠走迷宮算法研究

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

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

引言

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

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

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

（2）正確的預判能力；

（3）路徑記憶功能；

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

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

1.1電腦鼠走迷宮的理論基礎

“電腦鼠”走迷宮競賽的任務是電腦鼠在千變萬化的未知迷宮中從迷宮起點自主探索到迷宮終點的最佳路徑，用時最短者優(yōu)勝。比賽成績計算如式（1）所示。

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

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

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

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

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

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

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

2.1向心法則迷宮求解原理

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

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

2.2洪水算法迷宮求解原理

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

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

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

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

3.1向洪算法的基本思想

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

3.2向洪算法的求解步驟

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

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

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

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

4.向洪算法實驗測試

4.1測試平臺簡介

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

4.2算法測試過程及結果

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

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

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

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

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

結語

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

參考文獻：

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

[2]王磊.基于IEEE電腦鼠走迷宮競賽的迷宮算法分析與實現(xiàn).山東大學，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標準的電腦鼠走迷宮的智能算法研究[J].電子設計工程，2011，19（12）：42-45.

[5]賀少波，孫克輝.基于向心法則的電腦鼠走迷宮算法設計與優(yōu)化.計算機系統(tǒ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)代電子技術，2011，34（8）.

[8]林國恩.電腦鼠設計與制作[D].桃園：臺灣龍華科技大學，2010.

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