EUVIMEDEUVIMED entdecken
Crossref

GDBA Revisited: Unleashing the Power of Guided Local Search for Distributed Constraint Optimization

Yanchen Deng, Xinrun Wang, Bo An

Proceedings of the AAAI Conference on Artificial Intelligence · 14.03.2026 · 40 (35) · 29385-29393

DOI: 10.1609/aaai.v40i35.40179 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the AAAI Conference on Artificial Intelligence, online erschienen am 14.03.2026. Verfasst von Yanchen Deng und 2 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Local search is an important class of incomplete algorithms for solving Distributed Constraint Optimization Problems (DCOPs) but it often converges to poor local optima. While Generalized Distributed Breakout Algorithm (GDBA) provides a comprehensive rule set to escape premature convergence, its empirical benefits remain marginal on general-valued problems. In this work, we systematically examine GDBA and identify three factors that potentially lead to its inferior performance, i.e., over-aggressive constraint violation conditions, unbounded penalty accumulation, and uncoordinated penalty updates. To address these issues, we propose Distributed Guided Local Search (DGLS), a novel GLS framework for DCOPs that incorporates an adaptive violation condition to selectively penalize constraints with high cost, a penalty evaporation mechanism to control the magnitude of penalization, and a synchronization scheme for coordinated penalty updates. We theoretically show that the penalty values are bounded, and agents play a potential game in DGLS. Extensive empirical results on various benchmarks demonstrate the great superiority of DGLS over state-of-the-art baselines. Compared to Damped Max-sum with high damping factors, our DGLS achieves competitive performance on general-valued problems, and outperforms by significant margins on structured problems in terms of anytime results.

Zitieren

APA

Deng, Y., Wang, X., & An, B. (2026). GDBA Revisited: Unleashing the Power of Guided Local Search for Distributed Constraint Optimization. Proceedings of the AAAI Conference on Artificial Intelligence, 40(35), 29385-29393. https://doi.org/10.1609/aaai.v40i35.40179

Vancouver

Deng Y, Wang X, An B. GDBA Revisited: Unleashing the Power of Guided Local Search for Distributed Constraint Optimization. Proceedings of the AAAI Conference on Artificial Intelligence. 2026;40(35):29385-29393. doi:10.1609/aaai.v40i35.40179

BibTeX
@article{Deng2026,
  author = {Deng, Yanchen and Wang, Xinrun and An, Bo},
  title = {GDBA Revisited: Unleashing the Power of Guided Local Search for Distributed Constraint Optimization},
  journal = {Proceedings of the AAAI Conference on Artificial Intelligence},
  year = {2026},
  volume = {40},
  number = {35},
  pages = {29385--29393},
  doi = {10.1609/aaai.v40i35.40179}
}
Kostenlos starten →