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

王蒙+朱冬旭+李治

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

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

中圖分類號(hào)： TP242 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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 背景

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

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

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

1 走迷宮算法

1.1 性能指標(biāo)

智能小車的基本功能是從起點(diǎn)走到終點(diǎn)，這個(gè)過程稱為一次運(yùn)行，所花費(fèi)的時(shí)間稱為運(yùn)行時(shí)間。從智能小車的第一次激活到每次運(yùn)行開始，這期間所花費(fèi)的時(shí)間稱為迷宮時(shí)間。智能小車走迷宮的性能主要從速度、求解迷宮的效率和小車的可靠性來評(píng)判。

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

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

1.2 探測(cè)策略

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

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

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

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

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

中心法則：由于終點(diǎn)設(shè)在迷宮中心，遇到交叉時(shí)取指向迷宮中心的方向?yàn)閮?yōu)先選擇的方向。

1.3 標(biāo)記

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

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

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

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

1.4 試跑

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

1.5 阻隔

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

1.6 最佳路徑的選擇

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

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

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

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

2 搜索算法的改進(jìn)

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

2.1 擴(kuò)展搜索信息

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

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

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

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

2.2 剔除死路交叉

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

3 實(shí)驗(yàn)數(shù)據(jù)與分析

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

根據(jù)數(shù)據(jù)得知，改進(jìn)后的算法在搜索時(shí)間上均大大縮短，其中縮短時(shí)間最大的為第7組迷宮，縮短了38.75%，沖刺時(shí)間基本沒有變化?？梢姴捎酶倪M(jìn)后的算法大大減少了搜索所需要的時(shí)間。

4 結(jié)論

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

【參考文獻(xiàn)】

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

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

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

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