基于改善率统计的MAPF-LNS2+算法

耿文浩, 陈年生, 宋晓勇, 程松林

(上海电机学院 电子信息学院, 上海 201306)

多智能体路径规划(Multi-Agent Path Finding, MAPF)[1]是涉及协调多个智能体在动态环境中共享有限资源的路径选择问题,在实际场景中具有广泛应用,例如无人机编队飞行[2]、物流系统中的货物调度[3]和机器人协作[4]等。MAPF是非确定性多项式(Non-deterministic Polynomial, NP)问题[5],最优解的MAPF算法执行时间随着智能体数量增加而指数级增长,而有界次优的MAPF算法虽然可以在大型实例中执行完成,但可能无法获得完整无冲突的路径结果。由于其复杂性和NP难度,有效解决MAPF问题仍然面临巨大挑战。

MAPF算法按照规划方式[6]划分为分布式和集中式两种。前者主要基于强化学习,在路径重新规划方面显示出较大的潜力,但其训练时间较长;后者则要求中央规划器掌握所有智能体的起始位置、目标位置和障碍物位置等信息。集中式算法又可细分为以下类型:① 基于A*搜索算法[7-9],该类算法的空间代价高,求解速度慢,仅适用于小规模智能体环境;② 基于冲突搜索的算法[10-12],该类算法实现难度较大,并且存在着空间代价高和求解速度慢的问题;③ 基于代价增长树的算法[13],该类算法实现简单速度快,但在高密度智能体环境中易失效;④ 基于规约的算法[14],该类算法存在规约证明困难的问题。

MAPF-LNS2算法[15]是一个具有代表性的多算法融合类MAPF算法,它具有运行速度快、资源占用率低以及适应大规模问题等特点。但由于MAPF-LNS2算法中的自适应大邻域搜索算法在进行自适应大邻域搜索策略修复时,过分关注邻域搜索策略的近期表现,易陷入局部最优解,导致某些策略在得到较高权值后被过度执行,而其他更有潜力的策略则无法得到执行,进而出现“饥饿”现象,从而会增加算法的总运行时间。

本文针对MAPF-LNS2算法存在的问题,通过引入改善率统计和时间窗口,提出MAPF-LNS2+算法。改进算法在邻域搜索策略调度过程中通过观察其改善率趋势,同时考虑到邻域搜索策略的近期和长期表现,以缓解原算法中出现的“饥饿”现象。经对比实验,证实了MAPF-LNS2+算法有效减少了额外运行时间损耗,从而降低了算法总运行时间。

1 MAPF-LNS2算法

MAPF-LNS2算法首先采用有界次优的MAPF算法快速获得初始路径,如果该路径存在冲突,则基于自适应大邻域搜索算法修复初始路径。MAPFLNS2算法的基本流程如图1所示。MAPF-LNS2算法所采用的路径修复模块为自适应大邻域搜索(Adaptive Large Neighborhood Search, ALNS)模块,该模块在路径修复过程中会多次调用3种不同的邻域搜索策略:① 基于碰撞的邻域搜索策略,它所生成邻域的方法是选择当前路径相互碰撞的代理子集,这样就有可能减少冲突个数;② 基于失败的邻域搜索策略,该策略试图通过分析失败的多种原因来调整路径规划;③ 随机的邻域搜索策略,它基于当前路径随机选择周边的其他代理。

图1 MAPF-LNS2算法基本流程

ALNS模块的3种邻域搜索策略在路径的搜索和修复过程中具有不同的表现效果,ALNS模块会根据邻域搜索策略执行完成后的冲突解决个数为其更新权重。更新权重的表达式为

式中:wi为更新后策略的权重(初始时所有被设置为1);wold,i为每个邻域搜索策略的上一次权重;c-、c+分别为邻域搜索策略执行前后路径上的冲突个数;γ为一个用户指定的反应因子,控制权重对冲突代价变化的敏感程度,γ取值在[0,1]内,代表权重相对成功变化的快慢程度,较小的γ值表示权重更快地适应变化。

