生物群体智能算法在移动机器人路径规划中的应用研究综述*

李琼琼 布升强 杨家富

（南京林业大学机械电子工程学院，南京210037）

移动机器人路径规划是指在有障碍物的环境 中，根据时间最短、距离最短和转折点最少等要求快速规划出一条连接起始点、目标点且与障碍物无碰撞的路径［1］。传统路径规划算法主要有快速搜索随机树算法（Rapidly-exploring Random Trees，RRT）［2］、人工 势 场 法 （Artificial Potential Field，APF）［3］和 可 视 图 法 （Visibility Graph，VG）［4］等。近些年来，随着科学技术的发展，新的路径规划算法不断地涌现，其中以借鉴生物智能理论与方法提出的生物群体智能算法尤为突出。生物群体智能算法因具有原理简单、稳定性良好、能自控制和自适应性等特点，在移动机器人、无人机、无人船和无人车路径规划中得到了广泛地应用。

1 群体智能算法及其分类

群体智能算法包括非生物智能算法和生物群体智能算法两种。非生物智能算法是依据自然现象或规律提出的算法，代表算法有烟花爆炸算法（Fireworks Algorithm，FWA）［5］、智能水滴算法（IntelligentWater Drop，IWD）［6］和头脑风暴算法（Brain Storm Optimization Algorithm，BSO）［7］等。生物群体智能算法是受到自然界生物群体智能现象启发所提出的一种随机算法，但是到目前为止没有明确的定义和统一的分类标准，部分学者根据生物群体智能算法的起源，将其笼统地归纳为受到生物群体行为启发的启发式算法［8］。本文基于生物群体智能算法的原理和路径搜索机制将其分为功能仿生算法、信息仿生算法、成分（化学）仿生算法三类。

群体智能算法分类如图1所示，主要列出了已成功应用于移动机器人路径规划中的算法，基于不同的类别，重点讨论近些年提出的生物群体智能算法在移动机器人路径规划中的研究成果及算法改进策略。

图1 群体智能算法的分类Fig.1 Classification of Swarm Intelligence Algorithm

2 生物群体智能算法在移动机器人路径规划的应用

生物群体智能算法发展历史如图2所示，2002年开始生物群体智能算法逐渐成为研究热点，新的算法不断涌现。

图2 生物群体智能算法发展历史Fig.2 Development History of Biological Swarm Intelligence Algorithm

2.1 功能仿生算法

功能仿生算法是模拟生物体的某特定生理功能在觅食、群居、逃脱或其他生物行为中的作用而提出的算法。自然界中蝙蝠利用声纳来探测猎物、避免障碍物，天牛依靠两个触角接收到食物气味的强弱动态改变自身的运动方向，YANG教授模拟蝙蝠利用超声波对障碍物或目标进行探测的行为于2010年提出蝙蝠算法（Bat Algorithm，BA），JIANG基于天牛觅食原理在2017年提出天牛须搜索算法（Beetle Antennae Search Algorithm，BAS）。近年来，功能仿生算法已经广泛地应用到视觉跟踪［9］和资源调度［10］中，在移动机器人路径规划中的应用也逐渐成熟。

2013年Niknam T等［11］基于混沌策略产生蝙蝠的初始种群，贺兴时［12］和 Alihodzic［13］分别把模拟退火法、差分简化策略引入到基本蝙蝠算法中，Khooban等［14］在基础蝙蝠算法中引入交叉变异算子，以上改进策略都在一定程度上增加了种群的多样性，但增加种群多样性仅仅能使算法具有更高的分类精度和更强的跳出局部最优的能力，难以提高和平衡算法的全局与局部之间的寻优能力，为了解决此问题，仉新等［15］利用小生境理论优化传统蝙蝠算法，引入排挤机制和惩罚函数提高了算法的全局搜索能力，LIU等［16］聚焦于蝙蝠算法的位置改进，引入邻域算子将位置更新改进为动态邻域操作，但还是存在全局路径规划效率低和精度低等问题。与蝙蝠算法相似，天牛须搜索算法没有较多的参数需要调整，WU Qing等［17］基于生物退回机制（生物在觅食、迁移等过程中具有进入死胡同就会后退一段距离并重新进行搜索的特性）提出一种改进的天牛须搜索算法，改进算法没有明显缩短路径长度，但在运行时间上具有非常显著的优势。为了提高算法的路径搜索速度和精度，LEIM［18］，赵玉强［19］分别将蝙蝠算法与花朵授粉算法（Flower Pollination Algorithm，FPA）、遗传算法（Genetic Algorithm，GA）融合，加快了全局搜索时的收敛速度。

