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