段伟浩，赵 瑾，梁家瑞，曹 锐
(太原理工大学软件学院，山西 晋中 030600)
近年来，在机器人寻路领域、虚拟仿真系统以及游戏等领域，对路径规划的要求越来越高，普通、单一的寻路方式已经无法满足需要。一个优秀的寻路算法不仅要保证路线最优，时间、空间消耗低，同时也需要路线更加智能、合理。不能出现路线单一、碰撞、拥堵、死锁等现象。
目前，在寻路领域，A*算法及其改进算法，因实时性，搜索效率高等特点被广泛应用于各个领域[1]。大量学者为了提高算法的效率、可靠性，在A*算法的基础上衍生出其它算法，如A-STAR-Dijkstra-integrated算法[4]可以避免死锁问题，IBAS算法[5]降低了时间复杂度以及空间复杂度。但是由于A*算法本身无法避免拥堵、碰撞、路线单一等问题，因此这些算法无法完全满足路线智能化的需求。
而随着深度强化学习(deep reinforcement learning)成为学者们的研究热点。在寻路领域，也出现了大量研究成果。Martinsen A B，Lekkas A M等人使用深度强化学习解决曲线路径跟随问题[6]；
Li M，Gao J，Zhao L等人在复杂城市交通网络中寻找最佳解决方案[7]；
Gutiérrez-Maestro E，López-Sastre R J，Maldonado-Bascón S提出了一个基于地图的模型，将奖励函数设计为具有碰撞感知的功能[8]。Song W，Zhou Y，Hu X等人提出了使用MRNS q-learning提高处理效率和收敛速度[9]。
然而，上述研究与应用无法完全解决多智能体动态寻路所遇到的问题。例如，多个智能体在环境未知的情况下，能否避免相互碰撞、拥堵等情况；
面对突发的道路阻挡问题，是否可以有效避让，重新规划路线。
近年来，多智能体寻路研究取得了一定的突破，例如Okoso A，Otaki K，Nishi T针对停车场短缺的问题提出CBS-Pri和CA+-Pri两种方法为车辆自动规划路线[10]。Barták R，vancara J，kopková V等人使用机器人在避免碰撞的前提下抵达目标位置[11]，但仍存在问题。
在虚拟领域的多智能体寻路也存在碰撞、拥堵、路线单一等问题。以目前十分流行的3D开发引擎Unity为例，其提供的NavMesh导航系统的核心算法是基于A*算法的扩展算法，可以很好的适应三维环境寻路。但是无法检测环境的变化，依旧存在拥堵问题、道路交通变化等问题[12]。更为关键的是，NavMesh系统所规划的路线，在起点、终点以及环境不变时，多次规划的路线完全相同，与现实不符。虽然Unity官方曾经发布动态规划的工具，但是依旧无法灵活的根据环境自行调整路线。针对NavMesh存在的问题，很多学者也提出了优化方法。例如ANavMG[12]，HNA*[14]等，但是这些大都是对NavMesh本身进行优化，依旧无法解决上述问题。针对其它方面的改进，很多学者都提出了自己的想法。例如He Z，Shi M，Li C等人在其文中提出了在特殊游戏场景中的一些改进与应用[15]，以及动态加权BDBOP[16]等方法。
本文中利用深度强化学习的优势，提出了一种基于全连接神经网络的近端策略优化算法应用于多智能体动态寻路领域。为了解决训练过程慢、效果差、稀疏奖励等问题，本文还将采取好奇心驱动(Curiosity-driven)以及生成对抗性模仿学习(Generative Adversarial Imitation Learning)加快训练进程。通过将训练成功的模型与Unity提供的NavMesh系统对比，以证明本文所使用的基于全连接神经网络的近端策略优化算法可以解决路线单一、拥堵、相互碰撞等问题，更加适合于多智能体动态寻路。
2.1 近端策略优化算法
近端策略优化(Proximal Policy Optimization，PPO)算法是Schulman J，Wolski F，Dhariwal P等人提出的一种策略梯度(Policy Gradient，PG)算法的改进算法[17]，通过与环境交互进行数据抽样。PG算法训练的目标就是找到具有最大期望奖励的序列[18]。采取梯度上升(gradient ascent)的方法，求出期望奖励的梯度，并不断更新。
但PG算法通常因为对步长的选择很敏感而无法取得良好的效果。如果步长太小，可能导致训练进程非常慢；
如果步长过大，可能会出现信号被噪声淹没的情况。不仅如此，PG算法的效率往往也不会太高。
为选择合适的步长，定义目标函数为
(1)
其中πθold(at|st)表示更新之前的动作出现的概率，πθ(at|st)表示当前动作出现的概率；
上标CPI指保守策略迭代(conservative policy iteration)；
At表示在t时的优势函数(advantage function)的估计量。
式(1)中引入了概率比的概念，可以看出：如果不对概率比率进行约束，CPI的最大化会使梯度更新过大。因此，还需要对其进行约束，使概率比rt(θ)不能过大。综上所述，PPO的目标函数为
LCLIP(θ)=Et[min(rt(θ)At，clip(rt(θ)，1-ε，1+ε)At)]
(2)
其中ε是超参数，通常为0.1或0.2。clip( )是截断函数，作用是使第一项的值在第二项和第三项中间。也就是使概率比在1-ε和1+ε之间，不会和1相差太大。若策略更新过大，则会受到惩罚。
PPO算法约束了策略更新的大小，使其不会更新过大，有效解决了PG算法中因步长敏感而导致训练效果不佳的问题，而且应用起来更加简单。
2.2 基于全连接神经网络的PPO算法
虽然上文提到的PPO算法为行为提供了一种范式，能够让整个系统做正确的决策，但是想要在三维场景中实现动态寻路，首先要对场景中的环境信息进行处理，使得智能体可以感知到环境。然而这些原始的、非结构化的真实世界的感知信号并不是为机器的运行而设计的。虽然对人类来讲识别这些很容易，但是机器却很难识别。而深度学习是目前处理非结构化的环境的最好工具之一，它的一个主要优势是端到端，可以自动提取环境的特征、属性。而且使用端到端的训练得到的特征可能要比自己想得到的特征更加有效。
因此，本文在PPO算法的基础上，引入全连接神经网络。智能体通过自身搭载的射线组件探测周围陌生的环境，将射线信息传入全连接神经网络，使用深度学习的方法提取特征，并传入PPO网络中，最终输入五个动作的概率。其中，全连接神经网络的隐藏层层数为2，每层神经元的个数为512。具体结构如图1所示。
2.2.1 智能体行为
图1 算法结构
在实验过程中，每个智能体的行为(behavior)决定了其如何做决定。其中，行为参数是重要的属性，包括矢量观测空间(Vector Observation Space)、矢量动作空间(Vector Action Space)。
本文使用的矢量观测空间包括：智能体在空间坐标系中运动时三个正方向的速度，挂载在智能体上的7条射线，以及射线需要检测的三个对象(墙、智能体、目标)。
本文使用的矢量动作空间为一个离散的动作分段，矢量动作空间分为五个动作，分别为：前进、后退、左旋、右旋、无动作。通过变量控制移动速度以及旋转角度。
2.2.2 奖惩函数
在本文所使用的基于全连接神经网络的近端策略优化算法中，智能体需要不断与环境交互，得到环境给予的奖励或者惩罚，通过使奖励最大化而不断优化自己的寻路路线。
由于环境要根据智能体的行为动作给予反馈。在这里，定义了奖惩函数：
1) 每走一步则惩罚1/最大步长；
2) 若碰撞到障碍物惩罚0.01；
3) 中途若碰撞其它智能体，则惩罚0.1；
4) 到达目标之后，奖励1。
其中，每走一步设置惩罚是为了使智能体减少动作数量，尽量寻找最优路径。碰撞到障碍物以及其它智能体惩罚是为了避免相撞，避免拥堵。智能体到达目标位置后，则获得完整奖励。通过奖惩函数，智能体会减少产生惩罚的动作的概率，增加获得奖励的动作的概率，不断向获得更大的奖励靠近。
为验证本文所提出的基于全连接神经网络的近端策略优化算法的优越性与鲁棒性，特搭建简单、复杂两种实验场景进行仿真，并与Unity中NavMesh系统的算法进行对比。针对训练过程中存在的稀疏奖励问题，本文使用好奇心驱动及生成对抗性模仿学习完成模型训练。
本文实验使用CPU训练模型。所使用的软件、硬件信息如下所示：
引擎版本为Unity2018.4.10。CPU型号为Intel(R) Core(TM) i7-9700 CPU @ 3.00GHz，内存为16GB。
3.1 场景搭建
在实验中，首先使用Unity提供的工具，搭建实验环境，简单场景如图2所示：
其中，图2右侧的九个正方体为智能体，左侧圆球为目标位置。在场景正中设置了5个障碍物，智能体无法直接穿过。
图2 简单场景
简单场景中场景规模较小，智能体距离目标初始位置较近，且障碍物数量为五个，因此，智能体可选择的路线较少。为了证明本文算法不只适用于简单场景，特搭建复杂场景，如图3所示。
图3中，左侧圆球为目标点初始位置。右侧设置了12个智能体，场景中间摆放了大小不等的若干障碍物。从图3中可以看出：复杂场景相比简单场景不仅面积更广，智能体数量、障碍物数量更多，并且障碍物更加杂乱、无序，可选路线更多，出现碰撞、拥堵的几率更大。为智能体训练增加了难度。
图3 复杂场景
3.2 仿真研究
在Unity提供的NavMesh系统中，想要使智能体到达目标位置，目标位置和环境信息都必须是已知的。然而，本文使用的基于全连接神经网络的近端策略优化算法可以在环境、目标点未知的情况下寻找合理路线，更符合真实情况。
训练开始前，环境对于智能体来说是未知的。智能体需要自行探测周围环境。直至找到目标，并且到达目标位置。
3.2.1 训练参数
实验中，智能体按照上述方法不断接受信息，做出反应，并大量重复训练。当智能体的步长达到5000步还没有找到目标位置，则重新开始。
其中，训练时使用PPO算法所需配置的主要参数如表1所示：
表1 PPO算法中的参数信息
其中β代表熵正则化的强度，可确保代理在训练期间正确地探索动作空间；
ε的大小则影响着训练过程中策略演化的速度；
正则化参数的大小会影响训练的稳定性；
学习率代表更新步骤的强度。
3.2.2 好奇心驱动
上文中提到的奖励通常是由环境提供，可以认为这种奖励是外部奖励，因为这些奖励的规则是在训练模型之前就确定好的。相应的，也有内部奖励，目的是希望通过内部奖励的方式，使智能体可以积极地探索更广阔的空间，以便获取更大的外部奖励。
由于只有碰到目标物体才有奖励，当面对地图规模较大的场景时，在训练的初期阶段，智能体很难获得奖励。在这里，本文将这种情况叫做稀疏奖励任务。
针对这种情况，本文引入好奇心驱动(Curiosity-driven)来解决这一问题[19]，在其论文中，他们建议训练两个独立的神经网络，一个正向的(forward)和一个反向的模型(inverse model)。对反向模型进行训练，用于接收智能体当前和下一个观察值，并用结果去预测两个观察值之间采取的行为。对正向模型进行训练，对下一个观测进行预测。预测与真实之间的差异被用在内部奖励中，更大的差异就意味着更大的内部奖励。
使用好奇心驱动的主要配置参数如表2所示。
表2 好奇心驱动中的参数信息
其中，强度表示好奇心驱动模块产生的奖励增加的幅度；
gamma表示奖励的折扣系数。
使用好奇心驱动后，训练过程如图4所示。
在图2的简单场景中使用好奇心驱动后，训练过程中智能体累积奖励如图4(a)所示，好奇心驱动使用与否并不影响累积奖励的走势。原因是简单场景面积较小，智能体与目标初始位置相距较近，即使在不使用好奇心驱动的情况下依旧可以顺利找到目标。不属于稀疏奖励任务。然而，在图3的复杂场景中使用好奇心驱动后，从图4(b)中可以看到，若不使用好奇心驱动，在训练了2000000步后，依旧无法找到目标。而使用好奇心驱动后，500000步时，累积奖励变为正值，900000步时，累积奖励达到峰值，完成训练。
图4 好奇心驱动对累积奖励影响对比图
3.2.3 模仿学习
在使用强化学习训练的过程中，智能体通过不断试错的方式来探索环境，通过向获得奖励的方向靠近从而不断改良路径。然而，如果有一个简单的演示，告诉智能体如何执行，那么将大大减少前期的探索。在此，本文引入模仿学习的概念，使用生成对抗性模仿学习(Generative Adversarial Imitation Learning，GAIL)的方法[20]。其中主要配置参数如表3所示。
表3 模仿学习中的参数信息
在使用生成对抗性模仿学习之前，需要录制一个演示(demo)。本实验将Unity自带的录制工具挂载在智能体上，手动录制。由于演示是人为录制，其路线可能不会非常完美。为了避免因演示不完美而造成学习效果欠佳的情况，在此，将强度(strength)的值调小，控制在0.01。具体的训练进程如图5所示。
在图5(a)所示的简单场景中，智能体在80000步后奖励已经为正，200000步后奖励值保持稳定，相比于不使用模仿学习，奖励达到峰值提前了约200000步。在图5(b)所示的复杂场景中，单单使用PPO算法在训练了2000000步后依旧无法顺利找到目标，使用模仿学习之后，400000步后累积奖励成为正值。可以看出不论是在简单场景还是复杂场景中，使用生成对抗性模仿学习都可以加快训练进程。
图5 模仿学习对累积奖励影响对比图
综上所述，本文使用基于全连接神经网络的近端策略优化算法，并且同时使用好奇心驱动、生成对抗性模仿学习，将三者结合后，智能体训练速度更快，与其单独使用的对比如图6所示。
图6(a)中表示简单场景中的训练过程，可以看出好奇心驱动和生成对抗性模仿学习以及PPO同时使用比其单独使用更早达到累积奖励的峰值。不同方法在复杂场景的区别更加明显。如(b)中所示，三种方法同时使用比使用好奇心驱动和PPO算法两种方法效果更好，累积奖励变为正值提早了400000步。三种方法同时使用时，达到峰值后累积奖励变化浮动小，更加稳定。
图6 不同方法对累积奖励影响对比图
图6中可以看出不论简单还是复杂场景，同时使用好奇心驱动和模仿学习可以有效地将训练步长缩短。
3.3 结果分析
3.3.1 NavMesh寻路结果
NavMesh是Unity提供的导航系统，在普通三维寻路中操作简单，可以实现大部分简单的寻路功能。
在图3复杂场景中，指定目标位置后，使用NavMesh寻路具体路线如图7所示。
图7中线条为智能体寻路轨迹，智能体根据事先给定的目标位置，可以在避免碰撞障碍物的前提下快速抵达目标位置。
图7 NavMesh寻路结果图
虽然在上述实验中，NavMesh实现了寻路功能，而且使用方便，但是从图7中可以看出，多个智能体寻找目标的路径单一，所有智能体寻路轨迹一模一样。会出现拥堵情况，如图8所示。
由于NavMesh无法检测到路面是否拥堵，也无法避免碰撞。当多个智能体同时向一个目标点运动时，所有智能体只能同时拥挤在一处，无法根据实际情况寻找其它通路。
图8 NavMesh拥堵情况图
而在虚拟仿真系统以及游戏中，NPC(Non-Player Character)路线不可能完全一致。而且如果出现拥堵、碰撞等情况，既会大大降低用户体验，也不符合实际情况，破坏了沉浸式体验。因此应当避免此类事件发生。
3.3.2 使用本文算法训练结果
从NavMesh寻路结果中可以看出，NavMesh虽然在普通三维导航过程中表现良好，但是在多智能体寻路方面存在问题。从实际效果来看，NavMesh实现多智能体动态寻路时，无法判断前方是否拥堵，无法避免碰撞，也无法根据拥堵情况和其它智能体突然出现而调整自己的路线。
使用基于全连接神经网络的近端策略优化算法训练完成的模型可以避免上述问题。使用好奇心驱动、模仿学习以及PPO训练完成的模型的运动路线如图9所示：
图9中，多个智能体的路线并不相同，智能体会根据前方是否有其它智能体、障碍物做出判断，避免拥堵、碰撞。当前方有智能体阻挡通道时，智能体会选择其它路口通行，具体情况如图10所示。
图9 本文模型路线图
图8中NavMesh的寻路结果会使所有智能体拥堵在同一路口，造成拥堵和碰撞。使用本文方法训练出的模型可以有效避免这一问题，如图10所示，智能体会自主寻找其它通道，避免拥堵，避免碰撞。
图10 智能体自主选择路线示意图
通过对比，证明了使用本文算法训练出的模型在多智能体动态寻路上的优势：所规划的路线更加符合真实情况；
智能体的寻路过程也更加智能，符合多元化的需求。
本文在多智能体寻路领域，提出了使用基于全连接神经网络的近端策略优化算法解决寻路问题。通过射线检测周围环境，使智能体可以根据环境的实时情况改变自己的行动轨迹，避免拥堵，寻找目标。此外，还通过使用好奇心驱动的方法增加内部奖励，使训练模型的速度更快，适应性更广。实验结果表明，使用本文方法训练出的模型在多智能体寻路方面具有很好的适应性，可以很好的解决目前多智能体寻路时出现的无法避免拥挤，路线单一等问题。而且本文使用的方法不仅仅局限于虚拟领域，同时也可应用于机器人、无人机、汽车等现实世界的寻路。本文旨在针对多智能体动态寻路中存在的缺陷进行改进，以Unity引擎为例实现多智能体寻路，说明本文方法在多智能体寻路领域的可行性、优越性。同时也为解决其他类似问题提供了一种新的思路。
后续工作中，可对本算法中使用的全连接神经网络进行优化，或者使用更优的神经网络，进一步缩短训练时间、步数，提高训练的稳定性。
猜你喜欢路线神经网络驱动基于模糊PI控制的驱动防滑仿真系统分析汽车实用技术(2022年7期)2022-04-20屈宏斌：未来五年，双轮驱动，砥砺前行房地产导刊(2020年11期)2020-12-28最优路线数学小灵通·3-4年级(2020年11期)2020-12-14『原路返回』找路线数学小灵通·3-4年级(2020年3期)2020-06-24神经网络抑制无线通信干扰探究电子制作(2019年19期)2019-11-23轨旁ATC系统门控柜接收/驱动板改造铁道通信信号(2019年4期)2019-10-10画路线小学生导刊(2017年31期)2017-08-15找路线小学生导刊(低年级)(2016年8期)2016-09-24基于S3C6410的Wi-Fi驱动移植实现通信电源技术(2016年1期)2016-04-16基于神经网络的拉矫机控制模型建立重型机械(2016年1期)2016-03-01