基于DDPG算法的路径规划研究

张义　郭坤

摘要：路径规划是人工智能领域的一个经典问题，在国防军事、道路交通、机器人仿真等诸多领域有着广泛应用，然而现有的路径规划算法大多存在着环境单一、离散的动作空间、需要人工构筑模型的问题。强化学习是一种无须人工提供训练数据自行与环境交互的机器学习方法，深度强化学习的发展更使得其解决现实问题的能力得到进一步提升，本文将深度强化学习的DDPG（Deep Deterministic Policy Gradient）算法应用到路径规划领域，完成了连续空间、复杂环境的路径规划。

关键词：路径规划;深度强化学习;DDPG;ActorCritic;连续动作空间

中图分类号： TP301.6       文献标识码：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

传统算法如迪杰斯特拉算法[1]、A*算法[2]、人工势场法[3]等。迪杰斯特拉算法是路径规划领域的经典算法，由迪杰斯特拉于1959年提出，迪杰斯特拉算法遍历环境中的诸节点，采用贪心策略，每次扩展一个节点，遍历结束可得起点到其余各点的最短路径。A*算法在迪杰斯特拉算法的基础上进行了改进，在节点扩展时加入启发式规则，使得模型可以更快地收敛。虽然A*算法在诸多领域得到了诸多应用，但A*算法的应用场景局限在离散空间内。人工势场法则模拟物理学中的电力势场，在智能体与障碍之间设置斥力，智能体与目标之间设置引力，智能体沿着合力方向到达目标位置。势场法可以完成连续空间的路径规划，然而各种场景的施力大小配比只能人工协调，最优配置难以求得，这种问题在复杂环境中尤为严重。强化学习是一种自主与环境交互的机器学习方式，强化学习无须人工提供训练数据，通过不断与环境交互获得不同的回报来使模型收敛[4]。Mnih V在2013提出的DQN[5]（DeepQNetwork）算法，为深度强化学习的发展奠定了基础，自此不断涌现出深度强化学习的诸多优秀算法。DDPG[6]算法结合了DQN、ActorCritic、PolicyGrient等策略，首先将深度强化学习引入到连续空间领域[7]，本文采用DDPG算法实现连续复杂环境的路径规划。

1 基于DDPG算法的路徑规划原理

1.1 DDPG算法

DDPG算法底层采用ActorCritic的结构，其结构图如图1所示。

将模型整体分为Actor和Critic两部分，其中Actor为动作生成模型，以当前环境信息作为输入，通过神经网络计算生成一个动作值。Critic为评价模型，用以评价动作生成模型在当前环境下生成的动作，Critic模型将输出一个评价值，用以协助Actor模型的收敛。此外DDPG也采用了PolicyGrident的学习方式，不同于常见的概率梯度，DDPG采用一种确定性的策略梯度，根据Actor生成的动作值直接选择动作，而非采用softmax的映射方式依概率选择动作。此外，DDPG采用DQN的结构理念，设计两个结构相同参数异步更新的模型，利用时分误差进行模型更新[8]。对于Policy模型，采用式（1）所示的模型进行更新。

本文为智能体配置扫描射线获取环境信息，分别扫描环境中的墙体障碍、危险区域和安全出口，在本文中，前方设置5条射线，后方设置2条射线，总共组成21维的数据作为环境输入。

1.2 环境回报

为了验证本文算法处理复杂环境的能力，本文除了构建简单的常见障碍之外，模拟环境中有某种险情发生的场景，在环境中构建了危险区域。对于普通障碍，对智能体只起到障碍作用，而智能体接触危险区域将会死亡，回合结束，视为此次路径规划任务失败。

为了使模型尽量在更少的决策次数内到达目标位置，设置智能体每多决策一步，给予一定的惩罚回报，设置Rstep=-1 对于普通的墙体障碍，对智能体只起到障碍作用，但是仍需防止智能体出现“撞墙”的行为，因此设置Rwall=-1 对于危险区域，智能体应该避开，设置Rdagenr =-50 安全出口为智能体的最终目标，应该设置全局最优回报，本文结合经验与多次试验结论，设定Rtarget =200

2实验

2.1 环境搭建

本文采用Unity 3D引擎进行环境，构建如图2所示的环境。

利用Unity 3D引擎搭建如图所示的环境，环境有20单位×10单位的矩形局域围成，其中灰白色实体为墙体，红色区域为危险区域，右上角绿色墙体部分为出口，图中的黄色圆形实体为智能体。

2.2 模型训练及结果分析

本文利用Python下深度学习框架Pytorch进行编程，运行环境为处理器Intel（R） Core 8750H，显卡GTX1060。

模型在迭代500000回合后稳定在收敛状态，此时智能体可以完成在环境中任意位置的路径规划。智能体路径规划效果图如图3所示。

训练过程损失值变化如图4所示。模型训练过程中的平均回合回报（/1000步）变化图如图5所示。

由图4可以看出，DDPG算法模型在训练过程中逐步趋于收敛，说明利用深度强化学习算法DDPG进行路径规划具有可行性。结合图5也可以看出，模型逐步向着回合回报增加的方向收敛，这说明模型在逐步克服路径规划过程产生的方向震荡，最终平均回合回报趋于较高的平稳值，即代表所规划的路线平滑且路程尽可能短。综上所示，DDPG算法可以很好地完成路径规划任务。

3 结束语

本文将无须训练数据的强化学习算法应用在路径规划领域，实现了连续、复杂环境下的路径规划任务。在诸多深度强化学习算法中，本文使用了在连续空间具有良好表现的DDPG算法来完成任务，实验结果证明，DDPG算法应用在路径规划任务中的可行性与高效性。虽然本文取得了一定的成果，但是路径规划的维度是多方位的，动态环境下的路径规划将会是本文的一个拓展方向。

参考文献：

[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.

【通聯编辑：唐一东】