一种基于NEAT的智能体路径规划方法∗

吴 雷 刘 箴 钱平安 刘婷婷， 王 瑾 柴艳杰

（1.宁波大学信息科学与工程学院 宁波 315211）（2.宁波市第九医院 宁波 315211）（3.宁波大学科学技术学院 宁波 315211）

1 引言

智能体的路径规划问题是指在若干障碍物的环境下［1］，为智能体规划出一条从起始位置到目标位置的最优或者次优的安全无碰撞路径。路径规划问题通常存在环境信息量大、障碍物多等约束，其已被证实为NP-Hard问题［2］。一些学者从智能体对环境感知的角度，将智能体路径规划方法分为3种类型［3］：基于环境模型的规划方法、基于事例学习的规划方法和基于智能体行为的路径规划方法；根据智能体对环境信息的掌握程度，又可分为全局路径规划和局部路径规划；根据规划环境中障碍物位置信息是静态或者动态的角度，还可分为静态路径规划和动态路径规划［4］。

本文通过对智能体进行仿真建模，为智能体提供感知模型和记忆模型，并且将感知模型和记忆模型的数值作为神经网络的输入来指导智能体在仿真环境中的行为。并通过适应性函数来对智能体在仿真环境中执行路径规划任务的表现进行评价。然后通过NEAT算法对指导智能体行为的神经网络进行拓扑结构和连接权重的进化，并生成和优化出一个最佳神经网络，指导智能体在设定的进化周期内寻找到一条最优的路径。

2 相关工作

人工智能路径规划技术是通过现代人工智能技术进行智能体的路径规划研究［4］，常见的人工智能路径规划技术有遗传算法、人工神经网络、进化算法、模糊逻辑与信息融合［5～8］。

由于模糊逻辑与信息融合技术在不确定信息处理方面表现良好，且智能体传感器采集的环境信息存在不确定性，使得模糊逻辑与信息融合技术在智能体路径规划中有较好的应用［4］。如郝冬等［12］针对未知环境提出了一种基于模糊逻辑行为融合的路径规划方法，李擎等［13］提出基于动态环境下模糊逻辑路径规划方法，Zun等［14］提出基于信息融合技术的智能体路径规划与避碰方法。然而由于模糊逻辑对信息的精度要求较高，且模糊逻辑无法精确地定义控制目标，这些因素的存在限制了模糊逻辑在路径规划上的广泛应用。

遗传算法及其派生算法在智能体路径规划研究领域已得到了广泛的应用［9～11］。Pang等［18］利用遗传算法实现了智能体的自主避障。然而遗传算法本身结构简单且运行效率不高，只能解决路径规划的部分问题。遗传算法通过与其他算法相结合，充分发挥自身迭代进化的优势，能够得到较好的路径规划效果。近年来一些研究人员将进化算法用于基于行为的智能体仿真［15～18］，并且已经做了相当多的概念证明和实例研究。进化算法（EAs）一直是用于设计和训练神经网络的有力工具。José等［15］利用进化算法和离散时间递归神经网络进化出智能体的避障行为，然而该方法存在规划知识的学习过程，存在学习样本难以获取和学习滞后等问题，从而影响神经网络路径规划的实时性。

德克萨斯州大学的Stanley K.O.和Miikkulain⁃en R.创造性的提出了一种称之为NEAT（Neu⁃ro-Evolution Through Augmenting Topology）的新型进化算法［19］，这是一种逐步增加网络拓扑结构并不断演化网络权重的方法。NEAT算法已经被应用到了一些有趣的领域，并产生了许多令人印象深刻的效果。Stanley等将NEAT方法应用于一个FPS视频游戏中，使得虚拟智能体自主进化出射击目标、躲避敌人、寻找掩体等复杂行为［20］。赵金等利用NEAT方法进化智能体的行为，实现了多智能体对目标的围捕效果，从而证明了算法对于复杂环境适应的有效性［21］。

