Distributed constraint optimization (DCOP) has emerged as a useful technique for multiagent coordination. While previous DCOP
work focuses on optimizing a single team objective, in many domains, agents must satisfy additional constraints on resources consumed locally (due to interactions within their local neighborhoods).
Such resource constraints may be required to be private or shared
for efficiency’s sake. This paper provides a novel multiply-constrained
DCOP algorithm for addressing these domains which is based on
mutually-intervening search, i.e. using local resource constraints
to intervene in the search for the optimal solution and vice versa.
It is realized through three key ideas: (i) transforming n-ary constraints to maintain privacy; (ii) dynamically setting upper bounds
on joint resource consumption with neighbors; and (iii) identifying if the local DCOP graph structure allows agents to compute
exact resource bounds for additional efficiency. These ideas are
implemented by modifying Adopt, one of the most efficient DCOP
algorithms. Both detailed experimental results as well as proofs of
correctness are presented.