WikiEdge:ArXiv-2409.06486v1/summary

编辑

这篇论文研究了在简单多边形内部为标记代理安排的多智能体路径寻找（Multi-Agent Path Finding, MAPF）问题。目标是找到一系列并行、无冲突的代理动作序列，以最小化所有代理达到各自目标位置所需的总时间（即makespan）。研究集中在特别具有挑战性的场景，即代理密集排列，每个单元格一个代理，这严重限制了代理的移动性，并要求精心协调动作。论文提供了多种新的结果，包括：

1. 多边形的全面可重构性：描述了简单多边形P，其中保证存在重配置计划；证明了当且仅当P能被2×2正方形覆盖且具有连通的交叉图时，这种情况才会发生。
2. 形状参数对makespan的影响：基于多边形的形状参数，提供了makespan和拉伸因子的精细上下界。
3. 算法性能：对于严重限制机动性的案例，提供了一套算法，以实现与可实现的拉伸因子相关的渐近最坏情况最优性能。这对应于将获得的makespan与任何代理的起始和目标位置之间的最大最小距离以及我们的形状参数所提供的下界之间的比率进行限制。

论文还扩展了Demaine等人的研究结果，他们调查了实体矩形域中的该问题，并与Alpert等人在凸网格图的片段中提出的排列路由领域密切相关。