Typical Multi-agent Path Finding (MAPF) solvers assume that agents move synchronously, thus neglecting the reality gap in timing assumptions, e.g., delays caused by an imperfect execution of asynchronous moves. So far, two policies enforce a robust execution of MAPF plans taken as input: either by forcing agents to synchronize or by executing plans while preserving temporal dependencies. This paper proposes an alternative approach, called time-independent planning, which is both online and distributed. We represent reality as a transition system that changes configurations according to atomic actions of agents, and use it to generate a time-independent schedule. Empirical results in a simulated environment with stochastic delays of agents' moves support the validity of our proposal.
翻译:典型的多试剂路径查找(MAPF)解答者认为,代理商同步移动,从而忽略了时间假设中的现实差距,例如,由于不完全执行非同步动作造成的延误。到目前为止,有两种政策强制强力执行MAPF计划,作为投入:要么迫使代理商同步,要么执行计划,同时保持时间依赖性。本文提出了一种替代方法,称为时间独立规划,既在线又分布。我们把现实当作一种过渡系统,根据代理商的原子动作改变配置,并利用它产生一个时间独立的时间表。模拟环境中的模拟结果,代理商动作的拖延,证实了我们提案的有效性。