AAAI Publications, Twenty-Seventh AAAI Conference on Artificial Intelligence

Font Size: 
Decoupling the Multiagent Disjunctive Temporal Problem
James Calvin Boerkoel Jr., Edmund H. Durfee

Last modified: 2013-06-30


The Multiagent Disjunctive Temporal Problem (MaDTP) is a general constraint-based formulation for scheduling problems that involve interdependent agents. Decoupling agents' interdependent scheduling problems, so that each agent can manage its schedule independently, requires agents to adopt additional local constraints that effectively subsume their interdependencies. In this paper, we present the first algorithm for decoupling MaDTPs. Our distributed algorithm is provably sound and complete. Our experiments show that the relative efficiency of using temporal decoupling to find solution spaces for MaDTPs, compared to algorithms that find complete solution spaces, improves with the interconnectedness between agents schedules, leading to orders of magnitude relative speeedup. However, decoupling by its nature restricts agents' scheduling flexibility; we define novel flexibility metrics for MaDTPs, and show empirically how the flexibility sacrificed depends on the degree of coupling between agents' schedules.


Multiagent Scheduling; Distributed Scheduling; Temporal Decoupling; Disjunctive Temporal Problem

Full Text: PDF