ALNS模块根据解决的冲突个数来更新3种邻域策略的权重,这使得解决冲突个数较多的邻域搜索策略在接下来的选择中获得较高的权重。如果某个邻域策略的表现下降,其他更具潜力的邻域搜索策略必须等待权重值持平或超越后才能被执行。在权重值平衡的过程中,其他邻域搜索策略可能会出现短暂的“饥饿”现象,这种现象会增加算法的总运行时间。

2 MAPF-LNS2+算法

针对MAPF-LNS2算法中的ALNS模块存在的“饥饿”现象,引入改善率统计机制和时间窗口,在ALNS模块为邻域搜索策略分配权值时,同时考虑其长期表现,以确保算法在短期和长期时间效率之间取得平衡。

2.1 改善率统计机制

在MAPF-LNS2算法中,最为核心的模块是基于自适应大邻域搜索算法的ALNS模块。它首先初始化3种邻域搜索策略的权重为1,并基于概率随机选择一个邻域搜索策略执行。该概率基于3种邻域搜索策略的权重,假设每个邻域搜索策略的权重为wi,则其被选中的概率为wi∑wj。当某邻域搜索策略执行完成后,其解决路径上的冲突个数被用来更新权重。如果某邻域搜索策略在一次改善中取得较为显著的冲突个数减少,那么它将被奖励以更高的权重。即使其在随后的执行中表现出解决冲突个数呈下降的趋势,其他邻域搜索策略也必须等待,直至正在执行的邻域搜索策略的权重逐渐降低,降低至与其他邻域搜索策略权重相当,其他策略才会被执行。这就是ALNS模块存在的“饥饿”现象,即过多关注于当前或近期表现最好的邻域搜索策略。

本文的改进思想是使ALNS模块在为邻域搜索策略分配权值时,同时考虑其长期表现,以确保算法在短期和长期时间效率之间取得平衡。为此采用两个策略:引入改善率统计机制和时间窗口。改善率统计用于评估邻域搜索的效果,通过记录每次邻域搜索后冲突个数的改善情况,来动态调整邻域搜索策略,以提高算法性能;时间窗口则用来限制判断改善率变化趋势的策略。当选定某个邻域搜索策略时,通过历史邻域搜索策略的改善率和一个大小为N的时间窗口,来判断改善率的变化趋势。

定义1改善率是指邻域搜索策略迭代完成后,每次迭代中邻域搜索策略对于冲突数量的改进程度,改善率的计算公式如下:

定义2时间窗口是一种工具,若其大小为N则可以提取某个邻域搜索策略最近N次的改善率记录。

改善率公式在一定程度上反映了算法的改善效果。改善率统计机制就是在邻域搜索策略迭代完成后,通过计算其改善率,以决定下一轮执行的邻域搜索策略。一旦邻域搜索策略存在历史改善率并且数量不小于时间窗口大小,那么随后的迭代过程中ALNS模块会考虑其历史改善率,如若出现改善率下降趋势,则会选择其他最近改善率最高的邻域搜索策略执行,这个过程使得ALNS模块考虑了邻域搜索策略的长期表现并不断修复了邻域搜索策略的权重。

2.2 改善率趋势的判断

在ALNS模块完成策略的权值更新后,需要判断要执行的策略是否呈现下降趋势。为此,引入改善率趋势判断函数,通过提供时间窗口的大小N和改善率记录来检测邻域搜索策略最近N次的改善率趋势。

定义3改善率趋势函数

式中:r为策略最后一次执行的改善率。

改善率趋势函数内部根据时间窗口的大小来截取最近次的历史改善率记录,计算得到其平均值与最后一次执行的改善率r比较,若结果为真,则表明该邻域搜索策略出现了改善率下降趋势,此时则在另外两个策略中进行决策。改善率趋势函数的主要作用是帮助ALNS模块修正权重分配,当ALNS模块为某个邻域搜索策略分配了过高的权重时,考虑该邻域搜索策略其长期表现,使得其他更有“潜力”的邻域搜索策略仍然有机会被执行并修正权重,改善率趋势函数在一定程度上缓解了ALNS模块的权重分配失衡。

