《電子技術應用》
您所在的位置：首頁 > 人工智能 > 設計應用 > 基于模仿學習和強化學習的啟發(fā)式多智能體路徑規(guī)劃
基于模仿學習和強化學習的啟發(fā)式多智能體路徑規(guī)劃
網(wǎng)絡安全與數(shù)據(jù)治理
郭傳友，劉志飛，田景志，劉先忠
中國人民解放軍61150部隊
摘要： 多智能體路徑規(guī)劃（Multi-Agent Path Finding, MAPF）擴展到大型動態(tài)環(huán)境中是一個越來越有挑戰(zhàn)的問題。現(xiàn)實世界中，環(huán)境動態(tài)變化往往需要實時重新規(guī)劃路徑。在部分可觀察環(huán)境中，使用強化學習方法學習分散的策略解決MAPF問題表現(xiàn)出較大潛力。針對智能體之間如何學會合作和環(huán)境獎勵稀疏問題，提出基于模仿學習和強化學習的啟發(fā)式多智能體路徑規(guī)劃算法。實驗表明，該方法在高密度障礙環(huán)境中具有較好的性能和擴展性。
中圖分類號：TP181文獻標識碼：ADOI:10.19358/j.issn.2097-1788.2024.09.006
引用格式：郭傳友，劉志飛，田景志，等.基于模仿學習和強化學習的啟發(fā)式多智能體路徑規(guī)劃［J］.網(wǎng)絡安全與數(shù)據(jù)治理，2024，43（9）：33-40.
Heuristic multi-agent path finding VIA imitation learning and reinforcement learning
Guo Chuanyou，Liu Zhifei，Tian Jingzhi，Liu Xianzhong
Chinese People′s Liberation Army 61150 Unit
Abstract： The extension of multi-agent path finding(MAPF) to large-scale dynamic environment is an increasingly challenging problem. In the real world, dynamic changes in the environment often require real-time re planning. Using reinforcement learning method to learn decentralized strategies in some observable environments shows great potential to solve MAPF problems. A heuristic multi-agent path planning algorithm based on imitation learning and reinforcement learning is proposed to address the problems of how intelligent agents learn to cooperate and sparse environmental rewards. Experiments show that this method has good performance and scalability in high-density obstacle environment.
Key words : multi-agent path finding; reinforcement learning; imitation learning; heuristic

引言

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

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

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

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

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

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

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

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


本文詳細內(nèi)容請下載：

http://ihrv.cn/resource/share/2000006161


作者信息：

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

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


Magazine.Subscription.jpg

此內(nèi)容為AET網(wǎng)站原創(chuàng)，未經(jīng)授權禁止轉(zhuǎn)載。