Time-Independent Planning for Multiple Moving Agents

Authors

  • Keisuke Okumura Tokyo Institute of Technology
  • Yasumasa Tamura Tokyo Institute of Technology
  • Xavier Défago Tokyo Institute of Technology

Keywords:

Multiagent Planning, Planning under Uncertainty

Abstract

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.

Downloads

Published

2021-05-18

How to Cite

Okumura, K., Tamura, Y., & Défago, X. (2021). Time-Independent Planning for Multiple Moving Agents. Proceedings of the AAAI Conference on Artificial Intelligence, 35(13), 11299-11307. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/17347

Issue

Section

AAAI Technical Track on Multiagent Systems