張義　郭坤

摘要：路徑規(guī)劃是人工智能領(lǐng)域的一個(gè)經(jīng)典問(wèn)題，在國(guó)防軍事、道路交通、機(jī)器人仿真等諸多領(lǐng)域有著廣泛應(yīng)用，然而現(xiàn)有的路徑規(guī)劃算法大多存在著環(huán)境單一、離散的動(dòng)作空間、需要人工構(gòu)筑模型的問(wèn)題。強(qiáng)化學(xué)習(xí)是一種無(wú)須人工提供訓(xùn)練數(shù)據(jù)自行與環(huán)境交互的機(jī)器學(xué)習(xí)方法，深度強(qiáng)化學(xué)習(xí)的發(fā)展更使得其解決現(xiàn)實(shí)問(wèn)題的能力得到進(jìn)一步提升，本文將深度強(qiáng)化學(xué)習(xí)的DDPG（Deep Deterministic Policy Gradient）算法應(yīng)用到路徑規(guī)劃領(lǐng)域，完成了連續(xù)空間、復(fù)雜環(huán)境的路徑規(guī)劃。

關(guān)鍵詞：路徑規(guī)劃;深度強(qiáng)化學(xué)習(xí);DDPG;ActorCritic;連續(xù)動(dòng)作空間

中圖分類(lèi)號(hào)： TP301.6? ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2021）04-0193-02

Abstract：Path planning is a classic problem in the field of artificial intelligence， which has been widely used in national defense， military， road traffic， robot simulation and other fields. However， most of the existing path planning algorithms have he problems of single environment， discrete action space， and need to build artificial models. Reinforcement learning is a machine learning method that interacts with the environment without providing training data manually， deep reinforcement learning more makes its ability to solve practical problems of the development of further ascension. In this paper， deep reinforcement learning algorithm DDPG （Deep Deterministic Policy Gradient） algorithm is applied in the field of path planning， which completes the task of path planning for continuous space， complex environment.

Key words：path planning;deep reinforcement learning; DDPG;Actor Critic;continuous action space

傳統(tǒng)算法如迪杰斯特拉算法[1]、A*算法[2]、人工勢(shì)場(chǎng)法[3]等。迪杰斯特拉算法是路徑規(guī)劃領(lǐng)域的經(jīng)典算法，由迪杰斯特拉于1959年提出，迪杰斯特拉算法遍歷環(huán)境中的諸節(jié)點(diǎn)，采用貪心策略，每次擴(kuò)展一個(gè)節(jié)點(diǎn)，遍歷結(jié)束可得起點(diǎn)到其余各點(diǎn)的最短路徑。A*算法在迪杰斯特拉算法的基礎(chǔ)上進(jìn)行了改進(jìn)，在節(jié)點(diǎn)擴(kuò)展時(shí)加入啟發(fā)式規(guī)則，使得模型可以更快地收斂。雖然A*算法在諸多領(lǐng)域得到了諸多應(yīng)用，但A*算法的應(yīng)用場(chǎng)景局限在離散空間內(nèi)。人工勢(shì)場(chǎng)法則模擬物理學(xué)中的電力勢(shì)場(chǎng)，在智能體與障礙之間設(shè)置斥力，智能體與目標(biāo)之間設(shè)置引力，智能體沿著合力方向到達(dá)目標(biāo)位置。勢(shì)場(chǎng)法可以完成連續(xù)空間的路徑規(guī)劃，然而各種場(chǎng)景的施力大小配比只能人工協(xié)調(diào)，最優(yōu)配置難以求得，這種問(wèn)題在復(fù)雜環(huán)境中尤為嚴(yán)重。強(qiáng)化學(xué)習(xí)是一種自主與環(huán)境交互的機(jī)器學(xué)習(xí)方式，強(qiáng)化學(xué)習(xí)無(wú)須人工提供訓(xùn)練數(shù)據(jù)，通過(guò)不斷與環(huán)境交互獲得不同的回報(bào)來(lái)使模型收斂[4]。Mnih V在2013提出的DQN[5]（DeepQNetwork）算法，為深度強(qiáng)化學(xué)習(xí)的發(fā)展奠定了基礎(chǔ)，自此不斷涌現(xiàn)出深度強(qiáng)化學(xué)習(xí)的諸多優(yōu)秀算法。DDPG[6]算法結(jié)合了DQN、ActorCritic、PolicyGrient等策略，首先將深度強(qiáng)化學(xué)習(xí)引入到連續(xù)空間領(lǐng)域[7]，本文采用DDPG算法實(shí)現(xiàn)連續(xù)復(fù)雜環(huán)境的路徑規(guī)劃。

