收稿日期:2021-05-07 修回日期:2021-09-10基金项目：国家自然科学基金(61573154)
作者简介：彭云建(1974-)，男，副教授，研究方向为动态系统建模与应用㊁强化学习；梁 进(1996-)，男，硕士研究生，研究方向为强化学习㊂
基于探索-利用权衡优化的Q 学习路径规划
彭云建，梁 进
(华南理工大学自动化科学与工程学院，广东广州510640)
摘 要：针对移动智能体在未知环境下的路径规划问题，提出了基于探索-利用权衡优化的Q 学习路径规划㊂对强化学习方法中固有的探索-利用权衡问题，提出了探索贪婪系数ε值随学习幕数平滑衰减的εDBE(ε-decreasing based episodes)方法和根据Q 表中的状态动作值判断到达状态的陌生/熟悉程度㊁做出探索或利用选择的A εBS(adaptive εbased state)方法，这一改进确定了触发探索和触发利用的情况，避免探索过度和利用过度，能加快到最优路径㊂在未知环境下对基于探索-利用权衡优化的Q 学习路径规划与经典的Q 学习路径规划进行仿真实验比较，结果表明该方法的智能体在未知障碍环境情况下具有快速学习适应的特性，最优路径步数收敛速度更快，能更高效实现路径规划，验证了该方法的可行性和高效性㊂
关键词：强化学习;Q 学习；探索-利用；路径规划；未知环境
中图分类号:TP391 文献标识码:A 文章编号:1673-629X (2022)04-0001-07doi:10.3969/j.issn.1673-629X.2022.04.001
Q -learning Path Planning Based on Exploration /Exploitation
Tradeoff Optimization
PENG Yun -jian ,LIANG Jin
(School of Automation Science and Engineering ,South China University of Technology ,Guangzhou 510640,China )
Abstract :Aiming at the path planning problem of mobile agent in unknown environment ,a Q -learning path planning based on exploration /exploitation tradeoff optimization is proposed.For the inherent problem of exploration /exploitation tradeoff in reinforcement learning ,the εDBE (ε-decreasing based episodes )method of exploring greedy coefficient εvalue decreasing smoothly with the number of learning episodes and the A εBS (adaptive εbased state )method of judging strangeness /familiarity of arriving state and making exploration or exploitation selection according to the state action value in Q table are proposed.This improvement determines the situation of triggering exploration or triggering exploitation ,avoids over exploration and over exploitation ,and can speed up finding the optimal path.In unknown environment ,the Q -learning path planning based on exploration /exploitation tradeoff optimization is compared with the
classical Q -learning path planning.The simulation results show that the agent with the proposed method has the characteristics of fast learning and adaptation in the unknown obstacle environment ,the optimal path steps converge faster ,and can realize the path planning more efficiently.The feasibility and efficiency of the proposed method are verified.
Key words :reinforcement learning ;Q -learning ;exploration /exploitation ;path planning ;unknown environment
0 引 言
随着人工智能的发展，能自主移动的智能体机器人在工业㊁军事以及医疗领域得到广泛使用[1]，路径规划要求智能体避开障碍物，到从出发点到目标点的最佳或次优路径[2]，是移动智能体被广泛使用和发挥价值的基础㊂其中未知环境下的路径规划是研究的难点和热点，目前主要的方法有人工势场法[3]㊁神经网络㊁遗传算法㊁粒子等智能算法[4]㊂
在利用强化学习解决未知情况下的路径规划方
面,M.C.Su 等人提出在路径规划的理论中增加强化学习方法[5]㊂沈晶等人提出基于分层强化学习的路径规划的方法[6]㊂Y.Song 等人提出一种有效的移动机器人Q 学习方法[7]㊂然而，在利用强化学习解决路径规划时，都会遇到强化学习本身固有的问题，即探索-利用问题[8]㊂为了解决探索-利用问题，目前提出的方法有ε贪婪方法和对其改进的ε-first 方法[9]㊁ε-decreasing 方法[10]，还有梯度算法[11]㊁value difference based exploration (VDBE )方法[12]等，但各有优点和不
第32卷 第4期2022年4月 计算机技术与发展COMPUTER TECHNOLOGY AND DEVELOPMENT
Vol.32 No.4
Apr. 2022
足，仍然有优化的空间㊂
该文根据优化ε值的改变方式和利用动作价值来动态选择采取的动作的思想，提出了基于探索-利用权衡优化的Q 学习路径规划方法，解决移动智能体在未知环境下的路径规划问题㊂
1 探索-利用权衡优化的Q 学习算法
为了实现智能体在未知环境下的路径规划，基于探索-利用权衡优化的Q 学习路径规划可以分为两个部分，一是利用强化学习中Q 学习不需要事先知道环境，智能体依然能与未知环境的互动中学习的特点，通过获得足够的幕数学习经验，不断更新Q 表的动作价
值，进而不断更新优化路径规划策略，实现路径规划；二是利用提出的εDBE 方法和A εBS ，权衡强化学习中固有的探索-利用问题，提高未知环境下路径规划的快速性㊂
基于探索-利用权衡优化的Q 学习路径规划如图
1所示㊂提出改进探索-利用权衡问题的εDBE 方法和A εBS 方法，着重优化ε值的改变方式和利用Q 表中的动作价值来动态选择采取的动作，通过智能体与环境互动产生每幕学习经验来影响Q 表动作价值的评估，进而获得更优动作行为㊁更新获得更优路径规划策略㊂
图1 探索-利用权衡优化的Q 学习路径规划
图2 智能体与环境交互图
智能体与环境交互如图2所示，每幕学习经验定
义如下：在t 时刻，智能体处于状态s t ，采取动作a t ，因此在t +1时刻，智能体获得来自环境的奖励r t +1，并在环境中发生了状态转移，到达了状态s t +1㊂在智能体
与环境的不断交互过程中可获得一个状态㊁行动㊁奖励的序列:s 0,a 0,r 1,s 1,a 1,r 2,s 2,a 2,r 3,s 3, ,s T ，其中T 是终止时刻，这样有终止状态的一个序列也称为一幕(episode )学习经验㊂
2 改进探索-利用权衡问题的εDBE 方法和
A εBS 方法
2.1 权衡探索-利用问题的基本方法
为了解决强化学习固有的探索-利用问题，经典的Q 学习算法中采用了ε-贪婪方法㊂之后有研究人员提出了改进ε-贪婪方法的ε-first 方法㊁ε-decreasing 方法，都是为了更好权衡探索-利用问题，提
高Q 学习算法解决问题的能力㊂
㊃
2㊃ 计算机技术与发展 第32卷
2.1.1
ε-贪婪方法
ε-贪婪方法的思想是设定一个小的贪婪探索系
数,0<ε≤1，在选择要采取哪个动作时，有ε的概率从所有可选的动作中随机选择，有1-ε的概率选择目前能获得最大回报的动作㊂可用式(1)表示:
π(a |s )=1-ε+εm
,if a =a *
εm
,if a ≠a ìîí
ïïïï*(1)
其中,π(a |s )为在状态s 下选择动作a 的概率,m 为状态s 下动作集合A (s )中动作a 的总个数,a ∈A (s ),a *为状态s 下的最优动作㊂
2.1.2
ε-first 方法
ε-first 方法[9]的思想是一开始将ε的值设为1,
让智能体处于完全探索状态，一段训练幕数(episode)之后，将ε的值设为0，让智能体处于完全利用环境状态㊂可用式(2)表示:
ε=
1,if episode ≤preset_episo
0,{if episode >preset_episo
(2)
其中,episode 为幕数变量,preset_episo 为预先设定的幕数值㊂2.1.3
ε-decreasing 方法
改进的ε-decreasing 方法[10]是ε-贪婪方法和ε-first 方法的折中，思想是初始将ε设为一个较大的值，从训练幕数来看,ε随着训练幕数增加不断减少；从单幕的步数来看,ε随者步数增加而增大㊂可用式(3)表示:
ε=ε0*0.1
episode step
(3)
其中,ε0为贪婪系数的初始设定值,episode 为幕数变量,step 为每幕的步数变量㊂2.2 εDBE 方法和A εBS 方法
针对Q 学习中固有的探索-利用问题，该文提出随幕数(episodes)平滑衰减ε-值的ε-decreasing based episodes(εDBE)方法，以及根据Q 表中的状态动作值判断到达状态的陌生/熟悉程度㊁做出探索或利用选择的adaptive εbased state (A εBS)方法㊂2.2.1
εDBE 方法
随幕数(episodes)平滑衰减ε值的εDBE 方法结
合了ε-decreasing 方法和ε-贪婪方法的特点，即将初始ε设为一个较小的值，从训练幕数的角度来看，随着训练幕数增加而不断衰减；从单幕的步数角度来看ε保持不变，结合了ε-decreasing 方法中ε衰减的特点，同时也具有ε-贪婪方法在每一幕步数中ε保持不变的特点㊂在选择同时满足上述两个特点的ε衰减函数上，采用式(4)控制ε值的衰减㊂
ε=
ε0
episode
(4)
其中,ε0为贪婪系数的初始设定值,0<ε0≤1,episode 为幕数变量㊂
将式(4)与式(1)结合可得式(5)㊂
π(a |s )=1-ε0episode +ε0m episode
,if a =a *
ε0m episode
,if a ≠a ìîí
ïïï
ï
*(5)
规定了探索或利用的概率，即有ε0/
episode 的
概率从所有可选的动作中进行探索选择，有1-ε0/
episode 的概率利用已学到的状态动作值，选择目前
能获得最大回报的动作㊂在引入到下节的Q 学习方法时，令从Q 表中得到策略π，通过εDBE 方法进行策略评估和策略改进后得到的改进策略为π'，根据策略改进定理[13]可知,π'相比于π更优，最终不断迭代后得到最优策略π*㊂
2.2.2 A εBS 方法根据到达位置的陌生/熟悉程度和动作价值，从而
做出探索/利用的动态动作选择A εBS 方法㊂引入不断学习更新的Q 表中动作价值作为陌生/熟悉程度的指标，当状态s 下所对应的所有动作价值全为0时，认为该状态对于智能体来说是陌生的；当状态s 下所对应的所有动作价值不全为0时，认为该状态对于智能体来说是熟悉的㊂在每幕学习的每一个步(step)中，遇到陌生的位置状态,ε值变为1，采取探索模式随机选择动作集中的任一动作；遇到熟悉的位置状态,ε值变为0，采取利用模式选择状态动作价值最大的动作㊂另外融合ε-first 方法的思想，根据未知环境情况的不同，在幕数段中加入很小的ε值对Q 表更新进行微调整㊂可用式(6)表示:
ε=1,if ∀Q (s ,a )=0,a ∈A (s )
0,if ∃Q (s ,a )≠0,a ∈A (s )
ε0,if episode ∈[episo1,episo2{
]
(6)
其中,episode 为幕数变量,episo1和episo2为设定的幕数值,ε0为贪婪系数的初始设定值,0<ε0≤1,A (s )为状态s 下的动作集合㊂
由于初始阶段中Q 表的动作价值均初始化为零，因此采用A εBS 方法的智能体可以充分探索环境，即每当遇到动作价值为零时智能体会判断出自身处于陌生环境，更倾向于随机选择不同的动作进行探索，更有可能不断遇到陌生情况，探索更为充分㊂同时在与环境的交互中不断更新Q 表的动作价值，增加环境熟悉程度，从而利用Q 表的动作价值的大小比较选择最优
㊃
3㊃ 第4期 彭云建等：基于探索-利用权衡优化的Q 学习路径规划
动作，进而不断更新路径策略㊂
3 引入εDBE 方法和A εBS 方法的Q 学习
路径规划
在未知环境路径规划下，移动智能体在不同的状态s 下通过策略π选择要采取的动作a ，与环境进行交互获得奖励r ，并到达下一状态s '㊂重复上述过程不断迭代探索，更新Q 表中的动作价值，到更好的动作，直至到最优策略π*，完成未知环境下的路径规划㊂时序差分方法是评估价值函数和寻最优策略的实用方法㊂时序差分方法可以使智能体能直接与环境互动的经验中学习，不需要构建关于环境的动态特性㊂
Q 学习是off-policy 下的时序差分控制方法，是强化学习的一个重要突破[14]㊂Q 学习更新的是动作价值函数，更新方法如式(7)所示:
Q (s t ,a t )←Q (s t ,a t )+α[r t +1+
γmax a Q (s t +1,a )-Q (s t ,a t )]
(7)
其中,α为学习率,0<α<1;γ称为折扣因子，表示未来奖励对当前状态的影响程度[15],0≤γ≤1㊂
在t 时刻智能体处于状态s t ，动作状态价值为
Q (s t ,a t )，当智能体采取动作a t 后在t +1时刻到达状态s t +1并获得奖励r t +1，此时智能体将在Q 表中到能够使在状态s t +1下动作价值最大的动作a ，以此来获得Q (s t +1,a )，从而对Q (s t ,a t )进行更新㊂快速学习
可将式(7)改写成式(8)㊂Q (s t ,a t )←(1-α)Q (s t ,a t )+α[r t +1+γmax a Q (s t +1,a )]
(8)
假设s t +1所对应的max a Q (s t +1,a )恒定，通过式(8)可迭代求得稳定的Q (s t ,a t )㊂
一次迭代:
Q (s t ,a t )←(1-α)Q (s t ,a t )+α[r t +1+γmax a Q (s t +1,a )](9)
二次迭代:
Q (s t ,a t )←(1-α)[(1-α)Q (s t ,a t )+
α[r t +1+γmax a Q (s t +1,a )]]+α[r t +1+γmax a Q (s t +1,a )]←(1-α)2
Q (s t ,a t )+
[1-(1-α)2][r t +1+γmax a Q (s t +1,a )]
(10)
以此类推,n 次迭代:
Q (s t ,a t )←(1-α)n Q (s t ,a t )+
[1-(1-α)n ][r t +1+γmax a Q (s t +1,a )]
(11)
因为0<α<1，所以0<1-α<1，当n →∞时,
Q (s t ,a t )将以概率1收敛到最优值，即:
Q (s t ,a t )←r t +1+γmax a Q (s t +1,a )
(12)
当Q 表更新后，根据式(13)即可选出状态下具有最大动作状态价值的动作，从而获得路径规划更优策略π'的更新㊂
π'(s )=arg max a Q (s ,a )
(13)
该文以稀疏奖励的形式定义奖励函数r ，如式
(14)所示，将状态分为障碍状态㊁路径状态和目标终点状态，分别用状态集合O (s )㊁P (s )㊁G (s )表示㊂
其中到达障碍状态获得-1奖励值，到达目标终点状态获得+1奖励值，到达路径状态获得0奖励值，促使智能体避开障碍物快速到达目标终点㊂
r =
-1,if s ∈O (s )0,if s ∈P (s )1,if s ∈G (s {
)
(14)
每个状态有上㊁下㊁左㊁右四个动作可选择，训练的过程为输入当前状态后，根据(εDBE)方法或根据(A εBS)方法从Q 表中选出当前状态的相应动作，与未知环境交互后获得奖励，进入下一状态并判断是否撞到障碍物㊂
若判定会撞到障碍物，则根据式(8)更新Q 表后结束本幕学习，开始下一个幕的学习；若判定不会撞到障碍物，则根据式(8)更新Q 表后进入下一状态，本幕学习直至到达终点或判定会发生碰撞障碍物后结束㊂重复学习过程，不断更新Q 表中各个状态的动作价值，直至到最优策略，实现路径规划㊂
4 实验结果及分析
4.1 实验设计
该文在10*10的地图上进行Q 学习路径规划，设定了两种智能体未知的不同环境，对提出的基于探索-利用权衡优化的Q 学习路径规划与基于经典的ε-贪婪方法㊁ε-first 方法㊁ε-decreasing 方法的Q 学习路径规划进行比较，验证提出方法的可行性和高效快速性㊂
其中每个网格对应一个状态，用不同的状态标号
表示[16]㊂即在位置(x ,y )处的网格对应的状态标号stateno 可用式(15)表示㊂
stateno =10(x -1)+y
(15)
图3所示为两种智能体未知的情况地图，状态SS 为起点位置,GS 为终点位置，起始位置和路径均用深灰表示，黑为障碍物㊂智能体在每个无障碍物的浅灰位置状态下，有上㊁下㊁左㊁右四个动作可以选择，碰到障碍物意味着一幕学习以失败结束，获得-1奖励值，并返回起点位置；到达终点意味着一幕学习以成功结束，获得+1奖励值，并返回起点位置；到达其余
㊃
4㊃ 计算机技术与发展 第32卷
状态均获得0奖励值
㊂
图3 两种智能体未知的环境地图
4.2 结果分析
通过Q学习路径规划可以得到以下仿真实验结
果：图4所示为未知环境地图1下的仿真实验结果，其
中折扣因子γ=0.8，学习率α=0.2,ε-贪婪方法的ε
值为0.1,ε-decreasing方法的ε初始值为0.8,εDBE
的ε初始值为0.2,AεBS方法在30幕前的ε值为0.
05㊂从图4(b)可以发现,Q学习可以实现路径规划,
到从起点到终点的最优路径，状态转移步数为
11步
㊂
1.0
1.0
图4 未知环境地图1中的仿真实验结果
㊃5㊃ 第4期 彭云建等：基于探索-利用权衡优化的Q学习路径规划
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论