基于分布式環境下的機器人的路徑規劃及實現

摘要:在研究機器人的運動規劃中發現，分布式環境中路徑規劃問題是一個很復雜的問題。該文通過基于Snake模型的蟻群優化算法，順利解決了這一難題。文中根據Snake的特點構建了一種新的蟻群求解算法，在分布式環境中可以順利解決在有固定障礙物的情況下的最優路徑的搜索問題。并且，結合我們本身的實驗環境，我們在對上述算法稍微進行了一些修改后，使這種算法可以在我們的嵌入式硬件平臺上運行，最終驗證了這種算法的可行性和穩定性。

關鍵詞:分布式環境;Snake模型;蟻群優化算法

中圖分類號:TP311 文獻標識碼:A文章編號:1009-3044(2010)02-376-03

A Snake Model Based on Ant Colony Optimization for Robot Path Planning in the Distributed Environment

BI Bo， ZHU Jin， WANG Xiao-nian

(Robot control and Intelligent control Institute， Electronic Information and Engineering， Tongji University， Shanghai 201804， China)

Abstract: It is found that path planning in the distributed environment is a very complex problem in the Robot motion planning. In this paper， we use the ant colony optimization algorithm based on the Snake model， resolved this problem successfully. This algorithm providing a new approach path， is the best in the search procedure. It also resolved the problem in the case of a fixed obstruction in a distributed environment. However， we carried out the above-mentioned algorithm combined with our lab environment. This algorithm had been modified slightly， so that it be run in our embedded hardware platform to prove the final validation of this algorithm is feasible and stability.

Key words: distributed Environment; snake models; ant colony optimization

路徑規劃是機器人是研究中的一個基本而且重要的問題。自20世紀70年代以來，國內外已相繼提出了多種路徑規劃的方法。現代最常見的是在層次上分為了兩種。一種是基于環境先驗完全信息的全局路徑規劃;另一種是基于傳感器信息的局部路徑規劃[1]。全局路徑規劃的方法主要有可視圖法，環境分割法等;局部路徑規劃主要有人工勢場法，遺傳算法，模糊邏輯算法，神經網絡算法等。但在智能分布式視覺環境中，傳統的路徑規劃方法都已經不能滿足需求。針對分布式環境自身的特點，本課題引入了基于Snake模型的蟻群算法。該算法通過通訊實現局部內力的交互以獲得一個動態、無碰撞、滿足動態約束的優化軌跡，即獲得一個Snake模型，以應對可能的動態環境變化。然后結合傳統的蟻群算法，完成最優路徑搜索。實質上，這種主動軌跡算法是一個基于分布式圖像的信息融合與迭代。是對傳統蟻群算法的一個優化。

蟻群算法是M. Dorigo 等人提出的一種新型的模擬進化算法[6]，它模擬自然界中蟻群從蟻巢到目的地之間尋找最短路徑時的一種隨機搜索過程。蟻群算法本質上構成了一種多智能體的復雜適應系統，通過每只螞蟻的個體尋優和多只螞蟻的協同工作，把正反饋原理和啟發式算法相結合，使其具有很強的并行性、魯棒性。文獻[6]的實驗結果顯示，如果參數合適，對節點數為50-100的組合優化問題，蟻群算法的仿真結果普遍好于遺傳算法、進化算法、模擬退火算法[2]。此外，結合本實驗環境，是在分布式環境下，使用這種算法可以使多攝像頭之間的路徑搜索更容易銜接，形成一條完成的路徑。因此，使用基于Snake模型的蟻群優化算法，為解決路徑規劃問題提供了新的途徑。

1 分布式環境中Snake模型

Snake模型又稱主動輪廓模型，是1987年Kass首次提出的，他起初描述的是在圖像分割過程中的一個概念。主要是通過構造合適的形變能量Esnake來定義目標輪廓，包括內部能量Einternal和外部能量Eexternal。能量函數表達式為:

Esnake= Einternal + Eexternal(1)

Ein表示主動輪廓線的內部能量，保持曲線的連續性和平滑性，也就是保持一個完成輪廓的能量。在分布式環境中，我們相當于將輪廓展開，將其轉化成一條路徑。Ein表示的就是這條蛇在選擇路徑過程中保持自身特性的一個能量;Eexternal為外部約束，是在外部未知條件下對輪廓的影響[3]。在分布式環境中，我們的Eexternal表示的是障礙物對蛇的形變的影響，那么原來的基于輪廓的Snake模型就轉化為智能環境中，在障礙物作用下的路徑規劃問題。圖1清晰的展示了這一轉變。

