尹會明

（南京信息職業(yè)技術(shù)學(xué)院, 南京,210046）

0 引言

智能老鼠走迷宮比賽中，能否迅速準(zhǔn)確的找到迷宮的最佳路徑已成為系統(tǒng)設(shè)計的關(guān)鍵問題。對于智能老鼠走迷宮的算法，國內(nèi)外的研究者大體采用兩種算法：深度優(yōu)先搜索算法和廣度優(yōu)先搜索算法。傳統(tǒng)的深度優(yōu)先搜索算法從迷宮的入口出發(fā), 若所在當(dāng)前位置可通,則朝下一位置探索, 切換下一位置為當(dāng)前位置； 若所在當(dāng)前位置不可通, 則退回上一位置。如此重復(fù), 直至到達(dá)出口。廣度優(yōu)先搜索法又叫流水法。從迷宮的入口出發(fā), 若所在當(dāng)前位置可通,則依次探索當(dāng)前位置的鄰接位置。然后依次將這些鄰接位置設(shè)置為當(dāng)前位置, 探索他們的鄰接位置。層層推進, 直至找到迷宮出口。廣度優(yōu)先搜索與深度優(yōu)先搜索相比，深度優(yōu)先搜索在整個探索過程中,只需要一個探索點。而廣度優(yōu)先搜索比較適合在一個已知的迷宮中尋找最佳路徑。相對來說，深度優(yōu)先搜索成本較低,它適合于在一個未知的迷宮尋找一條通路，當(dāng)然不一定是最優(yōu)的。由此可見，利用深度優(yōu)先算法肯定可以以順利找到迷宮出口，但是對于有孤島的迷宮，這種算法很容易陷入死循環(huán)[1]。本研究在分析以上兩種算法的優(yōu)缺點后，同時結(jié)合本次設(shè)計的實際要求，提出了一種改進的具有記憶能力的深廣結(jié)合的迷宮探索方法，較好的解決了迷宮最佳路徑的搜索問題，能夠準(zhǔn)確有效的找到最優(yōu)路徑。

1 智能老鼠系統(tǒng)的硬件設(shè)計

為了實現(xiàn)智能老鼠在迷宮中的順利的行走，本設(shè)計的系統(tǒng)的硬件部分主要由幾個模塊組成，電源控制模塊，主要用來為整個系統(tǒng)供電；PWM模塊主要用來驅(qū)動直流步進電機；紅外感知模塊，用來檢測智能老鼠周圍是否有墻壁以及與墻壁的距離。系統(tǒng)的硬件框圖如圖1所示。

圖1 系統(tǒng)的硬件框圖

1.1 微控制器選擇

微控制器采用luminray micro 公司生產(chǎn)的32位ARM Cortex?-M3內(nèi)核的LM3S1138微控制器。具體的GPIO的功能配置如表1所示。

1.2 電機驅(qū)動模塊

電機控制系統(tǒng)主要是用來控制智能老鼠的運動,電機的選擇對機械結(jié)構(gòu)的影響明顯，它不但直接影響小車的尺寸和結(jié)構(gòu)安排，并且對小車的運動靈活性起關(guān)鍵作用，主要包括電機和電機驅(qū)動電路兩部份。電機采用的是直流反應(yīng)式步進電機，開環(huán)控制，無需測速器件，也不需要減速器，減少了機構(gòu)的復(fù)雜性。而電機驅(qū)動電路采用的是Rohm公司的生產(chǎn)的直流步進電機專用驅(qū)動芯片BA6845fs，具體的控制方法如表2所示[2-3]。

表1 GPIO的功能配置表

表2 BA6845fs電機驅(qū)動控制方式

1.3 紅外傳感電路模塊

智能老鼠的紅外傳感模塊主要負(fù)責(zé)對外部環(huán)境的監(jiān)測和處理。本系統(tǒng)中的紅外模塊主要采用了IRM-8601S 紅外線一體化接收頭和普通的紅外線發(fā)射管。為了讓智能老鼠在迷宮中能夠順暢的行走，轉(zhuǎn)彎，在傳統(tǒng)3組傳感器的布局基礎(chǔ)上進行了改進，采用了5組紅外傳感器單元，除了正前正左正右3個方向外，還在車頭前方再添加左右兩個45度斜角傳感器單元，在行進過程中對兩側(cè)墻壁進行實時探測，一旦任一斜角傳感器單元接收到反射信號，則說明智能老鼠已經(jīng)向該方向傾斜，需要及時調(diào)節(jié)步進電機使智能老鼠恢復(fù)到正確姿勢。

1.4 電源部分

