計(jì)算機(jī)迷宮搜索算法仿真研究①

鄧 輝，詹 杰，何家偉，李先春

(湖南科技大學(xué)物理與電子科學(xué)學(xué)院，湖南湘潭411201)

電腦鼠［1］(Micromouse)是一個(gè)由微控制器、探測(cè)器、驅(qū)動(dòng)電機(jī)組成的一種集感知、判斷、行走功能于一體，能夠在迷宮中自動(dòng)尋找到達(dá)終點(diǎn)最佳路徑的微型機(jī)器人。電腦鼠走迷宮比賽集競(jìng)賽和趣味性于一體，吸引了大量青年科技人員參加，文獻(xiàn)［1］給出了有關(guān)迷宮電腦鼠的比賽規(guī)則和要求。

在迷宮電腦鼠的設(shè)計(jì)中，迷宮搜索算法的設(shè)計(jì)和調(diào)試最困難［3－7］。主要因?yàn)槊詫m搜索算法的設(shè)計(jì)和調(diào)試過(guò)程容易受到周圍環(huán)境以及電腦鼠底層軟硬件的影響而出現(xiàn)運(yùn)行錯(cuò)誤，從而使得調(diào)試經(jīng)常被打斷，完成一次完整的調(diào)試非常麻煩［8］，需耗費(fèi)大量時(shí)間。本文針對(duì)電腦鼠設(shè)計(jì)者在迷宮搜索算法設(shè)計(jì)和調(diào)試上所面臨的問(wèn)題，設(shè)計(jì)了迷宮搜索算法仿真程序，提高迷宮搜索算法設(shè)計(jì)和調(diào)試的效率，減輕設(shè)計(jì)者的負(fù)擔(dān)。該算法仿真程序及其實(shí)現(xiàn)思路不僅可以推廣到電腦鼠走迷宮競(jìng)賽中，而且還可以作為電腦鼠迷宮搜索算法研究者的一個(gè)理想研究平臺(tái)。

1 仿真模塊設(shè)計(jì)

迷宮搜索算法仿真程序的主要功能模塊包含動(dòng)態(tài)仿真器、迷宮搜索算法接口、人機(jī)交互界面和迷宮地圖編輯器。動(dòng)態(tài)仿真器是整個(gè)程序的核心，迷宮搜索算法接口用于連接動(dòng)態(tài)仿真器和迷宮搜索算法，人機(jī)交互界面和迷宮地圖編輯器，分別負(fù)責(zé)響應(yīng)用戶的鼠標(biāo)動(dòng)作和迷宮地圖的設(shè)置。地圖編輯器需要接受用戶的動(dòng)作來(lái)完成地圖的編輯工作，所以將迷宮地圖編輯器作為人機(jī)交互界面的一個(gè)子功能來(lái)實(shí)現(xiàn)。圖1是迷宮搜索算法仿真程序的系統(tǒng)模塊框圖。

圖1 迷宮搜索算法仿真程序的總框圖

動(dòng)態(tài)仿真器實(shí)現(xiàn)了三個(gè)功能，為迷宮搜索算法獲取迷宮信息，根據(jù)迷宮搜索算法的指令控制模擬電腦鼠運(yùn)動(dòng)，顯示運(yùn)行中產(chǎn)生的過(guò)程數(shù)據(jù)。迷宮搜索算法接口定義了該算法的函數(shù)格式及通信協(xié)議。人機(jī)交互界面是人機(jī)交互平臺(tái)，內(nèi)部實(shí)現(xiàn)了與用戶交互的按鈕控件和控制程序工作狀態(tài)的狀態(tài)機(jī)，按鈕控件獲取用戶的鼠標(biāo)事件，并將其作為狀態(tài)機(jī)的輸入信號(hào)，狀態(tài)機(jī)用于控制迷宮搜索算法仿真程序工作狀態(tài)的轉(zhuǎn)移。迷宮地圖編輯器用于編輯二維迷宮地圖，完成地圖設(shè)置后，將該地圖以圖片形式保存。這里采用多線程設(shè)計(jì)方法，將動(dòng)態(tài)仿真器和人機(jī)交互界面分別設(shè)計(jì)于兩個(gè)不同的線程中。

2 迷宮搜索算法仿真程序的設(shè)計(jì)

2.1 人機(jī)交互界面的設(shè)計(jì)