1 基于DDPG算法的路徑規(guī)劃原理

1.1 DDPG算法

DDPG算法底層采用ActorCritic的結(jié)構(gòu)，其結(jié)構(gòu)圖如圖1所示。

將模型整體分為Actor和Critic兩部分，其中Actor為動(dòng)作生成模型，以當(dāng)前環(huán)境信息作為輸入，通過(guò)神經(jīng)網(wǎng)絡(luò)計(jì)算生成一個(gè)動(dòng)作值。Critic為評(píng)價(jià)模型，用以評(píng)價(jià)動(dòng)作生成模型在當(dāng)前環(huán)境下生成的動(dòng)作，Critic模型將輸出一個(gè)評(píng)價(jià)值，用以協(xié)助Actor模型的收斂。此外DDPG也采用了PolicyGrident的學(xué)習(xí)方式，不同于常見(jiàn)的概率梯度，DDPG采用一種確定性的策略梯度，根據(jù)Actor生成的動(dòng)作值直接選擇動(dòng)作，而非采用softmax的映射方式依概率選擇動(dòng)作。此外，DDPG采用DQN的結(jié)構(gòu)理念，設(shè)計(jì)兩個(gè)結(jié)構(gòu)相同參數(shù)異步更新的模型，利用時(shí)分誤差進(jìn)行模型更新[8]。對(duì)于Policy模型，采用式（1）所示的模型進(jìn)行更新。

本文為智能體配置掃描射線(xiàn)獲取環(huán)境信息，分別掃描環(huán)境中的墻體障礙、危險(xiǎn)區(qū)域和安全出口，在本文中，前方設(shè)置5條射線(xiàn)，后方設(shè)置2條射線(xiàn)，總共組成21維的數(shù)據(jù)作為環(huán)境輸入。

1.2 環(huán)境回報(bào)

為了驗(yàn)證本文算法處理復(fù)雜環(huán)境的能力，本文除了構(gòu)建簡(jiǎn)單的常見(jiàn)障礙之外，模擬環(huán)境中有某種險(xiǎn)情發(fā)生的場(chǎng)景，在環(huán)境中構(gòu)建了危險(xiǎn)區(qū)域。對(duì)于普通障礙，對(duì)智能體只起到障礙作用，而智能體接觸危險(xiǎn)區(qū)域?qū)?huì)死亡，回合結(jié)束，視為此次路徑規(guī)劃任務(wù)失敗。

為了使模型盡量在更少的決策次數(shù)內(nèi)到達(dá)目標(biāo)位置，設(shè)置智能體每多決策一步，給予一定的懲罰回報(bào)，設(shè)置Rstep=-1 對(duì)于普通的墻體障礙，對(duì)智能體只起到障礙作用，但是仍需防止智能體出現(xiàn)“撞墻”的行為，因此設(shè)置Rwall=-1 對(duì)于危險(xiǎn)區(qū)域，智能體應(yīng)該避開(kāi)，設(shè)置Rdagenr =-50 安全出口為智能體的最終目標(biāo)，應(yīng)該設(shè)置全局最優(yōu)回報(bào)，本文結(jié)合經(jīng)驗(yàn)與多次試驗(yàn)結(jié)論，設(shè)定Rtarget =200

2實(shí)驗(yàn)

2.1 環(huán)境搭建

本文采用Unity 3D引擎進(jìn)行環(huán)境，構(gòu)建如圖2所示的環(huán)境。

