趙廣復，方加娟

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

1 研究背景

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

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

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

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

2 機器人規(guī)劃模型

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

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

圖1 環(huán)境場景柵格化圖

圖2 仿真場景設置

3 基于蟻群算法的機器人路徑規(guī)劃

3.1 蟻群算法

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

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

3.2 蟻群信息素的更新

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

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

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

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

算法1 基于離策略學習的信息素動態(tài)更新算法

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

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

Repeat(ET)

Loop(ETS)

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

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

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

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

(8)更新當前時步；

End Loop

更新當前情節(jié)

End Repeat

輸出：各狀態(tài)動作處的Q值

3.3 改進的轉(zhuǎn)移概率

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

①

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

對于任意一個可行節(jié)點j，轉(zhuǎn)移概率可以表示為：

②

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

3.4 基于蟻群算法的機器人路徑規(guī)劃

本文提出的基于蟻群算法的機器人規(guī)劃算法對傳統(tǒng)蟻群算法的改進主要在于蟻群信息素更新方法和轉(zhuǎn)移概率，分別如前文3.2節(jié)和3.3節(jié)所示。

算法2 基于蟻群算法的機器人規(guī)劃算法

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

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

Repeat(T輪迭代)

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

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

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

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

(5)更新各節(jié)點的信息素：τ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)更新當前迭代次數(shù)；

End Repeat

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

4 仿真實驗

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

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

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

圖3 簡單障礙物環(huán)境下收斂曲線

圖4 仿真得到的最優(yōu)路徑

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

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

5 結語

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