圖2為迷宮搜索算法仿真程序的界面。迷宮地圖根據(jù)IEEE標(biāo)準(zhǔn)迷宮場(chǎng)地的大小進(jìn)行等比例的縮小。迷宮地圖中每個(gè)像素代表0.4 cm，和實(shí)際迷宮相比，邊長(zhǎng)等效為723個(gè)像素，迷宮單元的柵欄長(zhǎng)度、厚度分別為45個(gè)像素和3個(gè)像素。整個(gè)顯示界面分為三部分，左方正方形部分顯示迷宮地圖，右方上半部分顯示按鈕控件，右方下半部分顯示運(yùn)行信息。按鈕控件有6個(gè)，分別是載入地圖按鈕、設(shè)置地圖按鈕、保存地圖按鈕、迷宮算法按鈕、設(shè)置起點(diǎn)按鈕和開(kāi)始仿真按鈕。

2.2 用戶事件檢測(cè)與狀態(tài)轉(zhuǎn)移

用戶在人機(jī)交互界面的動(dòng)作信息通過(guò)鼠標(biāo)事件獲取函數(shù)GetMouseMsg()進(jìn)行檢測(cè)，通過(guò)事件檢測(cè)函數(shù)User-EventDetect()獲取;用戶事件檢測(cè)函數(shù)所返回的數(shù)據(jù)作為參數(shù)傳遞給狀態(tài)機(jī)，由狀態(tài)機(jī)控制相應(yīng)的動(dòng)作和效果。

圖2 迷宮搜索算法仿真程序的界面

圖3 用戶事件檢測(cè)函數(shù)的流程圖

人機(jī)交互界面定義了7個(gè)工作狀態(tài)，分別為初始狀態(tài)、地圖編輯狀態(tài)、地圖保存狀態(tài)、地圖載入狀態(tài)、算法載入狀態(tài)、起點(diǎn)設(shè)置狀態(tài)，這7種狀態(tài)反映了狀態(tài)機(jī)在用戶事件驅(qū)動(dòng)下的狀態(tài)跳轉(zhuǎn)。

2.3 動(dòng)態(tài)仿真器的設(shè)計(jì)

2.3.1 電腦鼠屬性定義

動(dòng)態(tài)仿真器首先定義了電腦鼠的絕對(duì)方向和相對(duì)方向，絕對(duì)方向以迷宮地圖為參照系，相對(duì)方向以電腦鼠自身作為參考的方向，如前后左右。為電腦鼠創(chuàng)建了一個(gè)結(jié)構(gòu)體MICROMOUSE.mouse用于存儲(chǔ)電腦鼠的相關(guān)信息，其原型如下:

結(jié)構(gòu)體中，dir用于存儲(chǔ)電腦鼠的絕對(duì)方向，x和y用于電腦鼠的當(dāng)前坐標(biāo)、start_x和start_y用于存儲(chǔ)電腦鼠的起點(diǎn)坐標(biāo)，而state用于存儲(chǔ)電腦鼠的當(dāng)前狀態(tài)。

2.3.2 電腦鼠的運(yùn)動(dòng)控制

電腦鼠的基本動(dòng)作分為直行、右轉(zhuǎn)、左轉(zhuǎn)、原地后轉(zhuǎn)和停止，動(dòng)態(tài)仿真器收到動(dòng)作指令后，首先根據(jù)動(dòng)作指令action更新電腦鼠的絕對(duì)方向mouse.dir，然后根據(jù)新的絕對(duì)方向調(diào)取相應(yīng)的圖像，用于動(dòng)畫繪制。當(dāng)執(zhí)行動(dòng)畫動(dòng)作時(shí)，仿真器會(huì)根據(jù)電腦鼠的絕對(duì)方向?qū)﹄娔X鼠的坐標(biāo)進(jìn)行更新。

為了使仿真程序更具一般性，將模擬電腦鼠的移動(dòng)速度設(shè)置為可調(diào)，兩個(gè)控制參數(shù)分別是flame和delay_time。flame代表模擬電腦鼠每次移動(dòng)的像素個(gè)數(shù)，delay_time為每次移動(dòng)后需要延時(shí)等待的時(shí)間(等待指令)。默認(rèn)為每移動(dòng)一個(gè)基本單元所用的時(shí)間為450 ms。delay_time的值為0到2 000 ms之間的任意整數(shù)值。

2.3.3 迷宮信息的獲取

