A Class of Algorithms for Distributed Constraint Optimization

✍ Scribed by A. Petcu

• Publisher: IOS Press
• Year: 2009
• Tongue: English
• Leaves: 305
• Series: Frontiers in Artificial Intelligence and Applications 194: Dissertations in Artificial Intelligence
• Category: Library

✦ Synopsis

Multi Agent Systems (MAS) have recently attracted a lot of interest because of their ability to model many real life scenarios where information and control are distributed among a set of different agents. Practical applications include planning, scheduling, distributed control, resource allocation etc. A major challenge in such systems is coordinating agent decisions, such that a globally optimal outcome is achieved. Distributed Constraint Optimization Problems (DCOP) are a framework that recently emerged as one of the most successful approaches to coordination in MAS. A Class of Algorithms for Distributed Constraint Optimization addresses three major issues that arise in DCOP: efficient optimization algorithms, dynamic and open environments and manipulations from self-interested users. It makes significant contributions in all these directions by introducing a series of DCOP algorithms, which are based on dynamic programming and largely outperform previous DCOP algorithms. The basis of this class of algorithms is DPOP, a distributed algorithm that requires only a linear number of messages, thus incurring low networking overhead. For dynamic environments, self-stabilizing algorithms that can deal with changes and continuously update their solutions, are introduced. For self interested users, the author proposes the M-DPOP algorithm, which is the first DCOP algorithm that makes honest behavior an ex-post Nash equilibrium by implementing the VCG mechanism distributedly. The book also discusses the issue of budget balance and mentions two algorithms that allow for redistributing (some of) the VCG payments back to the agents, thus avoiding the welfare loss caused by wasting the VCG taxes.

IOS Press is an international science, technical and medical publisher of high-quality books for academics, scientists, and professionals in all fields.

Some of the areas we publish in:

-Biomedicine -Oncology -Artificial intelligence -Databases and information systems -Maritime engineering -Nanotechnology -Geoengineering -All aspects of physics -E-governance -E-commerce -The knowledge economy -Urban studies -Arms control -Understanding and responding to terrorism -Medical informatics -Computer Sciences

✦ Table of Contents

