mapf-lns-benchmark

mapf-lns-benchmark数据集由西蒙弗雷泽大学、滑铁卢大学和卡内基梅隆大学共同创建，用于评估多智能体路径寻找（MAPF）算法。该数据集包含25个随机场景，覆盖多种地图类型，旨在为MAPF-LNS方法提供统一的评估标准。数据集的创建过程包括选择代表性地图和生成评估场景，主要应用于优化多智能体系统的路径规划问题。

The MAPF-LNS-Benchmark dataset was co-developed by Simon Fraser University, University of Waterloo, and Carnegie Mellon University to evaluate Multi-Agent Path Finding (MAPF) algorithms. It contains 25 randomized scenarios covering various map types, and is designed to provide a unified evaluation standard for MAPF-LNS methods. The dataset's development process includes selecting representative maps and generating evaluation scenarios, and it is primarily applied to optimize path planning problems for multi-agent systems.

原始信息汇总

数据集概述

简介

多智能体路径寻找（MAPF）旨在为一组智能体安排无碰撞的目标到达路径。基于大邻域搜索（LNS）的随时MAPF求解器因其灵活性和可扩展性而受到关注。邻域选择策略对MAPF-LNS的成功至关重要，已有多种方法被提出。

我们通过对同一基准和超参数搜索设置下的突出方法进行公平比较，推动现有基于学习的方法的新挑战，并展示将机器学习与MAPF-LNS集成时的未来研究机会。

数据准备

请查看数据准备了解如何下载数据。

方法

基于规则

生成基于规则结果的可执行文件位于子模块exe/lns-rule-based下。请查看子模块exe/lns-rule-based的说明了解如何实现基于规则的结果。

基于学习

• SVM 有关如何训练和推断SVM-LNS的说明，请遵循SVM-LNS实现。

• 神经网络 有关如何训练和推断NNS-LNS的说明，请遵循NNS-LNS实现。

• Bandit 生成bandit结果的可执行文件位于子模块exe/bandit下。有关如何推断bandit的说明，请遵循bandit实现。

搜集汇总

数据集介绍

构建方式

mapf-lns-benchmark数据集的构建基于多智能体路径规划（MAPF）问题，旨在为多个智能体规划无碰撞的路径。该数据集通过大规模邻域搜索（LNS）方法生成，LNS通过迭代破坏和修复智能体的路径来逐步优化解。具体而言，初始解通过快速次优MAPF求解器（如优先规划PP）获得，随后在每次迭代中选择一个邻域（即一组智能体），破坏其路径并重新规划以避免冲突。通过这种方式，数据集生成了多种场景下的路径规划解，涵盖了不同地图和智能体数量的组合。

使用方法

mapf-lns-benchmark数据集的使用方法主要包括以下几个步骤：首先，用户可以选择不同的地图和智能体数量组合来生成实验场景；其次，用户可以选择不同的邻域选择策略（如基于规则或基于机器学习的策略）来优化路径规划解；最后，用户可以通过对比不同策略的最终延迟和曲线下面积（AUC）来评估其性能。数据集还提供了统一的实验设置和超参数搜索，确保了不同方法之间的公平比较。此外，用户还可以通过调整初始解和重新规划求解器来进一步探索不同参数对结果的影响。

背景与挑战

背景概述

mapf-lns-benchmark数据集由Jiaqi Tan、Yudong Luo、Jiaoyang Li和Hang Ma等研究人员于2024年创建，旨在为多智能体路径规划（Multi-Agent Path Finding, MAPF）领域提供一个统一的基准测试平台。该数据集的核心研究问题在于如何通过大规模邻域搜索（Large Neighborhood Search, LNS）方法，为多个智能体规划无碰撞的路径。MAPF-LNS方法因其灵活性和可扩展性，近年来在仓库机器人、机场牵引车和视频游戏导航等实际应用中得到了广泛关注。该数据集的推出为MAPF-LNS算法的公平比较提供了基础，推动了该领域的研究进展。

当前挑战

mapf-lns-benchmark数据集面临的挑战主要包括两个方面。首先，在解决领域问题上，MAPF-LNS方法需要应对大规模地图和大量智能体情况下的路径规划复杂性，尤其是在路径优化过程中如何高效选择邻域以消除总延迟。其次，在数据集构建过程中，研究人员遇到了基线性能不准确、缺乏统一的评估设置和标准，以及监督学习方法缺乏可执行模型等问题。这些挑战使得现有方法的全面评估变得困难，进而影响了算法的公平比较和进一步优化。

常用场景

经典使用场景

在多智能体路径规划（MAPF）领域，mapf-lns-benchmark数据集被广泛用于评估基于大邻域搜索（LNS）的算法性能。该数据集通过提供统一的基准测试环境和超参数设置，帮助研究者公平比较不同方法的优劣。特别是在大规模地图和大量智能体的情况下，该数据集能够有效测试算法的扩展性和运行效率。

解决学术问题

mapf-lns-benchmark数据集解决了多智能体路径规划领域中的几个关键问题。首先，它通过统一的评估设置和标准，避免了以往研究中由于不一致的实验条件导致的性能误报问题。其次，该数据集提供了一个可执行的代码库，使得基于监督学习的方法能够被复现和验证。此外，数据集还提出了一个简单的邻域选择策略，显著提升了在大规模地图中的运行效率，为未来的研究提供了新的挑战和机遇。

实际应用

在实际应用中，mapf-lns-benchmark数据集为仓库机器人、机场牵引车和视频游戏中的导航等场景提供了有效的路径规划解决方案。通过优化多智能体的无碰撞路径，该数据集能够显著提升这些应用中的操作效率和安全性。特别是在需要处理大量智能体的复杂环境中，该数据集的算法表现出了优异的扩展性和实时性。

数据集最近研究

最新研究方向

近年来，多智能体路径规划（MAPF）领域的研究重点逐渐转向基于大邻域搜索（LNS）的求解方法，尤其是在大规模地图和智能体数量较多的场景中。MAPF-LNS通过迭代优化初始解，逐步提升路径规划的质量，具有较高的灵活性和可扩展性。然而，当前的研究中存在一些挑战，如基准性能的误报、缺乏统一的评估标准以及监督学习方法缺乏可复现的代码库。针对这些问题，最新的研究提出了统一的评估框架，并对现有的邻域选择策略进行了公平比较。研究还提出了一种简单但高效的邻域选择策略，显著提升了大规模地图中的运行时效率。此外，研究还揭示了将机器学习与MAPF-LNS结合的潜力，尤其是在智能体优先级排序和邻域大小选择方面，为未来的研究提供了新的方向。

相关研究论文

• Benchmarking Large Neighborhood Search for Multi-Agent Path Finding

  西蒙弗雷泽大学, 滑铁卢大学, 卡内基梅隆大学 · 2024年