Distributed Search By Constrained Agents

by Meisels, Amnon

• ISBN13: 9781848000391
• ISBN10: 1848000391
• Format: Hardcover
• Copyright: 2007-11-08
• Publisher: Springer-Verlag New York Inc

Summary

Agent technology is evolving as a leading field of research connected to diverse areas such as A.I., E-commerce, robotics and information retrieval. Agents systems use reasoning and constraint-based reasoning that has a wide potential for representing multiple types of problems. A fundamental building block within all these areas is the ability to perform search and an inherent part of all agents must therefore relate to distributed and cooperative methods of search. This book presents a comprehensive discussion on the field of distributed constraints, its algorithms and its active research areas. It introduces distributed constraint satisfaction and optimization problems and proceeds to present a complete state-of-the-art in DisCSP & DisCOP research. The presentation assumes no prior knowledge of constraints or distributed constraints. Features and topics: a?? Introduces in great detail search algorithms for DisCSPs and DisCOPs a?? Presents a comprehensive study of distributed performance measures for all algorithms, allowing an extensive experimental evaluation to be constructed a?? Addresses potential problems following current research on DisCSPs and DisCOPs a?? Discusses the impact of communication quality on distributed search (for example message delays) a?? Describes the most significant recent research in the field of distributed constraints satisfaction and optimization, including its difficulties This exposition of the many elements of distributed search algorithms for DisCSPs and DisCOPs will be a research asset and an invaluable read for researchers and graduate students who focus on distributed CSPs and COPs. In addition, the booka??s comprehensiveness and style make it an ideal tool for a graduate course on distributed search in AI. Professor Amnon Meisels has an active research group who have worked in distributed constraints for a number of years and has published extensively in the field. He is a member of the Department of Computer Science at Ben-Gurion University, Beer-Sheva, Israel.

Table of Contents

Introduction	p. 1
Constraints Satisfaction Problems - CSPs	p. 7
Defining CSPs	p. 8
CSP Algorithms and Techniques	p. 10
Behavior of CSP solving algorithms	p. 13
Constraints Optimization Problems - COPs	p. 19
Branch and Bound (BnB)	p. 20
Branch and Bound + Arc-Consistency (BnB-AC)	p. 23
Branch and Bound + AC* (BnB-AC*)	p. 24
Phase Transition in MaxCSPs	p. 25
Distributed Search	p. 27
Distributed search algorithms on DisCSPs	p. 30
Introducing Asynchronous Backtracking	p. 33
Asynchronous Backtracking (ABT)	p. 37
A Complete 4-Queens Example	p. 40
The ABT Algorithm - Polynomial Storage	p. 43
Correctness of ABT	p. 47
Improving Performance of ABT	p. 49
Asynchronous Forward-Checking	p. 53
AFC - Algorithm Description	p. 55
Correctness of AFC	p. 59
Improved Backtrack Method for AFC	p. 61
Concurrent Dynamic Backtracking	p. 63
4-Queens with Concurrent Search	p. 65
The ConcBT Algorithm	p. 67
A splitting of search space example	p. 72
Concurrent Dynamic Backtracking	p. 75
Correctness of Concurrent Search	p. 79
Distributed Ordering Heuristics	p. 83
Ordering heuristics for Synchronous Backjumping	p. 85
Heuristics with no additional messages	p. 85
Heuristics with additional network overhead	p. 86
Ordering heuristics for AFC	p. 86
Asynchronous Ordering Heuristics	p. 89
Specific Asynchronous Heuristics	p. 89
Dynamically ordered ABT	p. 91
Correctness of ABT	p. DO
A new class of asynchronous heuristics	p. 97
Correctness of Retroactive ABT	p. DO
Performance measures for distributed search	p. 105
A Simple Example with Naive Methods	p. 107
Dividing concurrent search into rounds	p. 108
A More Complex Example for Computing NCCCs	p. 110
A Model for Nonconcurrent Constraints Checks	p. 111
The Cumulative Cost Algorithm (CCA)	p. 113
Realization of the Model by the CCA Algorithm	p. 115
Experimental Evaluation of DisCSP Algorithms	p. 121
Comparing Different Algorithms	p. 122
Asynchronous forward-checking vs. ABT	p. 122
Experimental evaluation of ConcDB	p. 123
Empirical Evaluation of Heuristic Ordering	p. 125
Evaluation of synchronous ordering heuristics	p. 126
Evaluation of dynamically ordered ABT	p. 128
Retroactive ordering for ABT	p. 133
The Impact of Communication - Message Delays	p. 137
Simulating Delayed Messages on DisCSPs	p. 139
Adjusting the measuring method for dynamic ordering	p. 140
Validity of AMDS	p. 141
Message Delays and DisCSP Search Algorithms	p. 143
The Impact of Message Delays	p. 145
A summary of the Impact of Message Delays	p. 154
Message Delays and Dynamic Ordering	p. 156
Distributed Constraint Optimization Problems (DisCOPs) 159
Pseudo-trees	p. 160
Synchronous Branch and Bound (SBB)	p. 161
Distributed Pseudo-tree Optimization (DPOP)	p. 162
Optimal Asynchronous Partial Overlay (OptAPO)	p. 164
Asynchronous Optimization for DisCOPs	p. 169
Lower and Upper Bounds in ADOPT	p. 170
Computing lower and upper bounds	p. 171
Assigning Values	p. 172
The Threshold Mechanism	p. 175
ADOPT - Summary and Termination	p. 176
Special (and Surprising) Features of ADOPT	p. 178
Updating context from lower priority agents	p. 179
Pseudo-trees and concurrency of computation	p. 180
Network load of ADOPT	p. 182
Asynchronous Forward-Bounding	p. 183
AFB - Overview	p. 183
Lower Bound Estimation for the Cost Increment	p. 184
AFB - Algorithm Description	p. 186
The Time-Stamp Mechanism	p. 188
AFB - Proof of Correctness	p. 189
Concurrency in AFB	p. 190
Extending AFB - BackJumping	p. 193
Adding Value Ordering Heuristics	p. 194
Backjumping - Key Concepts	p. 194
A Backjumping Example	p. 196
The AFB-BJ Algorithm	p. 198
AFB-BJ - Proof of Correctness	p. 201
Empirical Evaluation of DisCOP algorithms	p. 203
Empirical Evaluation of AFB and AFB-BJ	p. 204
References	p. 209
Index	p. 215
Table of Contents provided by Publisher. All Rights Reserved.