智能小車走迷宮算法的設(shè)計與研究

王蒙+朱冬旭+李治

【摘 要】智能小車是一種集感知、判斷、行走功能于一體的微型機器人，能夠自動尋找最佳路徑并且達到目的地。對智能車搜索和沖刺迷宮提出了一種算法。智能小車可根據(jù)行走的路線和拐彎的情況進行變速調(diào)節(jié)，提高了智能車的行進速度以及靈活性。利用已經(jīng)搜索到信息的耦合關(guān)系，對算法提出改進，縮短了智能小車搜索的時間。

【關(guān)鍵詞】智能小車；算法；迷宮；探索策略

中圖分類號： TP242 文獻標(biāo)識碼： A 文章編號： 2095-2457（2017）23-0017-002

【Abstract】Intelligent car is a micro robot with the functions of perception，judgment and walking.It can automatically find the best path and achieve the destination.An algorithm for intelligent vehicle search and sprint maze is proposed. Smart car according to the routes and turns of speed regulation，improve the speed and flexibility of intelligent vehicle By using the coupling relation of searching the information，the algorithm is improved，and the time of searching the intelligent car is shortened.

【Key words】Smart car；Algorithm；Maze；Exploration strategy

0 背景

智能機器人的需求越來越大，應(yīng)用領(lǐng)域日益廣泛，大到宇宙探索、深海研究、軍事等領(lǐng)域，小到工廠企業(yè)、家庭等都對智能機器人提出了很高的要求。智能機器人的路徑研究成為熱點。

智能機器人的路徑研究，放到迷宮中進行探索，能更好地適應(yīng)自主尋找目標(biāo)。迷宮的生成通過仿真模擬實現(xiàn)，由隔墻板沿方塊的四周布設(shè)，形成迷宮通道。智能小車的包括電源模塊、微處理器模塊、傳感器模塊、電機模塊、驅(qū)動模塊。小車的整體設(shè)計方案如圖1所示。

智能小車是由一個微處理器控制的，集感知、判斷、行走功能與一體，能夠自主尋找最佳路徑并達到目的地的微型機器人，可以在迷宮中感知并記憶迷宮地圖，通過一定的算法，尋找一條最佳路徑，以最快的速度達到目的地。

1 走迷宮算法

1.1 性能指標(biāo)

智能小車的基本功能是從起點走到終點，這個過程稱為一次運行，所花費的時間稱為運行時間。從智能小車的第一次激活到每次運行開始，這期間所花費的時間稱為迷宮時間。智能小車走迷宮的性能主要從速度、求解迷宮的效率和小車的可靠性來評判。

智能小車在在有限的時間或探測次數(shù)下，采用部分迷宮探索策略，只探測迷宮的一部分，從中找出最佳路徑。如果小車根據(jù)設(shè)定的算法行進，最終選擇出一條最優(yōu)的路徑，稱為相對最優(yōu)路徑。迷宮中實際存在的最優(yōu)路徑稱為絕對最優(yōu)路徑。

如果進入迷宮是為了進行探索和記憶，則這次運行稱為“試跑”。如果進入迷宮是根據(jù)先前的記憶和經(jīng)驗，按照智能算法確定最佳路徑，并以最快的速度達到終點，則這次運行稱為“沖刺”。

1.2 探測策略

智能小車在迷宮內(nèi)行走，如果最終無路可走，則該路徑稱為“死路”；如果存在2個或2個以上的方向可以行走，稱為“交叉”。遇有交叉時，在行走方向的選擇上可以有如下幾種選擇法則：

右手法則：以右邊為優(yōu)先前進的方向，其次是直線方向、左邊方向。

左手法則：以左邊為優(yōu)先前進的方向，其次是直線方向、右邊方向。

中左法則：以直線為優(yōu)先前進的方向，其次是左邊方向、右邊方向，同理還有中右法則。

亂數(shù)法則：取隨機值作為前進方向。

中心法則：由于終點設(shè)在迷宮中心，遇到交叉時取指向迷宮中心的方向為優(yōu)先選擇的方向。

1.3 標(biāo)記

為了記憶迷宮的詳細(xì)信息，需要對迷宮單元的位置進行線路標(biāo)記。迷宮共有16×16個單元，可采用二維坐標(biāo)的方式進行標(biāo)記，即用每個單元的XY坐標(biāo)表示。此外，還需要對迷宮單元的可行進方向進行標(biāo)記，可采用絕對方位和相對方位兩種方式。

絕對方位：這是一種與電腦鼠行進方向無關(guān)的標(biāo)記方式，以一個四位的二進制數(shù)，分別表示“東”﹑“西”﹑“南”和“北”四個方向。以1表示允許行進（無墻壁），0表示不允許行進（有墻壁）。

相對方位：這是一種與電腦鼠行進方向有關(guān)的標(biāo)記方式，以一個三位的二進制數(shù)即可實現(xiàn)標(biāo)記，分別表示“前”“左”“右”， 以1表示允許（無墻壁），0表示不允許（有墻壁）。

絕對方式利用具體的坐標(biāo)來記憶，具有唯一性，能夠減少處理器的運算，但沒有考慮小車的具體指向。相對方式根據(jù)小車具體的指向來確定，容易造成混淆，增加記憶的數(shù)據(jù)。

1.4 試跑

試跑是獲得迷宮地圖的唯一方法，在規(guī)則允許的情況下，應(yīng)盡可能多的獲取迷宮信息，為最后的沖刺做準(zhǔn)備。在試跑過程中除了要對經(jīng)過的單元進行線路標(biāo)記外，還要選擇一種合理的探測策略。

1.5 阻隔

根據(jù)小車試跑的數(shù)據(jù)，可以將小車遇到死路的路徑進行分析，將其前一個遇到交叉的路口進行阻隔，當(dāng)小車再次遇到此交叉時，不會再次尋找此路徑，縮短探索時間。

