On Modeling Multiagent Task Scheduling as a Distributed Constraint Optimization Problem

Abstract

This paper investigates how to represent and solve multiagent task scheduling as a Distributed Constraint Optimization Problem (DCOP). Recently multiagent researchers have adopted the C_TAEMS language as a standard for multiagent task scheduling. We contribute an automated mapping that transforms C_TAEMS into a DCOP. Further, we propose a set of representational compromises for C_TAEMS that allow existing distributed algorithms for DCOP to be immediately brought to bear on C_TAEMS problems. Next, we demonstrate a key advantage of a constraint based representation is the ability to leverage the representation to do efficient solving. We contribute a set of pre-processing algorithms that leverage existing constraint propagation techniques to do variable domain pruning on the DCOP. We show that these algorithms can result in 96% reduction in state space size for a given set of C_TAEMS problems. Finally, we demonstrate up to a 60% increase in the ability to optimally solve C_TAEMS problems in a reasonable amount of time and in a distributed manner as a result of applying our mapping and domain pruning algorithms.