Algorithms for a Temporal Decoupling Problem in Multi-Agent Planning

The Temporal Decoupling Problem (TDP) arises when a group of agents collaborating on a set of temporallydependent 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.

Authors

• Luke Hunsberger

Keywords

No keywords are indexed for this paper.