DISTRIBUTED ASYMMETRIC CONSTRAINT SATISFACTION, THE PHASE TRANSITION, AND EVOLUTIONARY PROTOCOLS

摘要

The distributed constraint satisfaction problem (DisCSP) can be viewed as a 4-tuple (X, D, C, A), where X is a set of n variables, D is a set of n domains (one domain for each of the n variables), C is a set of constraints that constrain the values that can be assigned to the n variables, and A is a set of agents for which the variables and constraints are distributed. The objective in solving a DisCSP is to allow the agents in A to develop a consistent distributed solution by means of message passing. The constraints are typically considered private and are not allowed to be communicated to fellow agents. When constraint privacy is enforced, inter-agent constraints that exist between the variables of multiple agents will most likely be asymmetric. In this paper, we develop an equation for predicting where the phase transition might be in randomly generated distributed asymmetric CSPs (DisACSPs). We then test this equation by comparing the performances of six evolutionary protocols referred to as societies of hill-climbers (SoHCs) [41] on 800 randomly generated binary DisACSPs. We then apply the best performing SoHC to an additional 2,000 randomly generated DisACSPs in order to provide a better view of the phase transition. Our results show that a SoHC (evolutionary protocol) is more effective in solving DisACSPs, in terms of success rate and average number of communication cycles needed, than a single distributed hill-climbing protocol running alone.