Algorithms and Ordering Heuristics for Distributed Constraint Satisfaction Problems (ePub)

DisCSP (Distributed Constraint Satisfaction Problem) is a
general framework for solving distributed problems arising in
Distributed Artificial Intelligence.

A wide variety of problems in artificial intelligence are solved
using the constraint satisfaction problem paradigm. However, there
are several applications in multi-agent coordination that are of a
distributed nature. In this type of application, the knowledge
about the problem, that is, variables and constraints, may be
logically or geographically distributed among physical distributed
agents. This distribution is mainly due to privacy and/or security
requirements. Therefore, a distributed model allowing a
decentralized solving process is more adequate to model and solve
such kinds of problem. The distributed constraint satisfaction
problem has such properties.

Contents

Introduction

Part 1. Background on Centralized and Distributed Constraint
Reasoning

1. Constraint Satisfaction Problems

2. Distributed Constraint Satisfaction Problems

Part 2. Synchronous Search Algorithms for DisCSPs

3. Nogood Based Asynchronous Forward Checking (AFC-ng)

4. Asynchronous Forward Checking Tree (AFC-tree)

5. Maintaining Arc Consistency Asynchronously in Synchronous
Distributed Search

Part 3. Asynchronous Search Algorithms and Ordering Heuristics for
DisCSPs

6. Corrigendum to "Min-domain Retroactive Ordering for
Asynchronous Backtracking"

7. Agile Asynchronous BackTracking (Agile-ABT)

Part 4. DisChoco 2.0: A Platform for Distributed Constraint
Reasoning

8. DisChoco 2.0

9. Conclusion

About the Authors

Mohamed Wahbi is currently an associate lecturer at Ecole des
Mines de Nantes in France. He received his PhD degree in Computer
Science from University Montpellier 2, France and Mohammed V
University-Agdal, Morocco in 2012 and his research focused on
Distributed Constraint Reasoning.