Decoupling the Multiagent Disjunctive Temporal Problem

TitleDecoupling the Multiagent Disjunctive Temporal Problem
Publication TypeConference Proceedings
Year of Conference2013
AuthorsBoerkoel, J. C., and E. H. Durfee
Conference NameAAAI Conference on Artificial Intelligence (AAAI)
Date Published07/2013
Call Number4
KeywordsDisjunctive Temporal Problem, Multiagent Scheduling, Temporal Decoupling

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,improveswith 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.