電源部分包括電池組和電壓調(diào)節(jié)電路，電壓調(diào)節(jié)電路使用的是Sipex公司的sp6641A生產(chǎn)的芯片, 該芯片是一個極低靜態(tài)電流、高效率的DC-DC轉(zhuǎn)換器, 輸入電壓3.3v, 輸出電壓5v.:電源模塊主要是來為整個系統(tǒng)供電。對于移動機器人來說，其電源通常采用蓄電池，提供給功率器件和邏輯器件。對于一個機電控制系統(tǒng)來說，系統(tǒng)的抗干擾性能是非常重要的。對不同的功能部件提供相互隔離的電源是提高抗干擾性能的一個重要手段。

2 智能老鼠走迷宮的軟件設(shè)計

迷宮機器人的軟件采用模塊化設(shè)計思想，這樣軟件實現(xiàn)模塊化、標(biāo)準(zhǔn)化，易于理解和移植。電腦鼠的軟件部分主要用來判斷迷宮環(huán)境, 發(fā)送控制信息給相應(yīng)的硬件模塊, 對迷宮中的電腦鼠進行導(dǎo)航。迷宮的探索算法主要由主程序和實現(xiàn)各種功能的子程序組成, 主程序主要起到導(dǎo)向決策功能, 而智能老鼠具體的各種功能的實現(xiàn)則是通過調(diào)用子程序來實現(xiàn)的。

智能老鼠需在迷宮中完成探測道路和全速沖刺任務(wù)。智能老鼠一方面需具有探測周圍環(huán)境的能力并能完成前進、轉(zhuǎn)彎、停止等基本動作,另一方面還要能夠?qū)ふ易顑?yōu)路徑并沿著最優(yōu)路徑?jīng)_刺。迷宮搜索的算法選擇是系統(tǒng)設(shè)計中很關(guān)鍵的一部分，傳統(tǒng)的搜索迷宮算法很多，深度優(yōu)先搜索，廣度優(yōu)先搜索，以及遺傳算法都是比較經(jīng)典的算法。在不同規(guī)模的迷宮中各有自己的優(yōu)勢[4]。

本算法根據(jù)廣度優(yōu)先搜索與深度優(yōu)先搜索兩種算法的優(yōu)缺點，同時結(jié)合本次設(shè)計的實際要求，提出了一種新的改進的具有記憶能力的深廣結(jié)合的迷宮探索方法，能夠有效的找到最優(yōu)路徑。

2.1 迷宮的探測子程序

在本次設(shè)計中，由于迷宮的規(guī)模不大，探測階段的策略主要還是采用傳統(tǒng)的深度優(yōu)先的算法,即在有限的時間或探測次數(shù)下,只探測迷宮的一部分,從中找出一條可行的路徑。智能老鼠在巷道內(nèi)行走,如果最后無路可走,則該巷為“死巷”[5-7]；智能老鼠在巷道內(nèi)行走的方向最多只有3個(前、左、右) ,如果存在2 個或2 個以上的方向可以行走,稱為“交叉”。在遇有交叉時本次設(shè)計采用的是右手法則。即當(dāng)遇到障礙和交叉時，以右邊為優(yōu)先的前進方向[8]。

2.2 最優(yōu)路徑選擇階段

本文采用一種改進的深廣結(jié)合的算法來搜索最優(yōu)路徑。首先，要引入幾個概念，本算法把迷宮細(xì)分為8種狀況：死胡同，右轉(zhuǎn)彎 ，左轉(zhuǎn)彎，直丁字路口，直通道，右丁字路口，左丁字路口，十字路口。

算法思想：根據(jù)迷宮的特點, 如果存在不只一條迷宮通道, 則在通道的路徑上必然存在一個分叉口。如果先用深度優(yōu)先搜索探出一條通道, 然后再在分叉點處增加搜索的寬度, 則必然能找到最短的通道。同時，記錄下已搜索到的路徑，在下一次深度優(yōu)先搜索時候，如果碰到上次已經(jīng)走過的分叉路口時，則根據(jù)上次的轉(zhuǎn)向，決定當(dāng)前的運動，或前進，或左轉(zhuǎn)或右轉(zhuǎn)，這樣就大大的節(jié)省了計算量，即改進的具有記憶能力的深廣結(jié)合的迷宮探索法[9]。

本算法其實是在計算量和最短通路之間一個較好的折衷，實際測試結(jié)果也表明，與傳統(tǒng)的迷宮算法相比，本文所采用的最優(yōu)路徑的搜索算法更適用于探索未知的迷宮，即在本階段的深度優(yōu)先搜索階段時，遇到迷宮分叉口，就可以利用上次在探測階段的路況數(shù)據(jù)，決定智能老鼠的運動。

