Multiagent Disjunctive Temporal Networks

Temporal network formalisms allow us to encode a set of constraints relating distinct events in time, and by deploying algorithms over these networks, we can determine whether schedules for these networks exist that satisfy all constraints. By augmenting simple temporal networks, we can consider the effects that disjunctive constraints, temporal uncertainty, and coordinating agents have on modeling fidelity and the algorithmic efficiency of schedule construction. In this paper, we introduce Partially Observable Disjunctive Temporal Networks with Uncertainty (PODTNUs) and Multiagent Disjunctive Temporal Networks with Uncertainty (MaDTNUs), generalizing previously studied multi-agent variants of temporal networks. We provide the first theoretical completeness results for the controllability of multiagent temporal network structures and discuss the importance of these results for modelers.