改进的匿名多智能体路径查找算法

文章预览

本文提出了一种改进的匿名多智能体路径寻找算法（ AMAPF ），旨在解决多个未标记的智能体在一个共享环境中从初始位置无冲突地移动到指定目标位置的问题。该研究通过将 AMAPF 问题转化为辅助图上的最大流问题，并采用了一种新颖的搜索算法，该算法不是单独考虑各个搜索状态，而是同时处理大量状态，以压缩、存储并扩展这些状态，从而减少运行时间和内存使用。这种方法在实证研究中显示出优越的表现，能够在不到 30 秒的时间内解决 MovingAI 基准测试中所有可用的多智能体路径寻找问题实例。此外，文中还讨论了网络流理论的应用背景，并详细描述了如何将 AMAPF 问题映射到网络流问题上求解，最终通过最大流解决方案转换回 AMAPF 解决方案的过程。 1 多智能体路径寻找问题 多智能体路径寻找（MAPE）问题是关于一组智能体如何在共享环境中 ………………………………