基于電腦鼠實驗平臺的Dijstra算法和Floor-fill算法比較研究*

薛盼為　王玉平　余　鷹

(湖北省安全生產應急救援中心1)　武漢　430070)　(武漢明德生物科技股份有限公司2)　武漢　430074)　(美國克萊姆森大學3)　克萊姆森　29631)

?

基于電腦鼠實驗平臺的Dijstra算法和Floor-fill算法比較研究*

薛盼為1)王玉平2)余鷹3)

(湖北省安全生產應急救援中心1)武漢430070)(武漢明德生物科技股份有限公司2)武漢430074)(美國克萊姆森大學3)克萊姆森29631)

介紹了迷宮環(huán)境的建模和2個路徑規(guī)劃算法，Djikstra和Flood-fill算法，并進一步通過流程圖和仿真來闡述如何使用該算法在任意的迷宮環(huán)境中導航，以最佳路徑從起始位置到達目標位置.結合實物實驗來驗證算法的正確性和分析其相對優(yōu)缺點.

電腦鼠；Djikstra；Flood-fill

0　引　　言

在未知環(huán)境下的基于多種任務的的自主導航系統(tǒng)的設計是一件非常復雜的任務.隨著同步完成捕獲目標和規(guī)避障礙物的目的，這個挑戰(zhàn)將變得更加復雜.如果障礙物和目標的配置產生局部極小點，就像在機器人和目標之間有凹的形狀和曲徑.純粹的反應式的導航系統(tǒng)是不能恰當的處理這種阻礙性質的情況，而是需要額外的認知上的設備.因此，來自于免疫網絡理論的概念用于將先前的反應式機器人控制，基于學習分類器系統(tǒng)，轉換成鏈接模式的設備.從一開始沒有先見的知識，分類器和鏈接模式將在機器人導航的過程中發(fā)展進化[1-3].

1　Djikstra算法

采用Djikstra最短路徑算法來解決迷宮路徑規(guī)劃的問題，該算法利用有多個節(jié)點的有向圖來找到最短路近.算法利用了多種行為的協(xié)調的策略，其中發(fā)展出了一種創(chuàng)新的路徑規(guī)劃行為來決定最短路徑.

1.1Djikstra算法原理

算法的輸入是由一個加權的有向圖G和G中的一個起始頂點組成.將用V來表示G中所有頂點的集合.圖中的每一個邊是一個有序的頂點對(u,v)，表示從頂點u到頂點v的鏈接.所有邊的集合由E表示.每一個邊的權重由一個權重方程w表示：w:E→[0,∞]，因此w(u,v)即為從頂點u移動到頂點v的費用值.一個邊e的費用值可以是兩頂點之間的可行距離(需要轉彎的地方e=e+1).任意2頂點之間路徑的費用值則是其中經過的所有邊的費用值之和.對于V中一對所給的頂點s和t，Djikstra算法將找出一條從s到t的具有最小費用值的路徑.其本質是在代數圖中優(yōu)化可行路徑的最小費用和[4].

2個相繼的節(jié)點之間距離的計算是通過在機器人步進電機的步數計數器來實現，這個數值將代表了邊e的費用值.迷宮的地圖將由一個10×10的二維數組表示，單元坐標由[R,C]表示.因此頂點集合V是由一對變量[R,C]來表示每一個節(jié)點所組成.具體流程見圖1.

圖1　Djikstra算法流程圖

生成有向圖的節(jié)點需要機器人搜索整個迷宮為前提.搜索程序的流程見圖2.

圖2　搜索程序流程圖

1.2迷宮路徑規(guī)劃仿真

在生成了有向圖之后，最終的Djikstra最短路徑算法將應用到有向圖上生成最短路徑[5]，機器人將利用它達到終點節(jié)點，即迷宮的中心，見圖3～4.

圖3　迷宮simulator

圖4　迷宮由Djikstra算法所破解

1.3Djikstra算法存在的缺點

使用Djikstra算法存在一定的問題.最主要的是整個迷宮需要被穿越.為了鑒別所有的節(jié)點和邊，穿行迷宮的全部尤為重要，不管這一部分是否包含了最短路近.即使對于較小的迷宮，它也要在開始尋找最短路徑之前穿越所有的方格.所以很多時間和能量在穿越迷宮過程中被浪費了.在產生了有向圖G后，算法也需要一定的時間來找到最短路徑，它必須檢查所有指向中點的邊.這又增加了迷宮搜索的總體時間.

2　Flood-Fill算法

2.1Flood-fill算法原理

