Flaws of Termination and Optimality in ADOPT-based Algorithms
Flaws of Termination and Optimality in ADOPT-based Algorithms
Koji Noshiro, Koji Hasebe
Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence
Main Track. Pages 1996-2003.
https://doi.org/10.24963/ijcai.2023/222
A distributed constraint optimization problem (DCOP) is a framework to model multi-agent coordination problems. Asynchronous distributed optimization (ADOPT) is a well-known complete DCOP algorithm, and owing to its superior characteristics, many variants have been proposed over the last decade. It is considered proven that ADOPT-based algorithms have the key properties of termination and optimality, which guarantee that the algorithms terminate in a finite time and obtain an optimal solution, respectively. In this paper, we present counterexamples to the termination and optimality of ADOPT-based algorithms. The flaws are classified into three types, at least one of which exists in each of ADOPT and seven of its variants that we analyzed. In other words, the algorithms may potentially not terminate or terminate with a suboptimal solution. We also propose an amended version of ADOPT that avoids the flaws in existing algorithms and prove that it has the properties of termination and optimality.
Keywords:
Constraint Satisfaction and Optimization: CSO: Distributed constraints
Agent-based and Multi-agent Systems: MAS: Coordination and cooperation
Constraint Satisfaction and Optimization: CSO: Constraint optimization