Paper Info
Title
Offline Time-Independent Multi-Agent Path Planning.
Abstract
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.
Year
DOI
Venue
2022
10.24963/ijcai.2022/645
European Conference on Artificial Intelligence
Keywords
DocType
Citations 
Planning and Scheduling: Distributed, Multi-agent Planning,Agent-based and Multi-agent Systems: Multi-agent Planning,Planning and Scheduling: Planning under Uncertainty,Planning and Scheduling: Robot Planning,Robotics: Motion and Path Planning
Conference
0
PageRank 
References 
Authors
0.34
0
4
Name
Order
Citations
PageRank
Keisuke Okumura112.73
François Bonnet200.68
Yasumasa Tamura300.68
xavier defago418822.39