News Release

Find counterexamples to completeness of major algorithms in distributed constraint optimization problem

Peer-Reviewed Publication

University of Tsukuba

Tsukuba, Japan—Distributed constraint optimization problems are crucial for modeling cooperative-multiagent systems. Asynchronous Distributed OPTimization (ADOPT) is a well-known algorithm for solving these problems, which is considered to have two important properties: termination, which means that the algorithm terminates in a finite time, and optimality, which indicates that an optimal solution is always obtained when the algorithm terminates. These properties were thought to hold for successor algorithms based on ADOPT.

This study presents counterexamples to the termination and optimality of ADOPT and its successor algorithms. This implies that the proofs given for ADOPT and its successor algorithms are incorrect and that there exists a possibility that the algorithm does not terminate or terminates with a suboptimal solution. Additionally, the researchers identified the cause of the existence of such counterexamples in ADOPT and proposed an algorithm that corrects them. Furthermore, they proved the termination and optimality of the modified version of ADOPT.

By applying the modified version of ADOPT, failures in ADOPT and its successor algorithms can be prevented, and the reliability of systems based on these algorithms is expected to be improved.


Original Paper

Title of original paper:
Counterexamples and amendments to the termination and optimality of ADOPT-based algorithms

Artificial Intelligence



Associate Professor HASEBE, Koji
Institute of Systems and Information Engineering, University of Tsukuba

Degree Programs in Systems and Information Engineering, Graduate School of Science and Technology, University of Tsukuba

Related Link

Institute of Systems and Information Engineering

Disclaimer: AAAS and EurekAlert! are not responsible for the accuracy of news releases posted to EurekAlert! by contributing institutions or for the use of any information through the EurekAlert system.