2.3 MAPF-ALNS2+算法流程

本文基于MAPF-LNS2算法,通过增强ALNS模块得到改进算法MAPF-LNS2+,其中增强后的ALNS模块称为ALNS+模块。MAPF-LNS2+保留了MAPF-LNS2算法的基础框架,其具体流程为:首先,采用MAPF解搜索器获得初始路径,若该初始路径上存在冲突,则调用ALNS模块启动路径的修补过程。在该过程中,ALNS模块维护了3个邻域搜索策略(基于碰撞的邻域搜索策略、基于失败的邻域搜索策略、随机的邻域搜索策略)的权重(初始权重为1),并随机选中某一邻域搜索策略执行,当其执行完成后更新权重。若路径修补未完成,则重复该过程:ALNS模块根据权重较高者选中邻域搜索策略执行,执行完成后根据式(1)更新权重。ALNS+模块的改进在该重复过程中,具体而言,ALNS+模块在邻域搜索策略执行完成后额外记录了此次结果的改善率,在下次迭代过程中若某邻域搜索策略被选中,则根据大小为N的时间窗口截取其最近N次改善率,并传递给改善率趋势函数判断其改善率是否呈现下降趋势。若出现下降趋势则进行下一步决策,具体的决策过程如下:

(1) 如果其他两个邻域搜索策略都没有被执行过,则随机选择一个邻域搜索策略。

(2) 如果其他两个邻域搜索策略都最近被执行过,则选择改善率较高的邻域搜索策略。

被执行的邻域搜索策略会被重新分配权重,此时可能出现3种情况:

(1) 如果被执行的邻域搜索策略解决冲突的数量降低,则该策略的权值降低,被选择的概率降低。

(2) 如果被执行的邻域搜索策略解决冲突的数量增加,则将该策略的权值提高至K。如果K比其他两个策略的权重更高,则下一次迭代该邻域搜索策略被执行的概率最高。

(3) 如果被执行的邻域搜索策略解决冲突的数量保持不变,则权值保持不变。

由于改进后的ALNS+模块相比ALNS+模块考虑了邻域搜索策略最近N次的表现趋势,因此可以及时修复过高的权重分配,从而避免其他更有“潜力”的邻域搜索策略出现“饥饿”现象,ALNS+模块的流程如图2所示。

图2 ALNS+模块流程

3 MAPF-LNS2+算法的性能验证

为了分析验证ALNS+模块以及MAPFLNS2+算法整体的改进效果,本文设置了相关实验:其中安排第1组实验对ALNS+与ALNS以及ALNS单独运行3种邻域搜索策略的情况进行了对比。实验使用MAPF基准测试套件[1]中的随机场景实例,在地图“random-32-20”上生成了25个实例,每个实例具有不同的映射和代理数量。实验在阿里云ECS服务器“ecs.c8i.24xlarge”上进行,服务器配置为16GB内存,并设置了5min的运行时间限制。其中选取随机场景实例为25个,时间窗口大小设置为8。实验结果如表1所示。表中,R、F、C分别为ALNS模块在单一运行基于碰撞邻域搜索策略、基于失败邻域搜索策略、基于随机邻域搜索策略的情况,后文简称R、F、C 3种策略;A表示ALNS模块,后文简称A 策略;A+表示ALNS+模块,后文简称A+策略。其中,算法的运行时间为25个场景实例中成功实例运行时间的平均值。

表1 5种策略的运行时间对比 s

