基于蟻群優化和離策略學習的機器人路徑規劃

趙廣復，方加娟

(鄭州職業技術學院軟件工程系，河南鄭州 450121)

1 研究背景

機器人路徑規劃是機器人領域的一個研究重點和難點，也是人工智能走向工業和生活必須要解決的一個關鍵問題。機器人的路徑規劃可以定義為：在一個具有障礙物的場景中，機器人從某初始位置出發，避開障礙物，尋求一條從初始位置到目標位置的最優路徑。最優路徑指的是路徑長度最短，或是花費時間最短，或是路徑上消耗的能量最少[1]。

從移動機器人路徑規劃的定義可以看出，移動機器人規劃的關鍵問題可以分為三個部分：(1)路徑規劃是從初始位置到目標位置的一條路徑；(2)規劃出的路徑必須要避開環境場所中的所有障礙物；(3)在滿足條件(1)(2)的情況下，盡可能地根據機器人規劃的具體優化目標，來尋求其運動軌跡。

根據機器人是否依賴在線產生的數據，機器人規劃方法可以分為在線和離線的方法。離線方法是指機器人一開始就擁有全部的環境信息，機器人只需要根據已知環境信息和知識來進行規劃即可。在線方法是指機器人在初始時刻并不知道環境的所有信息，可能只知道部分的信息，因此，機器人需要同時進行路徑規劃和獲取環境的信息。鄭延斌[2]提出了一種基于分層強化學習和人工勢場的多agent路徑規劃算法，以提高規劃的收斂速度和規劃效率。將規劃場景虛擬為一個人工勢場，采用先驗知識來初始化每點的勢能值，并利用分層強化學習算法來更新策略。趙開新[3]提出了一種改進的自適應遺傳算法，根據進化過程中對個體的適應度值，來對交叉概率和變異概率進行調節，使得算法能跳出局部最優解，求取全局近似最優解，并通過柵格法對機器人工作空間進行建模。祁若龍[4]采用概率論方法結合機器人的線性控制和卡爾曼濾波對機器人可行軌跡進行規劃，并對先驗概率進行評估，從而獲得機器人的先驗估計概率，采用高斯運動模型對可行軌跡評估，從而計算出避開障礙和到達目標點的概率。陳洋[5]分別考慮了空中飛行機器人和地面移動機器人的最大運動速度，在滿足最小充電時間、最大滯空時間以及各目標位置的鄰域的約束，將目標序列訪問任務的總時間最短作為目標優化模型，從而將機器人系統路徑規劃問題轉換為混合整數凸優化問題進行求解。唐建業[6]提出了一種改進的多項式插值軌跡規劃方法，在滿足運動學約束的前提下實現時間和沖擊的綜合最優，采用序列二次規劃方法求得最優運動時間，綜合關節空間位置序列的運動學參數確定最終的關節軌跡。方嘯[7]首先定義了連續型的強化信號，采用強化學習信號對輸入和輸出量進行了定義，并設計了機器人自主學習尋路和避障的控制策略，在不同的初始位置和目標狀態下進行仿真實驗，并通過實驗表明了基于啟發式動態規劃的方法使得機器人具有更好的適應能力。游曉明[8]定義了一種新的動態搜索誘導算子，并對動態搜索模型進行了定義，通過設計較大的閾值來增加多樣性，同時利用衰減模型調整來加快算法收斂。

由于現實世界的機器人規劃場景通常是動態變化的，因此，機器人規劃通常要采用在線方法來尋求。本文通過離策略的強化學習算法來動態更新路徑上各個位置點的信息素，然后通過蟻群算法來基于信息素尋求初始位置到目標位置的最優路徑。通過機器人路徑規劃的仿真實例，對所提的方法進行驗證，結果表明所提的方法能滿足動態在線規劃的需求，具有很強的適應能力。

2 機器人規劃模型

