MA-LAMA: Exploiting the Multi-Agent Nature of Temporal Planning Problems

Abstract

Background: In the field of Automated Planning, the existence of multiple agents in a certain temporal setting introduces the possibility of concurrency. This severely increases the complexity of planning in multi-agent temporal scenarios, as the possible states in the search space grow exponentially. Objectives: These types of domains are traditionally solved by making use of temporal reasoning techniques that do not directly address the “multi-agent nature” at their core. In contrast, we introduce MA-LAMA, a multi-agent temporal planner that makes use of multi-agent techniques to deal with the inherent complexity of multi-agent temporal scenarios. Methods: We propose a sequenced framework in which several multi-agent planning techniques are applied: automatic agent detection, task decomposition, cost-informed goal assignment, and agent interaction analysis; that are aimed to reduce the search complexity when solving temporal planning tasks. Results: Our results show that, in many cases, MA-LAMA outperforms other state-of-the-art temporal planners in plan cost optimization for well-known temporal domains. Conclusions: These results, along with the fact that MA-LAMA does not incorporate any temporal reasoning during search, suggest that several widely considered temporal domains are best suited to be solved with multi-agent planning techniques, rather than with temporal reasoning.