引言

MAPF是對不同起始位置的多個智能體到他們各自目標位置的路徑規劃問題，關鍵約束是在保證智能體之間互相不碰撞的前提下到達目標位置，并保證路徑規劃的速度和質量。MAPF在實際場景中有許多應用，如大型倉庫管理［1-2］、數字游戲［3］、火車調度［4］、城市道路網絡［5］、多機器人系統［6］等，更多實際應用可參考文獻［7］。近年來，越來越多的團隊對MAPF展開研究［8-11］，MAPF取得了突破性進展，尤其是基于強化學習(Reinforcement Learning, RL)方法應用到MAPF問題中取得了較好效果，國內對MAPF問題的研究也越來越濃厚。

求解MAPF的最優解已經被證明是NPHard問題［12］。傳統方法將MAPF規約為其他已解決的問題如SAT［13］,或使用基于搜索的算法來解決，經典方法有增強的搜索［14］、基于沖突的搜索［15］以及改進的變體［16］等。然而，隨著環境的動態變化和智能體數量的增加，搜索空間巨大對傳統MAPF算法構成挑戰。基于搜索的MAPF算法通過引入優先規劃、大領域搜索和復雜的啟發式函數來優化改進MAPF算法，前沿的算法有EECBS［17］、CCBS［18］、MOA*［19］、MAPFMLLNS［20］。這些算法能解決3 000多個智能體規模的MAPF問題，而且規劃效率和質量較高，但這些集中式規劃算法不能實時規劃路徑，可擴展性差。最近，分散式執行的強化學習方法應用于解決MAPF問題表現出較大的潛力，每個智能體根據局部觀察分散執行策略。

RL智能體在大型環境中和環境互動時，只有達到目標才可以獲取獎勵，而到達目標的過程中獎勵稀疏，學習效率不高，訓練時間長，智能體還可能陷入死胡同。PRIMAL(Pathfinding via Reinforcement and Imitation MultiAgent Learning)［21］采取集中式MAPF規劃器生成專家演示路徑，訓練過程中結合了模仿學習和強化學習，加速了學習過程，但計算比較耗時，求解質量還需提高。G2RL(Globally Guided RL)［22］給予每個智能體額外的獎勵遵循單智能體最短路徑，但這可能會誤導智能體，因為到達目標位置的路徑不是唯一的，這會影響智能體和其他智能體之間的協調合作。DHC(Distributed Heuristic multiagent path finding with Communication)［23］使用多條潛在路徑作為智能體路徑的啟發式輸入，并采用圖卷積網絡來加強智能體之間的通信，促進智能體之間的顯式協調，但學習速度較慢。為了解決上述問題，本文提出了基于強化學習和模仿學習的啟發式多智能體路徑規劃算法(Heuristic multi-agent path planning via Imitation and Reinforcement Learning, HIRL)，在智能體的觀察中加入額外的目標向量，并嵌入從目標源到智能體的多條潛在最短路徑作為神經網絡的輸入，使用模仿學習來促進智能體之間的隱式協調，引入目標牽引的獎勵函數來鼓勵智能體進行有效的探索，當智能體向目標方向移動時給予正獎勵。智能體依據自己的局部觀察來做出決策，不需要學習聯合動作值，因此具有很好的可擴展性。本文采用的主要方法如下：

（1）采用模仿學習框架加速智能體學習，促進智能體之間的隱式協調，而不需要智能體之間的顯式通信。

（2）采用智能體到目標位置的方向向量作為智能體觀察的額外信息。

（3）引入目標牽引的獎勵函數，鼓勵智能體朝著目標方向進行有效的探索。

（4）嵌入了從目標源到智能體多條最短路徑作為神經網絡的輸入，能更有效地避免智能體之間的沖突和死鎖情況發生。

（5）使用部分可觀察的環境，智能體根據有限視野的觀察決策行動，更加符合現實世界的環境。

本文詳細內容請下載：

http://www.cowatch.cn/resource/share/2000006161

作者信息：

郭傳友，劉志飛，田景志，劉先忠

(中國人民解放軍61150部隊，陜西榆林719000)