基于多智能體協(xié)同強化學習的多目標追蹤方法

王毅然,經(jīng)小川,,賈福凱,孫宇健,佟 軼

(1.中國航天系統(tǒng)科學與工程研究院,北京 100048; 2.航天宏康智能科技(北京)有限公司,北京 100048)

0 概述

隨著人工智能技術(shù)的不斷發(fā)展,多智能體協(xié)同控制在軍事應(yīng)用中取得了重大突破[1-2],以無人機、無人車[3]和無人水面艇等為代表的無人智能體在執(zhí)行軍事作戰(zhàn)中的偵察、護航、打擊等任務(wù)時[4-6]通常以追蹤問題為基礎(chǔ)開展研究。而在現(xiàn)代戰(zhàn)場環(huán)境下,由于任務(wù)和環(huán)境的復雜性,一般需要多個作戰(zhàn)智能體協(xié)同完成對多個動態(tài)運動目標的追蹤任務(wù),因此智能體面對動態(tài)變化的戰(zhàn)場態(tài)勢,如何進行任務(wù)分工及采取何種行動策略將會影響智能體的作戰(zhàn)質(zhì)量和作戰(zhàn)效率。

針對多目標追蹤問題,學者們進行了大量研究并取得一定的成果。文獻[7]提出一種合作團隊追蹤單一運動目標的方法,針對運動目標位置估計的不確定性,最大限度地縮小目標可到達空間。仿真結(jié)果表明,在位置不確定的情況下,該方法能通過追蹤智能體捕獲目標。文獻[8]提出基于軌跡集和隨機有限集的多目標追蹤問題求解方法,通過多對象密度函數(shù)確定測量值的貝葉斯軌跡分布,其中包含所有軌跡的信息。

強化學習主要解決智能決策問題,其目前在單智能體決策領(lǐng)域取得了較大成功,如AlphaGo、AlphaGo Zero等。針對團隊最優(yōu)決策問題,學者們主要通過基于價值函數(shù)和概率這兩種方法將單智能體強化學習擴展到多智能體強化學習。文獻[9-11]基于價值函數(shù)的方法,采用Q-learning、DQN和IQL算法并結(jié)合獎勵函數(shù),仿真模擬了在完全協(xié)作、完全競爭及非完全協(xié)作/競爭環(huán)境下多個智能體的性能表現(xiàn)。但是,當環(huán)境較復雜及智能體規(guī)模較大時,上述算法的穩(wěn)定性和可擴展性較差,且難以應(yīng)對較大的連續(xù)動作空間,無法輸出離散狀態(tài)動作值。文獻[12-14]基于概率的方法提出深度確定性策略梯度(Deep Deterministic Policy Gradient,DDPG)算法,在動作輸出方面通過網(wǎng)絡(luò)擬合策略函數(shù)并直接輸出動作值,可應(yīng)對更大的動作空間以及連續(xù)動作的輸出。針對上述方法存在的學習時間長、實時性差等問題,本文提出一種基于多智能體協(xié)同強化學習的多目標追蹤方法(Multi-Target Tracking method based on Multi-Agent Collaborative Reinforcement Learning,MTT-MACRL)。

1 多目標追蹤問題

1.1 問題描述

多目標追蹤問題涉及追蹤和目標智能體兩方面,其主要的研究目標為多個自主追蹤智能體的協(xié)同追蹤策略[15-17]。目前,關(guān)于追蹤問題的描述不一,本文將追蹤問題定義為:假設(shè)在相同的有限二維空間內(nèi)存在np個追蹤智能體,則追蹤智能體集合P={P1,P2,…,Pnp},假設(shè)在相同有限二維空間內(nèi)存在ne個目標智能體,則目標智能體集合E={E1,E2,…,Ene},追蹤智能體和目標智能體統(tǒng)稱為智能體A,A=P∪E。OPi(i=1,2,…,np)代表追蹤智能體Pi的中心,OEj(j=1,2,…,ne)代表目標智能體Ej的中心,VPi(i=1,2,…,np)代表追蹤智能體Pi的運動速度,VEj(j=1,2,…,ne)代表目標智能體Ej的運動速度。

圖1 多智能體追蹤示意圖

1.2 多目標追蹤方法框架

