Distributed constraint satisfaction problems (
s) with asymmetric constraints reflect the fact that agents may wish to retain their constraints private. Brito and Meseguer proposed a model for asymmetric constraints which they term
Partially Known Constraints
). In the
model each binary constraint is divided between the two constraining agents. In order to solve the resulting
with asymmetric constraints, a two phase asynchronous backtracking algorithm was proposed [BM03]. In the first phase an asynchronous backtracking algorithm is performed, in which only the constraints held by the lower priority agents are examined. When a solution is reached, a second phase is performed in which the consistency of the solution is checked again, according to the constraints held by the higher priority agents in each binary constraint.
The present paper proposes a one phase asynchronous backtracking algorithm which solves
with asymmetric constraints. In the proposed
asynchronous backtracking for asymmetric constraints
) agents send their proposed assignments to all their neighbors in the constraints graph. Agents assign their local variables according to the priority order as in
but check the constraints also against the assignment of lower priority agents. When an agent detects a conflict between its own assignment and the assignment of an agent with a lower priority than itself, it sends a
to the lower priority agent
but keeps its assignment
. Agents which receive a
from higher priority agents, perform the same operations as if they have produced this
themselves. As in
[Yok00], they remove their current assignment from their current-domain, store the eliminating
and reassign their variable.
algorithm is evaluated experimentaly on randomly generated
and is shown to outperform the 2-phase
with respect to two different distributed performance measures. ABT_ASC performs fewer non-concurrent constraints checks by a factor of 6, for the harder problem instances. The load on the network is very similar for both algorithms, counting the total number of messages sent by both algorithms.