Grid-based MAPF Benchmark

Grid-based MAPF Benchmark是一个包含24个地图的数据集，用于评估多代理路径寻找（MAPF）算法。这些地图来源于真实城市、视频游戏、开放网格和随机障碍网格等。数据集提供了多种场景，包括随机和指定源目标设置，旨在模拟自动化仓库和自动驾驶车辆等应用场景。此数据集为MAPF研究提供了一个统一的评估平台，有助于推动算法的发展和优化。

The Grid-based MAPF Benchmark is a dataset consisting of 24 maps for evaluating multi-agent path finding (MAPF) algorithms. These maps are sourced from real-world cities, video games, open grids, and random obstacle grids, among other categories. The dataset provides diverse scenarios including random and predefined start-goal configurations, which are designed to simulate application scenarios such as automated warehouses and autonomous vehicles. This dataset offers a unified evaluation platform for MAPF research, facilitating the advancement and optimization of relevant algorithms.

搜集汇总

数据集介绍

构建方式

在构建Grid-based MAPF Benchmark时，研究团队从多个来源精心选取了24张地图，涵盖了城市街区、电子游戏场景、开放网格、迷宫结构及房间布局等多种类型，这些地图均源自公开的MovingAI路径规划资源库。每个地图配置了25个场景，每个场景包含1000个随机生成的起点-目标点对，这些点对通过算法在最大可达区域内进行随机配对，确保了问题的多样性和复杂性。通过这种系统化的构建方式，该数据集能够全面评估多智能体路径规划算法在不同环境下的性能表现。

使用方法

使用该数据集时，研究者首先选择特定的地图类型及对应场景，然后从场景中按顺序提取起点-目标点对，逐步增加智能体数量以构建多智能体路径规划问题。算法评估过程中，通常以能否在合理时间内成功求解作为性能指标，通过记录最大可解智能体数量来量化算法能力。这种递增式测试方法不仅能够系统化地比较不同算法的求解效率，还能揭示算法在问题规模扩大时的性能衰减规律，为优化与改进提供明确方向。

背景与挑战

背景概述

多智能体路径规划（MAPF）作为人工智能与机器人领域的核心问题，旨在为多个智能体规划无碰撞的协同路径，广泛应用于自动化仓库、自动驾驶等场景。随着该领域研究的蓬勃发展，不同文献在假设与目标函数上存在显著差异，导致基准比较与成果整合面临困难。为此，Roni Stern、Nathan R. Sturtevant等学者于2019年联合提出了Grid-based MAPF Benchmark，通过构建统一的术语体系与标准化测试集，为MAPF研究提供了严谨的评估框架。该数据集融合了城市地图、游戏场景及多种网格环境，不仅推动了算法比较的科学性，还显著提升了领域内研究的可复现性与应用衔接。

当前挑战

Grid-based MAPF Benchmark所应对的核心挑战在于解决多智能体路径规划中的算法评估标准化问题。具体而言，早期研究因缺乏统一的冲突定义（如顶点冲突、边冲突等）与目标函数（如最小化完成时间或总动作成本），导致不同算法难以公平比较。在数据集构建过程中，挑战主要体现在地图与任务生成的多样性平衡上：需涵盖从开放网格到复杂城市布局的多种环境，同时设计随机、聚类及指定等多种源-目标分配策略，以模拟真实应用场景的复杂性。此外，确保基准既能有效测试现有算法极限，又避免引入结构性偏差，亦是构建过程中的关键难点。

常用场景

经典使用场景

在自动化仓储与机器人协同导航领域，Grid-based MAPF Benchmark 作为多智能体路径规划（MAPF）研究的标准化评估工具，其经典使用场景集中于算法性能的横向比较与基准测试。该数据集通过整合多样化的网格地图（如城市布局、游戏场景、开放网格及迷宫结构），并配以随机生成的起点-终点对，为研究者提供了一个统一且可复现的实验平台。学者们通常利用该数据集，逐步增加智能体数量以测试算法在复杂环境下的可扩展性与求解效率，从而推动MAPF领域在理论优化与工程实践方面的协同发展。

解决学术问题

Grid-based MAPF Benchmark 主要解决了多智能体路径规划研究中长期存在的术语不统一与评估标准缺失问题。在MAPF领域，不同研究对智能体冲突类型（如顶点冲突、边冲突）、目标行为假设（停留或消失）及优化目标（完工时间与总成本）的定义往往存在差异，导致算法比较缺乏公平基准。该数据集通过明确定义经典MAPF的约束条件与目标函数，并提供了结构化测试场景，使研究者能够清晰界定问题边界，从而促进学术交流的严谨性，加速新算法在理论验证与性能突破方面的进展。

实际应用

在实际应用中，Grid-based MAPF Benchmark 为自动化仓储物流、自动驾驶车辆协同调度等场景提供了关键的技术验证基础。例如，在电商仓库的机器人分拣系统中，多台自主移动机器人需在密集货架间高效穿梭并避免碰撞，该数据集的网格化环境模拟了真实仓库的布局与通道约束。通过在此类基准上测试路径规划算法，工程师能够评估系统在高负载下的鲁棒性，优化任务分配策略，进而提升整体物流效率与安全性，推动智能仓储系统从实验室原型向产业化落地迈进。

数据集最近研究

最新研究方向

在自动化仓储和自动驾驶等应用场景的推动下，Grid-based MAPF Benchmark作为多智能体路径规划领域的标准化评估工具，其前沿研究聚焦于扩展经典MAPF的约束与假设。当前热点方向包括探索加权图环境下的路径规划，其中智能体的移动动作具有不同耗时，以及研究具有体积或运动学约束的大型智能体，以更贴近真实机器人系统的运动特性。此外，在线MAPF问题，如终身路径规划，因应动态任务分配和智能体持续出现的实际需求，成为算法鲁棒性与实时性验证的关键。这些进展不仅深化了对冲突类型与目标函数的理论建模，也通过该基准集的多样化地图与场景设计，为算法性能提供了严谨、可复现的评估框架，显著促进了领域内算法的比较与优化。

相关研究论文

• Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks

  本古里安大学 · 2019年