功能仿生算法数学模型简单，需要改进的参数较少，对生物种群整体的要求不高，更注重对于个体的位置、速度的更新。两种功能仿生算法的主要改进措施及其优点如表1所示，功能仿生算法进行路径规划时主要存在容易陷入局部最优值、搜索精度低和无法平衡算法的全局和局部的搜索能力等问题。针对以上问题，主要通过引入混沌、差分、变异交叉算子等策略初始化种群，增加种群的随机性和多样性以防止算法搜索路径时陷入局部最优并且主要采用融合算法加快全局搜索收敛速度。

表1 主要功能仿生算法Tab.1 Main Function Bionic Algorithms

2.2 信息仿生算法

信息仿生算法是模拟生物体在器官、个体、群体等进行信息传递和智能行为的基本原理而提出的算法。早在 1995年，美国社会学家Kenney通过模拟鸟群捕食行为，设计出粒子群优化算 法 （Particle Swarm Optimization，PSO）［20］。2002年，Passino遵循最优觅食原则，模拟人体内大肠杆菌（E.coli）或粘细菌（觅食行为，提出细菌觅食优化算法（Bacterial Foraging Optimization Algorithm，BFO），因细菌觅食算法具有突出的并行搜索优点，现已成功地应用于图像处理［21］、资源调度［22］和机器人技术［23］等领域。2005年土耳其学者Karaboga受到蜜蜂觅食行为的启发提出了人工蜂群算法（Artificial Bee Colony Algorithm，ABC），已经广泛地应用到神经网络训练中［24］。

PSO的核心是一组位置与速度状态方程，计算简单、易于实现，但该模型的随机性大、群体智能性低、算法优化精度低，粒子易早熟。秦元庆等［25］在2004年采用Dijkstra算法在MAKLINK图中搜索最短路径，再使用PSO进行二次路径优化，但PSO的全局优化能力受到二次优化的限制，得到的路径不是最优；SHENG Longyu［26］以遗传算法、自适应遗传算法为对比算法进行车辆路径规划仿真试验，试验结果证明PSO算法所规划出的路径较优，说明尽管传统的PSO算法在规划路径存在优化能力受限等问题，但相比遗传算法仍具有较大的优势。为了提高路径搜索效率，NIE Zhibin等［27］在基础PSO算法中引入非线性惯性权重系数并融合模拟退火算法；康玉祥等［28］基于梯度下降法中的变量沿着负梯度方向变化的原则，引入自适应粒子位置更新系数提高了搜索精度，以上改进策略旨在提高路径搜索的效率，却没考虑到移动机器人搜索路径的过程中与障碍物碰撞导致的精度问题。李擎［29］从避障策略出发，提出“可移动区域”的概念，将迭代过程中的无效粒子设置为全局最优解的避障策略；GAO Qiong［30］提出非目标区域的障碍物填充、坡度对比的碰撞检测、碰撞类型的标记和避障处理的避障策略；陈秋莲等［31］采用神经网络统一静态和动态的障碍物表示和碰撞的模型，快速实现障碍物与路径的检测，引入以上避障策略均能快速规划出无碰撞的路径。

BFO包括趋化、复制和驱散三个步骤。在趋化过程中，细菌运动模式包括翻转和前进，细菌向任意方向移动单位步长定义为翻转。CHEN Hanning等［32］通过自适应调整其运行长度单元在局部搜索和全局搜索中取得良好的平衡。对于较复杂的环境，BFO算法不仅容易陷入局部最优，还具有较差的收敛性，其性能随着搜索空间维数的增加和问题复杂度的增加而大大降低，为了提高算法整体的收敛性和寻优能力，LIANG Xiaodan等［33］引入最优觅食机制使得搜索主体能最大范围的搜索周围的环境；谭立静［34］等从群体拓扑结构出发，在传统BFO算法中引入全面学习策略；Nizar［35］利用BFO算法模型中细菌“翻滚”和“运行”策略，保证机器人能够在不碰撞任何障碍的情况下完成全局路径搜索；Yisti Vita Via为每个细菌选择消除和扩散的概率；Abdi［36］采用APF融合算法将APF中的引力、斥力场的概念引入到基本BFO算法中。最优觅食机制、全面学习策略和定义消除、扩散的概率等策略的引入，扩大了算法的搜索空间，避免细菌个体与障碍物碰撞和逃离局部搜索的状态。

