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