迷宮柵欄信息的獲取根據(jù)電腦鼠當(dāng)前所在迷宮單元的坐標(biāo)mouse.x和mouse.y完成。絕對(duì)方向的信息分別對(duì)應(yīng)變量的 bit3、bit2、bit1和bit0中，對(duì)應(yīng)關(guān)系如表1所示。相對(duì)方向的對(duì)應(yīng)關(guān)系如表2所示。絕對(duì)方向的柵欄信息反應(yīng)迷宮地圖信息，相對(duì)方向的柵欄信息反映電腦鼠可能運(yùn)動(dòng)的方向。

表1 絕對(duì)方向下的柵欄信息存儲(chǔ)格式

表2 柵欄信息的存儲(chǔ)格式

2.3.4 仿真數(shù)據(jù)統(tǒng)計(jì)

動(dòng)態(tài)仿真器的仿真過(guò)程產(chǎn)生兩種數(shù)據(jù)，分別是模擬電腦鼠運(yùn)動(dòng)的軌跡圖和行走步數(shù)統(tǒng)計(jì)數(shù)據(jù)。在仿真過(guò)程中，動(dòng)態(tài)仿真器會(huì)一直記錄電腦鼠的坐標(biāo)，當(dāng)發(fā)現(xiàn)電腦鼠從迷宮起點(diǎn)到達(dá)了迷宮終點(diǎn)或者從迷宮終點(diǎn)到達(dá)了迷宮起點(diǎn)，則使用圖像輸出函數(shù)putimage()將模擬電腦鼠的行走軌跡繪制出來(lái)，如圖4所示。繪制模擬電腦鼠的行走軌跡之后，動(dòng)態(tài)仿真器使用圖像獲取函數(shù)getimage()對(duì)電腦鼠的行走軌跡進(jìn)行截取，截取后的軌跡圖像保存在程序當(dāng)前目錄下的Result文件夾中。

圖4 模擬電腦鼠的軌跡圖

圖5 步數(shù)統(tǒng)計(jì)

3 算法測(cè)試

為了驗(yàn)證迷宮搜索算法仿真程序的方案是否可行以及該方案是否能夠減少迷宮搜索算法設(shè)計(jì)和調(diào)試的時(shí)間，本文對(duì)迷宮搜索算法仿真程序進(jìn)行了一系列的測(cè)試。本測(cè)試基于兩套迷宮搜索算法和3個(gè)難度各異的迷宮地圖開(kāi)展，最短路徑生成采用洪水填充算法，測(cè)試的內(nèi)容包括迷宮搜索算法的仿真情況以及仿真所用時(shí)間。測(cè)試結(jié)束后，通過(guò)分析對(duì)比迷宮搜索算法的仿真情況以及仿真所用時(shí)間，判斷是否達(dá)到設(shè)計(jì)目的。

為了便于對(duì)比測(cè)試結(jié)果，對(duì)實(shí)際電腦鼠的運(yùn)行速度和模擬電腦鼠的運(yùn)行速度作統(tǒng)一的假設(shè)。假設(shè)在實(shí)際環(huán)境中，電腦鼠每個(gè)基本動(dòng)作用時(shí)為0.36 s(由電腦鼠0.5 m/s的運(yùn)動(dòng)速度計(jì)算而來(lái)，0.5米/秒的運(yùn)動(dòng)速度參考了比賽中電腦鼠的常用速度)。同時(shí)也假設(shè)在模擬環(huán)境中，模擬電腦鼠的基本動(dòng)作用時(shí)為0.03 s(由模擬電腦鼠在模擬迷宮中1.5像素/ms的速度計(jì)算而來(lái))。

3.1 迷宮地圖的選擇

為使測(cè)試結(jié)果具有普遍的參考意義，本次測(cè)試使用的迷宮地圖為國(guó)內(nèi)外比賽中出現(xiàn)過(guò)的3個(gè)迷宮地圖。如圖6所示，其中圖6(a)為2009年中國(guó)電腦鼠走迷宮競(jìng)賽的迷宮地圖。圖6(b)為2012年湖南省電腦鼠走迷宮競(jìng)賽的迷宮地圖。圖6(c)為2011年日本電腦鼠走迷宮競(jìng)賽的迷宮地圖。

圖6 測(cè)試所選用的迷宮地圖

3.2 測(cè)試結(jié)果

3.2.1 左手法則迷宮搜索算法的測(cè)試結(jié)果

圖7、圖8和圖9分別是模擬電腦鼠在左手法則迷宮搜索算法的控制下，分別在三個(gè)迷宮地圖中生成的軌跡圖。

圖7 左手法則在迷宮地圖一中的運(yùn)行軌跡圖

