This paper studies a novel planning problem for multiple agents moving on graphs that we call offline time-independent multi-agent path planning (OTIMAPP). The motivation is to overcome time uncertainties in multi-agent scenarios where we cannot expect agents to act perfectly following timed plans, e.g., executions with mobile robots. For this purpose, OTIMAPP abandons all timing assumptions; it is offline planning that assumes event-driven executions without or less run-time effort. The problem is finding plans to be terminated correctly in any action orders of agents, i.e., guaranteeing that all agents eventually reach their destinations. We address a bunch of questions for this problem: required conditions for feasible solutions, computational complexity, comparison with well-known other multi-agent problems, construction of solvers, effective relaxation of a solution concept, and how to implement the plans by actual robots. Throughout the paper, we establish the foundation of OTIMAPP and demonstrate its utility. A video is available at https://kei18.github.io/otimapp.
翻译:本文研究在图表上移动的多个代理物的新规划问题,我们称之为脱线时间独立多试剂路径规划(OTIMAPP)。目的是克服多试剂情景中的时间不确定性,我们无法期望代理物按照计时计划完美行事,例如使用移动机器人处决。为此,OTIMAP放弃所有时间假设;这是假设不做或少做运行时间执行事件处决的离线计划。问题在于在代理物的任何行动命令中找到正确终止计划,即保证所有代理物最终到达目的地。我们讨论了这一问题的众多问题:可行解决办法的必要条件、计算复杂程度、与其他众所周知的多试剂问题的比较、构建解答器、有效放宽解决方案的概念,以及实际机器人如何执行计划。我们在整个文件中建立了OTIMAP的基础并展示其效用。一个视频可在 https://kei18.github.io/otimapp上查阅。