Routing and Scheduling in Answer Set Programming applied to Multi-Agent Path Finding: Preliminary Report

我们提出了在答案集编程（ASP）中进行路由和调度的替代方法，并在多智能体路径规划的背景下探讨了它们。这个想法是通过部分顺序来捕捉时间的流动，而不是将时间步骤附加到动作和流变量上。这也消除了计划长度的固定上限的需要。这种避免的代价是（部分）时间轨迹必须是无环的，因为不能再区分同一动作或流变量的多个出现。虽然这种方法为建模路由提供了有趣的替代方案，但对于调度来说，它是无可替代的，因为无法以可行的方式在ASP中表示细粒度的时间安排。这与部分顺序不同，部分顺序可以通过外部手段（如无环性和差异约束）高效地处理。我们正式阐述了这个想法，并提出了几个结果ASP编码。最后，我们通过实证分析证明了它们的有效性。

论文试图提出一种基于部分序的ASP编码方法，用于解决路径规划和调度问题，特别是在多智能体路径规划方面。

论文提出了一种基于部分序的ASP编码方法，用于表示时间流，避免了将时间步骤与行动和流言相关联的需要，同时也避免了计划长度的固定上界限制。

论文提出的部分序ASP编码方法在路径规划方面提供了一种有趣的新方法，但在调度方面则没有替代品。实验结果表明，该方法在多智能体路径规划问题上表现出了高效性和可扩展性。

最近的相关研究包括：'Solving Multi-Agent Pathfinding with Factored Transition Systems'，'Multi-Agent Pathfinding with Delay Probabilities'，'Integrated Task and Motion Planning in Belief Space'等。