Algorithms for a Temporal Decoupling Problem in Multi-Agent Planning

Luke Hunsberger, Harvard University

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.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.