引言

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://forexkbc.com/resource/share/2000006161

作者信息：

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

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