融合探索规则和知识共享的单智能体路径规划

邓辅秦，官桧锋，黄焕钊，李伟科，洪俊填，王宏民，冯其

（1.五邑大学 智能制造学部，广东 江门 529020；2.深圳市人工智能与机器人研究院，广东 深圳 518116；3.五邑大学 应用物理与材料学院，广东 江门 529020）

移动机器人是科学技术发展中最活跃的领域之一，越来越多地用于医疗、交通运输、安防等领域.路径规划是移动机器人不可或缺的一部分，在一定程度上代表了移动机器人的发展水平.因此，路径规划的研究对于促进移动机器人的发展具有重要意义.解决机器人路径规划问题的方法主要分为3类：传统搜索类算法、强化学习算法以及二者的结合.

传统搜索类路径规划算法因其独特的优势而被应用于机器人导航，例如，Dijkstra算法可以计算从源节点到其他节点的最短路径长度，但是在大规模复杂环境中搜索两点间的最短路径时，算法效率较低[1].人工势场算法[2]具有求解实时性，但是需要计算复杂的合力大小与方向，若合力大小为0，则容易陷入局部最优点.广度优先搜索算法[3]和深度优先搜索算法[4]可以规划出最佳路径，却需要遍历环境模型的每个节点，不适用于高维度的未知环境.蚁群算法可以在未知环境中找到路径，但每一次迭代后所有蚂蚁得出的解可能不是最优的[5].Rapidly-exploring Random Tree算法可以通过随机采样来快速规划路径，但是存在生成的路径曲折的问题[6].

强化学习是一类允许移动机器人与环境互动并不断提高机器人学习能力的算法，适用于未知环境下的路径规划[7].近年来基于传统方法积累先验知识再利用强化学习进行路径优化的方法逐渐成为主流，因为先验知识有助于提高强化学习的收敛速度，如文献[8]利用人工势场法初始化环境每个点的Q值，提供了先验知识，减少了Q-learning算法初始阶段因重复探索而产生的大量无效迭代，但该算法容易陷入势场值为 0的点，不适用于障碍物密度大的复杂环境.在栅格环境下，首先基于搜索规则积累先验知识，再将其应用于强化学习算法进行路径优化的方法已经取得了一定的效果[9].但是对于一些复杂的环境，固定性搜索规则容易使机器人陷入死角区域，不能积累有效的先验知识.其次，需要探求能够将所积累的先验知识进行有效整合与共享方法.最后，需要设计出良好的奖励机制才能促使强化学习算法有效地收敛.为此，本文在 3方面进行改进：首先在固定性搜索规则内加入随机因子；其次，采用对Q值求和与求最大值两种方法进行先验知识的合成并共享；最后，通过对比实验设计出一套良好的奖励机制.

1 基于固定性搜索规则的强化学习路径规划

1.1 强化学习算法

强化学习方法是一种在未知环境中通过反复试错来学习近似最优策略，从而使机器人能够在序列决策任务中选择最佳动作的方法[10].在强化学习中，通常将机器人与其周围环境之间的交互过程称为马尔可夫决策过程[11].马尔可夫决策过程的基本单元是一个元组(S,A,R,T,γ)[12]，其中：S是状态空间；A是动作空间；R奖励函数；T是状态转移模型；γ奖励折扣因子.

强化学习方法通过式（1）的贝尔曼方程不断更新状态动作值函数Q(s,a)来进行策略的优化[13]，

将环境建模成二维栅格地图，基于Q-learning的强化学习算法能有效地在栅格地图进行动作决策来规划最优路径.Q-learning是目前应用于机器人路径规划中最有效且能保证收敛的强化学习算法.该算法首先建立一张Q表，机器人在与环境进行交互的同时不断基于环境反馈的奖励来修改Q表的值，更正动作策略集，最终使得机器人的动作趋于最优动作集，规划出最优路径[14].

