一种基于改进DQN算法的室内巡逻机器人自主导航方法

一种基于改进dqn算法的室内巡逻机器人自主导航方法
技术领域
1.本发明涉及dqn算法技术领域，尤其涉及一种基于改进dqn算法的室内 巡逻机器人自主导航方法。


背景技术：

2.传统的安防体系是“人防+物防”来实现。可随着人口老龄化加重、劳动 力成本飙升、安保人员流失率高等问题，已经难以适应现代安防需求，安防巡 逻机器人产业迎来新的发展契机。安防巡逻机器人还处于起步阶段，但巨大的 安防市场需求下，其发展潜力和未来前景广阔。由于深度强化学习中的深度q 网络(deep q network/dqn)算法在q-learning的基础上利用神经网络进行融 合，从而克服因q-learning存储数据消耗的内存过大而导致的“维数灾难”问 题的缺陷，使得搜索过程不断收敛，最终逼近最优解，已经被广泛应用于解决 机器人的自主导航问题中；而室内巡逻机器人又与普通机器人不同，它们的巡 逻路径相对统一，且当路径中有障碍出现应优先避开障碍。
3.mnih等提出第一个深度强化学习模型，即深度q网络(dqn)，该网络模 型是将神经网络和q-learning相结合，利用神经网络代替q值表解决了 q-learning中的维数灾难问题，但在网络训练时收敛速度较慢；tail等把dqn应 用到了无模型避障的路径规划中，但存在状态-动作值过估计问题，造成移动机 器人获得的奖惩稀疏，且规划出的路径并非最优。
4.传统的路径规划算法有a*算法、人工势场法以及快速扩展随机树法等。a* 算法有着目标点不可达时会造成大量性能消耗的特点；人工势场法的路径一般 是平滑、安全的，但该方法存在局部最优点问题，容易陷入局部极小点，在相 似的障碍物之间找不到路径，检测到新的环境障碍物后，人工势场法规划的路 径可能发生振荡，在狭窄通道中摆动，快速扩展随机树法的一个弱点是难以在 有狭窄通道的环境找到路径。


技术实现要素：

