Asynchronous Branch Bound and A{sup}* for DisWCSPs, With Heuristic Function Based on Consistency-Maintenance

摘要

Distributed weighted constraint satisfaction problems occur, for example, when privacy requirements exclude the centralization of the problem description. New definitions of arc consistency (AC) and node consistency (NC{sup}*) for centralized weighted constraint satisfaction problems (WCSP) have been recently proposed and prove increased simplicity and effectiveness [4]. We show how they can be exploited in asynchronous search: (a) Weighted Consistency Labels (WCL) are introduced to represent costs inherent to each value of a variable in an explored subproblem. (b) A maximal propagation of the weights with NC{sup}* can be guaranteed by either (b') designating a single agent for performing the summation of the costs synthesized by different agents for the same value and subproblem, or (b") having all agents learn and separately sum up all such costs, (c) The obtained weights combined with asynchronous Branch & Bound (B & B) leads to a distributed equivalent of powerful centralized versions of B & B. (d) The heuristic function needed by asynchronous A{sup}* can also be extracted from such costs computed concurrently with the search.