NEAT算法是遗传算法和神经网络相结合的无监督强化学习方法。该算法对于优化复杂环境中的控制类问题具有良好效果。本文将NEAT算法引入到路径规划这一领域，通过设计合理有效的智能体模型和适应性函数，来研究NEAT算法对于解决复杂环境下智能体路径规划问题的有效性。

3 智能体建模

3.1 智能体动力模型

智能体的动力模型包括以下属性：

1）智能体为两轮差速驱动模型。即，智能体的移动是通过左右两个仿真轮子的速度来控制，vL，vR分别代表智能体左右轮子的速度大小。设定智能体的移动速度大小为：vspeed=vL+vR。

2）只有速度大小不能驱动智能体正确地移动。为了明确智能体在下一个时刻的运动方向，还需要给智能体设置一个视觉向量。若当前时刻智能体的运动角度为 θ ，设定=(sin(θ)，cos(θ))。

3）通过以上两步，可以获得智能体在当前时刻所具备的速度v⇀=vspeed，智能体在运动的过程中，需要保留智能体当前的位置坐标。设定下一时刻智能体的位置坐标为：。

3.2 智能体感知模型

在路径规划中，智能体应该首先具备探测环境的能力。智能体对环境中的障碍物，具备认知和反馈的能力。这就需要为智能体设置相应的传感器或者更形象的称之为触觉器。智能体在运行的过程中，通过传感器与障碍物之间的交互来熟悉环境。在本文中，我们为智能体设置五个传感器S={ }s1，s2，s3，s4，s5，如图1所示。

图1 智能体感知模型

传感器的作用是在智能体探测环境的过程中，如果传感器探测到障碍物，则返回当前传感器与障碍物的碰撞点到智能体中心的距离di，式（1）描述了距离d的求解过程，设传感器的距离向量为D={d1，d2，d3，d4，d5} 。如果传感器返回的碰撞距离di小于了规定的阈值，设置智能体的检测碰撞状态位C为真，否则为假。

判断是否发生碰撞的条件公式为式（2）。其中di是检验仿真机器人是否和障碍物发生碰撞并停止运行的阈值。碰撞检测位C也是作为神经网络的输入，参与到网络的学习中。

3.3 智能体记忆模型

在二维地图中随机分布着若干任意形状的障碍物 oi(i=1，2，3，…，n)，智能体的感知模型在和障碍物oi的交互过程中，会逐渐产生对障碍物的认知，从而避开障碍物。但是，仍然会存在一个问题，那就是智能体虽然成功的避开了障碍物，却可能在没有障碍物的可通行区域，重复访问已经走过的路段。因此，除了探测环境的能力外，我们还赋予智能体另外一种能力：记录环境的能力。通过对访问环境的记录，避免智能体在探索环境的过程中，出现对已经探索过的环境的重复探索。为了实现上述功能，我们将二维平面地图进行栅格化处理。设定地图的长度为l，宽度为w，单元格的长度为u。可以推导出二维地图横向和纵向的栅格数分别为：Nc=l/u，Nl=w/u。经过栅格化处理的二维地图，如图2所示，定义栅格坐标系为。在智能体对未知环境的探索过程中，每一个时刻智能体所访问的单元格都会被系统标记。在实验平台中，对于重复访问的区域，我们做加深渲染处理。以此来区分在此迭代过程中，智能体对区域的探测效果。而传感器负责记录某一时刻传感器末端所占据的单元格被访问的次数ti。设定某一时刻传感器的访问集为T={t1， t2， t3， t4， t5} 。

传 感 器 所 返 回 的 距 离 向 量 D={d1，d2，d3，d4，d5} 、传感器的访问集 T={t1，t2，t3，t4，t5} ，以及智能体的状态位C，共同构成了支配智能体行为的神经网络的输入集I={D，T，C}。

图2 智能体记忆模型