機器人規劃的環境場景首先需要被建模，使機器人可以對環境場景進行更為精確的表示。本文采用柵格對機器人規劃的二維環境進行建模。在機器人規劃環境場景中，障礙物、初始位置和目標都是初始時刻確定的，一旦確定則在規劃的整個過程中均不會發生變化。

在對二維環境場景進行柵格化的過程中，可以通過對x軸方向和y軸方向分別進行等分來進行柵格化。圖1是對一個二維的環境場景進行柵格化的圖，其中黑色填充部分為障礙物，而其它坐標則是對場景進行柵格化的結果。

圖1 環境場景柵格化圖

圖2 仿真場景設置

3 基于蟻群算法的機器人路徑規劃

3.1 蟻群算法

蟻群算法是Dorigo M[9]提出的一種蟻群系統算法，其主要思想是通過對螞蟻行走路徑上信息素進行實時更新，通過強化最優信息反饋加快算法的收斂。目前蟻群算法已經廣泛應用于旅行商問題、車間調度問題、無線傳感器路由控制問題以及機器人路徑規劃問題中。

經典的蟻群算法在通過正反饋機制尋求最優路徑的同時，也會導致蟻群多樣性缺失，使得全局搜索能力大為減弱。本文對蟻群算法的改進主要分為兩個方向：(1)對蟻群信息素的更新方法進行改進；(2)對蟻群算法中當前位置到下一位置的轉移概率進行改進。

3.2 蟻群信息素的更新

蟻群信息素通過離策略的學習算法進行實時更新，將路徑上任意一個柵格點的信息素作為離策略學習算法中的長期回報來求解。任意時刻、任意柵格上的信息素都會采用離策略學習算法來進行全局更新。

在采用離策略算法對蟻群信息素進行更新時，采用離策略算法中的Q學習算法對各位置的蟻群信息素進行更新。

立即獎賞函數的設置為：達到目標狀態后，獲得一個較大的正值為10的立即獎賞；而在其它位置獲得值為1的累積獎賞。

遷移函數的設置為：機器人向上移動時，x軸方向的坐標不變，而y軸方向的坐標加1；機器人向下移動時，x軸方向的坐標不變，而y軸方向的坐標減1；機器人向左移動時，x軸方向的坐標減1，而y軸方向的坐標不變；機器人向右移動時，x軸方向的坐標加1，而y軸方向的坐標不變。

算法1 基于離策略學習的信息素動態更新算法

輸入：探索因子ε，折扣率γ，步長因子α，情節最大數ET，每個情節包含的最大時間步ETS；

初始化：狀態空間X為所有柵格化的離散二維點，動作空間包含的動作有：向下(-1)，向上(+1)，向左(-2)，向右(+2)，原地(0)，初始化所有狀態動作處的Q值為0,即Q0(x,u)=0，初始化當前狀態x=x0；

Repeat(ET)

Loop(ETS)

(2)根據ε的值，以1-ε的概率選擇最優動作a，以ε的概率選擇其它動作；

(3)基于選擇的動作和當前的狀態，根據遷移函數將當前狀態遷移到后續狀態x′，并根據獎賞函數獲得立即獎賞r；

(5)更新當前狀態：x←x′；

(7)更新下一個狀態處執行的動作：a←a′；

(8)更新當前時步；

End Loop

更新當前情節

End Repeat

輸出：各狀態動作處的Q值

3.3 改進的轉移概率

為了增加多樣性，在轉移概率的基礎上加入隨機選擇機制，如同離策略學習中的ε。設定隨機參數s∈(0,1)，對于每個時間步t產生的隨機數st∈(0,1)。當s≤st，必須通過計算轉移概率來確定下一個可以選擇的位置；當s≥st時，則查看當前位置旁邊所有的可達位置，除去障礙位置和已經過的位置，隨機選擇一個可行的位置作為下一個要達到的位置：

①

其中，rand(allowedt)表示可行位置從非障礙位置和未經過的位置集allowedt中選擇。

對于任意一個可行節點j，轉移概率可以表示為：

②