機器人尋找路徑所花費的時間主要由執(zhí)行的算法所影響.如果使得迷宮搜索和最短路徑的尋找同步進行，則可以降低總體時間.Flood-fill算法正由此而生.其基本原理包含了給迷宮中每一個單元進行賦值.這些值代表著從它到迷宮目標單元的距離.目標單元因此被賦予了0.例如：如果機器人正在被賦予3的單元中，它距離目標還有3個單元.文中假設機器人無法走對角線，且每當它到達一個單元時已經獲取并存儲其4面的墻壁信息.

迷宮的賦值用一個10×10的矩陣MazeValue[R][C]存表示，終點被賦予(0,0).最初該迷宮矩陣被分割為4個鏡像區(qū)域，然后每個單元如下進行賦值.

行的增加和減少：R-(i×decr)+(i×incr).

列的增加和減少：C-(j×decr)+(j×incr).

整個方程如下.

MazeValue[R-(i×decr)+(i×incr)]

利用石門桂花村的歷史文化背景進行推廣，可以打造石門桂花村“畫家之鄉(xiāng)”、“金桂花?！钡绕放?，加大宣傳力度，通過廣播、電視、報紙、網絡等現代媒體廣泛宣傳介紹，并結合“五一”、“國慶”等旅游黃金周的強勢推介，提高知名度。

[C-(j×decc)+(j×incc)]=i+j

式中：變量i,j在循環(huán)中由0～8變化.

現在賦值已經完成，整個數值分布見圖5.

圖5　單元的賦值分布圖

另外，算法針對任意單元形成一個臨時的棧temp[4].該棧用于存儲機器人當前所在單元的相鄰單元信息.包括其坐標(R,C)和賦值，見圖6.

圖6　在temp[4]中存儲元素

當機器人準備運行下一個動作之前，它必須檢測所有相鄰的且沒有被墻壁阻隔的單元，并選擇一個賦值最低的單元.在程序中，將相鄰單元的信息存儲于棧temp[4]中，運用排序的方法決定最低賦值的單元.這里使用了選擇排序法，決策的流程見圖7.

圖7　選擇單元策略圖

機器人穿越迷宮的同時記錄經過的每一個單元的信息.顯然，迷宮墻壁信息將影響到機器人選擇下一個移動到的單元.因為當檢測到新單元的墻壁信息時，整個或局部迷宮的單元信息本身將受到影響.算法需要對其進行更新.更新程序改變需要更新單元的賦值，以保證機器人選擇的路徑永遠是從賦值高的單元到賦值低的單元.更新程序的流程圖見圖8.

圖8　單元賦值的更新程序

綜上，Flood-fill算法的主程序由以下兩步組成，每次機器人到達一個新的單元時運行一次該程序來搜索從當前單元到目標單元的最短路徑[6-7]：(1)更新迷宮地圖的單元信息賦值；(2)選擇最小賦值的相鄰單元并移動到該單元.

2.2迷宮仿真破解

圖9是由Flood-fill算法仿真的具體線路.其中上方的路徑為機器人的破解路徑.下方的路徑為迷宮的全局最優(yōu)路徑.

2.3Flood-fill算法的缺點

Flood-fill算法的缺點在于對環(huán)境的探索未完成之前即作出了優(yōu)化路徑的決策選擇，所以很難保證作出的決策是全部路徑規(guī)劃的最優(yōu)解.對于非常大型復雜的迷宮或含有設計陷阱的迷宮，Flood-fill算法所生產的路徑有可能陷于局部極小點中，從而使得機器人運行過程中走了很多“彎路”，浪費了很多時間和能量.

3　迷宮破解實驗的實施

3.1實驗步驟

步驟1部署迷宮，將機器人置于迷宮起始位置(0,0).

步驟2執(zhí)行機器人搜索迷宮程序.待其搜索完整個迷宮之后回到起始位置.

步驟3執(zhí)行Djikstra算法獲取最短路徑，并按照該路徑運行到目標位置.

步驟4再次執(zhí)行Djikstta算法獲取最短路徑，并按照該路徑回到起始位置.

2) 基于Flood-fill算法的迷宮破解實驗.

步驟1部署迷宮，將機器人置于迷宮起始位置(0,0).

步驟2執(zhí)行Flood-fill算法搜索迷宮并同時獲取最短路徑，并按照該路徑運行到目標位置.

步驟3再次執(zhí)行Flood-fill算法搜索迷宮并同時獲取最短路徑，并按照該路徑回到起始位置.