4 基于NEAT的智能体路径规划

4.1 行为学习

设定有N个智能体同时在N个相同的二维环境下运动。智能体具有相同的起点S和相同的终点E。智能体i在一个仿真周期中的路径为Pi，如果路径Pi可以到达终点，则设定Pi为Pi*。则基于NEAT的智能体路径规划模型可表述为：寻找N个智能体的可行路径集合}(m≤n)，并最终获得一条路径，使得 f()=min{P*}。

智能体的运动规则取决于为其分配的神经网络。每一时刻，智能体都会根据其感知器和记忆器，来获取当前时刻神经网络的输入集I，并通过神经网络获得输出vL，vR。智能体根据输出决策出下一时刻的运动位置。在一个运行周期中，智能体不断地进行上述步骤，直至结束当前周期。当前周期结束时，评估每个智能体的表现。我们的目标是优化出一条路径，因此必须构建出可以指导NEAT算法按照此目标方向正确进化的适应性函数F。上文中，为智能体设置记忆器的目的，是防止智能体在不和障碍物发生碰撞的过程中，避免智能体发生“徘徊”的现象，从而尽可能多地访问智能体没有访问过的区域。但是又会带来一个问题，那就是智能体在通向目的地的过程中，会行驶太多的路程。我们希望随着迭代次数的增加，可以消除这一现象，让智能体做到既不重复访问已经行驶过的区域，又可以花费尽可能少的路程到达指定位置。设定智能体运动的总路程为L(P)=N·u，其中N为一次迭代周期中，智能体在没有到达终点时，所访问的单元格的个数，则设定适应性函数为

其中，dx和dy分别表示在一个周期结束时，智能体的最终位置相对起点S的横纵坐标差值，α为设定的权重。

4.2 NEAT算法的基本思想

4.2.1 基因编码

为了进化神经网络的结构，需要一个动态并且可扩展的基因编码方法。在NEAT算法中，为了完整的描述一个神经网络的全部信息，每个基因组都要包含一个连接信息和节点基因信息。每个连接信息都指明一个输入节点和输出节点，以及连接权重。节点基因描述了节点在神经网络内的功能，指示该节点在神经网络中的属性。每个节点基因都包含一个唯一的ID。基因编码示意图如图3所示。

图3 基因编码示意图

4.2.2 突变操作

在NEAT算法中，突变可以同时改变连接权重和网络结构。连接权重的突变和一般的神经进化系统相同，每个权重以固定概率加上一个符合正态分布的浮点数即可。

结构突变则分为两种，如图4所示，DIS表示基因不表达。在增加连接突变中，一个新的连接被加入，将之前未被连接的两个节点相连。在增加节点的突变中，一个现存的连接被断开，一个新的节点被添加在连接断开的位置。旧的连接被断开，并且两个新的连接被添加到基因组中。在新形成的两个连接中，新节点和前一个节点之间的连接权重被设置为1，而新节点和后一个节点的连接权重则继承了旧的连接值。

图4 突变操作示意图

4.2.3 杂交操作

如图5所示，在杂交操作中，Parent1和Parent2称为两个双亲网络，为双亲中的每个基因指定一个创新号，DISAB表示基因不表达。Parent1和Par⁃ent2中都拥有从创新号1～5的结构，而创新号为6、7、8、9、10的结构分别只存在于单一双亲中，在基因组内部的单独基因称为脱落基因（disjoint gene），而在基因组末端的无匹配基因称为过量基因（ex⁃cess gene）。创新号允许NEAT对不同的网络拓扑结构进行杂交，当网络的大小和结构随着进化变得越来越复杂时，网络之间仍然保持兼容。

图5 杂交操作示意图

4.3 人工神经网络的设定