在式②中，τij(t)為當前位置i到下一個可行位置j的路徑ij上的信息素，這個信息素通過算法1來實時更新，而ηj為啟發式因子，ηj為節點j的被訪問的次數的倒數，即當下一個節點的訪問次數越多，該節點由于已經被充分探索，因此避免訪問該節點，以增加多樣性。a和β分別為信息素和啟發式信息的權重因子。

3.4 基于蟻群算法的機器人路徑規劃

本文提出的基于蟻群算法的機器人規劃算法對傳統蟻群算法的改進主要在于蟻群信息素更新方法和轉移概率，分別如前文3.2節和3.3節所示。

算法2 基于蟻群算法的機器人規劃算法

輸入：探索因子ε，折扣率γ，步長因子α，情節最大數ET，每個情節包含的最大時間步ETS，信息素權重因子a，啟發式信息的權重因子β，信息素的揮發因子ρ；

初始化：調用算法1求解出所有狀態動作對處的Q值，并用于初始化信息素τij；

Repeat(T輪迭代)

(1)螞蟻從初始位置出發；

(2)根據公式①，螞蟻計算出下一個可行的位置節點集合；

(3)根據公式②計算螞蟻轉移到下一個可行位置節點的概率，選擇概率最大的節點進行轉移；

(4)調用算法1來計算各節點的Q值，并用于更新各節點的信息素Δτij(t+1)；

(5)更新各節點的信息素：τij(t+1)=(1-ρ)*τij(t)+ρΔτij(t+1)，其中，τij(t+1)和τij(t)分別表示t+1時刻和t時刻時路徑ij上的信息素，Δτij(t+1)為t+1時刻通過算法1得到的實時信息素；

(6)更新當前迭代次數；

End Repeat

輸出：選擇從初始位置開始到目標位置中信息素最大的路徑

4 仿真實驗

在Matlab仿真環境下，對本文所提方法進行驗證。仿真場景如圖1所示，按圖1對場景進行柵格化后，但圖1并未標記初始位置和目標位置。因此，在對圖1標記了初始位置和目標狀態后，初始位置被標記為“Initial State”，其坐標位置為(1,1)，目標位置為“Goal”，其坐標位置為(5,7)。

仿真場景如圖2所示。仿真環境參數為：探索因子ε=0.05，折扣率γ=0.9，步長因子α=0.5，情節最大數ET=100，每個情節包含的最大時間步ETS=200，信息素權重因子a=0.5，啟發式信息的權重因子β=0.5，信息素的揮發因子ρ=0.4，最大迭代次數T=500。

將由本文方法得到的規劃仿真結果收斂性與文獻[2]中基于強化學習的機器人路徑規劃方法以及文獻[8]所示的基于蟻群算法的機器人路徑規劃方法進行比較，得到的收斂結果如圖3所示。

圖3 簡單障礙物環境下收斂曲線

圖4 仿真得到的最優路徑

從圖3中可以看出，本文方法在第10個情節左右就開始趨于收斂，收斂的解為11個時間步；文獻[2]方法直接采用強化學習算法來尋求最優解，但在40個情節時才開始收斂，且收斂解為12個時間步；文獻[8]方法在第125個情節時收斂，收斂的時間步為11個時間步。

本文方法得到的最優路徑，從初始位置到目標位置的最優路徑一共包含兩條，如圖4所示，其中實心三角形組成的路徑為其中一條最優路徑，另一條最優路徑從初始位置縱坐標5處仍然由實心三角形構成，而另一段路徑由空心三角形構成。

5 結語

為了實現機器人的在線實時路徑規劃，本文提出一種基于蟻群優化和離策略學習的機器人規劃方法。首先，提出了機器人規劃模型，并采用柵格法對環境場景進行離散化；然后，設計了基于離策略學習算法的蟻群信息素初始化和更新方法；最后，提出了一種基于蟻群算法的機器人路徑規劃算法。對兩個算法均進行了定義和描述。仿真實驗證明，本文方法具有收斂速度快和收斂精度高的優點，具有很強的適應能力。