基于蟻群優(yōu)化和離策略學(xué)習(xí)的機(jī)器人路徑規(guī)劃

趙廣復(fù)，方加娟

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

1 研究背景

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

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

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

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

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

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

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

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

圖2 仿真場景設(shè)置

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

3.1 蟻群算法

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

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

3.2 蟻群信息素的更新

蟻群信息素通過離策略的學(xué)習(xí)算法進(jìn)行實(shí)時(shí)更新，將路徑上任意一個(gè)柵格點(diǎn)的信息素作為離策略學(xué)習(xí)算法中的長期回報(bào)來求解。任意時(shí)刻、任意柵格上的信息素都會(huì)采用離策略學(xué)習(xí)算法來進(jìn)行全局更新。

在采用離策略算法對(duì)蟻群信息素進(jìn)行更新時(shí)，采用離策略算法中的Q學(xué)習(xí)算法對(duì)各位置的蟻群信息素進(jìn)行更新。

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

遷移函數(shù)的設(shè)置為：機(jī)器人向上移動(dòng)時(shí)，x軸方向的坐標(biāo)不變，而y軸方向的坐標(biāo)加1；機(jī)器人向下移動(dòng)時(shí)，x軸方向的坐標(biāo)不變，而y軸方向的坐標(biāo)減1；機(jī)器人向左移動(dòng)時(shí)，x軸方向的坐標(biāo)減1，而y軸方向的坐標(biāo)不變；機(jī)器人向右移動(dòng)時(shí)，x軸方向的坐標(biāo)加1，而y軸方向的坐標(biāo)不變。

算法1 基于離策略學(xué)習(xí)的信息素動(dòng)態(tài)更新算法

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

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

Repeat(ET)

Loop(ETS)

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

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

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

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

(8)更新當(dāng)前時(shí)步；

End Loop

更新當(dāng)前情節(jié)

End Repeat

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

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

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

①

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

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

②

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

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

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

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

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

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

Repeat(T輪迭代)

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

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

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

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

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

(6)更新當(dāng)前迭代次數(shù)；

End Repeat

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

4 仿真實(shí)驗(yàn)

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

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

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

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

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

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

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

5 結(jié)語

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