Asynchronous Backtracking for Asymmetric DisCSPs
Roie Zivan and Amnon Meisels
Abstract
Distributed constraint satisfaction problems (DisCSPs) with
asym-metric constraints reflect the fact that agents may wish to retain their
constraints private. The set of pairs of values of every binary constraint
is split between the two constrained agents. An asynchronous backtracking
algorithm for asymmetric DisCSPs is presented. The new algorithm is based
on asynchronous backtracking (ABT), but, propa-gates assignments both to
lower priority agents and to higher priority agents. The proposed ABT ASC
algorithm is proven sound and complete. The ABT ASC algorithm is evaluated
experimentally on randomly generated asymmetric DisCSPs. Its performance
is compared to that of the privacy keeping version of ABT, proposed by Brito
and Meseguer, which splits the search into two phases. The ABT ASC algorithm
improves the run-time of the 2-phase ABT by a large factor with no additional
load on the communication network.