本文为每个智能体分配一个神经网络。我们在实验中，采用可以同时进化人工神经网络的拓扑结构和连接权重的NEAT算法来训练神经网络。NEAT算法的优势在于，神经网络的连接权重和拓扑演化均由该算法负责，因此我们并不需要人工建立神经网络，只需要根据实验需求设置输入和输出神经元的个数，并根据交互环境获得输入数据I，以及引导网络进化的适应性函数即可，当一个仿真运行周期结束后，每个智能体都会依据其表现得到相应的适应性分数，这些适应性分数汇总后，将传递给NEAT算法用于生成下一代的智能体的“大脑”（人工神经网络）。

相比较于传统的拓扑权重演化神经网络，NEAT算法在以下三个方面做了细致的优化：

1）使用历史标记来判断基因之间的同源性。

2）使用物种（Speciation）形成来保护创新。

3）当网络初始化时，采用无隐含节点的最小网络，并且只在必要情况下增加网络拓扑，以此来达到网络维度的最小化。

NEAT算法训练智能体进行路径规划的步骤如下：

Step1智能体根据设定的时间步长，在仿真环境中随机寻路。根据设置的适应性函数，取得上一代所有智能体（表现型）的适应性分数。

Step2只保留适应性分数最高的智能体所对应的神经网络，清空父代中剩余的智能体。

Step3适应性分数最高的智能体的神经网络作为该物种的代表，计算该神经网络和其他物种的兼容性。

Step4若存在15代内适应性分数没有提高的物种，删除该物种。

Step5重新计算显示适应性共享分数，并根据显示适应性共享分数调整种群。

Step6计算在新的一代中，每个物种中子代的孵化数。

Step7通过突变和杂交，生成相应个数的子代，并将子代的基因型转化成神经网络表现型。

Step8计算所有物种及其个体的适应性分数。如果适应性分数小于阈值，则将该个体划分至原来所属物种中。反之，如果适应性分数大于阈值，则创建新的物种，并将该个体加入其中。

Step9将种群中所有物种所含有的个体的基因型转换为神经网络表现型，并将每个表现型网络加载到智能体，指导智能体的行为。

Step10重复Step1～Step9，随着进化代数的增加，智能体在路径规划方面的性能会不断提高。

5 实验分析

仿真实验平台：智能体运动区间为400×400像素的窗口，其边界存在屏障，所有智能体只能在屏障内部运动。活动区域内，存在静态障碍物。仿真环境的运行速度为60帧/s，每代的运行周期为2000步长。智能体的半径为5个像素，传感器的半径为25像素。仿真实验运行500代。神经网络的两个输出值vL，vR经过logistic sigmoid函数做平滑处理，分别用于驱动智能体左右轮子的转动。每代运行完毕之后，采用NEAT方法，根据个体的适应性分数，进化智能体的神经网络。网络的初始状态无隐含层。NEAT方法的主要演化参数如表1所示。

表1 NEAT神经网络主要的演化参数

将本文实验所采用的NEAT算法和基于权重进化神经网络（Weight Evolving Neural Networks，WENN）算法［22］的仿真结果进行比较。设定进化代数为500代，分别通过智能体的适应性值和智能体在趋于终点的过程中，访问单元格的数量，以及优化路径的多样性，这三个方面来评价两种算法的特点。

图6所呈现出的是众多组仿真实验中的一组实验数据图表。在本组实验中，如图6（b）所示，蓝色曲线表示的是WENN算法，所访问的单元格个数。在设定的运行代数内，每一代所访问的单元格个数均为2000，和实验设置的步长一致。这表明在设定的进化代数内，WENN算法并没有成功的优化出一条路径。这说明此方法对初始化敏感，当对固定结构神经网络的权重进行随机初始化时，不同的初始化将对进化算法的进化效果产生根本性的影响。以这组实验而言，WENN算法在优化的过程中，陷入了局部最优解，虽然在进化到320代的时候，适应性值出现了波动，但是并没有对实验的最终结果有所改善。NEAT算法并不存在初始化敏感的问题。虽然NEAT算法的网络初始化也是随机的，但是网络会根据智能体在与环境的交互过程中所反馈的信息，以及NEAT算法本身的进化规则，使得网络拓扑结构不断进化，从而不断地添加网络节点和链接，而新的链接会被赋予新的权重。因此，NEAT算法对于初始化不敏感。

