WikiEdge:ArXiv-2409.06486v1/methods

编辑

这篇文献的工作部分详细介绍了如何在密集填充的有界区域内进行多智能体路径规划（Multi-Agent Path Finding, MAPF）。以下是这部分的主要内容：

1. 问题定义：
   • 定义了在简单多边形域内的多智能体路径规划问题，每个智能体都有唯一的起始位置和目标位置。目标是找到一系列并行、无冲突的智能体运动序列，以最小化所有智能体达到目标位置的总时间（makespan）。
2. 多智能体路径规划理论：
   • 讨论了计算几何早期关于协调圆盘形对象在障碍物间运动的方法，以及其在多智能体路径规划问题中的复杂性，包括PSPACE完全性和图基变体的线性时间算法。
3. 多智能体路径规划算法：
   • 提出了一种算法框架，用于在有界区域内实现多智能体的协调运动规划。算法考虑了智能体的密集排列和域的几何特性，如瓶颈长度（bottleneck length）和域深度（domain depth）。
4. 算法性能分析：
   • 分析了算法在不同形状参数下的最坏情况性能，包括在特定条件下实现渐近最坏情况最优的makespan。
5. 实验验证：
   • 通过在不同形状的多边形域内进行模拟实验，验证了算法的有效性和效率。