由表1可知,R、F、C、A、A+ 5种策略在智能体数量设置不同的场景中,A+策略始终保持了最低运行时间,相较于A 策略,其运行时间降低了9%至65%。此现象证实了ALNS+模块相较于ALNS模块本身在运行时间方面的优势。横向对比表1中的数据可以发现,5种策略的运行时间在智能体数量不同的场景下各有其优势,而随着智能体数量逐渐增加,A 和A+策略的优势更加显现,且在运行时间方面A+策略始终优于A策略。

图3为5种策略的运行时间变化趋势。在智能体数量逐渐上升过程中,算法运行时间的改进有下降趋势,图中折线的斜率反映了算法运行时间的变化增速,由于是最小化问题,更大的斜率则表明了算法具有更低的改进效果。尤其在智能体数量为360至400时,斜率出现了最明显的增大趋势。上述实验现象可以解释说明:ALNS+由于在改进上增加了“改善率统计”和“改善率趋势判断”机制,因而产生了额外的开销。在智能体数量较少时,算法本身运行时间较短,因此无法呈现明显优势。随着智能体数量的增加,额外开销与算法本身运行时间的比重会大大降低,则体现了明显的改进效果。当继续增大场景中智能体的数量使其达到某一阈值时,ALNS+模块的改进效果则会有所下降。通过参数调整可以保持ALNS+模块在不同场景中的优势,过高或过低的时间窗口大小都会影响“改善率趋势”的判断,因而直接影响ALNS+模块的改进效果,但减少时间窗口大小会降低改进机制的计算开销。通过参数修正对算法进行调优,能够找到性能提升和额外开销的平衡,保证ALNS+模块的最大优势。多次实验发现,在改善效果较为明显的场景中,时间窗口大小的合理值在4到8之间;对于无明显改进效果的场景中,时间窗口大小为0时,额外开销最小。由表1最后一行数据可知,单独执行R、F、C 3种策略时,解决智能体密集场景的能力有所不足。由于ALNS+模块依赖于3种基本的邻域搜索策略,某一时刻只执行单一的邻域搜索策略,因而会降低改进效果。

图3 5种策略的运行时间变化趋势

第2 组实验对比了MAPF-LNS2+算法和MAPF-LNS2算法在更短限制时间下的成功率。本组实验的最大限制时间分别设置为30、60、90s,其他参数与第1组实验的设置相同。表2展示了对比结果,其中算法的成功率为成功的实例数量与场景实例总数的比值。

表2 算法成功率对比结果

由表2可知,① 在同一智能体数量下,逐渐增加算法运行限制时间,以及同一限制时间下,若逐渐增加智能体的数量,算法的成功率都会有所降低;② 当设置智能体数量为400时,MAPF-LNS2和MAPF-LNS2+算法的成功率最低为28%和44%;③ 相同限制时间和智能体数量下,在成功率方面,MAPF-LNS2+始终优于MAPF-LNS2。实现现象②③表明了MAPF-LNS2+相比MAPFLNS2算法具有较好的成功率表现,但当场景中智能体较为密集时,其表现效果较差。此外实验现象①额外说明了:增加限制时间或降低智能体数量可有效增加算法的成功率。上述实验现象可以解释说明:MAPF-LNS2+算法由于引入了ALNS+模块,因此一定程度上降低了算法的运行时间,在相同智能体数量和时间限制下,其成功率更高。但在智能体数量较为密集的场景中,参考表2数据可知“ALNS+模块在智能体较为密集场景下表现有所不足”,造成了算法的成功率降低。

4 结 论

针对MAPF-LNS2算法中的ALNS模块,存在分配邻域搜索策略权重时产生额外算法运行时间损耗的问题。通过引入改善率统计和时间窗口等机制提出MAPF-LNS2+算法。对比实验结果显示,MAPF-LNS2+算法在运行时间和成功率方面均表现最佳,其运行时间最高降低了65.1%,成功率最大提升了16%。改进效果表明,在对任务实时性要求较高的应用场景,例如自动化仓储系统中,MAPF-LNS2+算法展现出显著的优越性,能够迅速找到解决方案,并有效缩短订单完成时间。