引用格式:郭傳友,,劉志飛,,田景志,等.基于模仿學(xué)習(xí)和強(qiáng)化學(xué)習(xí)的啟發(fā)式多智能體路徑規(guī)劃[J].網(wǎng)絡(luò)安全與數(shù)據(jù)治理,,2024,,43(9):33-40.
引言
MAPF是對(duì)不同起始位置的多個(gè)智能體到他們各自目標(biāo)位置的路徑規(guī)劃問(wèn)題,關(guān)鍵約束是在保證智能體之間互相不碰撞的前提下到達(dá)目標(biāo)位置,,并保證路徑規(guī)劃的速度和質(zhì)量,。MAPF在實(shí)際場(chǎng)景中有許多應(yīng)用,如大型倉(cāng)庫(kù)管理[1-2],、數(shù)字游戲[3],、火車(chē)調(diào)度[4]、城市道路網(wǎng)絡(luò)[5]、多機(jī)器人系統(tǒng)[6]等,,更多實(shí)際應(yīng)用可參考文獻(xiàn)[7],。近年來(lái),越來(lái)越多的團(tuán)隊(duì)對(duì)MAPF展開(kāi)研究[8-11],,MAPF取得了突破性進(jìn)展,,尤其是基于強(qiáng)化學(xué)習(xí)(Reinforcement Learning, RL)方法應(yīng)用到MAPF問(wèn)題中取得了較好效果,國(guó)內(nèi)對(duì)MAPF問(wèn)題的研究也越來(lái)越濃厚,。
求解MAPF的最優(yōu)解已經(jīng)被證明是NPHard問(wèn)題[12],。傳統(tǒng)方法將MAPF規(guī)約為其他已解決的問(wèn)題如SAT[13],或使用基于搜索的算法來(lái)解決,經(jīng)典方法有增強(qiáng)的搜索[14],、基于沖突的搜索[15]以及改進(jìn)的變體[16]等,。然而,隨著環(huán)境的動(dòng)態(tài)變化和智能體數(shù)量的增加,,搜索空間巨大對(duì)傳統(tǒng)MAPF算法構(gòu)成挑戰(zhàn),。基于搜索的MAPF算法通過(guò)引入優(yōu)先規(guī)劃,、大領(lǐng)域搜索和復(fù)雜的啟發(fā)式函數(shù)來(lái)優(yōu)化改進(jìn)MAPF算法,,前沿的算法有EECBS[17]、CCBS[18],、MOA*[19],、MAPFMLLNS[20]。這些算法能解決3 000多個(gè)智能體規(guī)模的MAPF問(wèn)題,,而且規(guī)劃效率和質(zhì)量較高,,但這些集中式規(guī)劃算法不能實(shí)時(shí)規(guī)劃路徑,可擴(kuò)展性差,。最近,,分散式執(zhí)行的強(qiáng)化學(xué)習(xí)方法應(yīng)用于解決MAPF問(wèn)題表現(xiàn)出較大的潛力,每個(gè)智能體根據(jù)局部觀察分散執(zhí)行策略,。
RL智能體在大型環(huán)境中和環(huán)境互動(dòng)時(shí),,只有達(dá)到目標(biāo)才可以獲取獎(jiǎng)勵(lì),而到達(dá)目標(biāo)的過(guò)程中獎(jiǎng)勵(lì)稀疏,,學(xué)習(xí)效率不高,,訓(xùn)練時(shí)間長(zhǎng),智能體還可能陷入死胡同,。PRIMAL(Pathfinding via Reinforcement and Imitation MultiAgent Learning)[21]采取集中式MAPF規(guī)劃器生成專(zhuān)家演示路徑,,訓(xùn)練過(guò)程中結(jié)合了模仿學(xué)習(xí)和強(qiáng)化學(xué)習(xí),加速了學(xué)習(xí)過(guò)程,,但計(jì)算比較耗時(shí),,求解質(zhì)量還需提高,。G2RL(Globally Guided RL)[22]給予每個(gè)智能體額外的獎(jiǎng)勵(lì)遵循單智能體最短路徑,但這可能會(huì)誤導(dǎo)智能體,,因?yàn)榈竭_(dá)目標(biāo)位置的路徑不是唯一的,,這會(huì)影響智能體和其他智能體之間的協(xié)調(diào)合作。DHC(Distributed Heuristic multiagent path finding with Communication)[23]使用多條潛在路徑作為智能體路徑的啟發(fā)式輸入,,并采用圖卷積網(wǎng)絡(luò)來(lái)加強(qiáng)智能體之間的通信,,促進(jìn)智能體之間的顯式協(xié)調(diào),但學(xué)習(xí)速度較慢,。為了解決上述問(wèn)題,,本文提出了基于強(qiáng)化學(xué)習(xí)和模仿學(xué)習(xí)的啟發(fā)式多智能體路徑規(guī)劃算法(Heuristic multi-agent path planning via Imitation and Reinforcement Learning, HIRL),在智能體的觀察中加入額外的目標(biāo)向量,,并嵌入從目標(biāo)源到智能體的多條潛在最短路徑作為神經(jīng)網(wǎng)絡(luò)的輸入,,使用模仿學(xué)習(xí)來(lái)促進(jìn)智能體之間的隱式協(xié)調(diào),引入目標(biāo)牽引的獎(jiǎng)勵(lì)函數(shù)來(lái)鼓勵(lì)智能體進(jìn)行有效的探索,,當(dāng)智能體向目標(biāo)方向移動(dòng)時(shí)給予正獎(jiǎng)勵(lì),。智能體依據(jù)自己的局部觀察來(lái)做出決策,不需要學(xué)習(xí)聯(lián)合動(dòng)作值,,因此具有很好的可擴(kuò)展性,。本文采用的主要方法如下:
(1)采用模仿學(xué)習(xí)框架加速智能體學(xué)習(xí),促進(jìn)智能體之間的隱式協(xié)調(diào),,而不需要智能體之間的顯式通信,。
(2)采用智能體到目標(biāo)位置的方向向量作為智能體觀察的額外信息。
(3)引入目標(biāo)牽引的獎(jiǎng)勵(lì)函數(shù),,鼓勵(lì)智能體朝著目標(biāo)方向進(jìn)行有效的探索,。
(4)嵌入了從目標(biāo)源到智能體多條最短路徑作為神經(jīng)網(wǎng)絡(luò)的輸入,能更有效地避免智能體之間的沖突和死鎖情況發(fā)生,。
(5)使用部分可觀察的環(huán)境,智能體根據(jù)有限視野的觀察決策行動(dòng),,更加符合現(xiàn)實(shí)世界的環(huán)境,。
本文詳細(xì)內(nèi)容請(qǐng)下載:
http://forexkbc.com/resource/share/2000006161
作者信息:
郭傳友,劉志飛,,田景志,,劉先忠
(中國(guó)人民解放軍61150部隊(duì),陜西榆林719000)