Title page......Page 2
Contents......Page 16
Introduction......Page 26
Overview......Page 29
I Preliminaries and Background......Page 32
Definitions and Notation......Page 34
Assumptions and Conventions......Page 36
Privacy and Self-Interest......Page 37
Distributed Meeting Scheduling......Page 38
Distributed Combinatorial Auctions......Page 39
Overlay Network Optimization......Page 42
Distributed Resource Allocation......Page 44
Takeoff and Landing Slot Allocation......Page 45
Background......Page 48
Backtrack Search in DCOP Algorithms......Page 49
dAO-Opt: Simple AND/OR Search For DCOP......Page 51
dAOBB: AND/OR Branch and Bound for DCOP......Page 54
Asynchronous search for DisCSP......Page 58
ADOPT......Page 61
Asynchronous Forward Bounding (AFB)......Page 62
Dynamic Programming (inference) in COP......Page 63
Partial Centralization: Optimal Asynchronous Partial Overlay (OptAPO)......Page 64
DFS trees......Page 65
Distributed DFS generation: a simple algorithm......Page 68
Heuristics for finding good DFS trees......Page 70
Heuristics for generating low-width DFS trees for dynamic programming......Page 71
II The DPOP Algorithm......Page 74
DPOP: A Dynamic Programming Optimization Protocol for DCOP......Page 76
DPOP phase 1: DFS construction to generate a DFS tree......Page 77
DPOP phase 2: UTIL propagation......Page 78
DPOP phase 3: VALUE propagation......Page 80
DPOP: Algorithm Complexity......Page 81
A Bidirectional Propagation Extension of DPOP......Page 82
H-DPOP: compacting UTIL messages with consistency techniques......Page 86
Preliminaries......Page 87
CDDs: Constraint Decision Diagrams......Page 88
H-DPOP - Pruning the search space with hard constraints......Page 89
Building CDDs from constraints:......Page 90
Implementing the JOIN operator on CDD messages......Page 92
The isConsistent plug-in mechanism......Page 93
Comparing H-DPOP with search algorithms......Page 95
NCBB: Non Commitment Branch and Bound Search for DCOP......Page 96
NCBB with caching......Page 97
Comparing pruning in search and in H-DPOP......Page 98
Experimental Results......Page 99
Random Graph Coloring Problems......Page 100
NQueens problems using graph coloring......Page 103
Winner Determination in Combinatorial Auctions......Page 104
H-DPOP vs NCBB: N-Queens......Page 105
H-DPOP vs NCBB: Combinatorial Auctions......Page 107
Related work......Page 108
Summary......Page 109
III Tradeoffs......Page 112
DPOP: a quick recap......Page 114
DFS-based method to detect subproblems of high width......Page 116
DFS-based Label propagation to determine complex subgraphs......Page 117
MB-DPOP(k): Trading off Memory vs. Number of Messages......Page 120
MB-DPOP - Labeling Phase to determine the Cycle Cuts......Page 121
Heuristic labeling of nodes as CC......Page 122
MB-DPOP - UTIL Phase......Page 123
MB-DPOP - VALUE Phase......Page 124
Meeting scheduling......Page 125
Related Work......Page 127
Summary......Page 129
O-DPOP: Message size vs. Number of Messages......Page 131
Propagating GOODs......Page 133
Value ordering and bound computation......Page 134
Valuation-Sufficiency......Page 135
Properties of the Algorithm......Page 136
Comparison with the UTIL phase of DPOP......Page 137
O-DPOP: soundness, termination, complexity......Page 138
Experimental Evaluation......Page 139
Comparison with search algorithms......Page 140
Summary......Page 141
LS-DPOP: a local search - dynamic programming hybrid......Page 142
LS-DPOP - local search/inference hybrid......Page 143
Detecting areas where local search is required......Page 144
Local search in independent clusters......Page 145
One local search step......Page 146
Iterative LS-DPOP for anytime......Page 147
Experimental evaluation......Page 149
Summary......Page 151
A-DPOP: approximations with minibuckets......Page 153
UTIL propagation phase......Page 154
Limiting the size of UTIL messages with approximations......Page 155
A-DPOP complexity......Page 157
AnyPOP - an anytime algorithm for large optimization problems......Page 158
Dominant values......Page 159
Propagation dynamics......Page 160
Iterative A-DPOP for anytime behaviour......Page 161
Experimental evaluation......Page 162
Summary......Page 164
PC-DPOP: Tradeoffs between Memory/Message Size and Centralization......Page 166
PC-DPOP - UTIL Phase......Page 168
PC-DPOP – Centralization......Page 169
Solving centralized subproblems......Page 170
PC-DPOP - VALUE Phase......Page 171
Experimental evaluation......Page 172
Meeting scheduling......Page 173
Related Work......Page 174
Summary......Page 175
IV Dynamics......Page 176
Dynamic Problem Solving with Self Stabilizing Algorithms......Page 178
Self-stabilizing AND/OR search......Page 179
S-DPOP optimizations for fault-containment......Page 180
Fault-containment in the DFS construction......Page 181
S-DPOP Protocol Extensions......Page 184
Super-stabilization......Page 185
Fast response time upon low-impact faults......Page 186
Commitment deadlines specified for individual variables......Page 188
Solution Stability as Minimal Cost of Change via Stability Constraints......Page 189
Algorithm RS-DPOP......Page 190
VALUE propagation......Page 191
Real time guarantees in dynamically evolving environments......Page 192
V Self-Interest......Page 194
Distributed VCG Mechanisms for Systems with Self-Interested Users......Page 196
Background on Mechanism Design and Distributed Implementation......Page 199
Social Choice Problems......Page 200
A Centralized COP Model as a MultiGraph......Page 202
A Decentralized COP (DCOP) Model Using Replicated Variables......Page 203
Cooperative Case: Efficient Social Choice via DPOP......Page 205
Constructing the DFS traversal......Page 206
Handling the Public Hard Constraints.......Page 208
Handling replica variables......Page 209
Complexity Analysis of DPOP Applied to Social Choice......Page 210
Handling Self-interest: A Faithful Algorithm for Social Choice......Page 211
The VCG Mechanism Applied to Social Choice Problems......Page 212
Faithful Distributed Implementation......Page 214
The Partition Principle applied to Efficient Social Choice......Page 216
Simple M-DPOP......Page 218
M-DPOP: Reusing Computation While Retaining Faithfulness......Page 220
Phase One of M-DPOP for a Marginal Problem: Constructing DFS-i......Page 222
Phase Two of M-DPOP for a Marginal Problem: UTIL-i propagations......Page 225
Experimental Evaluation: Distributed Meeting Scheduling......Page 226
Summary of M-DPOP......Page 229
Adapting ADOPT for Faithful, Efficient Social Choice......Page 230
Reusability of computation in ADOPT......Page 231
Adapting OptAPO for Faithful, Efficient Social Choice......Page 232
Budget Balance......Page 234
Related Work......Page 237
The VCG Mechanism Applied to Social Choice Problems......Page 239
Incentive Compatible VCG Payment Redistribution......Page 240
R-M-DPOP: Retaining Optimality While Seeking to Return VCG Payments......Page 241
An example of possible, indirect influence......Page 243
Detecting Areas of Indirect, Possible Influence......Page 245
A concrete numerical example of LABEL propagation......Page 249
BB-M-DPOP: Exact Budget-Balance Without Optimality Guarantees......Page 250
Experimental evaluation......Page 252
R-M-DPOP: Partial redistribution while maintaining optimality......Page 253
BB-M-DPOP: Complete redistribution in exchange for loss of optimality......Page 254
Distributed implementations: incentive issues......Page 256
Tuning the redistribution schemes......Page 257
Summary......Page 258
Conclusions......Page 260
Contributions......Page 261
Concluding Remarks......Page 264
Performance Evaluation for DCOP algorithms......Page 266
FRODO simulation platform......Page 271
Distributed Control......Page 272
Distributed Coordination of Robot Teams......Page 273
Relationships with author’s own previous work......Page 274
Bibliography......Page 276
List of Figures......Page 292
List of Tables......Page 296
List of Algorithms
......Page 298