2.3 沖刺階段

找到了最短路徑, 智能老鼠就可以從起點開始以最快的速度沖到終點, 沖刺子程序可以實現(xiàn)該功能。

2.4 其他控制子程序

在智能老鼠的行走過程中肯定還需要調(diào)用其他的一些子程序，如老鼠行走時候需要檢測其前方以及兩側(cè)的障礙狀況的時候，就要用到紅外檢測子程序[10-11]。轉(zhuǎn)彎時候需要轉(zhuǎn)彎子程序和行走控制子程序，系統(tǒng)一些延時功能則需要延時子程序來實現(xiàn)。

3 實驗結(jié)果及分析

為了驗證本文所采用的改進的深廣結(jié)合的最佳路徑搜索算法在迷宮搜索時的有效性，選取了5種規(guī)模的迷宮：5×5,10×10,15×15,20×20,40×40[12-13].從智能老鼠的實際行走的路徑長度以及算法的指令的執(zhí)行狀況兩個方面對比了本算法和經(jīng)典的兩種算法，下面的兩張表格給出了實驗結(jié)果。表3展示了在不同規(guī)模的迷宮中采用不同的算法，智能老鼠的判斷次數(shù)和調(diào)整次數(shù)。表4給出了在不同的規(guī)模的迷宮環(huán)境下采用不同的迷宮算法時智能老鼠所走的實際路徑長度以及算法執(zhí)行的指令條數(shù)。

表3 不同迷宮智能老鼠的判斷次數(shù)和調(diào)整次數(shù)比較

表4 路徑長度和執(zhí)行指令條數(shù)的對比結(jié)果

以上的實際數(shù)據(jù)的對比結(jié)果表明，在規(guī)模較小的迷宮時候，本算法和經(jīng)典的算法差別不大，沒有太大的優(yōu)勢，但是在大型的未知迷宮探索時，本算法的優(yōu)越性就明顯的體現(xiàn)出來。智能老鼠所走的實際路徑長度是最短的，算法的實驗結(jié)果比較令人滿意。

4 結(jié)語

本文設(shè)計了一種基于LM3S1138處理器的走迷宮智能老鼠，實驗表明，智能老鼠在迷宮中行走的比較平穩(wěn)，并能順利完成前進，后退，轉(zhuǎn)彎避障等相關(guān)的系統(tǒng)功能。算法方面，本文采用了一種改進的深廣結(jié)合的最優(yōu)路徑搜索辦法。實際的測試表明，本文的所提出的算法大大減少了路徑搜索的次數(shù)，減少了計算量，提高了迷宮搜索的準(zhǔn)確性和有效性。

[1]嚴(yán)蔚民.數(shù)據(jù)結(jié)構(gòu)[M].北京:清華大學(xué)出版社，2003:5052.

[2]胡小兵,黃席樾.蟻群算法在迷宮最優(yōu)路徑問題中的應(yīng)用[J].計算機仿真，2005,22(4).

[3]宗光華等.機器人的創(chuàng)意設(shè)計與實踐[M].北京：北京航空航天大學(xué)出版社，2004.

[4]西原主計等[日],機器人C 語言機電一體化接口[M].牛連強、趙文珍譯.北京：科學(xué)出版社，2002.

[5]孫巧榆等.八方向走迷宮算法[J].計算機工程，2004(1)：90-91.

[6]周立功等.Cortex-M3 開發(fā)指南—基于LM3S8000[M].北京：北京航空航天大學(xué)出版社，2005.

[7]張新誼.一種電腦鼠走迷宮的算法[J]單片機與嵌入式系統(tǒng)應(yīng)用，2007（5）：84-85.

[8]周航慈.單片機程序設(shè)計基礎(chǔ)[M].北京：航空航天大學(xué)出版社，2003

[9]李學(xué)海.PIC 單片機實用教程—提高篇[M].北京：航空航天大學(xué)出版社，2002.

[10]潘道才,陳一華.數(shù)據(jù)結(jié)構(gòu)[M].成都:電子科技大學(xué)出版社,1995.

[11]袁蒲佳,龍玉國,楊薇薇.數(shù)據(jù)結(jié)構(gòu)[M].武漢:華中理工大學(xué)出版社,1995.

[12]王會麗,傅衛(wèi)平,方宗德等.基于改進勢場函數(shù)的移動機器人路徑規(guī)劃[J].機床與液壓，2002，10(6):67-68.

[13]Zhangb,ZhangL.AnAlgorithmfo{FindPathwi士hRotation.ln:Proe.} EEEInt.Conf Roboties and Automation，1988:917-921.