Reasoning about and dynamically posting n-ary constraints in ADOPT
Federico Pecora, Jay Modi, Paul Scerri · 2006
This article describes an approach to solving distributed constraint optimization problems (DCOP) with n-ary constraints. A key instance of this problem is distributed resource-constrained task scheduling, in which limited resource capacities implicitly imply n-ary relations among the start-times of the tasks. We describe ADOPT-N, an extension of ADOPT [16], a recent successful algorithm for DCOP. ADOPT-N is an optimal asynchronous distributed n-ary constraint optimization algorithm in which specific agents are empowered with n-ary constraint evaluation capabilities. We show how the algorithm’s correctness and optimality relies on (1) the choice of which agents to dedicate to constraint evaluation, and (2) an admissible (partial) variable ordering. Moreover, we demonstrate empirically how ADOPT-N’s performance depends on how much knowledge about the n-ary violations that can arise during resolution can be provided to the algorithm. 1