多目標追蹤方法主要包括環(huán)境建模、任務(wù)分配和追蹤策略學習3個方面,具體框架如圖2所示。先對追蹤智能體、目標智能體、障礙數(shù)量及位置等環(huán)境信息進行建模,將追蹤智能體、目標智能體作為多智能體多目標任務(wù)分配算法的輸入,經(jīng)過計算得到各個智能體的任務(wù)分配結(jié)果。根據(jù)各個智能體的任務(wù)分配結(jié)果和環(huán)境信息,對其進行獎勵函數(shù)設(shè)置。在每一個時間步長中,各個智能體根據(jù)觀察到的環(huán)境信息采取相應(yīng)行動作用于環(huán)境,使得環(huán)境的狀態(tài)發(fā)生變化,同時通過獎勵函數(shù)從環(huán)境中獲得獎勵反饋并進行學習更新策略,然后多個智能體根據(jù)觀察新的環(huán)境狀態(tài)采取行動從中獲得獎勵再進行學習。重復上述過程,通過不斷優(yōu)化決策并更新策略庫得到最優(yōu)策略或較優(yōu)策略。

圖2 多目標追蹤方法框架

2 基于多智能體協(xié)同強化學習的多目標追蹤

2.1 多智能體多目標任務(wù)分配算法

在多智能體多目標追蹤問題中,多個智能體需要通過協(xié)調(diào)與協(xié)作完成對多個運動目標的追蹤任務(wù)。本文假設(shè)多個智能體之間能夠進行交流與通信,同時可獲取各個運動目標的位置,以縮短目標智能體的總追蹤路徑為優(yōu)化目標,根據(jù)參與任務(wù)的智能體數(shù)目與運動目標數(shù)目建立以下任務(wù)分配模型:

1)當追蹤智能體數(shù)目與目標智能體數(shù)目相同時,即np=ne,其數(shù)學模型為:

xPiEj=0或1,i=1,2…,np,j=1,2,…,ne

2)當追蹤智能體數(shù)目小于目標智能體數(shù)目時,即np

xPiEj=0或1,i=1,2…,np,j=1,2,…,ne

3)當追蹤智能體數(shù)目大于目標智能體數(shù)目時,即np>ne,其數(shù)學模型為:

xPiEj=0或1,i=1,2…,np,j=1,2,…,ne

多智能體多目標任務(wù)分配算法具體步驟如下:

步驟1初始化追蹤智能體數(shù)目np、各個追蹤智能體的位置Xp(t0)、目標智能體數(shù)目ne以及各個目標智能體的位置Xe(t0)。

步驟2依次計算追蹤智能體與每個目標智能體之間的距離dPiEj組成距離效益矩陣D,計算公式為:

步驟3當追蹤智能體數(shù)目np等于目標智能體數(shù)目ne時轉(zhuǎn)步驟4;當追蹤智能體數(shù)目np小于目標智能體數(shù)目ne時轉(zhuǎn)步驟5;當追蹤智能體數(shù)目np大于目標智能體數(shù)目ne時轉(zhuǎn)步驟6。

步驟4運用匈牙利算法根據(jù)距離效益矩陣D對多個智能體的任務(wù)分配模型進行求解,轉(zhuǎn)步驟7。

步驟5虛擬增加(ne-np)個追蹤智能體,采用加邊補零法將該非標準指派問題轉(zhuǎn)化為標準指派問題,并利用匈牙利算法對多個智能體的任務(wù)分配模型進行求解,轉(zhuǎn)步驟7。

步驟6虛擬增加(np-ne)個目標智能體,采用加邊補零法將該非標準指派問題轉(zhuǎn)化為標準指派問題,并利用匈牙利算法對多個智能體的任務(wù)分配模型求解,轉(zhuǎn)步驟7。

步驟7輸出多個追蹤智能體的任務(wù)分配結(jié)果,算法結(jié)束。

2.2 多智能體協(xié)同強化學習算法

2.2.1 狀態(tài)和動作設(shè)置

在多智能體追蹤問題中,每個智能體的行為都會導致環(huán)境狀態(tài)的改變進而影響其他智能體的行動。多個智能體之間存在合作關(guān)系或競爭關(guān)系,每個智能體所獲得的回報不僅與自身動作有關(guān),而且與其他智能體的動作有關(guān)[18-20]。

