2021年2月第2期Vol. 42 No. 2 2021
小型微 型计算 机系统
Journal of Chinese Computer Systems
武曲，张义，郭坤，王玺
(青岛理工大学信息与控制工程学院，山东青岛266520)
E-mail :zhangyi_626@ 126. com
摘 要：在路径规划领域已经涌现出了诸多的优秀的经典算法，但这些传统方法往往基于静态环境，对于动态可变环境缺乏处
理能力.本文提出一种结合LSTM 强化学习动态环境路径规划算法.首先，本文以环境图像作为输入，最大限度了保证了原始 的信息来源.而后构建了自动编码器用来对环境图像进行特征降维，降低了整体模型的复杂程度.最后釆用深度强化学习算法
DDPG 进行路径规划，其中Actor 部分釆用LSTM 的网络构建，使Actor 在决策时可以参考前序信息，做到有预测的避开动态障
碍.最后通过实验证明了本文算法的可行性和高效性.
关键词：自动编码器;LSTM ；DDPG ；强化学习；动态路径规划中图分类号：TP391
文献标识码:A
文 章编号:1000-1220(2021)02-0334-06
LSTM Combined with Reinforcement Learning Dynamic Environment Path Planning Algo rithm
WU Qu,ZHANG Yi.GUO Kun,WANG Xi
(School of Information and Control Engineering , Qingdao University of Technology , Qingdao 266520, China )
Abstract :Many excellent classical algorithms have emerged in the field of path planning,but these traditional methods are often based on static environment and lack processing power for dynamic variable environment. This paper proposes a path planning algorithm for
dynamic environment based on LSTM reinforcement learning. First of all,this paper takes the environment image as the input to ensure the original information source to the maximum extent. Then an Autoencoder is built to reduce the dimension of environment image ,
which reduces the complexity of the whole model. At last , the deep reinforcement learning algorithm DDPG is used for path planning , and the Actor part uses LSTM network , so that the Actor can refer to the prior information and make decisions with the prediction of environment change. Finally , the feasibility and efficiency of the proposed algorithm are proved by experiments.
Key words : autoencoder ； LSTM ； DDPG ； reinforcement learning ； dynamic path planning
1引言
路径规划是人工智能领域的一个重要研究方向，在各个 领域得到了广泛的应用•迄今已经有许多经典的路径规划算 法被提出.
Dijkstra 算法是一种很早就被提出的路径规划算法⑴，它
将环境抽象为一个图问题，利用广度优先搜索策略遍历图，直 到到最短路径.A *算法是Dijkstra 算法⑷的改进.在原有 算法的基础上增加了启发式函数，并定义了一种当区域与扩
展点之间的一种度量作为扩展优先级，在进行路径扩展时会 优先扩展优先级高的节点.但当该方法用于处理多维复杂问
题时，无论是把环境抽象为图模型还是对图模型求解都将变
得很复杂.势场法⑶把规划空间看作物理学中的场，把智能 体看作一种粒子.障碍物对粒子产生排斥力，目标对粒子产生 引力.两者的合力即为智能体的最终运动的方向.这种方法实
时性较好，产生的路径通常十分平滑，适合于机械臂一类的应
用，缺点是在合力为0的位置智能体容易陷入局部最优解.
近年来，随机人工智能的兴起，很多基于人工智能的路径 规划方法被提出,Chen 等⑷提出了一种双向神经网络来解决
未知环境下的路径规划问题.Wu 等⑸将路径规划任务转化 为环境分类任务，使用CNN 来进行路径规划.Yu 等⑹提出 了一种基于神经网络的鲁棒控制方案，并结合自适应补偿器
和自适应控制增益来实现具有避障能力的编队控制.
强化学习是一类应用在未知环境的算法，作为机器学习 的3大分支之一，不同于监督学习和无监督学习，强化学习无
需提供数据，所有的学习资料都将从环境中获取.智能体通过 不断的探索环境，根据不同的动作产生的不同的反馈进行模 型的学习，最终智能体将能以最优策略在指定环境中完成 任务.
自V. Mnih 等提出DQN [71以来，深度强化学习不断取得
突破性进展，也有一些研究者尝试通过深度强化学习解决路 径规划问题.Piotr Mirowski 等⑻以多模态感知信息作为输 入，通过强化学习进行决策来完成网格空间中的导航任务. Panov 等⑼使用神经Q-Leaming 算法来完成网格环境下的路
收稿日期：2020Q8Q3收修改稿日期:2020-09-25基金项目：山东省自然科学基金项目(ZR2017BF043)资助.作者简介：武 曲，女，1982 年生，博士，副教授,CCF 会员，研究方向为强化学习、深度强化学习；张义，男，1995年生，硕士研究生，研究方向为深度强化学习；郭坤，女， 1995年生，硕士
研究生，研究方向为深度强化学习；王 玺，女，1996年生，硕士研究生，研究方向为深度强化学习.
2期武曲等：结合LSTM的强化学习动态环境路径规划算法335
径规划任务.Lei等"°)采用CNN和DDQN进行动态环境下的路径规划.Lv等M提出了一种改进的基于DQN的学习策略，在学习的初始阶段，创建一个体验价值评价网络，当发生路径漫游现象时，利用并行探索结构考虑对漫游点之外的其他点的探索，提高体验池的广度.
尽管上述方法在各自的领域都取得了不错的效果，但是他们实现路径规划仍存在一些不足之处.他们大多数只是在静态环境中进行路径规划，缺乏处理动态场景的能力；动作空间或状态空间是离散的，这与连续的现实环境是不符合的，而且在某些情况下，离散动作得出的最优解还可以被连续动作进一步优化；上述方法实现的路径规划多是从固定起点到固定终点的路径规划，这相当于模型只学习到了一个局部最优解，并不能完成整个环境的路径规划，这对指导现实应用具有很大的局限性.
为了实现全局动态环境下的路径规划任务，本文提出了一种结合了LSTM的路径规划算法.本文算法以环境图像作为输入，通过预训练的自动编码器进行降维提取特征.在训练模型时，以连续4帧图片降维后的特征信息作为输入，通过LSTM构建的DDPG模型进行路径规划，利用LSTM处理时序数据的特性，实现了在动作选择时进行有预测的规避环境中的危险区域的动态路径规划.
2相关工作
2.1自动编码器
自动编码器(Autoencoder)可以看做是利用深度学习的对数据进行降维的一种方式，通过一系列的神经网络计算将高维数据压缩到低维，再以对称的方式将数据复原，其结构图如图1所示.
图1自动编码器
Fig.1Autoencoder
当编码器模型收敛后即可认为中间的低维数据为压缩后的降维数据，再对低维数据进行其他操作，即可在保证达到与原数据相同效果的同时，亦能极大地降低操作过程的复杂度.
2.2LSTM
循环神经网络(Recurrent Neural Network,RNN)是一种处理时序数据的神经网络,RNN以一条时序数据为输入，其结构单元如图2(a)所示，在一个计算单元的计算中，输入部分除当前时刻数据x，之外，还有一项人t，该数据是由之前的t-1个时刻的数据传导计算而得，同样地,RNN在t时刻的输出，除了y，之外，还会生成一项人，而曾则是包含了前t个时刻的信息，曾将被传送到t+1时刻参与到t+1时刻的输出的计算过程中.
RNN的这种结构设计，使得RNN网络具有了预测的能力.但是，在经典的RNN网络中，隐藏单元h，所携带的信息是所有前t个时刻的信息，这样的结构产生了两个问题：有些前序时刻信息对当前时刻的输出而言并没有价值，参与到当前时刻输出的计算过程中反而会造成误差；大量的前序信息参与当前时刻输出的处理过程将增加计算的负担，该问题在序列较长时将会变得尤为突出.
染料废水
长短期记忆(Long Short-Term Memory,LSTM)是一种改进的RNN，该网络结构在产生当前时刻的输出时又增加了一项遗忘门的设计，通过一个状态参量c来实现遗忘功能，LSTM的结构但愿如图2(b)所示.
(a)(b)
图2RNN结构单元
Fi&2RNN unit
在LSTM的当前时刻，计算单元首先通过%，和曾"计算出一个中间结果，而后通过状态参量C-参与构建的遗忘门进行选择，最终输出y,.h，以及c,.LSTM的设计方式以一种更有效的方式利用了前序信息，同时也减少了中间过程携带的数据量，相对于经典RNN具有更好的效果.
2.3DDPG
2.3.1马尔科夫决策
强化学习过程普遍遵循马尔科夫决策过程(Markov Decision Process,MDP).MDP由一个<S,A,P,R>的四元组组成，其中S(Stole)为状态空间，表示智能体在环境中可能存在的状态描述的集合-A(Action)为动作空间，表示智能体在环境中可能采取的动作描述的集合-P(Policy)为转移策略，处在某个状态的智能体将依P进行动作选择，进而从一个状态转移到另一个状态.R(Reward)为回报，表示智能体在某个状态下采取某个动作而从环境中获得的回报值.强化学习的目标即为一个求取最佳策略P，在环境中进行执行一系列的动作，使智能体以最佳的回合回报完成给定任务.
2.3.2Actor-Critic
Actor-Critic[121是Vijay R.Konda和John N.Tsitsiklis提出的一种应用在马尔科夫决策过程中的算法，该算法由两部分构成，用来生成决策动作了Actor部分和用来对动作进行评价的Critic部分,Actor是动作生成器，以当前状态作为输入，输出一个当前状态下的要执行的动作.Critic则是一个评价器，即值函数生成器，以当前状态和Actor生成的动作为输入，生成一个价值量，该量用以衡量Actor生成的动作的优劣.
在训练过程中，模型按式(1)所示对探索过程中产生的数据进行处理.
m
/(兀⑷二工记妳兀,")(1)
使Critic模型学会为Actor生成的动作进行评估,Actor 则向着Critic
评价高的方向学习.
336小型微型计算机系统2021年
2.3.3Policy Grident
策略梯度(Policy Grident,PG)是由Richard S.Sutton等人提出的一种独立与价值函数的、根据期望回报进行策略更新的强化学习方式⑴],PG采用回合更新的方式，在得到一条完成回合序列之后，对于序列中的状态的值函数定义如式(3)所示.
(2)
r=l
多个回合后，的值应表示为多个回合的期望值，其定义如式(3)所示.
I S。,”}(3)
r=l
在PG方法中，策略77按式(4)所示进行参数更新.
fl*-0+aV8logir9(J,,a,)V,(4) 2.3.4DQN
无线视频服务器
深度Q网络(Deep Q Network,DQN)是深度强化学习的一个重要算法，它通过神经网络来构造状态价值函数，直接生成Q值，解决了传统Q-Learning方法维度受限、无法处理未参与训练的状态数据的问题；通过off policy的策略解决了强化学习数据的强相关性导致的很难应用深度学习方法处理的问题.DQN由两个结构相同，时间差分的网络构成，通过式(5)所示的算法进行网络参数的更新，由DQN开始，围绕深度强化学习不断涌现出许多优秀的研究成果.
ry=r+-ymax o,e，(s',a'),
4(0)=Eg,”，[(Q・(s,aW)-y)T
2.3.5DDPG
DDPG[I4](Deep Detenninistic Policy Gradient)算法结合了AC,PG,DQN中的诸多特点，率先将深度强化学习扩展到连续空间领域.DDPG整体采用Actor-Critic的框架结构，DDPG中的Actor和Critic两部分都由神经网络来构建，两部分的网络各自采用DQN的设计思路，分别为是两个时间差分的网络.在Critic更新时，采用策略梯度的更新方式、与传统的策略梯度不同的是,DDPG采用一种确定性策略进行动作选择.
3结合LSTM的强化学习动态环境路径规划算法在很多路径规划研究中，通常为智能体设置扫描射线，以此来观察周围的环境，智能体需要对当前周围的不同类型的实体进行扫描，然后构建包含到这些物体距离的向量，提供给模型进行动作选择.使用扫描射线的方式虽然可以尽可能的使得智能体获取周围的信息，但是仍然不可避免地会信息遗漏，针对这种情况，本文采用图像为模型提供输入.图像虽然极大地保留了环境的真实数据，但是同样存在着维度过大，模型难收敛的问题.自动编码器是一种采用深度学习对数据进行降维的方式，本文在处理图像数据时，首先采用预训练的编码器对图像数据进行了降维.
dna测序3.1预训练图像编码器
为了降低高维图像对模型收敛增加的复杂度问题，本文设计了图像编码器对图像数据进行特征降维，本文构建的图像编码器结构如图3所示.
编码器首先对图片进行预处理，包括通过常规方法降低图片尺寸和灰度化，然后对得到的灰图片进行编码和解码过程，通过解码后的图像与编码器的图像的差值作为损失来拟合编码器的参数.表1所示为本文设计的编码器参数表，本文编码器由5层组成，前2层为编码部分，后3层为解码部分.
Table1Parameters of autoencoder
表1编码器参数
Layer Neure Parameters
Data size
(after process) 0//1*200*100 Conv c=16；k=5；!s=5；p=0；16*40*20 1Relu/16*40*20 Pool k=2；s=2；p=016*20*10
两相流闸阀Conv c=16；k=3；:s=5；p=0；8*20*10 2Relu/8*20*10
Pool k=2；s=2；p=08*10*5 3
海泡石纤维ConvTrans c=16；k=2；s=2；p=0；16*20*10
Relu/16*20*10
ConvTrans c=8；k=2；s=2；p=0；8*40*20 4
Relu/8*40*20
ConvTrans c=1；k=5；s-5,p-0,1*200*100
Tanh/1*200*100
*c代表深度、k代表卷积核尺寸、s代表步长、p代表填充
3.2结合LSTM的DDPG
本文算法的主要目标是更好的避开动态危险区域，根据到动态危险区域的距离来进行规避诚然是一种可行方式，但是这种被动的响应方式对整体的路径规划是不利的，它仍然避免不了智能体需要探索对应区域才能进行规避，这造成规划路线上增加了一些额外的长度.如果模型能预测环境的变化趋势，就可以避开某些未来不能通过的区域，避免一些没有结果的探索工作，直接规划出一条最佳的可行路径.本文利用
图3LSTM DDPG结构图
Fig.3Structure of LSTM DDPG
了循环神经网络实现了这一设想，循环神经网络是一种用来处理时序数据的神经网络，会结合前序信息来生成当前时刻的输出，当前时刻的输出参考了之前时刻信息的变化趋势，所以循环神经网络是一种具有预测功能的网络LSTM的RNN
2期武曲等：结合LSTM的强化学习动态环境路径规划算法337
的一种改进，解决了经典RNN无差别携带前序信息带来的弊
端.DDPG是一个在连续动作上有很好表现的强化学习算法,
本文将LSTM融合到DDPG的框架中，构建了如图3所示的LSTM-DDPG算法.
其中Actor网络由3层构成，分别是两层LSTM和1层全连接层，对于LSTM设置input size为400，隐藏层单元为64，之后接一个全连接层以64维数据为输入计算生成2维的动作输出•Critic网络首先对输入的环境数据和动作数据做分别处理，其中环境数据利用LSTM进行处理，网络设置与Actor中的LSTM部分设置相同；对于Actor产生的Action，用一个全连接层将2维输入映射到20维；然后将上面两步的输出拼接一个向量传递给下一层的全连接层，由这个全连接层计算生成对Action的评价Q值.
3.3动作空间
本文模拟人类的动作行为方式设计了智能体的动作空间，采用连续的动作空间设计，将动作空间设计为两个维度(8,1)，其中8表示智能体的转动角度，取值范围设定为(-180,180)，其中当5<0时，智能体向左转动相应角度，当8>0时，智能体向右转动相应角度.I表示智能体执行动作的位移大小，取值范围为(-0.7,0.7)，其中/<0当时，表示智能体后退相应距离,/>0时，表示智能体前进相应距离.
3.4环境回报
在强化学习中，智能体通过在环境获得的累计回报来修正策略函数的参数，因此，环境回报的设定对策略函数能否收敛到理想的状态而言至关重要.为了验证本文方法处理动态环境的能力，本文除了设计墙体这种单纯的静态障碍之外，还设计一种危险区域，智能体接触该区域即死亡，回合结束，视为一次失败的路径规划.结合现实经验和多次试验结果作为参考，本文进行了以下环境回报的设定.
3.4.1决策回报
在一条路径生成的过程中，智能体通过一系列的动作选择在不同状态间切换，为了能保证智能体能以最少的状态切换次数即为了使智能体尽可能规划出一条更短的路径，智能体每执行一步动作，为智能体设置-1的回报，即『,“=1.
3.4.2碰壁回报
本文在环境中设置了墙体，用来圈围边界和构建智能体前进的障碍.对于智能体而言“撞墙”的行为是无意义的，不但增加了动作执行次数，也不会增加位移，因此对于智能体撞墙这种行为应该给予一定的负回报，在本文中设置口…=-1.
3.4.3遇险回报
本文设置了动态变化的危险区域来对提出的算法进行验证，该区域设置在智能体和目标位置之间，其体积会随着时间动态变化，对于智能体而言该区域的效果为在智能体接触到该区域时，智能体即死亡，回合结束，路径规划任务失败，因此应该对涉足该区域的智能体以最低的回报来使智能体远离该区域，在本文中设置『沁”=-50.
3.4.4目标回报
目标区域是路径规划任务的最终目标，应该给予其全局最大的回报，引导智能体向着最终目标进行路径规划.在本文中设置j=200.
看门狗电路
综上，设置环境回报如式(6)所示.
Reward=
if s w
if s w S dmger
if s'e S*”
else
(6) 4实验及结果分析
本文通过Unity-3D引擎构进行了强化学习环境的搭建，实验所用的软硬件配置如下:CPU i7-8750H，内存24G，显卡GTX1060，显存6G，软件环境Unity2019.4.2fl，深度学习框架使用Pytorch.
4.1实验环境搭建
在Unity工具中构建如图4所示的环境.
图4实验环境
Fig.4Experimental environment
该环境由面积为40x20矩形区域构成，在地面平面建立坐标系，以矩形区域中点为坐标原点，分别以向右和向上为x 轴,y轴的正方向.其中中部较小的圆形个体为智能体，半径为0.5，在每个回合训练开始时智能体将会随机生成在环境中的任意位置.两处黑圆形区域为危险区域，智能体碰撞到该区域即死亡，回合结束.该区域为动态变化区域，两处危险区域各自由初始半径为0.5的规格随智能体决策次数的增加而扩大，其半径依0.3单位/次的速度增加，此处之所以设置危险区域依智能体决策次而变化，是因为执行一个回合的具体时间会因计算机处在不同状态而有所差异，从而造成训练结果不稳定.左边危险区域的底面圆心坐标为(-6.5, -1.5)，右边危险区域的底面圆心坐标为(6,-6).图中的灰条形实体为
墙体，该区域为静态障碍.左右两面边界墙的中线分别为x=±20.5，上下两面边界墙的中线分别为y=士10.5，内部的障碍墙的中心线为x=10，墙的长度为12.图中右下角的深灰区域为安全出口，智能体到达此处视为路径规划成功的标志.
根据上述设定，随着智能体决策次数的增加，障碍墙下方的通道将会被危险区域封堵，智能体只能选择从上方的通道绕行到达终点.另外，为了避免智能体在训练前期探索环境的阶段不停地在环境中往返而不能结束一个回合，设定智能体单个回合的最大步数为200.
4.2图形编码器训练结果
首先，通过随机动作的方式令智能体在环境中探索，获得不同状态下的环境截图，为了减小模型训练的难度，在训练时将环境地面设置为白，并为智能体设置添加一个箭头用来指示方向•截取的原始图像大小为1200x600.
在本文实验中，共截取1
万张环境图像用来训练编码器.
338小型微型计算机系统2021年
在正式训练之前，为了降低模型的处理难度，首先使用OpenCV模块下的函数将截图初步降维到200x100，再对图片进行灰度化处理，处理后如图5(a)所示.本文使用小批量
(a)(b)
图5“编码-解码”过程前后的图片
Fig.5Images before and after encode-decode
梯度下降的方式训练自动编码器，设置学习率为0.01，经过1000轮训练之后，模型趋于收敛.提取训练好的模型，对一张环境截图进行编码解码过程，得到如图5所示“编码-解码”过程前后的两张图片对比，可以看到降维后的数据被比较完整的复原了，说明本文构建额的编码器成功的完成了图像数据降维的工作，训练的编码器可以应用到后续的任务中.
4.3LSTM DDPG实验结果
通过上一步的编码器，环境图像被压缩到了400维的大小.通过连续4帧图像编码后的数据构成时序数据作为LSTM-DDPG算法的输入数据.实验设置Actor学习率为0.001,Critic 学习率为0.001，回报衰减设置为0.95，采用小批量梯度下降的方式进行模型训练，批次大小设置为128；模型收敛后，收集到的训练过程中的数据变化如图6所示.
图6LSTM DDPG模型训练数据
Fig.6Training data of LSTM DDPG
其中图6(a)为Actor部分的损失变化曲线，图6(b)为Critic部分的损失变化曲线，观察两图可以发现，模型的两个部分都可以收敛，说明本文设计的模型是合理的，具有可行性.图6(c)为平均回合步数(/1000步)的变化，图6(d)为平均回合回报(/1000步)的变化，结合两图可以发现，在训练的前期，算法模型还不能进行正确的路径规划，动作选择多为随机动作，智能体在环境中执行较多的步数才能结束一个回合，结合图6(d)可以发现，此时智能体结束一个回合多因为陷入危险区域或达到回合步数上限而结束.在训练后期，算法模型逐渐收敛，平均回合步数和平均回报都趋于稳定，回报稳定在140上下，回合步数稳定在60步左右，这基本上可以说明智能体可以在不碰到墙壁和危险区域的情况下到达目标位置，进一步说明了本文的算法是可行的.
本文除了通过上述方式验证了提出算法的可行性，还在相同的环境下，设计了与经典的A•算法、遗传算法以及文献[11]
(Improved DQN)和文献[14](DDPG)中的深度强化学习方法实现效果的对比实验.对比实验分别以环境中的3处为起点测试3种算法的路径规划能力，这3个点分别是(5, 0)、(-10,5)和(-10,-5)，图7给出了LSTM-DDPG与其他4种算法的规划路径结果对比.
(c)
*为了避免轨迹被危险区域遮挡，在展示轨迹时将危险区域设定为了初始化状态，其中(b)和(c)中A*算
法产生的路径在中途停止是因为接触危险区域而结束.
图7LSTM-DDPG与其他算法规划路径对比
Fig.7Comparison of LSTM-DDPG with other
algorithms in the results of path planning
其中图7(a)表示以(-10,5)为起点时5种路径规划算法所规划的路径，图7(b)表示以(-10,-5)为起点时5种路径规划算法所规划的路径.表2所示是LSTM-DDPG同其他4种算法进行路径规划的相关数据.
表2LSTM-DDPG与其他算法的路径规划对比
Table2Comparison of LSTM-DDPG with other
algorithms in path planning
Origin Arithmetic Length Steps Epoch reward A*18.6726174
Genetic Algrithm20.3733162 (5,0)Improved DQN19.1727173
DDPG20.2231163
LSTM-DDPG19.8529171
A*Fail//
Genetic Algrithm42.3478122
(-10,5)Improved DQN50.389111
DDPG43.2576124
LSTM-DDPG38.7261139
A"Fail//
Genetic Algrithm46.6173127
(-10,-5)Improved DQN48.4286114
DDPG46.1374126
LSTM-DDPG43.0269131通过就表2中的数据进行横向对比，发现本文提出的算法在同等条件下拥有较好的表现.在以离目标点比较近的(0,5)点为起点时,A*算法取得了最好的表现，可以看到A*
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议