ABC参数少，简单灵活，具有较好的探索能力，但由于人工蜂群的搜索随机性大，导致算法在寻优的过程中容易陷入局部搜索停滞，无法实时搜索，具有全局搜索能力不强和局部搜索精度不足等缺点。MA Qianzhi等［37］以预测控制理论为参考，使用一系列滚动窗口中的局部路径代替全局路径以满足实时要求。黎竹娟［38］把机器人路径规划模拟为蜜蜂寻找蜜源，蜂群之间通过信息交流，协作搜索到全局最优路径。针对ABC算法容易陷入局部最优的缺点，LIANG Junhao［39］利用精英个体来保持种群良好的进化能力；WANG Song［40］在传统的人工蜂群算法中引入交叉变异算子以增加种群的多样；LIZhaoying等［41］从环境地图方面改进，基于凹多边形凸分解原理将凹点与其可见顶点连接起来，最后利用人工蜂群算法在所有的连接域中搜索最优路径，但算法迭代到后期时，食物来源几乎都是最优的，位置的有效数量的差异较小导致路径搜索速度较慢；Contreras-Cruz［42］把人工蜂群算法应用到多移动机器人之间的协调运作中；张林等［43］将障碍物边缘平滑化以减少位置参数，在原算法中引入自适应搜索因子以提高算法的收敛速度和搜索精度。

信息仿生算法具有普遍适用性，模型简单且易于实现，但算法控制参数较多且没有明确的取值标准，只能依据经验，导致算法在不同的搜索时期不能匹配到最优参数，且因传统的信息仿生算法缺乏信息交流，收敛缓慢且易陷入局部最优，研究学者多数以引入精英策略、使用融合算法增加种群的多样性，避免算法在搜索路径时陷入局部最优；通过引入自适应搜索机制、改进算法参数等办法扩大算法的搜索范围，减少无效搜索的次数，提高了算法的收敛速度和搜索精度。在众多的应用领域中，信息仿生算法大多数还停留在静态、单目标问题的处理上，在动态和多目标的问题的求解应用较少。主要信息仿生算法及比较参见表2。

表2 主要信息仿生算法Tab.2 Main Information Bionic Algorithm

2.3 成分仿生算法

成分仿生算法是从化学的角度模拟生物体的行为与功能，通过模拟昆虫分泌、释放微量化学物质来实现觅偶、聚集等活动行为提出的算法。主要成分仿生算法可参见表3。1992年意大利学者DORIGO M模拟蚁群觅食活动规则提出了蚁群算法（Ant Colony Optimization，ACO）；2009年剑桥大学的杨新社教授模拟萤火虫群体发光、趋光行为提出了萤火虫算法（Firefly Algorithm，FA），由于光亮度低的萤火虫总是受到亮度强的萤火虫的吸引，在萤火虫个体移动的过程中实现对解空间地探索，从而完成算法寻优。由于生物体分泌的化学物质具有挥发性，成分仿生算法在路径搜索性能上易出现过早的停滞状态，无法发现更优的路径，许多研究学者对传统成分仿生算法进行改进。

表3 主要成分仿生算法Tab.3 Main Composition Bionic Algorithm

屈鸿［44］通过修改蚁群算法中信息素的更新步骤、调整转移概率，限定信息素浓度的上下界限，解决了由于信息素挥发或更新引起的局部搜索停滞等问题。当外界环境较为复杂时，移动机器人可能会陷入死锁状态，且随着局部信息素的更新，会出现死角边缘周围的信息素不断生长，蚂蚁将很容易在下一次迭代中重复选择死角路径，如果保持这样，就会延迟找到最短的路径，甚至找不到最短的路径，ZHU Xiaoguang等［45］为了避免移动机器人路径死锁，建立了一个死角表。王晓燕等［3］使用惩罚功能对死锁边上信息素进行惩罚，使蚂蚁摆脱束缚，在当前路径上重新选择节点进行搜索。刘建华［46］在蚁群算法中融合APF算法，全局路径的信息素沿着势场合力的方向四周扩散，信息素分布均匀，使蚁群向具有较高适应值的空间搜索，减少蚂蚁搜索过程中“迷失”的数量，但所规划出的路径转折点数量较多，收敛速度过快导致路径不是最优；2018年LIAO Jinquan［47］提出人工免疫和蚁群融合算法，人工免疫算法中的抗体靶向攻击和免疫系统的自动调节功能给出正反馈信息，然后利用蚁群算法进行局部构建，解决了路径规划实验中局部优化但未达到全局最优的问题。马小陆［48］将跳点算法和蚁群算法相融合，由于蚁群算法自身的正反馈机制，搜寻解的质量在增加，但信息素随着时间不断挥发，导致搜寻解的选择性降低，为了解决蚁群算法搜索能力和收敛速度之间的矛盾，Saroj Kumar等［49］在传统的蚁群算法上融合混合正余弦算法，利用正余弦函数的震荡性趋于全局最优解。蚁群算法的核心是信息素浓度的更新和转移策略的改进，与蚁群算法相似，萤火虫算法的核心是光吸收系数和算法参数，LIU Chang［50］在基本萤火虫算法中引入自适应随机参数和自适应吸光系数、Arup Kumar Sadhu等［51］通过 Q学习策略控制随机化萤火虫算法参数和光吸收系数、薛晗等［52］提出一种基于文化算法框架的萤火虫优化算法，可以通过调整FA的随机化参数和光吸收系数实现平衡探索候选解空间和开发新搜索方向的功能，但仅仅对参数进行改进，算法易陷入局部最优，若将路径长度作为唯一的目标函数，每一步都要计算步长及坐标，对于大范围的路径规划来说需要较大的计算量且不能保证找到最优路径。为了解决路径不是最优问题，徐晓光等［53］通过使用小生境萤火虫算法，得到多条优化路径以便二次择优；Alejandro［54］提出多目标（路径安全性、路径长度和路径平滑）函数的萤火虫算法，提高了路径的规划质量。

