Investigation of Anytime Evolutionary DCOP Algorithm on Pub/Sub Communication Platform with Message Losses
Toshihiro Matsui · 2025
Distributed constraint optimization problems (DCOPs) have been studied as a fundamental framework for cooperative problem solving in multiagent systems, including distributed resource allocation and collaborative tasks. With a DCOP, a cooperation task is represented as a constraint optimization problem distributed among agents, and a decentralized optimization algorithm is applied to find its optimal solution. Although several studies have addressed extended problems toward practical implementations, opportunities exist to investigate the implementation techniques of the solution methods on dedicated platforms for different devices. Several recent platforms for robots and communication infrastructures for IoT devices employ a publish/subscribe communication model. Toward the application of distributed constraint optimization methods to the cooperation of edge devices on such platforms/infrastructures, solution methods for dedicated communication models must be explored. Previous studies investigated an implementation methodology of the case of the maximum gain message (MGM) algorithm, which is the simplest local search method, on a pub/sub communication platform with message losses under best-effort settings. However, further investigation and typification for different types of solution methods are necessary to extend this approach. As the next step of this research direction, we investigate the case of the Anytime Evolutionary DCOP (AED) algorithm and verify its actual implementation in a similar ROS2 environment. The contribution of this study is summarized as follows. (1) We present a version of the AED algorithm for the implementation on pub/sub communication platforms. (2) We modify the AED on pub/sub communication so that the solution process continues under the situations with temporarily missing agents. (3) We implement the proposed method on an actual platform of an ROS2 environment and experimentally verify its effect. (4) We experimentally compare the proposed method with the MGM algorithm implemented on the same actual environment and present promising solution quality with the proposed approach in convergence steps.