圖8 左手法則在迷宮地圖二中的運(yùn)行軌跡圖

圖9 左手法則在迷宮地圖三中的運(yùn)行軌跡圖

除了軌跡圖之外，左手法則迷宮搜索算法的仿真結(jié)果還包括模擬電腦鼠在三個(gè)迷宮地圖中仿真時(shí)的步數(shù)統(tǒng)計(jì)數(shù)據(jù)。如圖10所示，圖10a)、b)、c)是左手法則迷宮搜索算法分別在迷宮地圖一、二、三中的仿真步數(shù)統(tǒng)計(jì)數(shù)據(jù)。

圖10 左手法則分別在三個(gè)迷宮地圖中運(yùn)行的統(tǒng)計(jì)數(shù)據(jù)

3.2.2 右手法則迷宮搜索算法的測(cè)試結(jié)果

圖11、圖12和圖13分別為模擬電腦鼠在右手法則迷宮搜索算法的控制下，在三個(gè)迷宮地圖中運(yùn)行生成的軌跡圖。圖11，圖12、圖13中，圖a)為模擬電腦鼠第一次搜索時(shí)的軌跡圖，圖b)為模擬電腦鼠第二次搜索時(shí)的軌跡圖，圖c)為模擬電腦鼠沖刺時(shí)的軌跡圖。

圖11 右手法則在迷宮地圖一中的運(yùn)行軌跡圖

圖12 右手法則在迷宮地圖二中的運(yùn)行軌跡圖

圖13 右手法則在迷宮地圖三中的運(yùn)行軌跡圖

同樣，右手法則迷宮搜索算法的仿真結(jié)果也包含了步數(shù)統(tǒng)計(jì)數(shù)據(jù)。左手法則迷宮搜索算法的仿真統(tǒng)計(jì)數(shù)據(jù)，如圖14所示，圖a)、b)、c)是右手法則迷宮搜索算法分別在迷宮地圖一、二、三中的仿真統(tǒng)數(shù)據(jù)。

圖14 右手法則分別在三個(gè)迷宮地圖中運(yùn)行的統(tǒng)計(jì)數(shù)據(jù)

4 結(jié)論

從兩套迷宮搜索算法生成的軌跡圖中可以看出，軌跡圖和電腦鼠真實(shí)的運(yùn)動(dòng)情況沒(méi)有區(qū)別，雖然兩套迷宮搜索算法的搜索軌跡都不一樣，但最終都能成功搜索到三個(gè)迷宮的最短路徑。經(jīng)過(guò)多次的測(cè)試檢驗(yàn)，發(fā)現(xiàn)仿真程序均可穩(wěn)定工作，這說(shuō)明兩套迷宮搜索算法在仿真程序中均能正常運(yùn)行，設(shè)計(jì)的迷宮搜索算法仿真程序正確。

采用仿真的形式來(lái)研究迷宮搜索算法，可以直觀地看到整個(gè)仿真過(guò)程，還可以顯示電腦鼠的行走數(shù)據(jù)，對(duì)算法的性能分析可以起到很大的幫助。因此，本仿真程序可以廣泛推廣到電腦鼠走迷宮競(jìng)賽中使用，幫助參賽隊(duì)伍有效地提高迷宮搜索算法和電腦鼠的整體設(shè)計(jì)進(jìn)度。

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

［3］林國(guó)恩.電腦鼠的設(shè)計(jì)與實(shí)作［D］.臺(tái)灣:龍華科技大學(xué)，2010.

［4］陳 鋒.環(huán)境搜索與路徑規(guī)劃算法的研究［D］.長(zhǎng)春:吉林大學(xué)，2012.

［5］張新誼.一種電腦鼠走迷宮的算法［J］.單片機(jī)與嵌入式系統(tǒng)應(yīng)用，2007(5):84－85.

［6］萬(wàn)玉瓊，梁俊有.基于嵌入式微處理器的走迷宮機(jī)器人的設(shè)計(jì)［J］.洛陽(yáng)理工學(xué)院學(xué)報(bào)(自然科學(xué)版)，2010(4):36－39.

［7］李亞洲，嚴(yán) 石.電腦鼠軟件系統(tǒng)關(guān)鍵技術(shù)研究［J］.單片機(jī)與嵌入式系統(tǒng)應(yīng)用，2011(5):72－73.

［8］付秀偉，張 驊.基于ARM－M3的電腦鼠硬件設(shè)計(jì)［J］.吉林化工學(xué)院學(xué)報(bào)，2012(1):47 －49.