Solving Distributed Constraint Optimization Problems Using Cooperative Mediation

TLDR

Distributed Constraint Optimization Problems are a key research area for multi‑agent systems, modeling many real‑world situations, and researchers have long sought efficient fully distributed solutions derived from centralized techniques. This paper introduces OptAPO, an optimal distributed algorithm that solves DCOPs using cooperative mediation. OptAPO operates by having mediator agents centralize overlapping portions of the problem, progressively enlarging these subproblems as solving proceeds. Empirical results demonstrate that OptAPO outperforms existing optimal DCOP methods.

Abstract

Distributed Constraint Optimization Problems (DCDP) have, for a long time, been considered an important research area for multi-agent systems because a vast number of real-world situations can be modeled by them. The goal of many of the researchers interested in DCOP has been to find ways to solve them efficiently using fully distributed algorithms which are often based on existing centralized techniques. In this paper, we present an optimal, distributed algorithm called optimal asynchronous partial overlay (OptAPO) for solving DCOPs that is based on a partial centralization technique called cooperative mediation. The key ideas used by this algorithm are that agents, when acting as a mediator, centralize relevant portions of the DCDP, that these centralized subproblems overlap, and that agents increase the size of their subproblems as the problem solving unfolds. We present empirical evidence that shows that OptAPO performs better than other known, optimal DCOP techniques.