Algorithms and Ordering Heuristics for Distributed Constraint Satisfaction Problems

DisCSP (Distributed Constraint Satisfaction Problem) is ageneral framework for solving distributed problems arising inDistributed Artificial Intelligence. A wide variety of problems in artificial intelligence are solvedusing the constraint satisfaction problem paradigm. However, thereare several applications in multi-agent coordination that are of adistributed nature. In this type of application, the knowledgeabout the problem, that is, variables and constraints, may belogically or geographically distributed among physical distributedagents. This distribution is mainly due to privacy and/or securityrequirements. Therefore, a distributed model allowing adecentralized solving process is more adequate to model and solvesuch kinds of problem. The distributed constraint satisfactionproblem has such properties. Contents Introduction Part 1. Background on Centralized and Distributed ConstraintReasoning 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 SynchronousDistributed Search Part 3. Asynchronous Search Algorithms and Ordering Heuristics forDisCSPs 6. Corrigendum to “Min-domain Retroactive Ordering forAsynchronous Backtracking” 7. Agile Asynchronous BackTracking (Agile-ABT) Part 4. DisChoco 2.0: A Platform for Distributed ConstraintReasoning 8. DisChoco 2.0 9. Conclusion About the Authors Mohamed Wahbi is currently an associate lecturer at Ecole desMines de Nantes in France. He received his PhD degree in ComputerScience from University Montpellier 2, France and Mohammed VUniversity-Agdal, Morocco in 2012 and his research focused onDistributed Constraint Reasoning.