1.2 基于固定性搜索规则的强化学习算法

在超市、物流仓库等环境中，货架的排列一般是规则的，所以机器人的导航地图常是栅格地图，基于Q表的Q-learning算法适用于该场景下的路径规划.由于经典的Q-learning算法在初始化时没有先验知识，这意味着机器人将随机选择一个可能会碰到障碍物的动作，但是在以上环境中，机器人需要具有有效避开障碍物并像人类一样迅速向目标点移动的能力.

在现实生活中，一些基本的交通规则要求驾驶员具有正确的驾驶行为，而移动导航制造商积累了大量正确的驾驶行为知识作为基本路径数据，此路径数据可以协助其他驾驶员高效且安全地进行路径规划任务.相似地，在机器人使用 Q-learning规划路径之前，可以根据人类交通经验制定一些具有探索性的规则.文献[9]提出了一种基于固定性搜索规则的两阶段强化学习路径规划算法：Rule-Based Shallow-Trial Reinforcement Learning (RSRL)，本文使用该算法作为对比方法.该算法的第一阶段：机器人基于固定性搜索规则生成一张存储着前往目标点的路径知识Q表.固定性搜索规则可归纳为以下步骤：

1）在栅格环境中，分别检测上下左右 4个方向上距离机器人一个格子单元的位置是否有障碍物，并将不会碰壁的动作添加到可执行列表中；

2）以机器人当前位置为起点，得到一个指向目标点的向量，比较该向量的x分量和y分量的大小，以向量的大小为优先级依次检测2个分量方向对应的动作是否在可执行列表，若在，输出较大分量方向对应的动作，则执行步骤4），若都不在，执行步骤3）；

3）从可执行列表中随机挑选一个动作；

4）执行所选动作，每个动作只移动一个栅格，并使用状态动作值函数更新Q表；

5）若抵达目标点则该次迭代结束，否则继续执行步骤1）；

6）执行以上步骤N次后输出机器人对应的Q表；

该算法的第二阶段：机器人使用Q-learning算法进行训练直到完成设定的迭代次数.

2 固定性搜索规则强化学习算法的改进

2.1 固定性搜索规则强化学习算法的不足与改进

在障碍物少的静态场景中，使用RSRL算法第一阶段固定性搜索规则方法产生的先验知识可以提高第二阶段使用Q-learning算法进行路径优化的时间效率，但机器人在某些复杂环境下仍旧无法有效地进行路径规划，甚至会被卡在死角位置，这是因为在第一阶段的第 2步中，RSRL算法几乎以接近 100%的概率径直地驱使机器人往目标点方向移动，这使得机器人缺乏处理不同环境的灵活性，如果前往目标点的方向上障碍物围成了直角区域，如图1所示，左上角的三角形代表起点，右下角圆圈为目标点，黑色方块是障碍物，则机器人不能高效地移动到目标点.

为了解决上述问题，本文提出了一种两阶段强化学习路径规划方法.相比于 RSRL中固定性搜索规则，本文算法在第一阶段添加了概率为(100 -β)/100的随机探索规则，以提高适应不同场景的灵活性.本文将累积先验知识的机器人命名为先行机器人，β表示先行机器人对固定性搜索规则的依赖程度.为了验证不同β值对先行机器人路径规划的影响，在如图 1环境中，先行机器人需要基于本文算法第一阶段的方法完成从起点到目标点移动两次的实验.表 1记录了不同β值的程序运行时间.显然，在这类复杂障碍物环境中，β值越大，路径规划效率越低.

表1 β值与消耗时间的对应关系

图1 RSRL算法难以规划路径的环境

本文算法是一种两阶段的方法，第一阶段基于探索规则积累路径知识，而探索规则是对 RSRL算法中固定性搜索规则的创新，流程如下：

1）初始化仿真环境；

