Multi-Agent Path Finding Benchmark Maps

Multi-Agent Path Finding Benchmark Maps是由卡内基梅隆大学机器人研究所创建的数据集，用于评估多智能体路径寻找算法的性能。该数据集包含33个不同大小、布局和难度的地图，旨在全面测试算法在各种场景下的表现。数据集的创建过程结合了Quality Diversity算法和神经元细胞自动机（NCA），以生成多样化的地图。这些地图广泛应用于自动化仓库、视频游戏、无人机交通管理等领域，旨在解决多智能体路径规划中的公平比较问题。The Multi-Agent Path Finding Benchmark Maps dataset was created by the Robotics Institute of Carnegie Mellon University to evaluate the performance of multi-agent path finding algorithms. This dataset comprises 33 maps with varying sizes, layouts and difficulty levels, aiming to comprehensively test algorithm performance across diverse scenarios. The development of this dataset integrates the Quality Diversity algorithm and Neural Cellular Automata (NCA) to generate a diverse collection of maps. These maps are widely applied in domains such as automated warehouses, video games, UAV traffic management and more, with the goal of addressing the fair comparison problem in multi-agent path planning.

搜集汇总

数据集介绍

构建方式

该数据集采用质量多样性（QD）算法与神经元细胞自动机（NCA）相结合的方法，自动生成多智能体路径寻找（MAPF）算法的基准地图。传统的MAPF算法测试依赖于固定的人工设计地图，但这些地图存在覆盖不足和比较偏差的问题。通过利用QD算法和NCA，研究团队能够生成具有多样性和针对性的地图，以全面评估和比较不同MAPF算法的性能。具体构建过程中，首先通过采样参数向量生成NCA生成器，然后利用这些生成器生成基准地图。生成的地图可能存在无效性，因此采用混合整数线性规划（MILP）进行修复，确保地图的连通性和障碍物数量在预定义范围内。最后，通过运行MAPF算法评估地图的目标和多样性值，并将评估后的地图添加到档案中。

特点

该数据集的主要特点在于其生成的地图具有高度的多样性和针对性。通过QD算法和NCA的结合，生成的地图能够覆盖多种潜在的算法失败场景，从而提供了一个公平的比较平台。此外，数据集中的地图不仅在障碍物的数量上有所变化，还在空间布局上呈现出多样性，这有助于更全面地理解不同MAPF算法在各种环境下的表现。数据集还特别设计了针对单个算法和双算法的实验地图，以揭示各算法在特定条件下的优势和劣势。

使用方法

该数据集适用于评估和比较不同类型的MAPF算法，包括有界次优算法、次优算法和基于强化学习的算法。使用者可以通过运行数据集中的地图，评估其算法的运行时间、成功率和路径质量等指标。具体使用方法包括：首先，选择合适的MAPF算法；其次，加载数据集中的基准地图；然后，运行算法并记录其性能数据；最后，通过分析这些数据，比较不同算法在各种地图上的表现，从而为算法的选择和优化提供依据。数据集还提供了详细的实验设置和结果分析，帮助用户更好地理解和利用这些基准地图。

背景与挑战

背景概述

多智能体路径寻找基准地图（Multi-Agent Path Finding Benchmark Maps）数据集由卡内基梅隆大学和南加州大学的研究团队创建，旨在解决多智能体路径寻找（MAPF）算法在固定、人工设计基准地图上的局限性。这些固定地图可能无法涵盖算法所有潜在的失败场景，且在比较不同算法时可能引入偏见，导致不公平的比较。该数据集利用质量多样性（QD）算法和神经元细胞自动机（NCA）生成多样化的基准地图，以全面评估MAPF算法的性能，并确保算法间公平比较。数据集的创建时间为2024年，主要研究人员包括Cheng Qian、Yulun Zhang、Varun Bhatt、Matthew C. Fontaine、Stefanos Nikolaidis和Jiaoyang Li。该数据集对MAPF领域的研究具有重要影响，为算法评估和比较提供了新的工具和方法。

当前挑战

该数据集面临的挑战主要包括两个方面。首先，生成能够覆盖所有潜在失败场景的多样化基准地图是一个复杂的过程，需要精确控制地图的结构和难度，以确保对不同MAPF算法的全面评估。其次，在构建过程中，如何避免固定基准地图可能引入的偏见，确保算法间公平比较，是一个关键问题。此外，生成过程涉及复杂的算法和计算资源，如何提高生成效率和减少计算成本也是一大挑战。

常用场景

经典使用场景

Multi-Agent Path Finding Benchmark Maps 数据集的经典使用场景在于评估和比较多智能体路径规划（MAPF）算法。通过提供多样化的基准地图，该数据集能够全面测试不同算法的性能，识别其在不同地图结构下的优势和劣势。这种评估不仅限于单一算法的表现，还包括算法间的公平比较，从而为算法选择提供更全面的参考。

解决学术问题

该数据集解决了多智能体路径规划领域中的一个关键学术问题，即如何生成能够全面评估算法性能的多样化基准地图。传统的固定基准地图存在覆盖不全和比较偏差的问题，而该数据集通过使用质量多样性（QD）算法和神经元细胞自动机（NCA）生成多样化的地图，有效解决了这些问题。这不仅提升了算法评估的全面性和公平性，还为算法改进提供了更丰富的数据支持。

衍生相关工作

基于 Multi-Agent Path Finding Benchmark Maps 数据集，衍生了一系列相关工作。例如，研究者们利用该数据集生成的地图，进一步探索了不同算法的性能差异，提出了改进的算法和优化策略。此外，该数据集还激发了在其他领域（如自动驾驶和机器人交互）中应用类似生成方法的研究，推动了跨领域的技术交流和创新。