在本文二維平面空間的多目標追蹤問題中,任意時刻的狀態(tài)可以表示為s={X,V},其中,X表示各個智能體的初始位置及障礙等的位置信息,V表示各個智能體的運動速度。智能體的動作空間為智能體在二維平面空間(x,y)中任意方向移動的距離。

2.2.2 獎勵函數(shù)設(shè)置

2.3 多目標追蹤方法

本文采用多智能體多目標任務(wù)分配算法和多智能體協(xié)同強化學習算法進行多目標追蹤,其核心工作包括:1)根據(jù)環(huán)境中各個追蹤智能體以及目標智能體的位置信息,運用多智能體多目標任務(wù)分配算法確定多個智能體的任務(wù)分配結(jié)果;2)根據(jù)不同智能體的任務(wù)分配結(jié)果以及環(huán)境中的其他信息(如障礙位置、環(huán)境邊界等)設(shè)計相應(yīng)的學習模型,多個智能體與仿真環(huán)境交互并將其經(jīng)驗數(shù)據(jù)存儲至樣本池中,然后從樣本池中隨機取出一定數(shù)量的樣本進行學習同時更新策略。在多個智能體的學習任務(wù)中,所有智能體的策略由參數(shù)θ={θ1,θ2,…,θn}確定,其策略集合π={π1,π2,…,πn},則單智能體i的期望收益梯度為:

(1)

(2)

(3)

其中:

(4)

多目標追蹤的具體步驟如下:

1)參數(shù)初始化,設(shè)置環(huán)境的范圍邊界及追蹤智能體、目標智能體及障礙的數(shù)量、位置、速度等信息以及樣本池M的容量K和總訓練回合數(shù)N。

2)根據(jù)任務(wù)目標設(shè)置智能體的獎勵函數(shù)和動作空間。

3)設(shè)置初始訓練回合數(shù)Episode=0、最小取樣樣本數(shù)Ns和已存儲樣本池數(shù)量Nb。

4)判斷訓練回合數(shù)Episode是否小于N,如果是,則執(zhí)行下一步;否則算法結(jié)束。

5)根據(jù)當前狀態(tài)st,每個智能體遵循當前策略選擇動作ai。

6)執(zhí)行動作a=(a1,a2,…),各個智能體得到獎勵值ri,同時達到新的狀態(tài)st+1。

7)存儲(st,a,r,st+1)至樣本池M,Nb←Nb+1。

8)判斷Ns是否小于Nb,若是,則跳轉(zhuǎn)至步驟11;否則執(zhí)行步驟9。

9)對于每個智能體而言,隨機從樣本池M中取Ns個樣本,根據(jù)式(4)計算yj,并利用式(2)和式(3)分別更新actor網(wǎng)絡(luò)和critic網(wǎng)絡(luò)。

10)更新目標網(wǎng)絡(luò)。

11)賦值更新st←st+1,訓練回合數(shù)Episode←Episode+1,返回步驟4。

3 實驗結(jié)果與分析

3.1 實驗設(shè)置

為驗證本文MTT-MACRL方法的可行性和有效性,在同一實驗環(huán)境下將本文MTT-MACRL方法與DDPG方法[14]和MADDPG方法[21]進行對比。實驗場景設(shè)置如圖3所示,實驗環(huán)境為連續(xù)的二維平面空間,其中存在3個追蹤智能體、3個目標智能體和1個障礙,在同一離散時間內(nèi)3個追蹤智能體與3個目標智能體同時運動,由于目標智能體被限制在該環(huán)境中,因此追蹤智能體可以追蹤到目標智能體。在上述實驗場景中的參數(shù)設(shè)置如表1所示。

圖3 實驗場景

表1 參數(shù)設(shè)置

3.2 結(jié)果分析

3.2.1 學習速度和實時性對比

在多智能體追蹤問題中,追蹤智能體主要學習如何快速接近目標智能體以完成對多個目標智能體的追蹤任務(wù)。圖4為10 000個訓練回合中,DDPG方法[14]、MADDPG方法[21]以及本文MTT-MACRL方法的目標智能體在平均每100個訓練回合中被追蹤到的總次數(shù)與訓練回合數(shù)的關(guān)系。