2）每个先行机器人检测其当前位置上下左右 4个方向上距离一个格子的位置是否有障碍物，并将无障碍物方向对应的动作纳入各自的可执行列表；

3）每个先行机器人以β的概率执行：以当前位置为起点，得到一个指向目标点的向量，比较该向量的x分量和y分量的大小，以向量的大小为优先级依次检测两个分量方向对应的动作是否在可执行列表，若在，挑选较大分量对应的动作，执行步骤5），若都不在，则在可执行列表随机选择一动作；

4）每个先行机器人以100-β的概率在可执行列表选择一个动作；

5）每个先行机器人执行所选动作，并通过状态动作值函数更新各自的 Q表，直到抵达同一个目标点；

6）执行以上步骤N次后输出先行机器人对应的Q表；

2.2 知识共享方法的设计

第一阶段算法虽克服了RSRL方法的缺陷，但规划出来的路径有可能是次优的，原因有二：1）仅有一个机器人利用算法从同一起点积累先验知识不能对环境进行充分地探索；2）算法存在一定随机性.

假定一些随机分布在不同的位置的先行机器人使用第一阶段算法来生成路径知识，这些原始的路径知识共享给未被训练新机器人以提高路径规划效率.本文假设先行机器人与新机器人的相对位置是已知的，若在室外，通过定位技术可以确定机器人间的相对位置.

每个先行机器人使用本文算法第一阶段方法积累路径知识后都输出一张存储了路径知识的 Q表，路径知识以Q值的形式存储于Q表，Q表的每一格对应栅格环境中的每一格即强化学习中的状态，每一格根据动作维度划分为若干小格即状态动作序列，小格存储机器人在该状态下执行某一动作后得到的Q值.本文分别利用以下两种知识共享方法对Q表进行处理：

方法1）：在所有Q表中，将相同状态动作序列的Q值相加，然后合并到一个共享Q表中，该表可用作下一迭代中新机器人的基础经验.

方法2）：在所有Q表中，对挑选相同状态动作序列求最大的Q值，然后赋值到一个共享的Q表中，该表可用作下一迭代时新机器人的基础经验.文献[15]将类似的策略应用在Q-learning算法.

本文算法只包含两个子类：RBAQT和RBMQT，分别对应上述知识共享方法1）和2）.因此，在本文算法的第二阶段，分别利用知识共享方法1）或2）合成对应的新Q表后共享给新机器人，新机器人以新Q表作为先验知识，并基于Q-learning算法优化路径直到完成设定的迭代次数.

2.3 奖励机制的设计

强化学习算法需要良好的奖励机制才能有效收敛，如果机器人在探索过程中难以获得正奖励，则容易出现学习缓慢等问题.为解决该问题，本文设计了两种奖励机制并通过实验来挑选出最优的一种奖励方法，如表2所示.在表2中，实验设置R0是机器人成功规避障碍物的即时奖励；R1是机器人到达目标点的奖励；R2是机器人碰到障碍物的负奖励；R3是机器人到达目标点的奖励；R4是机器人基于两种算法第一阶段方法训练的即时奖励.在奖励机制二中，d表示机器人当前状态与目标点之间的欧式距离，距离目标点越近，d值越小，机器人获得的奖励值就越大，d大于等于1.若机器人执行动作后的位置比之前更加远离目标点，则参数i为-1；否则，i为1.参数 f表示在一次迭代中机器人访问某个状态s的频率，f值越大，奖励就越小.每迭代完一次后，f设置为0.

表2 奖励机制

3 仿真实验及结果分析

本文首先设置2种环境进行各10组的随机生成障碍物实验，分别为13× 13维度约有60个障碍物和14× 14维度约有80个障碍物，障碍物约占环境面积的 30%到 40%，但是为了更好地进行各算法在所规划出路径长度上的对比，本文还设置了19× 19维度约有121个障碍物的实验环境，如图2所示，起点为左上角的三角形，右下角实心圆点代表目标点，黑色方块表示障碍物.在该环境的10组实验中，障碍物的位置和数量是不变的.本文算法在以上网格环境进行路径规划时，仅设置了两个先行机器人（图2空心圆圈）积累先验知识，其在空白区域随机初始化.