1.6 最佳路徑的選擇

智能小車要在最短的時間完成沖刺，路徑的選擇至關(guān)重要。選擇步數(shù)少的路徑是確定最佳路徑的條件之一，但不是唯一條件。考慮智能小車在拐彎時同樣需要時間，所以要將拐彎次數(shù)加權(quán)后再加到步數(shù)中，以確定加權(quán)步數(shù)。endprint

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

拐彎次數(shù)：一個90度的拐彎算一次，一個180度的拐彎算兩次。

小車采用變速的行走方式，如果連續(xù)3個數(shù)據(jù)均為直行方向則確定小車為提速行進的狀態(tài)，如果不符合確定小車為普通速度行進。因此，小車的拐彎次數(shù)所占比重較大，經(jīng)過試驗權(quán)值設(shè)在1～1.3之間為宜。如圖2所示為模擬智能小車的軌跡圖。

2 搜索算法的改進

迷宮搜索的目標(biāo)是盡量用短的時間搜索出盡量多的信息。前面的搜索路徑只是根據(jù)已有的試跑數(shù)據(jù)來選擇最佳路徑，忽略了數(shù)據(jù)之間的相關(guān)性，不能充分利用智能小車搜索來的信息。提出在已有支路的的算法基礎(chǔ)上對搜索路徑進行優(yōu)化。通過上面的研究提出一種將中心法則與洪水推演法相結(jié)合，具有預(yù)推演功能的迷宮搜索算法，該算法從剔除無效搜索路徑和增加有效信息兩個角度，減小智能車的搜索時間，對墻面信息進行擴展。

2.1 擴展搜索信息

智能小車的行走路徑依照前面的算法只有根據(jù)當(dāng)前傳感器傳來的數(shù)據(jù)對小車的行走進行判斷，而沒有注意對已探索的數(shù)據(jù)之間的耦合性進行研究。根據(jù)已有的數(shù)據(jù)進行擴展，減少探索次數(shù)，縮短探索時間。

一、開辟兩個二維數(shù)組Realstep[x][y]、Exstep[x][y]。這兩個二維數(shù)組分別存放實際走過的路徑和擴展后的路徑。迷宮的規(guī)格為256（16×16），則坐標(biāo)[x][y]為16×16個單元，其中x為橫坐標(biāo)，y為縱坐標(biāo)。每個數(shù)據(jù)的bit7代表是否真實檢測，如bit7為0則代表此數(shù)據(jù)為真實路徑，bit7為1則代表此數(shù)據(jù)為擴展路徑。bit3～bit0代表“左”“下”“右”“上”方向，0代表該方向無路，1代表該方向有路。如0x05H表示這條數(shù)據(jù)為真實探索的數(shù)據(jù)，并且在上和下兩個方向均無墻壁，左和右兩個方向均有墻壁。

二、對兩個二位數(shù)組進行初始化。Realstep[x][y]存儲的信息為實際行走信息，在激活之前，假定迷宮內(nèi)部沒有墻壁，初始化為0x00H。Exstep[x][y]存放擴展信息。當(dāng)x=0時，迷宮的最下面一排沒有“下”方向，bit2=0；當(dāng)x=15時，迷宮的最上面一排沒有“上”方向，bit0=0。同理，當(dāng)y=0時，bit3=0，y=15時，bit1=0。

三、對數(shù)組內(nèi)部進行擴展。將Realstep[x][y]、Exstep[x][y]中的數(shù)據(jù)進行實時更新。Realstep[x][y]中的數(shù)據(jù)完全根據(jù)智能小車探索的數(shù)據(jù)進行更新，Exstep[x][y]不僅將Realstep[x][y]內(nèi)部信息全部復(fù)制到數(shù)組中，還需要對其中的數(shù)據(jù)進行擴展。如（3，3）點的數(shù)據(jù)為0x05H，則（2，3）右邊為0，（3，4）左邊為0，（2，3）和（4，3）為上下均可以行進。

2.2 剔除死路交叉

根據(jù)擴展的路徑進行分析，可以判斷在遇到交叉時會有死路的選擇，不必進行真實的路徑探索，而直接將其阻隔，減少搜索的時間。由于剔除的路徑都是經(jīng)過實際路徑過濾必定不能達到的路徑，所以會保留可能到達終點的所有信息。這一動作增加了微處理器的運行時間，但其數(shù)量級很小，且對于減少機械運行時間來說效果甚佳。

3 實驗數(shù)據(jù)與分析

在相同的環(huán)境和小車狀況下，選擇8幅不同的迷宮，使小車進行搜索和沖刺，得到數(shù)據(jù)如表1。

根據(jù)數(shù)據(jù)得知，改進后的算法在搜索時間上均大大縮短，其中縮短時間最大的為第7組迷宮，縮短了38.75%，沖刺時間基本沒有變化。可見采用改進后的算法大大減少了搜索所需要的時間。

4 結(jié)論

智能小車在直線行進時提速拐彎時普速，實現(xiàn)了速度的調(diào)節(jié)，使行進更靈活快速。最重要的是在優(yōu)化算法方面，通過對已知數(shù)據(jù)耦合性關(guān)系的推演改進，大大縮短了搜索迷宮的時間，提高了搜索的效率。

【參考文獻】

[1]周毅.基于智能算法的機器人路徑方法研究[D].北京： 北京工業(yè)大學(xué)，2009：1-15.

[2]尹偉峰.智能車設(shè)計及其追蹤系統(tǒng)研究[D].江蘇：南京理工大學(xué)，2010.

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

[4]吳哲輝，崔煥慶，馬炳先.算法設(shè)計方法[M].機械工業(yè)出版社，2008.endprint