成分仿生算法结构单一，算法核心都是改进某类化学分泌物的挥发速度和更新步骤，相应地，针对成分仿生算法的改进较为单一，对于蚁群算法，主要是采用修改信息素的更新步骤、调整其转移概率；对于萤火虫算法，主要是改进随机参数和吸光系数，但仅仅改进成分仿生算法的参数不能使其搜索路径的性能有较大提升，最优的策略是在改进参数的前提下，融合其他算法以提高算法的整体性能。

3 生物群体智能在移动机器人路径规划中的应用性能对比

每类生物群体智能算法在进行路径规划时都会存在自身的一些不足之处，综上所述，得出的结果如表4所示，可以看出功能仿生算法、信息仿生算法和成分仿生算法都存在着预先设定参数的问题，并且结果严重依赖参数的选取，往往会因为参数的取值问题而影响到最终的路径规划结果。功能仿生算法和信息仿生算法都具有容易陷入局部最优值的缺点。成分仿生算法的控制参数最少，但搜索机制不易改进，路径规划结果较差。基于上述分析，信息仿生算法的路径规划效果相比于其他两类算法较好，虽然信息仿生算法需要设定的参数较多，但通过引入自适应搜索机制、融合其他算法能极大地提高算法搜索路径的性能。

表4 各分类算法在移动机器人路径规划应用中的对比Tab.4 Comparison of Different Classification Algorithms in Mobile Robot Path Planning

4 生物群体智能算法研究趋势

依据生物群体智能算法的原理和机制将其分为功能仿生算法、信息仿生算法和成分仿生算法三类。在研究分析各类算法的基础上，对应用于移动机器人路径规划的算法存在的问题、解决方案和取得的优化效果进行综合比较，考虑到移动机器人路径规划的准确性和实时性的要求，未来生物群体平衡自适应搜索算法、边缘算法和云网融合技术将是移动机器人路径规划的研究热点。

生物学家利用Logistic方程研究生物种群生长规律，发现只有当种群数量的变化符合Logistic方程规律时整个种群才能维持平衡。相应的，生物群体智能算法是模拟生物群体智能行为提出的算法，在进行路径规划寻优时，只有设置算法中的种群数量符合Logistic方程曲线变化规律，再结合自适应搜索策略才能保证算法在不同的搜索阶段均能匹配到最优参数，才能根据环境变化信息时时更新搜索机制以达到最佳路径寻优效果。

生物群体智能算法在进行路径规划时需要大量的复杂计算，计算过程缓慢导致算法搜索策略不能及时更新从而无法适应环境的变化。边缘算法是在高宽带、时间敏感型和物联网集成的背景下发展起来的一种新的计算模式，边缘算法能够将程序部分移动到附近的设备中进行处理，提高数据处理速度，有力地解决移动机器人运算能力不足的问题，是移动机器人路径规划算法最重要的发展趋势之一。

随着云计算、大数据等新兴信息技术的发展和5G建设的全面启动，极大地解决了终端计算能力问题，未来网络基础设施和流量布局将会由一个个数据中心决定，近些年来在云网融合背景下以实现网络、存储、数据计算、资源调度和任务分配等功能。云网融合技术通过云计算和网络连接等能实现对移动机器人各性能参数的实时监测，对变化的地图环境及时调整行驶策略。