利用Unity 3D引擎搭建如圖所示的環(huán)境，環(huán)境有20單位×10單位的矩形局域圍成，其中灰白色實(shí)體為墻體，紅色區(qū)域?yàn)槲ｋU(xiǎn)區(qū)域，右上角綠色墻體部分為出口，圖中的黃色圓形實(shí)體為智能體。

2.2 模型訓(xùn)練及結(jié)果分析

本文利用Python下深度學(xué)習(xí)框架Pytorch進(jìn)行編程，運(yùn)行環(huán)境為處理器Intel（R） Core 8750H，顯卡GTX1060。

模型在迭代500000回合后穩(wěn)定在收斂狀態(tài)，此時(shí)智能體可以完成在環(huán)境中任意位置的路徑規(guī)劃。智能體路徑規(guī)劃效果圖如圖3所示。

訓(xùn)練過(guò)程損失值變化如圖4所示。模型訓(xùn)練過(guò)程中的平均回合回報(bào)（/1000步）變化圖如圖5所示。

由圖4可以看出，DDPG算法模型在訓(xùn)練過(guò)程中逐步趨于收斂，說(shuō)明利用深度強(qiáng)化學(xué)習(xí)算法DDPG進(jìn)行路徑規(guī)劃具有可行性。結(jié)合圖5也可以看出，模型逐步向著回合回報(bào)增加的方向收斂，這說(shuō)明模型在逐步克服路徑規(guī)劃過(guò)程產(chǎn)生的方向震蕩，最終平均回合回報(bào)趨于較高的平穩(wěn)值，即代表所規(guī)劃的路線(xiàn)平滑且路程盡可能短。綜上所示，DDPG算法可以很好地完成路徑規(guī)劃任務(wù)。

3 結(jié)束語(yǔ)

本文將無(wú)須訓(xùn)練數(shù)據(jù)的強(qiáng)化學(xué)習(xí)算法應(yīng)用在路徑規(guī)劃領(lǐng)域，實(shí)現(xiàn)了連續(xù)、復(fù)雜環(huán)境下的路徑規(guī)劃任務(wù)。在諸多深度強(qiáng)化學(xué)習(xí)算法中，本文使用了在連續(xù)空間具有良好表現(xiàn)的DDPG算法來(lái)完成任務(wù)，實(shí)驗(yàn)結(jié)果證明，DDPG算法應(yīng)用在路徑規(guī)劃任務(wù)中的可行性與高效性。雖然本文取得了一定的成果，但是路徑規(guī)劃的維度是多方位的，動(dòng)態(tài)環(huán)境下的路徑規(guī)劃將會(huì)是本文的一個(gè)拓展方向。

參考文獻(xiàn)：

[1] Dijkstra E W. A note on two problems in connexion with graphs[J]. Numerische mathematik， 1959， 1（1）： 269-271.

[2] Hart P E， Nilsson N J， Raphael B. A formal basis for the heuristic determination of minimum cost paths[J]. IEEE transactions on Systems Science and Cybernetics， 1968， 4（2）： 100-107.

[3] Borenstein J， Koren Y. Real-time obstacle avoidance for fast mobile robots in cluttered environments[C]. IEEE，1990：572-577.

[4] Lei X， Zhang Z， Dong P. Dynamic path planning of unknown environment based on deep reinforcement learning[J]. Journal of Robotics， 2018， 2018

[5] Mnih V， Kavukcuoglu K， Silver D， et al. Playing atari with deep reinforcement learning[J]. arXiv preprint arXiv：1312.5602， 2013，

[6] Lillicrap T P， Hunt J J， Pritzel A， et al. Continuous control with deep reinforcement learning[J]. arXiv preprint arXiv：1509.02971， 2015，

[7] Bae H， Kim G， Kim J， et al. Multi-Robot Path Planning Method Using Reinforcement Learning[J]. Applied Sciences， 2019， 9（15）： 3057.

[8] Lv L， Zhang S， Ding D， et al. Path planning via an improved DQN-based learning policy[J]. IEEE Access， 2019， 7： 67319-67330.

【通聯(lián)編輯：唐一東】