在Snake模型里面，使用v(s)=(x(s)，y(s))表示輪廓，式中s∈(0，1)為單位化的曲線弧長;

v(s)為輪廓曲線;x(s)，y(s)分別是其在x，y坐標軸上的投影。那么輪廓線的能量函數可以表示如下:

其中內部能量Ein由輪廓對弧長的一階導數vs(s)和二階導數vss(s)線性表示為:

Ein = α(s)|vs(s)|2 + β(s)|vss(s)|2(3)

式中α(s)表示對輪廓連續性約束的權重;β(s)調節平滑的程度;xi，yi為曲線上點的坐標;

在本實驗環境中，研究過程同樣用這樣的定義形式，而且在不涉及圖像能量對曲線的影響，可以得到Esnake能量函數的離散形式為:

(4)

外部能量Eexternal表示的障礙對蛇的斥力，是以圖像力的作用表現出來的，后面敘述。

因為(4)式中α，β是α(s)，β(s)的常數形式。所以基于Snake模型的求解過程就是尋找在圖像中，Esnake的極小值過程，也就轉化成了求其在多攝像頭環境下的最優路徑規劃問題。

2 基于Snake模型的蟻群算法

我們在智能環境中，將攝像頭所拍到的圖像灰度化以后，選擇圖像矩陣中數值大于120的點為默認障礙點，數值小于120的點為可以選擇的點，于是可以得到一個由0和1組成的矩陣，0表示障礙，1表示可以通過的路徑。

2.1 空間構造(Construction of image routine)

下面我們以一個簡單矩陣圖2為例說明基于Snake模型的求解過程，圖中的線加粗部分表示可以選擇的點的范圍。設xij∈vi為當初始點，也就是我們把機器人進入攝像頭范圍內之后的起始位置選擇為第一個點，那么選擇下一個點xpi+1∈vi+1是否為最優選擇點，取決于它是否使得Esnake能量函數是否趨于極小值。同理又以xpi+1為當前點繼續選擇新的最優點，于是可得到使Esnake取得最小值的從xi-1到xi+2列的所有點序列。這樣就會得到單一攝像頭下的一條最優路徑[4]。再以第一個攝像頭的最后一點為初始點，繼續搜索，就可以得到整個分布式環境下的最優路徑。

但是，因為機器人本身體積的原因，相對障礙物，他也不能完全被看為一個質點。因此在圖像中出現障礙物的時候，機器人應該選擇盡量遠離障礙物的點，那樣機器人才更有可能在不碰到障礙物的情況下達到終點。這樣的話，每次選擇考慮xi列中可選點的情況下(加粗部分)，又要盡量選擇粗線中靠近中間的點。

綜合兩方面的因素，結合圖2，我們再討論下這個過程中的蟻群優化過程。如果在滿足上述兩個條件的情況下，我們選擇一條從這xi列到xi+2列之間的最小能量路徑。設螞蟻的初始位置為xji∈vi位置，在概率的約束條件下，就會以一定的概率選擇下一個相鄰節點xpi+1∈vi+1，于是，螞蟻不斷的選擇下一個點，依次這樣的尋找下去，就會構成一條從xi-1列到xi+2列的路徑。那么，經過每一次迭代后，每只螞蟻都得到一條路徑，然后就會增加這條能量最優路徑對應的信息激素，進而增大螞蟻選擇這條路徑的概率。而新的激素場又會誘導下一代螞蟻的選擇。在整個蟻群的協同下，便得到最終的能量最小路徑。圖2中從xij到xi+1列上的連線表示螞蟻可能選擇的路徑。

2.2 信息素的更新與蒸發

在關于螞蟻行為的早期研究發現，群體中的個體之間以及個體與環境之間的信息傳遞是依賴于螞蟻產生的化學物質進行的。這就是我們后來所定義的信息素。初始時各路徑的信息素相等。隨著第一組螞蟻尋找路徑結束后，我們會算出一條最優路徑。然后加強這條路徑的信息素。進而影響下一組螞蟻的行為，使螞蟻選擇這條最優路徑的概率增大。即設螞蟻在任意xij∈vi位置，該螞蟻從vi+1集合中選擇任意元素，共有N種可能。那么集合vi的每個元素與集合vi+1任意元素的序對都可能是螞蟻選擇的路徑，就是說每兩個集合之間都有 N*N種連接的可能。這樣，我們便構造了一個信息素的初始矩陣。這條路徑的初始信息素是固定相等的，當一組螞蟻完成一次路徑尋優以后，相應路徑上的信息素濃度增加[5]。

