Algorithms and ordering heuristics for distributed constraint satisfaction problems /

• Κύριος συγγραφέας: Wahbi, Mohamed
• Μορφή: Ηλ. βιβλίο
• Γλώσσα: English
• Έκδοση: London : ISTE ; 2013.; Hoboken : Wiley, 2013.
• Σειρά: FOCUS Series.
• Θέματα: Computer algorithms.; Image processing > Digital techniques.; Neural computers.; TECHNOLOGY & ENGINEERING > Optics.; Multi-User.; Electronic books.

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...

Πίνακας περιεχομένων:

• Title Page; Contents; Preface; Introduction; Part 1: Background on Centralized and Distributed Constraint Reasoning; Chapter 1. Constraint Satisfaction Problems; 1.1. Centralized constraint satisfaction problems; 1.1.1. Preliminaries; 1.1.2. Examples of CSPs; 1.2. Algorithms and techniques for solving centralized CSPs; 1.2.1. Algorithms for solving centralized CSPs; 1.2.2. Variable ordering heuristics for centralized CSPs; 1.3. Summary; Chapter 2. Distributed Constraint Satisfaction Problems; 2.1. Distributed constraint satisfaction problems; 2.1.1. Preliminaries; 2.1.2. Examples of DisCSPs.
• 2.1.3. Distributed meeting scheduling problem (DisMSP)2.1.4. Distributed sensor network problem (SensorDCSP); 2.2. Methods for solving DisCSPs; 2.2.1. Synchronous search algorithms on DisCSPs; 2.2.2. Asynchronous search algorithms on DisCSPs; 2.2.3. Dynamic ordering heuristics on DisCSPs; 2.2.4. Maintaining arc consistency on DisCSPs; 2.3. Summary; Part 2: Synchronous Search Algorithms for DisCSPs; Chapter 3. Nogood-based Asynchronous Forward Checking (AFC-ng); 3.1. Introduction; 3.2. Nogood-based asynchronous forward checking; 3.2.1. Description of the algorithm.
• 3.2.2. A simple example of the backtrack operation on AFC-like algorithms3.3. Correctness proofs; 3.4. Experimental evaluation; 3.4.1. Uniform binary random DisCSPs; 3.4.2. Distributed sensor-target problems; 3.4.3. Distributed meeting scheduling problems; 3.4.4. Discussion; 3.5. Summary; Chapter 4. Asynchronous Forward-Checking Tree(AFC-tree); 4.1. Introduction; 4.2. Pseudo-tree ordering; 4.3. Distributed depth-first search tree construction; 4.4. The AFC-tree algorithm; 4.4.1. Description of the algorithm; 4.5. Correctness proofs; 4.6. Experimental evaluation.
• 4.6.1. Uniform binary random DisCSPs4.6.2. Distributed sensor-target problems; 4.6.3. Distributed meeting scheduling problems; 4.6.4. Discussion; 4.7. Other related works; 4.8. Summary; Chapter 5. Maintaining Arc Consistency Asynchronously in Synchronous Distributed Search; 5.1. Introduction; 5.2. Maintaining arc consistency; 5.3. Maintaining arc consistency asynchronously; 5.3.1. Enforcing AC using del messages (MACA-del); 5.3.2. Enforcing AC without additional kind of message (MACA-not); 5.4. Theoretical analysis; 5.5. Experimental results; 5.5.1. Discussion; 5.6. Summary.
• Part 3: Asynchronous Search Algorithms and Ordering Heuristics for DisCSPsChapter 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; Chapter 7. Agile Asynchronous Backtracking(Agile-ABT); 7.1. Introduction; 7.2. Introductory material; 7.2.1. Reordering details; 7.2.2. The backtracking target; 7.2.3. Decreasing termination values; 7.3. The algorithm; 7.4. Correctness and complexity; 7.5. Experimental results.