基于深度学习的森林消防机器人路径规划

    孙上杰 姜树海 崔嵩鹤 康玥 陈语唐

    

    

    

    摘 要：针对强化学习算法收敛速度慢，易产生“维度灾难”的问题提出一种深度学习与强化学习相结合的算法，用于解决六足森林消防机器人的路径规划问题。采用Python方法建立二维网格地图，对复杂的环境进行模拟，减小建模的复杂性，在相同的条件下，分别对强化学习和深度强化学习算法进行仿真研究。对比仿真结果表明，深度強化学习算法下机器人到达目标点所需步长随迭代次数而减少，能使学习效率得到显著的提高，可以说明算法的收敛速度更快。

    关键词：森林消防;机器人;深度学习;路径规划

    Abstract：In order to solve the problem of slow convergence and dimension disaster of reinforcement learning algorithm， an algorithm combining deep learning and reinforcement learning is proposed to solve the path planning problem of six legged forest fire fighting robot. Python method is used to build a two-dimensional grid map to simulate the complex environment and reduce the complexity of modeling. Under the same conditions， the reinforcement learning algorithm and the deep reinforcement learning algorithm are simulated respectively. The simulation results show that the step length required by the robot to reach the target point under the deep reinforcement learning algorithm decreases with the number of iterations， which can significantly improve the learning efficiency and show that the convergence speed of the algorithm is faster.

    Keywords：Forest fire fighting; robot; deep learning; path planning

    0 引言

    路径规划[1-3]是在已知或者未知环境下，为移动机器人提供全程无碰撞的最优路径，它是移动机器人定位与导航技术中的重要方法 。 路径规划方法[4]主要包括两个大的类别，一个是基于模型的全局路径规划，这类路径规划问题是已知移动机器人所在环境的信息，通过已知的环境信息进行路径规划;另一个是基于传感器的局部路径规划，即移动机器人所处的环境信息部分或全部是未知的，这里所说的环境是一个动态环境。不管是哪一类路径规划，算法主要包括传统算法、启发式算法[5]、智能仿生学算法[6]和强化学习算法[1]，以及上述算法的改进与融合[7-10]。

    强化学习算法[1]区别于其他算法，是一种不需要先验知识的人工智能算法，与环境直接进行试错迭代，获取奖励值来优化策略，非常适合于森林消防机器人路径规划的研究。根据求解方法不同，强化学习算法可以分为值函数法和直接策略搜索法。值函数法包含与模型无关的强化学习算法和基于模型的强化学习算法。与模型无关的强化学习算法无需构建环境模型就可应用于复杂环境下的机器人路径规划，更符合森林消防机器人路径规划的要求。

    Q-learning学习算法是Watkins等[11]在1989年提出的与模型无关的强化学习算法，这个算法不需要知道模型就可以保证收敛。Q-learning算法是通过构建Q值表来选择最优策略[12-13]，应用于路径规划时，离散精度难以控制，如果精度过低，易造成信息丢失;如果精度过细、维数很大时，会导致维数灾难[14]。因此，该方法不能完全适用于解决本文课题组开发的六足仿生森林消防机器人的路径规划问题。

    深度学习是最近几年流行的机器人人工智能学习算法，它能够有效地处理高维数据。这里将Q-learning算法与深度学习算法结合，解决六足仿生森林消防机器人的路径规划问题。针对强化学习算法收敛速度慢、易产生“维度灾难”的问题，本文提出一种深度学习与强化学习相结合的算法，用于解决六足森林消防机器人的路径规划问题。采用Python编程方法建立二维网格地图，对复杂的环境进行模拟，减小建模的复杂性。

    1 环境建模

    采用栅格法建模，建立二维栅格图。栅格图简单有效，可以对复杂的环境进行模拟，减少了建模的复杂性，数据容易在系统内表示、储存和处理，对于障碍物，森林消防机器人对其位置的判断也更加方便，所以这个环境建模的方法在路径规划等方面可以大规模应用[15-16]。通过建立一个10×10或5×5的二维栅格图对环境进行模拟，如图1所示。定义机器人为绿色方块，障碍物为红色方块，终点为蓝色方块，安全区域是灰色方块，障碍物可以随机定义位置，定义机器人向左运动记为0，向上为1，向右为2，向下为3，如图2所示。

    机器人是一个学习者或决策者，环境是机器人与之交互并包含机器人之外的一切。在仿真软件中，机器人可以是Q学习机器人或深度Q学习机器人。为了比较强化学习算法，在相同的环境中设置这两种算法。在网格图中，有一个a×b的矩阵c，a是行数，b是列数。为了将图形映射转换为矩阵，矩阵的每个状态将表示为浮点数。以下显示了矩阵的不同状态。

    （1）障碍物：在此处设置障碍物，使机器人必须避开此单元。

    （2）访问：机器人已经在一单元中。

    （3）占用：学习机器人正在使用的当前单元。

    （4）目标：机器人必须确定从起始单元格到目标单元格的路径。

    （5）空：机器人移动到此单元是有效的。

    访问的单元格仅用于计算奖励函数，因此不会显示在用户界面上。消防机器人只能够被允许在空单元格上行动，必须避免移出网格图，目的是到达目标。在强化学习中，机器人的目的是根据从环境传递给机器人的特殊奖励信号进行形式化。对于每一个时间步骤，奖励都是一个数字，机器人必须将收到的奖励总量最大化。它不仅可以最大化即时奖励，而且还可以累积奖励。因此去建立强化学习的奖励功能，定义以下规则：

    （1）奖励在这里可以是一个大的范围，它既包括奖励，也包括惩罚，在这里定义奖励为正，惩罚为负。

    （2）奖励范围从-1.0到1.0。

    （3）从一个单元到另一个单元的每一次移动都需要-0.05分。这将保证机器人在顺利到达指定目标的前提下，尽可能减少移动次数，从而找到最短的目标路径。

    （4）为了避免撞到障碍物，如果机器人移动到障碍物单元，将给予-0.75分的处罚。这是一个严格的惩罚，所以希望机器人能够学会完全避免这种惩罚。

    （5）如果机器人以-0.75分离开网格地图边界，将采用上述规则。

    （6）机器人会因为对自己访问过的单元中的任何操作受到-0.25分的惩罚。这里将使用前面提到的“访问的单元格”一词来确定哪些单元格已经访问过或没有访问过。这意味着不应考虑被访问的单元。

    （7）为了避免在有限的循环中，最低的总奖励将会设置为-0.5×环境大小。

    图3是一个动作和奖励功能的示例。由图3可以看出，每个合法行动的奖励是-0.05分，例如从步骤1到步骤2、从步骤2到步骤3或从步骤4到步骤5。当机器人移动到一个被访问过的单元时，将得到-0.25分的惩罚。对于最后的行动，机器人就会到达目的地，所以奖励是1。

    2 Q-learning算法

    Q-learning算法首先建立一张Q值表，设状态-动作对的评价值为Q（s，a）。所以函数Q（s，a）的值是从状态 s 执行动作 a 后的立即回报加上之后遵照最优策略的回报值，即当前状态下机器人选择策略的优劣程度。

    式中： St为t时刻机器人的状态; at为在状态St下的动作;rt为奖励值，是对状态St+1的评估，表示机器人由此状态执行到下一个状态所获得的奖励值。γ∈（0，1）称作为折算因子，r为由状态S执行动作 a 后所得到的奖励值。通过不断迭代修改Q值表，使选择正奖赏动作的概率不断增加，随着机器人不断与环境交互，更改动作策略集，将机器人的动作最后变化为最佳策略动作集。

    一个最典型 Q-learning 算法[17]可以用以下步骤来进行。

    Step 1 ：首先对所有的状态-行为对的 Q 值进行初始化处理，给定最终的初始状态 S。

    Step 2 ：根据机器人行为的选择策略规则给定行为a。

    Step 3 ：实行行为a，状态改变到St+1，并获得相应的报酬。

    Step 4 ：根据相应的公式进行Q的更新。

    Step 5 ： S→St+1。

    Step 6 ：如果 S∈St，结束算法;如果不属于St+1，转至 Step 2 。

    图4是对于确定性马尔可夫决策过程的 Q-learning 算法[18]与环境交互模型的描述。

    Q-learning算法在复杂障碍物密集的环境下需要构建庞大的Q值表，然后根据回报值循环更新Q值表的对应值，该方法极其耗时，因此Q-learning算法很难应用到大状态空间下的移动机器人路径规划。

    3 深度Q网络

    深度Q网络[19]是Q-learning算法和深度学习算法互相结合最终产生的结果。深度Q学习网络是用一个神经网络来保存内容。

    机器人与环境交互的每一步，机器人都有自己的状态，机器人会选择一个措施。在选择最佳措施后，就会进行下一步，机器人将获得一个奖励值。之后的神经网络会根据状态和奖励值来让机器人了解周围的环境。一开始，机器人不知道环境会转移到哪种状态和奖励是什么。在机器人学习期间，机器人会观察这些数值并且进行不断改进神经网络的输出是在0到1范围内作用的概率分布。较高的行动概率可能会为机器人提供更好的累积奖励，如图5所示。

    在左侧，二维网格图包括起点、终点和障碍物。对于机器人来说，理解这个地图太过于复杂，为此利用环境建模中的方法将他转化为矩阵。深度Q网络也像其他传统的神经网络一样，都需要一个包含多个节点的输入层。矩阵是二维的数组，但要将他转化为一维数组，之后隐藏层提取输入空间特征，输出层将其转化为概率分布。可以对Tensor Flow（最广泛使用实现机器学习的算法库）库充分地利用，从而构建一个数值计算图来执行这些任务。图6中的代码展示了如何用高级api-keras（一种易于使用的神经网络库）构建Tensor Flow神经网络。该神经网络不但可以经过激活层利用激活函数，也可以作为实现的代码通过激活参数使用激活函数。编译模型需要使用损失函数。Keras支持好几种十分常见的损失函数。为了使损失函数最小化，Keras模型还需要一个优化器。经过几次实验，选择了tanh（双曲正切函数）作为激活函数，mse（均方誤差）作为损失函数，adam（可以替代传统随机梯度下降过程的一阶优化算法）作为优化算法。

    4 仿真结果

    图7和图8分别为Q学习和结合算法的回报值和到达目标点所需步长随迭代次数变化图，由图7可以看出步长在迭代1 700次左右才开始收敛，而且迭代两千次后的回报值还是负数，说明算法没有很好的学习。图9为机器人在迭代2 000次过程中所得到的最短路径轨迹。该轨迹也是机器人从初始点到目标点的最短距离。说明通过机器人与它所处的环境之间的不断交互，机器人在强化学习的帮助下能够在简单环境中进行良好的路径规划。

    结合后的深度Q学习算法的回报值和到达目标点所需步长随迭代次数变化图（图8），可以看出步长在迭代200多次后就开始收敛，回报值迭代1 000次后也为正数，这说明该算法的收敛速度明显快于Q-learning算法，在复杂的环境下也可以进行良好的路径规划。其对应的最短路径为图10。

    5 结束语

    由于强化学习在复杂环境下的收敛速度比较慢，产生“维数灾难”，针对这个问题本文提出一种深度学习与强化学习相结合的算法，该算法用于解决六足森林消防机器人的路径规划问题。采用Python方法建立二维网格地图，在相同的条件下，对强化学习和深度强化学习算法进行仿真研究，仿真结果表明，深度强化学习算法的学习效率得到显著提高，算法的收敛速度更快。后期将在森林复杂的地形环境下开展森林消防机器人路径规划的实地试验研究。

    【参 考 文 献】

    [1]董瑶， 葛莹莹， 郭鸿湧， 等. 基于深度强化学习的移动机器人路径规划[J]. 计算机工程与应用， 2019， 55（13）： 15-19.

    DONG Y， GE Y Y， GUO H Y， et al. Path planning for mobile robot based on deep reinforcement learning[J]. Computer Engineering and Applications， 2019， 55（13）： 15-19.

    [2]唐文秀， 刘萍洋， 赵偲宇， 等. 基于立体视觉测量的移动机器人导航技术研究[J]. 森林工程， 2013， 29（6）： 102-105.

    TANG W X， LIU P Y， ZHAO S Y， et al. Research on mobile robot navigation technology based on stereo vision measurement[J]. Forest Engineering， 2013， 29（6）： 102-105.

    [3]丁柏群， 姜瑾. 基于蟻群算法和动态路阻的物流配送路径优化[J]. 森林工程， 2014， 30（2）： 149-152.

    DING B Q， JIANG J. Path optimization of logistics distribution vehicle based on ant colony algorithm and dynamic road impedance[J]. Forest Engineering， 2014， 30（2）： 149-152.

    [4]王志中. 复杂动态环境下自主机器人路径规划研究[J]. 组合机床与自动化加工技术， 2018，60（1）： 64-68.

    WANG Z Z. Automatic robot path planning under complicit dynamic environment[J]. Modular Machine Tool & Automatic Manufacturing Technique， 2018， 60（1）： 64-68.

    [5]张本群. 基于启发式算法的路径规划[J]. 计算机仿真， 2012， 29（10）： 341-343.

    ZHANG B Q. Path planning based on heuristic algorithm[J]. Computer Simulation， 2012， 29（10）： 341-343.

    [6]于振中，李强，樊启高.智能仿生算法在移动机器人路径规划优化中的应用综述[J].计算机应用研究，，2019，36（11）：3210-3219.

    YU Z Z， LI Q， FAN Q G. Survey on application of bioinspired intelligent algorithms in path planning optimization of mobile robots[J]. Application Research of Computers， 2019， 36（11）： 3210-3219.

    [7]程传奇， 郝向阳， 李建胜， 等. 融合改进A～*算法和动态窗口法的全局动态路径规划[J]. 西安交通大学学报， 2017， 51（11）： 137-143.

    CHENG C Q， HAO X Y， LI J S， et al. Global dynamic path planning based on Fusion of improved A～* algorithm and dynamic window approach[J]. Journal of Xian Jiaotong University， 2017， 51（11）： 137-143.

    [8]韩亚辉， 王琢， 刘佳鑫， 等. 森林防火机器人的研究现状与发展趋势[J]. 林业机械与木工设备， 2020， 48（3）： 4-9.

    HAN Y H， WANG Z， LIU J X， et al. Research status and development trend of forest fire protection robots[J]. Forestry Machinery & Woodworking Equipment， 2020， 48（3）： 4-9.

    [9]王艳新， 唐文秀， 吴函， 等. 基于多传感器融合技术的智能抢险救灾机器人设计[J]. 林业机械与木工设备， 2018， 46（5）： 17-20.

    WANG Y X， TANG W X， WU H， et al. Design of intelligent emergency rescue robots based on multi-sensor fusion technology[J]. Forestry Machinery & Woodworking Equipment， 2018， 46（5）： 17-20.

    [10]胡小平， 李泽玉. 一种改进的势场法路径规划算法[J]. 机械科学与技术， 2017， 36（10）： 1521-1529.

    HU X P， LI Z Y. An improved potential field method for robot path planning[J]. Mechanical Science and Technology for Aerospace Engineering， 2017， 36（10）： 1521-1529.

    [11]WATKINS C J C H， DAYAN P. Q-learning[J]. Machine Learning， 1992， 8（3/4）： 279-292.

    [12]童亮， 王准. 强化学习在机器人路径规划中的应用研究[J]. 计算机仿真， 2013， 30（12）： 351-355.

    TONG L， WANG Z. Research on application of reinforcement learning in robot path-planning[J]. Computer Simulation， 2013， 30（12）： 351-355.

    [13]劉志荣， 姜树海， 袁雯雯， 等. 基于深度Q学习的移动机器人路径规划[J]. 测控技术， 2019， 38（7）： 24-28.

    LIU Z R， JIANG S H， YUAN W W， et al. Robot path planning based on deep Q-learning[J]. Measurement & Control Technology， 2019， 38（7）： 24-28.

    [14]刘志荣， 姜树海. 基于强化学习的移动机器人路径规划研究综述[J]. 制造业自动化， 2019， 41（3）： 90-92.

    LIU Z R， JIANG S H. Review of mobile robot path planning based on reinforcement learning[J]. Manufacturing Automation， 2019， 41（3）： 90-92.

    [15]刘晓磊， 蒋林， 金祖飞， 等. 非结构化环境中基于栅格法环境建模的移动机器人路径规划[J]. 机床与液压， 2016， 44（17）： 1-7.

    LIU X L， JIANG L， JIN Z F， et al. Mobile robot path planning based on environment modeling of grid method in unstructured environment[J]. Machine Tool & Hydraulics， 2016， 44（17）： 1-7.

    [16]于红斌，李孝安.基于栅格法的机器人快速路径规划[J].微电子学与计算机，2005，22（6）：98-100.

    YU H B， LI X A. Fast path planning based on gird model of robot[J]. Microelectronics & Computer， 2005， 22（6）： 98-100.

    [17]高乐， 马天录， 刘凯， 等. 改进Q-Learning算法在路径规划中的应用[J]. 吉林大学学报（信息科学版）， 2018， 36（4）： 439-443.

    GAO L， MA T L， LIU K， et al. Application of improved Q-learning algorithm in path planning[J]. Journal of Jilin University （Information Science Edition）， 2018， 36（4）： 439-443.

    [18]白尘.马尔可夫决策问题的关键状态优先学习算法[J].中国管理信息化，2016，11（9）：198-202.

    BAI C. Markov decision process MDP critical states prioritized learning[J]. China Management Informatization， 2016， 11（9）：198-202.

    [19]张浩杰， 苏治宝， 苏波. 基于深度Q网络学习的机器人端到端控制方法[J]. 仪器仪表学报， 2018， 39（10）： 36-43.

    ZHANG H J， SU Z B， SU B. End to end control method for mobile robots based on deep Q network[J]. Chinese Journal of Scientific Instrument， 2018， 39（10）： 36-43.