Wahbi M. Algorithms and Ordering Heuristics for Distributed Constraint Satisfaction Problems

Издательство John Wiley/IEEE Press, 2013, -167 pp.Constraint programming is an area in computer science that has gained increasing interest in recent years. Constraint programming is based on its powerful framework called constraint satisfaction problem (CSP). CSP is a general framework that can formalize many real-world combinatorial problems such as resource allocation, car sequencing, natural language understanding and machine vision. A CSP consists of looking for solutions to a constraint network, i.e. a set of assignments of values to variables that satisfy the constraints of the problem. These constraints represent restrictions on value combinations allowed for constrained variables.
Various applications that are of a distributed nature exist. In this kind of application, the knowledge about the problem, i.e. variables and constraints, is distributed among physically distributed agents. This distribution is mainly due to privacy and/or security requirements: constraints or possible values may be strategic information that should not be revealed to other agents that can be seen as competitors. Several applications in multi-agent coordination are of such kind. Examples of applications are sensor networks [JUN 01, BÉJ 05], military unmanned aerial vehicle teams [JUN 01], distributed scheduling problems [WAL 02, MAH 04], distributed resource allocation problems [PET 04], log-based reconciliation [CHO 06], distributed vehicle routing problems [LÉA 11], etc. Therefore, the distributed framework distributed constraint satisfaction problem (DisCSP) is used to model and solve this kind of problem.
A DisCSP is composed of a group of autonomous agents, where each agent has control of some elements of information about the whole problem, i.e. variables and constraints. Each agent owns its local constraint network. Variables in different agents are connected by constraints. Agents must assign, in a distributed manner, values to their variables so that all constraints are satisfied. Hence, agents assign values to their variables, attempting to generate locally consistent assignments that are also consistent with constraints between agents [YOK 98, YOK 00a]. To achieve this goal, agents check the values assigned to their variables for local consistency and exchange messages to check the consistency of their proposed assignments against constraints that contain variables that belong to other agents.
Many distributed algorithms for solving DisCSPs have been designed in the last two decades. They can be divided into two main groups: synchronous and asynchronous algorithms. The first category includes algorithms in which agents assign values to their variables in a synchronous and sequential way. The second category includes algorithms in which the process of proposing values to the variables and exchanging these proposals is performed asynchronously between the agents. In the former category, agents do not have to wait for decisions of others, whereas, in general, onlyPart I Background on Centralized and Distributed Constraint Reasoning
Constraint Satisfaction Problems
Distributed Constraint Satisfaction Problems
Part II Synchronous Search Algorithms for DisCSPs
Nogood-Based Asynchronous Forward Checking (AFC-Ng)
Asynchronous Forward-Checking Tree (AFC-Tree)
Maintaining Arc Consistency Asynchronously in Synchronous Distributed Search
Part III Asynchronous Search Algorithms and Ordering Heuristics for DisCSPs
Corrigendum to Min-Domain Retroactiveordering for Asynchronous Backtracking
Agile Asynchronous Backtracking (Agile-ABT)
Part IV Dischoco 2.0: A Platform for Distributed Constraint Reasoning
Dischoco 2.0