图6 NEAT算法和固定结构网络的初始化敏感性比较

为了避免在进化的过程中陷入局部最优解，NEAT算法设计了一个特有的机制：物种的形成机制。NEAT算法中，把为网络添加新的链接和新的节点的行为，称之为创新。一般情况下，拥有创新的个体适应性并不是很强，这就意味着，新个体在尚未有机会去演绎任何潜在的有意义的行为时，就有很高的概率会被淘汰。这种情况的弊端在于，有潜力的创新不能被继承。因此接下来的进化，只能局限在历史相对较好的个体中，这种情况也会使得整体的优化陷入到局部最优解。而创新有可能在接下来的进化过程中，进化出相对于当前个体更好的表现型。

基于上述问题，NEAT算法模拟了物种形成机制，为整个种群产生新的拓扑创新提供进化场所。这种机制的特点是，具有相似结构的个体只在物种的内部竞争，而不参与其他物种间的竞争。这种机制尽可能的避免了新产生的创新被淘汰的情况发生。

仅仅使用物种的形成机制还不足以保护种群中新的创新。为了更好的保护种群中的创新，必须帮助年幼的个体调整其适应性的值，使得在合理长的一段时间内，能有更多的不同的个体保持为活跃状态。NEAT算法采用显示适应性共享的方法来实现这一想法。在NEAT中，适应性分数由物种的成员所共享，这实际上就是，每个个体的适应性值都除以其相应物种的大小。这样，规模较大的物种的扩张性就会受到限制，而新生的物种在进化竞争中得以生存。此外，年轻的物种在适应性共享计算中，被赋予了更易加速增长的适应性分数。

接下来这组实验，在排除初始化敏感因素的前提下，对比两种方法的实验效果。从实验结果分析来看，物种机制对于路径规划的多样性，以及跳出当前局部最优解，寻找到更优解均起到的良好的效果。图7（a）、（b）、（c）表示在进化的过程中，使用NEAT算法分别在100代、300代和500代所寻找到的路径，重复访问的单元格做颜色加深渲染。这些被智能体寻找到的路径，在轨迹上有本质的区别。

图7 NEAT算法实验效果

而WENN算法，因为其网络拓扑结构是预先设定的。在算法运行过程中，仅仅对网络的权重进行优化。所以该方法只是在寻找到一条可行路径之后，基于此路径进行优化，如图8（a）、（b）、（c）所示，而这种优化方式，往往会陷入局部最优解。

图8 WENN算法实验效果

本组实验中，基于NEAT算法和WENN算法的适应性值比对如图9（a）所示。基于NEAT算法和WENN算法的路径单元格访问数量比对如图9（b）所示。

图9 两种算法对比图

6 结语

本文采用NEAT算法进化神经网络，解决在未知环境下，智能体的路径规划问题。为了使智能体具备探测未知环境中障碍物的能力，设计了智能体的感知模型，同时为了解决智能体重复探测区域环境的问题，为智能体设计了记忆器模型。为了有效的指导NEAT算法的优化方向，设计了合理的适应性函数。实验结果表明，在智能体感知模型和记忆器模型的作用下，NEAT算法在设定的进化周期内，能够通过适应性函数的指导，快速优化出一条路程最短且平滑的路径。同时NEAT算法与传统的将神经网络权重作为优化对象的神经进化算法相比，具有更快的收敛性。NEAT算法的物种机制对于路径规划的多样性，以及跳出当前局部最优解，寻找到更优解均起到了良好的效果。该方法有望为新一代家庭扫地机的研发提供了新的思路。