图2 19×19维度固定障碍物实验环境

本文使用RBMQT和RBAQT两种方法分别基于奖励机制一和奖励机制二在如图2所示实验环境中进行10组实验，记录的10组实验的平均运行时间如表3所示.从表3可以明显得出奖励机制二比奖励机制一有更高的路径规划效率这一结论.机器人越接近目标点，d越小，获得的正奖赏值越大.因此，奖励机制二可以驱动机器人有效地朝目标点移动，故后续实验使用奖励机制二.

表3 程序运行时间对比

机器人的动作空间集合A包括上下左右 4个动作，每个动作只移动一个栅格.一次迭代被定义为机器人从其起点一直运动到目标点的一次过程.为了确保算法最终可以收敛，一组实验中设置19次迭代，其中包括了算法第一阶段方法进行先验知识积累的N次迭代.实验参数的设定如表4所示，ε是贪婪率，它表示机器人对先验知识的依赖，若ε太小，则不能充分利用先验知识；若ε太大，则机器人无法很好地探索，然后容易陷入局部最优状态.Δε表示每两次迭代中ε的增量，直到ε大于97.5则停止.α是学习率，γ是折扣因子.

表4 参数设置

在19× 19维度约有121个障碍物的实验环境中，机器人基于本文算法、蚁群算法、Q-learning、RSRL算法在相同的迭代次数下所规划的路径如图3所示.

图3 路径规划图

本文实验旨在算法能够稳定地规划出最优路径的前提下统计算法运行的时间.故在确保 RSRL算法和本文算法可以收敛的前提下，重复做 10组实验，每组实验迭代 19次，计算 10组实验的平均运行时间，这包括先行机器人使用两种算法第一阶段方法产生先验知识的训练时间.此外，本文还将近些年流行的强化学习算法Q-learning纳入对比范畴，迭代的次数、实验的组数与RSRL算法和本文算法一致.每种算法的平均运行时间对比如表5所示，与Q-learning、RSRL算法相比，本文算法在每种环境下均具有优势.特别地，为了量化本文算法的优势，先计算出对比方法中最具优势的RSRL算法在3种实验环境平均运行时间之和，为249.43 s，再计算出本文两个算法在3种实验环境平均运行时间之和的均值，为150.30 s，得出差值99.13 s，该差值占RSRL算法平均运行时间之和的百分比即为本文算法相对于RSRL算法在时间效率上的提升，最终求得为39.7%.

表5 不同实验环境下的各算法平均运行时间对比

最后，在gazebo仿真平台上进行了如图2所示实验环境下的机器人路径规划仿真，机器人规划最优路径的视频可以在以下链接中查看：https://www.bilibili.com/video/BV1SK411F75e/.

4 结论

本文提出了一种融合随机探索规则和知识共享的两阶段强化学习路径规划方法，适用于求解栅格环境下的单智能体路径规划任务.在本文算法的第一阶段，先行机器人基于随机探索规则高效地完成先验知识的积累，之后分别利用两种知识共享方法得到Q表.在本文算法的第二阶段，新机器人基于共享Q表进行路径规划，无需大量的训练时间即可规划出最优路径.本文在3种实验环境中进行了算法运行时间的对比测试，与传统方法中最优的RSRL算法相比，本文算法在时间效率上提均提升了39.7%.新机器人可以在训练过程中减少无效探索的次数，路径规划效率得以提高.本文算法适用于执行离散动作的无人仓储物流机器人.但是由于 Q-learning算法的局限性，如若目标点发生变动则需要再次学习才可规划出最优路径，后期有望通过更多的启发式的算法产生更加有效的先验知识以克服本文算法的局限性.