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

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

0 概述

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

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

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

1 多目標(biāo)追蹤問題

1.1 問題描述

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

圖1 多智能體追蹤示意圖

1.2 多目標(biāo)追蹤方法框架

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

圖2 多目標(biāo)追蹤方法框架

2 基于多智能體協(xié)同強(qiáng)化學(xué)習(xí)的多目標(biāo)追蹤

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

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

1)當(dāng)追蹤智能體數(shù)目與目標(biāo)智能體數(shù)目相同時(shí),即np=ne,其數(shù)學(xué)模型為:

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

2)當(dāng)追蹤智能體數(shù)目小于目標(biāo)智能體數(shù)目時(shí),即np

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

3)當(dāng)追蹤智能體數(shù)目大于目標(biāo)智能體數(shù)目時(shí),即np>ne,其數(shù)學(xué)模型為:

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

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

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

步驟2依次計(jì)算追蹤智能體與每個(gè)目標(biāo)智能體之間的距離dPiEj組成距離效益矩陣D,計(jì)算公式為:

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

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

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

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

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

2.2 多智能體協(xié)同強(qiáng)化學(xué)習(xí)算法

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

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

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

2.2.2 獎(jiǎng)勵(lì)函數(shù)設(shè)置

2.3 多目標(biāo)追蹤方法

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

(1)

(2)

(3)

其中:

(4)

多目標(biāo)追蹤的具體步驟如下:

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

2)根據(jù)任務(wù)目標(biāo)設(shè)置智能體的獎(jiǎng)勵(lì)函數(shù)和動(dòng)作空間。

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

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

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

6)執(zhí)行動(dòng)作a=(a1,a2,…),各個(gè)智能體得到獎(jiǎng)勵(lì)值ri,同時(shí)達(dá)到新的狀態(tài)st+1。

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)設(shè)置

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

圖3 實(shí)驗(yàn)場景

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

3.2 結(jié)果分析

3.2.1 學(xué)習(xí)速度和實(shí)時(shí)性對比

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

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

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

3.2.2 有效性驗(yàn)證

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

表2 第1次實(shí)驗(yàn)中追蹤到目標(biāo)智能體的總次數(shù)

表3 第2次實(shí)驗(yàn)中追蹤到目標(biāo)智能體的總次數(shù)

表4 第3次實(shí)驗(yàn)中追蹤到目標(biāo)智能體的總次數(shù)

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

圖5 3次實(shí)驗(yàn)中目標(biāo)智能體被追蹤到的總次數(shù)

3.2.3 協(xié)同情況對比

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

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

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

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

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

4 結(jié)束語

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