3.2實驗數據記錄

根據上一章所建立的坐標系，實驗中可以記錄下機器人在路徑中關鍵點的坐標值.通過和仿真分析對比作出驗證性分析.

1) 基于Djikstra算法的迷宮破解實驗實驗過程中，機器人經過一個有向圖的頂點則記錄并顯示其當前坐標值，仿真分析與實驗數據見表1～2.

表1　Djikstra算法(步驟3)數據記錄表　格

表2　Djikstra算法(步驟4)數據記錄表　格

2) 基于Flood-fill算法的迷宮破解實驗實驗過程中，機器人經過一個需要更新賦值的單元則記錄并顯示其當前坐標值，仿真分析與實驗數據見表3～4.

表3　Flood-fill算法(步驟2)數據記錄表　格

表4　Flood-fill算法(步驟3)數據記錄表　格

為了比較2種算法的優(yōu)劣，在實驗中記錄了2次實驗中機器人每一個步驟所經歷的時間和路程，見表5.

表5　兩種算法的比較數據記錄表

3.3實驗結果分析

通過上面的實驗數據記錄發(fā)現，不管是Djikstra算法還是Flood-fill算法，實驗所得的路徑和仿真的路徑相同.而且機器人均通過搜索和決策過程從起始位置運行到目標位置，并返回到起始位置，從而驗證了兩種算法的正確性.

不難發(fā)現雖然Djikstra算法所得到的是全局的最優(yōu)路徑，但是大部分的時間花費在搜索迷宮的過程中，所花費的總時間大于Flood-fill算法所花費的總時間.而Flood-fill第一次破解迷宮并沒有發(fā)現全局最優(yōu)路徑，花費的時間要大于Djikstra算法.即使在第二次回到起點的過程中發(fā)現了全局最優(yōu)路徑，也因為搜索到非最優(yōu)路徑的迷宮部分而花費了一些額外的時間.這也說明了Flood-fill算法在未知迷宮環(huán)境下搜索的局限性.

4　結 束 語

如果沒有時間和位置環(huán)境的限制，Djikstra算法能夠有效的找到迷宮的最優(yōu)路徑.但如果考慮到這兩個約束，Flood-fill算法將更加優(yōu)異.因此，對于當前的機器人迷宮搜索比賽(比如電腦鼠比賽)Flood-fill是迄今為止最有效的算法.另外機器人完成任務的能力也取決于其處理器的運算能力，硬件的性能，運行速度，控制策略等多方面的因素.在改進硬件等方面是有其機械或電子上的限制，而在改進算法方面仍有很大的優(yōu)化空間，還有待進一步研究.

[1]李文鋒.無線傳感器網絡與移動機器人系統(tǒng)[M].北京：科學出版社，2009.[2]MISHRA S. Maze solving algorithms for micro mouse[C]. Pune: IEEE,2008.[3]WANG Duyao. A new method of infrared sensor measure-ment for micromouse control[C]. Shanghai: IEEE,2008.

[4]SERGIO G V. An integrated undergraduate research experience in control, power electronics, and design using a micromouse[C]. Mayagüez: IEEE,2010.[5]PARASURAMAN S, GANAPATHY V, SHIRINZADEH B. Behavior based mobile robot navigation technique using ai system: experimental investigations[C]. Cairo: CICC,2005.

[6]李鐵柱.機器人導航中的定位與避碰方法研究[D].吉林：東北電力大學，2006.

[7]梁文君.機器人動態(tài)路徑規(guī)劃與協(xié)作路徑規(guī)劃研究[D].杭州：浙江大學，2010.

Comparison Research of Dijkstra and Floor-fill Based on Micromouse Experimental Platform

XUE PanweiWANG YupingYU Ying

(HubeiAdministrationforWorkSafetyEmergencyResponse,Wuhan430070,China)

This paper presents the mathematical model of maze environment and two path-planning algorithms including Djikstra and Flood-fill algorithm. This paper further shows how to apply them to navigate the robot in an arbitrary maze and find the optimal route from the starting position to the target position with detailed flowcharts and simulation. Lastly, it verifies the correctness of the above algorithms and evaluates their relative advantages and disadvantages with experiments.

micromouse; Djikstra; Flood-fill

2016-07-09

TP242.6

10.3963/j.issn.2095-3844.2016.04.036

薛盼為(1987- )：男，碩士，主要研究領域為環(huán)境感知與系統(tǒng)協(xié)作控制、物流自動化與機器人控制等

*廣東省科技專項資金項目資助(0104)