Distributed Interaction Graph Construction for Dynamic DCOPs in Cooperative Multi-agent Systems
This work addresses a specific bottleneck in cooperative multi-agent systems by enabling more robust graph construction in dynamic settings, though it appears incremental as it builds on existing DCOP methods.
The paper tackled the problem of constructing and maintaining interaction graphs for DCOP algorithms in open, dynamic multi-agent environments, proposing a distributed algorithm that stabilizes after changes and effectively builds stable graphs without predefined constraints.
DCOP algorithms usually rely on interaction graphs to operate. In open and dynamic environments, such methods need to address how this interaction graph is generated and maintained among agents. Existing methods require reconstructing the entire graph upon detecting changes in the environment or assuming that new agents know potential neighbors to facilitate connection. We propose a novel distributed interaction graph construction algorithm to address this problem. The proposed method does not assume a predefined constraint graph and stabilizes after disruptive changes in the environment. We evaluate our approach by pairing it with existing DCOP algorithms to solve several generated dynamic problems. The experiment results show that the proposed algorithm effectively constructs and maintains a stable multi-agent interaction graph for open and dynamic environments.