另外一方面，在增強最近一次信息素濃度的時候，也會減小上一次最優路徑的信息素的濃度。這個過程稱之為信息素的蒸發。事實上，這樣有助于在整個搜索過程中探索其他不同的路徑，也有利于避免螞蟻在路徑尋優過程的快速收斂。

2.3 路徑構建

設一組有m只螞蟻。最初，螞蟻被安排在同一初始位置。在路徑構建的每一步中，螞蟻k按照一個稱為隨機比例規則的概率行為選擇規則，來決定下一步移向哪一個位置。設螞蟻在xij∈vi位置，選擇xpi+1∈vi+1的概率為:

式中l∈xi+1，i=(1，2，...M)，j，k=(1，2，...N);τ(i，xij，xpi+1)表示連接xij∈vi和xpi+1∈vi+1的信息素值;η(xpi+1)為xpi+1點預先給定的啟發式信息，α和β兩個參數分別決定了信息素和啟發式信息的相對影響力。在這個概率規則下，選擇下一個點(i， j)的概率由該點所對應的信息素和啟發式信息的值決定。如果α=0，則靠近i的點將很有可能被選出，相當于一種經典的隨機貪心算法(螞蟻的行為具有完全的隨機性)。而如果β=0，那么就只有信息素的放大系數再起作用，也就是說，算法只使用了信息素，而沒有利用任何啟發式信息帶來的偏向性。這將會使算法的性能變得十分的糟糕，特別是如果這時α>1時，算法很快就會收斂，所有的螞蟻會沿著一條路線移動，最后構建的路徑與所要優化的路徑相差很遠。所以，螞蟻選擇概率值較大的點，這是蟻群算法快速收斂的原因，但還以小概率選擇其它點，這是保證全局收斂的原因。

2.4 求解過程

算法的求解過程表述為:設第k只螞蟻從任意點xij出發，在信息素的誘導下選擇下一個點xpi+1，依此類推，形成一條路徑Lα。當所有螞蟻完成一個迭代后，根據式(3)定義的能量函數評價每只螞蟻的路徑，然后更新最優路徑對應的信息素場。新的迭代過程在當前信息素場的基礎上進行，直到能量函數Esnake的值不再下降為止。具體算法過程這里不進行詳述[6]。

3 仿真結果與分析

我們以在分布式環境中，機器人在固定障礙物下的軌跡尋找過程為例，來說明上面的算法的可行性。

3.1 圖像處理

在分布式環境下，我們用imote2(ARM10帶OV7620的攝像頭模塊)拍攝到照片，并對圖片進行一系列的濾波和形態學計算。得到結果。

圖3 單攝像頭下的實際環境圖4 經過二值處理過的圖像

3.2 過程分析

在上述環境下，初始的概率矩陣視圖如圖5所示。螞蟻的收斂過程如圖6所示，本實驗大概經過了100次的循環尋跡，最終找到了一條最優路徑。

圖5 概率矩陣三維視圖圖6 能量函數收斂視圖

3.3 結論

最終我們得到的實驗結果還原到原來的圖片中如圖7所示。我們也可以知道他是最有收斂的。

圖7的黑線代表路徑。可以看到，這種基于Snake模型的蟻群尋優算法很合理的解決了分布式系統中的路徑規劃問題。

參考文獻:

[1] Kass M，Witkin A，TeizoPoulos D.Snakes:active contour models[J].International Journal of Computer Visiton，1987，1(4):321-331.

[2] 柯良軍，馮祖仁，馮遠靜.有限級信息素蟻群算法[J].自動化學報，2006，32(2).

[3] 趙敏，胡中華.一種求解機器人路徑規劃的智能優化算法[J].電焊機，2009，4(39).

[4] 馮遠靜，馮祖仁.一類自適應蟻群算法及其收斂性分析[J].控制理論與應用，2005，22(5).

[5] 齊勇，魏志強，殷波.增強蟻群算法的機器人最優路徑規劃[J].哈爾濱工業大學學報，2009，3(3).

[6] 王曉年，馮遠靜，馮祖仁.一種基于主動輪廓模型的蟻群圖像分割算法[J].控制理論與應用，2006，8(4).

[7] Thomas Stutzle，Marco Dorigo.A short convergence proof for a class of ant colony optimization algorithm[J].IEEE Transactions on evolutionary computation， 2002，6(4).