圖4 目標智能體被追蹤到的總次數(shù)

可以看出,在10 000個訓練回合中,本文MTT-MACRL方法平均每100個訓練回合成功追蹤到目標智能體的總次數(shù)為239次,DDPG方法和MADDPG方法平均每100個訓練回合成功追蹤到目標智能體的總次數(shù)分別為158次、153次。當平均每100個訓練回合成功追蹤到目標智能體的總次數(shù)達到145次時,運用本文MTT-MACRL方法、DDPG方法和MADDPG方法至少分別需要進行2 500個、8 000個和7 600個訓練回合。綜上所述,本文MTT-MACRL方法相比其他兩種方法,學習速度更快,能夠根據(jù)智能體的位置快速執(zhí)行有效策略,且實時性更好。

3.2.2 有效性驗證

為驗證本文MTT-MACRL方法的有效性,將其與DDPG方法和MADDPG方法的學習策略分別在上述場景中進行3次實驗。在每次實驗中,追蹤智能體和目標智能體的位置為隨機生成,每個訓練回合的最大時間步長為50步,共進行1 000個回合的測試,并統(tǒng)計3次實驗中每個目標智能體被追蹤到的次數(shù)以及所有目標智能體被追蹤到的總次數(shù),具體情況如表2～表4所示。

表2 第1次實驗中追蹤到目標智能體的總次數(shù)

表3 第2次實驗中追蹤到目標智能體的總次數(shù)

表4 第3次實驗中追蹤到目標智能體的總次數(shù)

在3次實驗中,采用DDPG方法、MADDPG方法以及本文MTT-MACRL方法得到目標智能體被追蹤到的總次數(shù)如圖5所示?？梢缘贸?利用DDPG方法、MADDPG方法和本文MTT-MACRL方法平均每次實驗追蹤到目標智能體的總次數(shù)分別為2 605次、2 650次和3 605次。本文MTT-MACRL方法對于目標智能體的成功追蹤次數(shù)相比DDPG方法和MADDPG方法分別提高了38.39%和36.04%。

圖5 3次實驗中目標智能體被追蹤到的總次數(shù)

3.2.3 協(xié)同情況對比

通過DDPG方法和MADDPG方法得到不同時刻追蹤智能體及目標智能體的位置分布情況,如圖6和圖7所示。可以看出,多個追蹤智能體未進行相互合作且出現(xiàn)了多個目標智能體同時追蹤同一個目標智能體的情況,因此造成某一個目標智能體無智能體追蹤,不能快速有效地完成追蹤任務(wù)。

圖6 DDPG方法在不同時刻的智能體位置分布情況

圖7 MADDPG方法在不同時刻的智能體位置分布情況

通過本文MTT-MACRL方法得到不同時刻追蹤智能體及目標智能體的位置分布情況,如圖8所示?？梢钥闯?多個追蹤智能體經(jīng)過學習訓練能夠與其他智能體相互協(xié)作進行任務(wù)分配,保證一個追蹤智能體對應(yīng)一個目標智能體。同時,根據(jù)追蹤智能體與目標智能體的位置信息能夠?qū)崟r更新任務(wù)分配情況,保證參與追蹤任務(wù)的智能體的總追蹤路徑最短。

圖8 MTT-MACRL方法在不同時刻的智能體位置分布情況

4 結(jié)束語

本文提出一種基于多智能體協(xié)同強化學習的多目標追蹤方法。根據(jù)追蹤和目標智能體數(shù)目及其位置信息建立任務(wù)分配模型,運用匈牙利算法對其進行求解得到多個追蹤智能體的任務(wù)分配情況,并結(jié)合環(huán)境信息為多個追蹤智能體設(shè)置獎勵函數(shù),同時通過多智能體協(xié)同強化學習算法使其在復雜環(huán)境中不斷重復執(zhí)行探索-積累-學習-決策過程,最終從經(jīng)驗數(shù)據(jù)中學習決策策略完成多目標追蹤任務(wù)。實驗結(jié)果表明,與DDPG方法和MADDPG方法相比,本文方法的學習速度更快,且多個智能體通過相互協(xié)作能更有效地追蹤目標智能體。