引言

MAPF是對(duì)不同起始位置的多個(gè)智能體到他們各自目標(biāo)位置的路徑規(guī)劃問題，關(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展開研究［8-11］,，MAPF取得了突破性進(jìn)展，尤其是基于強(qiáng)化學(xué)習(xí)(Reinforcement Learning, RL)方法應(yīng)用到MAPF問題中取得了較好效果,，國(guó)內(nèi)對(duì)MAPF問題的研究也越來(lái)越濃厚,。

求解MAPF的最優(yōu)解已經(jīng)被證明是NPHard問題［12］。傳統(tǒng)方法將MAPF規(guī)約為其他已解決的問題如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問題,，而且規(guī)劃效率和質(zhì)量較高,，但這些集中式規(guī)劃算法不能實(shí)時(shí)規(guī)劃路徑，可擴(kuò)展性差,。最近,，分散式執(zhí)行的強(qiáng)化學(xué)習(xí)方法應(yīng)用于解決MAPF問題表現(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í)速度較慢,。為了解決上述問題，本文提出了基于強(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)