Distributed search by constrained agents : algorithms, performance, communication

Title:

Personal Author:

Meisels, Amnon

Publication Information:

London : Springer-Verlag, 2008

Physical Description:

xx, 216 p. : ill. ; 24 cm.

ISBN:

9781848000391

Subject Term:

Intelligent agents (Computer software)

Computer algorithms

Available:*

Library	Item Barcode	Call Number	Material Type	Item Category 1	Status
Searching... PSZ JB	30000010172825	QA76.76.I58 M44 2008	Open Access Book	Book	Searching... Unknown

Distributed search by agents is an important topic of distributed AI and has not been treated thoroughly as such. While the scope of work on multi-agent systems has grown steadily over the last decade, very little of it has spilled into distributed search. In conrast, the constraints processing community has produced a sizable body of work on distributed constrained search. Parado- cally, a community that concentrates on search algorithms and heuristics has created a distributed model for agents that cooperate on solving hard search problems. Traditionally, this ?eld has been named Ditributed Constraints S- isfaction and lately also distributed constraints optimization. The present book attempts to prompt deeper response from the MAS community and hopefully to give rise to cooperative work on distributed search by agents. In order to achieve this high goal, the book presents the large body of work on distributed search by constrained agents. The presentation emphasizes many aspects of distributed computation that connect naturally to multi-agent systems, - pecially measures of performance for distributed search algorithms and the impact of delays in communication. Distributed Constraints Satisfaction Problems (DisCSPs) have been st- ied over the last decade, starting with the pioneering proposal by Makoto Yokoo [18]. The ?rst distributed search algorithm for DisCSPs - As- chronous Backtracking (ABT) - was ?rst published in complete format in 1998 [64]. The ?rst book on Distributed Constraints Satisfaction Problems has appeared as early as 2000 [61].

1 Introduction	p. 1
2 Constraints Satisfaction Problems - CSPs	p. 7
2.1 Defining CSPs	p. 8
2.2 CSP Algorithms and Techniques	p. 10
2.3 Behavior of CSP solving algorithms	p. 13
3 Constraints Optimization Problems - COPs	p. 19
3.1 Branch and Bound (BnB)	p. 20
3.2 Branch and Bound + Arc-Consistency (BnB-AC)	p. 23
3.3 Branch and Bound + AC* (BnB-AC*)	p. 24
3.4 Phase Transition in MaxCSPs	p. 25
4 Distributed Search	p. 27
4.1 Distributed search algorithms on DisCSPs	p. 30
4.2 Introducing Asynchronous Backtracking	p. 33
5 Asynchronous Backtracking (ABT)	p. 37
5.1 A Complete 4-Queens Example	p. 40
5.2 The ABT Algorithm - Polynomial Storage	p. 43
5.3 Correctness of ABT	p. 47
5.4 Improving Performance of ABT	p. 49
6 Asynchronous Forward-Checking	p. 53
6.1 AFC - Algorithm Description	p. 55
6.2 Correctness of AFC	p. 59
6.3 Improved Backtrack Method for AFC	p. 61
7 Concurrent Dynamic Backtracking	p. 63
7.1 4-Queens with Concurrent Search	p. 65
7.2 The ConcBT Algorithm	p. 67
7.2.1 A splitting of search space example	p. 72
7.3 Concurrent Dynamic Backtracking	p. 75
7.4 Correctness of Concurrent Search	p. 79
8 Distributed Ordering Heuristics	p. 83
8.1 Ordering heuristics for Synchronous Backjumping	p. 85
8.1.1 Heuristics with no additional messages	p. 85
8.1.2 Heuristics with additional network overhead	p. 86
8.2 Ordering heuristics for AFC	p. 86
9 Asynchronous Ordering Heuristics	p. 89
9.1 Specific Asynchronous Heuristics	p. 89
9.2 Dynamically ordered ABT	p. 91
9.3 Correctness of ABT	p. DO
9.4 A new class of asynchronous heuristics	p. 97
9.5 Correctness of Retroactive ABT	p. DO
10 Performance measures for distributed search	p. 105
10.1 A Simple Example with Naive Methods	p. 107
10.2 Dividing concurrent search into rounds	p. 108
10.3 A More Complex Example for Computing NCCCs	p. 110
10.4 A Model for Nonconcurrent Constraints Checks	p. 111
10.5 The Cumulative Cost Algorithm (CCA)	p. 113
10.6 Realization of the Model by the CCA Algorithm	p. 115
11 Experimental Evaluation of DisCSP Algorithms	p. 121
11.1 Comparing Different Algorithms	p. 122
11.1.1 Asynchronous forward-checking vs. ABT	p. 122
11.1.2 Experimental evaluation of ConcDB	p. 123
11.2 Empirical Evaluation of Heuristic Ordering	p. 125
11.2.1 Evaluation of synchronous ordering heuristics	p. 126
11.2.2 Evaluation of dynamically ordered ABT	p. 128
11.2.3 Retroactive ordering for ABT	p. 133
12 The Impact of Communication - Message Delays	p. 137
12.1 Simulating Delayed Messages on DisCSPs	p. 139
12.1.1 Adjusting the measuring method for dynamic ordering	p. 140
12.2 Validity of AMDS	p. 141
13 Message Delays and DisCSP Search Algorithms	p. 143
13.1 The Impact of Message Delays	p. 145
13.2 A summary of the Impact of Message Delays	p. 154
13.3 Message Delays and Dynamic Ordering	p. 156
14 Distributed Constraint Optimization Problems (DisCOPs) 159
14.1 Pseudo-trees	p. 160
14.2 Synchronous Branch and Bound (SBB)	p. 161
14.3 Distributed Pseudo-tree Optimization (DPOP)	p. 162
14.4 Optimal Asynchronous Partial Overlay (OptAPO)	p. 164
15 Asynchronous Optimization for DisCOPs	p. 169
15.1 Lower and Upper Bounds in ADOPT	p. 170
15.1.1 Computing lower and upper bounds	p. 171
15.2 Assigning Values	p. 172
15.3 The Threshold Mechanism	p. 175
15.4 ADOPT - Summary and Termination	p. 176
15.5 Special (and Surprising) Features of ADOPT	p. 178
15.5.1 Updating context from lower priority agents	p. 179
15.5.2 Pseudo-trees and concurrency of computation	p. 180
15.5.3 Network load of ADOPT	p. 182
16 Asynchronous Forward-Bounding	p. 183
16.1 AFB - Overview	p. 183
16.2 Lower Bound Estimation for the Cost Increment	p. 184
16.3 AFB - Algorithm Description	p. 186
16.4 The Time-Stamp Mechanism	p. 188
16.5 AFB - Proof of Correctness	p. 189
16.6 Concurrency in AFB	p. 190
17 Extending AFB - BackJumping	p. 193
17.1 Adding Value Ordering Heuristics	p. 194
17.2 Backjumping - Key Concepts	p. 194
17.3 A Backjumping Example	p. 196
17.4 The AFB-BJ Algorithm	p. 198
17.5 AFB-BJ - Proof of Correctness	p. 201
18 Empirical Evaluation of DisCOP algorithms	p. 203
18.1 Empirical Evaluation of AFB and AFB-BJ	p. 204
References	p. 209
Index	p. 215

Available:*

On Order

Summary

Summary

Table of Contents