Researchers from University of Tsukuba have presented counterexamples to assumed key properties of Asynchronous Distributed OPTimization (ADOPT) and its successor algorithms. ADOPT is a well-known algorithm for solving distributed constraint optimization problems.
The team demonstrated that these algorithms do not necessarily guarantee the key properties, namely termination and optimality. Furthermore, they proposed a modified version of ADOPT that guarantees these properties. The study is published in the journal Artificial Intelligence.
Distributed constraint optimization problems are crucial for modeling cooperative-multiagent systems. The ADOPT algorithm 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.
More information:
Koji Noshiro et al, Counterexamples and amendments to the termination and optimality of ADOPT-based algorithms, Artificial Intelligence (2024). DOI: 10.1016/j.artint.2024.104083
Provided by
University of Tsukuba
Post Disclaimer
The information provided in our posts or blogs are for educational and informative purposes only. We do not guarantee the accuracy, completeness or suitability of the information. We do not provide financial or investment advice. Readers should always seek professional advice before making any financial or investment decisions based on the information provided in our content. We will not be held responsible for any losses, damages or consequences that may arise from relying on the information provided in our content.
