Loosely Synchronized Rule-Based Planning for Multi-Agent Path Finding with Asynchronous Actions

这篇论文介绍了在异步行动的多智能体路径规划（MAPF）中使用搜索方法（LSS）和规则基于规划（PIBT）的新规划器，以牺牲解决方案质量换取可扩展性。LSRP算法通过将时间纳入状态空间并使用PIBT来解决异步行动的多智能体路径规划（MAPF-AA），通过缓存机制处理具有相近但不同开始时间的智能体，实现高效协调。LSRP在特定图条件下确保可达性，与现有方法相比，在解决更多智能体时运行时间更短，尽管完成时间稍长。LSRP、PIBT和LSS是处理异步行动的多智能体路径规划的算法。LSRP通过深度优先方式迭代规划多个智能体的动作，直到所有智能体达到目标。它维护联合状态列表、动作字典，并更新智能体的优先级。它提取下一个规划时间戳和需要动作的智能体子集，检查缓存动作，并使用ASY-PUSH程序为没有缓存动作的智能体规划动作。LSRP算法在有持续冲突的有向图中规划多智能体路径查找，使用优先级方法，智能体尝试移动到目标。如果顶点被占用，则通过递归调用ASY-PUSH确定智能体是否可以被推。此过程计算等待和移动动作的时间戳，并在字典Φ中缓存未来动作以实现高效规划。LSRP算法通过考虑持续冲突和缓存动作优于PIBT，后者立即在顶点可用时移动智能体。LSRP和Causal PIBT是多智能体路径规划算法。LSRP被动规划，记录执行期间的智能体依赖关系，而Causal PIBT主动规划，考虑已知动作持续时间。这两种算法具有相似的基本思想，但解决不同的问题。LSRP确保在环形图中优先智能体在限定时间内达到目标，而Causal PIBT在已知持续时间的情况下规划动作。LSRP-SWAP扩展引入了交换操作，以解决仅通过简单推操作无法解决的问题。实验结果表明，LSRP-SWAP算法在处理多达1000个智能体时表现出色，尽管解决方案质量有所降低。在稀疏地图中，LSRP和LSRP-SWAP表现出良好的可扩展性，而在拥挤环境中，LSRP-SWAP优于其他算法，显示交换操作的优势。论文开发了处理异步行动的多智能体路径规划的规则基于规划器，并验证了在各种地图中处理高达千个智能体的能力，尽管牺牲了解决方案质量。未来工作旨在开发一个在运行时间限制内可以提高解决方案质量的任何时间规划器。这些规划器在解决方案成本和完成时间方面优于基线，比例约为4倍和1.25倍。考虑异步行动导致解决方案通常比忽略此类行动时便宜30%至75%。