引言

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］、火車調(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)被證明是NPHard問(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)?；谒阉鞯腗APF算法通過(guò)引入優(yōu)先規(guī)劃、大領(lǐng)域搜索和復(fù)雜的啟發(fā)式函數(shù)來(lái)優(yōu)化改進(jìn)MAPF算法，前沿的算法有EECBS［17］、CCBS［18］、MOA*［19］、MAPFMLLNS［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 MultiAgent Learning)［21］采取集中式MAPF規(guī)劃器生成專家演示路徑，訓(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 multiagent 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://ihrv.cn/resource/share/2000006161

作者信息：

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

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