Algorithms for a Temporal Decoupling Problem in Multi-Agent Planning

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 18

Planning

The Temporal Decoupling Problem (TDP) arises when a group of agents collaborating on a set of temporally-dependent tasks seek to coordinate their execution of those tasks by applying additional temporal constraints sufficient to ensure that agents working on different tasks may operate independently. This paper: (1) formally defines the TDP, (2) presents theorems that give necessary and sufficient conditions for solutions to the TDP, (3) presents a family of sound and complete algorithms for solving the TDP, and (4) compares the performance of several variations of the basic algorithm. Although this work was motivated by a problem in collaborative multi-agent planning, it represents a contribution to the theory of Simple Temporal Networks that is independent of the motivating application.