Generalizing ADOPT and BnB-ADOPT

Patricia Gutierrez, Pedro Meseguer, William YeohIJCAI 2011 · OpenReview

Abstract

ADOPT and BnB-ADOPT are two optimal DCOP search algorithms that are similar except for their search strategies: the former uses best-first search and the latter uses depth-first branch-and-bound search. In this paper, we present a new algorithm, called ADOPT(k), that generalizes them. Its behavior depends on the k parameter. It behaves like ADOPT when k = 1, like BnB-ADOPT when k = ∞ and like a hybrid of ADOPT and BnB-ADOPT when 1 < k < ∞. We prove that ADOPT(k) is a correct and complete algorithm and experimentally show that ADOPT(k) outperforms ADOPT and BnB-ADOPT on several benchmarks across several metrics.

Introduction

In multi-agent systems, agents often need to coordinate to minimize global costs, a challenge modeled as a Distributed Constraint Optimization Problem (DCOP). Historically, two primary algorithms have dominated this space: ADOPT, which uses a "best-first" strategy, and BnB-ADOPT, which uses "depth-first branch-and-bound."

ADOPT is highly "eager," switching values as soon as a different option looks slightly better. This often leads to "thrashing," where agents repeatedly discard and reconstruct partial solutions. Conversely, BnB-ADOPT is more "stubborn," only switching values when the current one is provably suboptimal. While this avoids thrashing, it can cause agents to waste time exploring bad branches. This paper introduces ADOPT(k), a hybrid approach that navigates the trade-off between these two extremes.

Methodology: The ADOPT(k) Framework

The core innovation of ADOPT(k) is the introduction of a tunable parameter $k$ that governs when an agent decides to change its variable's value. In ADOPT(k), an agent $x_i$ changes its value $d_i$ if:

  • The lower bound of the current value exceeds the lower bound of the most promising value by at least $k$ units.
  • OR the current value is provably no better than the best solution found so far (the standard branch-and-bound condition).

When $k=1$, the algorithm behaves like ADOPT. When $k=∞$, it behaves like BnB-ADOPT. Intermediate values of $k$ create a hybrid behavior. The researchers implemented this as ADOPT+(k), incorporating modern efficiency gains like message reduction and timestamping to handle asynchronous communication.

Experimental Evaluation

The researchers evaluated ADOPT(k) using three distinct benchmarks: Random Binary DCOPs, Sensor Network instances, and Chain-Structured Sensor Networks.

Random Binary DCOPs

On instances with varying connectivity ($p_1$), ADOPT+(k) consistently outperformed BnB-ADOPT+. For example, at $p_1=0.6$, ADOPT+(k=4500) reduced the total number of messages by approximately 31% and the number of cycles by 37%.

Performance comparison on Random Binary DCOPs with varying connectivity.

Sensor Network Instances

In large-scale sensor instances, ADOPT+(k) demonstrated significant scalability. In instance A, ADOPT+(k=30M) reduced messages from 5 million to just 2 million compared to BnB-ADOPT+, while also cutting the number of non-concurrent constraint checks (NCCCs) nearly in half.

Performance comparison on large-scale Sensor Network instances.

Key Insights and Discussion

The performance of ADOPT(k) highlights a critical "eagerness" trade-off. By requiring a value to be $k$ units better before switching, agents gain "inertia," avoiding the thrashing characteristic of pure best-first search. The relationship between $k$ and performance is often non-monotonic, with a "sweet spot" for $k$ that outperforms both parent algorithms.

Furthermore, $k$ acts as a dial for resource management. Lower $k$ values tend to result in higher network load (more messages) but potentially fewer local constraint checks, while higher $k$ values stabilize the network at the cost of more local computation. This flexibility is critical for battery-operated or bandwidth-constrained agents.

Limitations and Future Work

The primary limitation is that the optimal value for $k$ is highly dependent on the specific problem instance and cost ranges. Currently, $k$ must be chosen manually. Future work should focus on automated tuning mechanisms that can adapt the value of $k$ dynamically during the search process.

Summary updated

Abstract

ADOPT and BnB-ADOPT are two optimal DCOP search algorithms that are similar except for their search strategies: the former uses best-first search and the latter uses depth-first branch-and-bound search. In this paper, we present a new algorithm, called ADOPT(k), that generalizes them. Its behavior depends on the k parameter. It behaves like ADOPT when k = 1, like BnB-ADOPT when k = ∞ and like a hybrid of ADOPT and BnB-ADOPT when 1 < k < ∞. We prove that ADOPT(k) is a correct and complete algorithm and experimentally show that ADOPT(k) outperforms ADOPT and BnB-ADOPT on several benchmarks across several metrics.
BibTeX
@inproceedings{gutierrez2011generalizing,
  author = {Patricia Gutierrez and Pedro Meseguer and William Yeoh},
  title = {{Generalizing ADOPT and BnB-ADOPT}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2011},
  url = {https://openreview.net/forum?id=rJ41g4z_-H},
}
Figure