張義　郭坤

摘要：路徑規(guī)劃是人工智能領(lǐng)域的一個經(jīng)典問題，在國防軍事、道路交通、機(jī)器人仿真等諸多領(lǐng)域有著廣泛應(yīng)用，然而現(xiàn)有的路徑規(guī)劃算法大多存在著環(huán)境單一、離散的動作空間、需要人工構(gòu)筑模型的問題。強(qiáng)化學(xué)習(xí)是一種無須人工提供訓(xùn)練數(shù)據(jù)自行與環(huán)境交互的機(jī)器學(xué)習(xí)方法，深度強(qiáng)化學(xué)習(xí)的發(fā)展更使得其解決現(xià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ù)動作空間

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

文章編號：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]、人工勢場法[3]等。迪杰斯特拉算法是路徑規(guī)劃領(lǐng)域的經(jīng)典算法，由迪杰斯特拉于1959年提出，迪杰斯特拉算法遍歷環(huán)境中的諸節(jié)點，采用貪心策略，每次擴(kuò)展一個節(jié)點，遍歷結(jié)束可得起點到其余各點的最短路徑。A*算法在迪杰斯特拉算法的基礎(chǔ)上進(jìn)行了改進(jìn)，在節(jié)點擴(kuò)展時加入啟發(fā)式規(guī)則，使得模型可以更快地收斂。雖然A*算法在諸多領(lǐng)域得到了諸多應(yīng)用，但A*算法的應(yīng)用場景局限在離散空間內(nèi)。人工勢場法則模擬物理學(xué)中的電力勢場，在智能體與障礙之間設(shè)置斥力，智能體與目標(biāo)之間設(shè)置引力，智能體沿著合力方向到達(dá)目標(biāo)位置。勢場法可以完成連續(xù)空間的路徑規(guī)劃，然而各種場景的施力大小配比只能人工協(xié)調(diào)，最優(yōu)配置難以求得，這種問題在復(fù)雜環(huán)境中尤為嚴(yán)重。強(qiáng)化學(xué)習(xí)是一種自主與環(huán)境交互的機(jī)器學(xué)習(xí)方式，強(qiáng)化學(xué)習(xí)無須人工提供訓(xùn)練數(shù)據(jù)，通過不斷與環(huán)境交互獲得不同的回報來使模型收斂[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算法實現(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)前環(huán)境信息作為輸入，通過神經(jīng)網(wǎng)絡(luò)計算生成一個動作值。Critic為評價模型，用以評價動作生成模型在當(dāng)前環(huán)境下生成的動作，Critic模型將輸出一個評價值，用以協(xié)助Actor模型的收斂。此外DDPG也采用了PolicyGrident的學(xué)習(xí)方式，不同于常見的概率梯度，DDPG采用一種確定性的策略梯度，根據(jù)Actor生成的動作值直接選擇動作，而非采用softmax的映射方式依概率選擇動作。此外，DDPG采用DQN的結(jié)構(gòu)理念，設(shè)計兩個結(jié)構(gòu)相同參數(shù)異步更新的模型，利用時分誤差進(jìn)行模型更新[8]。對于Policy模型，采用式（1）所示的模型進(jìn)行更新。

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

1.2 環(huán)境回報

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

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

2實驗

2.1 環(huán)境搭建

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

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

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

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

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

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

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

3 結(jié)束語

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

參考文獻(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)編輯：唐一東】