5.为了克服上述现有技术的不足，本发明所采用的技术方案是：一种基于改 进dqn算法的室内巡逻机器人自主导航方法包括以下步骤：
6.s1、巡逻机器人感知自身周围的环境信息，并结合自身的位置信息和将到 达的目标点组成一个状态空间，在状态空间中依次设置若干目标点，并作为dqn 算法的输入，巡逻机器人从起始点出发；
7.巡逻机器人巡逻方式为按照规定环状路径巡逻，当规定的环状路径中突然 出现障碍物时，巡逻机器人必须优先避障，其次才应该按照规定路径进行巡逻；
8.s2、通过对dqn算法的目标函数进行改进，巡逻机器人以当前位置和速度 作为下一步动作的输出，当到达第一目标点后，以第一个目标点为起始点寻找 下一个目标点，当机器人达到下一个目标点时即完成此段路径行走，依次不断 循环，直至找到最后一个目标点，最后一个目标点即起点；
9.以有边界环状路线为巡逻机器人的行进路线，巡逻机器人在规定路线有限 制条
件的环境下朝向目标点运行的过程且最终能回到出发点，从而完成移动机 器人的自主导航任务；
10.dqn算法结合神经网络和q-learning，神经网络需要对q表进行建模，q-learning利用马尔科夫决策进行建模，采用马尔科夫决策中的当前状态、动作、 奖惩、策略、下一步动作进行表示；dqn为了提高机器人的样本关联性和解决 机器人的效率利用问题引入了经验回放机制，并利用目标q值的唯一性来提高 动作更新的平稳性；dqn包括建立目标函数、目标网络和引入经验回放这三个 步骤：
11.目标函数：dqn的目标函数通过q-learning构建，公式如下所示：
12.q’(s,a)
←
q(s,a)+α[r+γmaxa′
q(s
′
,a
′
)-q(s,a)]
ꢀꢀꢀ
(1)
[0013]
其中，(s,a)表示当前的状态和动作，(s’,a’)表示下一步的状态和动作，q(s,a) 表示当前的动作-状态值，q’(s,a)表示更新后的状态-动作值；α表示学习率，即 当前状态下的误差有多少会被更新学习，取值范围0～1；γ表示对未来奖惩的衰 减值，取值范围0～1；因为在dqn算法中，q的取值是随机的，因此为了方便 计算，需要使用随机数中的最大值max，maxa′
q(s
′
,a
′
)表示在下一步的状态 动作值下q的最大值。将q值的表达式拆开，可以得到如下所示的表达式：
[0014]
q(s1)＝r2+γq(s2)＝r2+γ[r3+γq(s3)]＝r2+γ{[r3+γ[r4+γq(s4)]}＝
…ꢀꢀ
(2)
[0015]
即：q(s1)＝r2+γ
·
r3+γ2·
r4+γ3·
r5+γ4·
r6+
……
+γn·
r(n+2)+
……ꢀꢀ
(3)
[0016]
q值与之后每一步骤的奖惩都有关联，但这些关联奖惩会随时间不断衰减， 且离状态s1越远，状态衰减越严重；
[0017]
目标状态-动作值函数用贝尔曼方程可表示为：
[0018]y′
＝r+γmaxq(s
′
,a
′
,θ)
ꢀꢀꢀꢀ
(4)
[0019]
其中，y
′
表示目标q值，θ为神经网络结构模型中训练的权值参数， maxq(s
′
,a
′
.θ)表示下一个状态动作值和θ作用下q的最大值；
[0020]
损失函数为均方误差损失函数，公式如下所示：
[0021]
l(θ)＝e[(y
′‑
q(s,a,θ))2]
ꢀꢀꢀꢀ
(5)
[0022]
目标网络：dqn通过目标网络和预测网络来评估当前的状态-动作值函数；目标 网络基于神经网络得到目标q值，利用目标q值来估计下一动作的q值；预测网 络使用随机梯度下降法更新网络权重δθ，梯度下降算法的公式如下所示：
[0023][0024]
其中，为哈密顿算子；
[0025]
经验回放：经验回放机制提高机器人的样本关联性和解决机器人的效率利 用问题；在机器人和环境进行信息交互时，机器人可获得样本数据库；机器人 将样本数据库存储到建立的经验池中并随机抽取一小部分数据用于训练样本， 再将训练样本送入神经网络中训练；经验回放机制利用样本本身的可重复性来 提高学习效率；
[0026]
改进目标函数：目标点是巡逻机器人在运动状态下所需要达到的位置坐标， 表示机器人的最终位置，对于巡逻机器人而言，它在执行任务时，需要行驶在 固定路线上，并且在巡逻完成后应回到初始位置；将目标点处于起始位置，会 导致算法不进行迭代，直接跳转至结尾，从而跳过巡逻步骤；即使设计函数使 得算法在第二次达到初始位置时停止迭代，由于dqn算法的自身特点，也将快 速停止迭代，最终行走路径可能只有一小格；
[0027]
在环状路线中，由于最终行走路线是从起始点开始，到第二次行走至起始 点结束，机器人行走的路程较长，当遇到障碍物后dqn算法会重新从起始点开 始再次计算，导致整圈的计算周期过长。
[0028]
可以通过改进目标函数，实现巡逻机器人按照预定线路行走，并返回到出 发点；巡逻机器人到达第一个目标点位置，完成第一段路程后，会在机器人前 进线路上生成第二个目标点，同时将第一目标点变成下一段路程的迭代初始点， 并将路线上第一目标点的前一个点变为障碍点，通过分段迭代使巡逻机器人只 需对每一段寻找目标点过程进行单独迭代，从而减少迭代次数，还可以防止机 器人在每段迭代过程中走“回头路”；并将最后一个阶段的目标点设置为初始 阶段的起始点，这样就保证巡逻机器人走完整路线。
[0029]
s3、改进dqn算法的奖惩函数r，提高dqn算法收敛速度，优化环境状 态空间的奖惩稀疏性；
[0030]
巡逻机器人在行进的路径上难免会突然遇到障碍物，巡逻机器人必须先避 障，之后按照设定线路进行巡逻；
[0031]
通过改进奖惩函数使dqn算法演算时间减小，通过奖惩函数r对公式(4) 的目标q值进行优化，从而使公式(6)的梯度下降速度加快，减少迭代次数；
[0032]
奖惩函数r如式7所示：
[0033][0034]
其中，(i,j)为网格中横纵坐标；
[0035]
特殊奖惩点的r
(m,n)
特点为：以此点为中心，包括周围的8个点共9个点均 不是障碍点；
[0036]
特殊奖惩值μ，取值范围10-6
～0，赋予一个变化的μ值，即初始值μ1＝10-6
，随 着每一段目标点路径的完成，μ值逐渐减小，最终变成0，μk＝[μ1×
(n+1-k)]/n， 其中，n为目标点总个数，k为两个目标点之间的路径段，1＝《k《＝n+1。
[0037]
本发明的有益效果是：
[0038]
1、本发明对dqn算法进行改进，避免算法陷入死循环的问题；同时，将 机器人行驶的路径分段化，大大减少了dqn算法的迭代次数；最后通过改进奖 惩函数，使dqn算法收敛速度加快，从而完成室内巡逻机器人自主导航的任务。
附图说明
[0039]
图1是本发明的基于改进dqn算法的室内巡逻机器人自主导航方法流程图；
[0040]
图2是本发明模型一单循环起始目标点状态图；
[0041]
图3是本发明模型一单循环最终目标点状态图；
[0042]
图4是本发明模型二单循环起始目标点状态图；
[0043]
图5是本发明模型二单循环最终目标点状态图；
[0044]
图6是本发明实施例一的特殊奖惩点的解释图；
[0045]
图7是改进前dqn算法运行得到的训练次数-损失函数变化曲线；
[0046]
图8是本发明改进dqn算法运行得到的训练次数-损失函数变化曲线(奖惩 值μ＝0.5)；
[0047]
图9是本发明改进dqn算法运行得到的训练次数-损失函数变化曲线(奖惩 值μ＝10-6
)；
[0048]
图10是本发明改进dqn算法运行得到的训练次数-损失函数变化曲线(奖惩 值μ由10-6
变为0)；
[0049]
图11是本发明巡逻机器人在改进dqn算法下的运行路径。
具体实施方式
[0050]
下面结合附图和实施例对本发明作进一步说明，此图为简化的示意图，仅以示 意方式说明本发明的基本结构，因此其仅显示与本发明有关的构成。
[0051]
如图1所示，一种基于改进dqn算法的室内巡逻机器人自主导航方法包括 以下步骤：
[0052]
s1、巡逻机器人感知自身周围的环境信息，并结合自身的位置信息和将到 达的目标点组成一个状态空间，在状态空间中依次设置若干目标点，并作为改 进dqn算法的输入，巡逻机器人从起始点出发；
[0053]
s2、通过对dqn算法的目标函数进行改进，巡逻机器人以当前位置和速度 作为下一步动作的输出，当到达第一目标点后，以第一个目标点为起始点寻找 下一个目标点，依次不断循环，直至找到最后一个目标点，最后一个目标点即 起点；
[0054]
如图2所示为模型一，巡逻机器人的行进路径为环形单循环路径，在30*30 的网格中，将赛道边界设置成黑色，表示障碍点；红色点代表起始点，即巡逻 机器人所处起始位置；黄色点代表目标点，将环状线路分段化，初始状态下的 黄色点为机器人的第一阶段目标点，在机器人达成第一阶段后，将会在机器人 前进线路上生成第二个目标点，同时将第一目标点变成新的算法迭代初始点， 并且将之前前进路线上最靠近第一目标点的白色网格点变黑，使其变成障碍点； 保证巡航机器人在后续的迭代效率提高，同时也可以防止机器人在每段迭代过 程中走“回头路”；将最后一个阶段的目标点设置为初始阶段的起始点，这样 就保证机器人完整走完整个环状路线，最后一个阶段的目标点状态如图2所示。
[0055]
如图3所示为模型二，巡逻机器人的行进路径为环形单循环路径，但对两 圈黑色环形道的中间白色区域放大；如图4所示，在过道中随机设置多个黑色 障碍物，巡逻机器人必须优先避障，红色点代表起始点，即巡逻机器人所处起 始位置，黄色点代表目标点；由于巡航机器人行走的空间比模型一中扩大了3 倍，自由度大大提高，因此模型二中使用dqn算法演算时间会比模型一冗长；
[0056]
s3、改进dqn算法的奖惩函数r，提高dqn算法收敛速度，优化环境状 态空间的奖惩稀疏性；
[0057]
通过改进奖惩函数使dqn算法演算时间减小，通过奖惩函数r对公式(4) 的目标q值进行优化，从而使公式(6)的梯度下降速度加快，减少迭代次数；
[0058]
奖惩函数r如式7所示：
[0059][0060]
其中，(i,j)为网格中横纵坐标。
[0061]
特殊奖惩点的r
(m,n)
特点为：以此点为中心，包括周围的8个点共9个点均 不是障碍点；如图6所示，图中的小方格为特殊奖惩值点，小圆点则不是，因 为小圆点左下方的点是障碍点。
[0062]
特殊奖惩值μ，取值范围0～10-6
，赋予一个变化的μ值，即初始值10-6
，随着 完成每一段目标点的路径，μ值按照初始值均分递减，最终变成0；以图5为例， 目标点一共为7个(不包括最后一个目标点，即起点)，当到达一个目标点时， 如果行进过程中满足特殊奖惩点条件，采用特殊奖惩值，图5中8条路径的特 殊惩罚值分别是：μ1＝10-6
、μ2＝(6
×
10-6
)/7、μ3＝(5
×
10-6
)/7、μ4＝(4
×
10-6
) /7、μ5＝(3
×
10-6
)/7、μ6＝(2
×
10-6
)/7、μ7＝(10-6
)/7、μ8＝0。
[0063]
本发明对改进前后dqn算法的训练次数值-损失函数值进行对比；在使用 相同参数的情况下，参数如表1所示：
[0064]
表1：参数设定
[0065][0066]
改进dqn的收敛速度比改进前dqn算法的快30％左右，改进dqn算法 的平均损失函数值在相同训练次数的情况下比dqn降低了约25％；如图7表 示改进前dqn算法运行得到的训练次数-损失函数变化曲线，图8代表改进 dqn算法运行得到的变化曲线，其中，特殊奖惩值μ＝0.5，训练次数在500次 前属于训练初期，机器人处于刚开始探索学习阶段，未能对障碍物做出正确的 判断，损失值较大；当训练次数达到500次后，机器人仍探索学习避障阶段， 表示机器人已经开始识别障碍物并能够正确避开部分障碍物，但由于训练次数 的不足，它仍在和环境不断地交互学习进一步调整动作避开更多的障碍物，来 降低损失；图8中改进dqn算法更加趋于稳定，训练次数在500～1500时，机 器人在dqn算法和改进dqn算法下都不稳定，训练次数达到1800左右， 改进dqn算法的损失函数趋于平衡；而改进前dqn算法的训练次数要达到 2600次左右，损失函数趋于平衡。
[0067]
上述测试阶段是利用训练的结果模型在相同环境中做测试进一步验证网络 的有效性，测试和训练的目标函数及奖惩值函数一致，因此，改进dqn算法可 以缩短训练时间，使机器人规划出更短的路径。
[0068]
虽然改进的目标函数与奖惩函数加快了算法的收敛速度，但相对应的稍稍 增大了损失函数值；分析结果发现，由于设置的特殊奖惩值0.5过大，导致机器 人奖惩值累积过于膨胀，使得机器人在改进dqn算法趋于平衡的时的判断出现 了严重干扰，图9为特殊奖惩
值0.5修改成10-6
，并且该特殊奖惩值只在学习初 期造成影响，训练完成后将此特殊奖惩值设置为一般奖惩值点0；改进dqn算 法生成的训练次数-损失函数如图9，表示μ的值始终为10-6
时运行得到的训练次 数-损失函数变化曲线，如图10为μ的值在实验初期为10-6
实验后期为0时运行 得到的对应变化曲线：相比于改进之前的算法，两种算法的训练次数均有增加， 这是由于特殊奖惩值的减小导致的，对比图9和图10发现调整改进dqn算法 的μ值前后收敛速度减少约40％；训练次数少于500次，属于训练初期，机器人 处于刚开始探索学习阶段，未能对障碍物做出正确的判断，损失值仍较大，但 两种算法均有下降趋势，且μ值由10-6
变为0的损失函数更早下降；当训练次数 达到500次后，两种算法均已趋于平衡，且μ值改变的算法的训练次数更少，意 味着μ值改变的改进dqn算法能更快的完成训练，机器人能更快的避开障碍达 到目标点，表2中μ＝0为改进前dqn算法，改进dqn算法使用的特殊奖惩值 μ＝0.5、10-6
和changeable μ(10-6
均分后递减为0)，通过对比方向本发明方 法在运行时间、收敛步数和损失函数方面效果明显。
[0069]
表2：四种算法的比较
[0070][0071]
根据改进dqn算法进行多轮学习后，巡逻机器人按照图11所示的路线进 行巡逻；而利用dqn算法时，巡逻机器人容易在图10左下角的黄色圆形目标 点无限循环，无法完成巡逻任务。
[0072]
除了黑色环状障碍点模拟赛道设置之外，本发明中的目标点、起始点以及 中间的障碍点均为随机设置，因此本发明的算法具有较强的普适性；改进前dqn 算法的稳定性和计算速度明显不足；而本发明的效果在保证稳定性的基础上选 择最优的运行时间。
[0073]
以上述依据本发明的理想实施例为启示，通过上述的说明内容，相关工作 人员完全可以在不偏离本项发明技术思想的范围内，进行多样的变更以及修改。 本项发明的技术性范围并不局限于说明书上的内容，必须要根据权利要求范围 来确定其技术性范围。

技术特征：
1.一种基于改进dqn算法的室内巡逻机器人自主导航方法，其特征在于，包括以下步骤：s1、巡逻机器人感知自身周围的环境信息，并结合自身的位置信息和将到达的目标点组成一个状态空间，在状态空间中依次设置若干目标点，并作为dqn算法的输入；s2、通过对dqn算法的目标函数进行改进，使巡逻机器人以当前位置和速度作为下一步动作的输出，当到达第一目标点后，以第一个目标点为起始点寻找下一个目标点，依次不断循环，直至找到最后一个目标点；s3、改进dqn算法的奖惩函数r，提高dqn算法收敛速度，优化环境状态空间的奖惩稀疏性。2.根据权利要求1所述的基于改进dqn算法的室内巡逻机器人自主导航方法，其特征在于，所述奖惩函数r的公式为：其中，(i,j)为网格中横纵坐标，μ是特殊奖惩值；特殊奖惩点的r
(m,n)
特点为：以此点为中心，包括周围的8个点共9个点均不是障碍点；特殊奖惩值μ，取值范围10-6
～0，μ初始值10-6
，μ按照两个连续目标点对应的路径数均分后递减，直到变成0。

技术总结
本发明涉及DQN算法技术领域，尤其涉及一种基于改进DQN算法的室内巡逻机器人自主导航方法，包括S1、巡逻机器人感知自身周围的环境信息，并结合自身的位置信息和将到达的目标点组成一个状态空间，在状态空间中依次设置若干目标点，并作为DQN算法的输入；S2、对DQN算法的目标函数进行改进，使目标点不断变起始点，直到最后一个目标点；S3、通过对奖惩函数r进行改进，提高DQN算法收敛速度。本发明对DQN算法进行改进，避免算法陷入死循环的问题；将机器人行驶的路径分段化，大大减少了DQN算法的迭代次数；通过改进奖惩函数，使DQN算法收敛速度加快，从而完成室内巡逻机器人自主导航的任务。从而完成室内巡逻机器人自主导航的任务。从而完成室内巡逻机器人自主导航的任务。


技术研发人员：毛树人 郑剑锋 周海翔 吴振裕 孔鹏程
受保护的技术使用者：常州大学
技术研发日：2022.01.10
技术公布日：2022/7/5