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

MAPF-LNS2+algorithm based on improvement rate statistics

MAPF-LNS2是一种基于大邻域搜索的算法,用于解决多智能体路径规划问题。优势在于其速度更快,在大多数情况下提供接近最优解的解决方案。但该算法在分配权重时仅考虑当前邻域搜索策略的近期表现并有可能分配了较高的权重,使其他邻域搜索策略出现短暂的“饥饿”现象,导致增加算法的总运行时间。针对该问题基于MAPF-LNS2算法,通过引入改善率统计和时间窗口提出了一种新的多智能体路径规划算法。结果表明,无论是在运行时长还是成功率方面,MAPF-LNS2+算法均优于MAPF-LNS2算法,运行时间最高降低了65.1%,成功率最大提升了16%。

MAPF-LNS2 is an algorithm based on large neighborhood search,which is used to solve multi-agent path planning problem.The advantage is that it is faster and provides a solution close to the optimal solution in most cases.However,the recent performance of the current neighborhood search strategy is only considered in the algorithm and may be assigned a higher weight,which leads to a short“hunger”phenomenon appearing in other neighborhood search strategies,resulting in an increase in the total running time of the algorithm.To solve this problem,a new multi-agent path planning algorithm based on the MAPF-LNS2 algorithm is proposed by introducing improvement rate statistics and a time window.Comparative experimental results show that the MAPF-LNS2+algorithm is superior to the MAPF-LNS2 algorithm both in terms of running time and success rate.More specifically,the maximum running time can be reduced by 65.1%,and the maximum success rate is increased by 16%.