|Decoupling the Multiagent Disjunctive Temporal Problem
|Year of Conference
|Boerkoel, J. C., and E. H. Durfee
|AAAI Conference on Artificial Intelligence (AAAI)
|Disjunctive 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 ﬁrst algorithm for decoupling MaDTPs. Our distributed algorithm is provably sound and complete. Our experiments show that the relative efﬁciency of using temporal decoupling to ﬁnd solution spaces for MaDTPs, compared to algorithms that ﬁnd complete solution spaces,improveswith the interconnectedness between agents schedules, leading to orders of magnitude relative speeedup. However, decoupling by its nature restricts agents’ scheduling ﬂexibility; we deﬁne novel ﬂexibility metrics for MaDTPs, and show empirically how the ﬂexibility sacriﬁced depends on the degree of coupling between agents’ schedules.