A new distributed algorithm for efficient generalized arc-consistency propagation

Abstract

Generalized arc-consistency propagation is predominantly used in constraint solvers to efficiently prune the search space when solving constraint satisfaction problems. Although many practical applications can be modelled as distributed constraint satisfaction problems, no distributed arc-consistency algorithms so far have considered the privacy of individual agents. In this paper, we propose a new distributed arc-consistency algorithm, called π–£π—‚π—Œπ– π–’πŸ₯.𝟣DisAC3.1mathsf DisAC3.1, which leaks less private information of agents than existing distributed arc-consistency algorithms. In particular, π–£π—‚π—Œπ– π–’πŸ₯.𝟣DisAC3.1mathsf DisAC3.1 uses a novel termination determination mechanism, which allows the agents to share domains, constraints and communication addresses only with relevant agents. We further extend π–£π—‚π—Œπ– π–’πŸ₯.𝟣DisAC3.1mathsf DisAC3.1 to π–£π—‚π—Œπ–¦π– π–’πŸ₯.𝟣DisGAC3.1mathsf DisGAC3.1, which is the first distributed algorithm that enforces generalized arc-consistency on k-ary (π‘˜β‰₯2kβ‰₯2kge 2) constraint satisfaction problems. Theoretical analyses show that our algorithms are efficient in both time and space. Experiments also demonstrate that π–£π—‚π—Œπ– π–’πŸ₯.𝟣DisAC3.1mathsf DisAC3.1 outperforms the state-of-the-art distributed arc-consistency algorithm and that π–£π—‚π—Œπ–¦π– π–’πŸ₯.𝟣DisGAC3.1mathsf DisGAC3.1 ’s performance scales linearly in the number of agents.

Publication
Autonomous Agents and Multi-Agent Systems