9781848215948

Algorithms and Ordering Heuristics for Distributed Constraint Satisfaction Problems

by
  • ISBN13:

    9781848215948

  • ISBN10:

    1848215940

  • Format: Hardcover
  • Copyright: 2013-07-10
  • Publisher: Iste/Hermes Science Pub

Note: Supplemental materials are not guaranteed with Rental or Used book purchases.

Purchase Benefits

  • Free Shipping On Orders Over $35!
    Your order must be $35 or more to qualify for free economy shipping. Bulk sales, PO's, Marketplace items, eBooks and apparel do not qualify for this offer.
  • Get Rewarded for Ordering Your Textbooks! Enroll Now
List Price: $81.00 Save up to $8.10
  • Rent Book $72.90
    Add to Cart Free Shipping

    TERM
    PRICE
    DUE
    USUALLY SHIPS IN 3-4 BUSINESS DAYS

Supplemental Materials

What is included with this book?

  • The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.
  • The Rental copy of this book is not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.

Summary

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.

Author Biography

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, Moracco in 2012 and his research focused on distributed Constraint Reasoning.

Table of Contents

Introduction

1 Background

1.1 Centralized Constraint Satisfaction Problems (CSP)

1.1.1 Preliminaries

1.1.2 Examples of CSPs

1.1.2.1 The n-queens problem

1.1.2.2 The Graph Coloring Problem

1.1.2.3 The Meeting Scheduling Problem

1.2 Algorithms and Techniques for Solving Centralized CSPs

1.2.1 Algorithms for Solving Centralized CSPs

1.2.1.1 Chronological Backtracking (BT)

1.2.1.2 Conflict-directed Backjumping (CBJ)

1.2.1.3 Dynamic Backtracking (DBT)

1.2.1.4 Partial Order Dynamic Backtracking (PODB)

1.2.1.5 Forward Checking(FC)

1.2.1.6 Arc-Consistency (AC)

1.2.1.7 Maintaining Arc-Consistency (MAC)

1.2.2 Variable Ordering Heuristics for Centralized CSP

1.2.2.1 Static Variable Ordering Heuristics (SVO)

1.2.2.2 Dynamic Variable Ordering Heuristics (DVO)

1.3 Distributed constraint satisfaction problems (DisCSP)

1.3.1 Preliminaries

1.3.2 Examples of DisCSPs

1.3.2.1 Distributed Meeting Scheduling Problem (DisMSP)

1.3.2.2 Distributed Sensor Network Problem (SensorDCSP)

1.4 Methods for solving distributed CSPs

1.4.1 Synchronous search algorithms on DisCSPs

1.4.1.1 Asynchronous Forward-Checking (AFC)

1.4.2 Asynchronous search algorithms on DisCSPs

1.4.2.1 Asynchronous Backtracking (ABT)

1.4.3 Dynamic Ordering Heuristics on DisCSPs

1.4.4 Maintaining Arc Consistency on DisCSPs

1.5 Summary

2 Nogood based Asynchronous Forward Checking (AFC-ng)

2.1 Introduction

2.2 Nogood-basedAsynchronousForwardChecking

2.2.1 Description of the algorithm

2.3 Correctness Proofs

2.4 Experimental Evaluation

2.4.1 Uniform binary random DisCSPs

2.4.2 Distributed Sensor Target Problems

2.4.3 Distributed Meeting Scheduling Problems

2.4.4 Discussion

2.5 Other Related Works

2.6 Summary

3 Asynchronous Forward Checking Tree (AFC-tree)

3.1 Introduction

3.2 Pseudo-tree ordering

3.3 Distributed Depth-First Search trees construction

3.4 The AFC-tree algorithm

3.4.1 Description of the algorithm

3.5 Correctness Proofs

3.6 Experimental Evaluation

3.6.1 Uniform binary random DisCSPs

3.6.2 Distributed Sensor Target Problems

3.6.3 Distributed Meeting Scheduling Problems

3.6.4 Discussion

3.7 Other Related Works

3.8 Summary

4 Maintaining Arc Consistency Asynchronously in Synchronous Distributed Search

4.1 Introduction

4.2 Maintaining Arc Consistency

4.3 Maintaining Arc Consistency Asynchronously

4.3.1 Enforcing AC using del messages (MACA-del)

4.3.2 Enforcing AC without additional kind of message (MACA-not)

4.4 Theoretical analysis

4.5 Experimental Results

4.5.1 Discussion

4.6 Summary

5 Agile Asynchronous BackTracking (Agile-ABT)

5.1 Introduction

5.2 Introductory Material

5.2.1 Reordering details

5.2.2 The Backtracking Target

5.2.3 Decreasing termination values

5.3 TheAlgorithm

5.4 Correctness and complexity

5.5 ExperimentalResults

5.5.1 Uniform binary random DisCSPs

5.5.2 Distributed Sensor Target Problems

5.5.3 Discussion

5.6 Related Works

5.7 Summary

6 Corrigendum to “Min-domain retroactive ordering for Asynchronous Backtracking”

6.1 Introduction

6.2 Background

6.3 ABT_DO-Retro May Not Terminate

6.4 The Right Way to Compare Orders

6.5 Summary

7 DisChoco 2.0

7.1 Introduction

7.2 Architecture

7.2.1 Communication System

7.2.2 Event Management

7.2.3 Observers in layers

7.3 Using DisChoco 2.0

7.4 Experimentations

7.5 Conclusion

Conclusions

Rewards Program

Write a Review