0.25
0.5
0.75
1.25
1.5
1.75
2
Optimization in Multi-Agent Systems
Published on Aug 23, 201112346 Views
The number of novel applications of multi-agent systems has followed an exponential trend over the last few years, ranging from online auction design, through in multi-sensor networks, to scheduling o
Related categories
Chapter list
Distributed Constraint Optimization: Exact Algorithms00:00
Distributed Constraint Optimization: Approximate Algorithms00:00
Market-based Resource Allocation00:00
Combinatorial auctions - 100:00
Optimisation in Multi-Agent Systems00:00
Optimization in Multi-Agent Systems00:00
At the end of this block you will be able to00:24
At the end of this talk, you will be able to:00:39
Schedule00:40
Approximate Algorithms: outline01:32
Introduction01:38
OPTMAS in different forms ...01:42
Distributed Algorithms01:45
Historical note01:48
Contents02:08
Why OPTMAS?02:24
Part 102:26
A definition of coalition formation - 102:28
Why Approximate Algorithms02:35
What is an auction?02:50
A definition of coalition formation - 202:54
Where are auctions used nowadays?03:45
Exemplar Application: Surveillance03:49
Synchonous vs Asynchronous03:57
Outline - 103:59
Coalition Formation and other coordination paradigms - 104:30
Combinatorial auctions - 204:49
Why auctions?05:14
Distributed Constraint Optimization Problem for Decentralized Decision Making05:31
At the end of this talk, you will be able to:05:57
From CSP to DisCSP06:13
Coalition Formation and other coordination paradigms - 206:19
Outline - 206:46
Valuation functions06:57
Single good auctions07:00
Cooperative Decentralized Decision Making07:14
There are diverse cooperative and competitive scenarios07:30
Surveillance demo07:42
Multi-unit auctions - 108:11
DCOPs for DDM08:25
In cooperative settings we focus on optimisation08:39
Assumptions08:45
Multi-item auctions - 108:49
Modeling Problems as DCOP09:13
Multi-item auctions - 209:22
Target Tracking09:41
Reverse auctions09:50
In competitive settings we focus on stability09:59
Guarantees on solution quality10:42
CA in Transportation [Sheffi 2004]10:53
CA in Transportation - 111:00
CA in Transportation - 211:01
Transportation. Combinatorial bidding - 111:02
Transportation. Combinatorial bidding - 211:03
Valuation functions11:03
Winner determination problem11:04
Part 211:15
Multi-attribute auctions11:30
Coalition Formation - 111:32
Target Tracking - DCOP11:34
Synchronous Backtracking11:51
Coalition Formation - 212:22
Meeting Scheduling13:04
Types of Guarantees13:21
Coalition Structure - 113:25
Multidimensional Auctions13:28
Coalition Structure - 213:44
Coalition Formation Stages - 113:55
Outline - 314:08
Bidding languages14:20
ABT: Asynchonous Backtracking14:23
Meeting Scheduling - DCOP14:45
Centralized Local Greedy approaches - 114:51
Coalition Formation Stages - 214:53
Coalition Value Calculation - 114:56
Outline - 415:03
Single-unit auction protocols15:04
ABT: Description15:33
OR language Winner Determination Problem16:36
Centralized Local Greedy approaches - 216:54
Benchmarking problems17:05
Centralized Local Greedy approaches - 317:56
ABT: Directed Constraints17:59
Graph Coloring18:30
Coalition Value Calculation - 218:47
Auction rules - 118:51
Graph Coloring - MaxCSP19:13
CATS – Testing WDP algorithms [Leyton-Brown 2006]19:13
Distributed Stochastic Algorithm19:29
Auction rules - 219:51
ABT: Nogoods19:55
Weighted Graph Coloring - COP19:56
Winner Determination Problem (WDP)20:04
Distributed Constraint Optimization: Exact Algorithms20:36
DSA-1: Execution Example20:40
Multi-unit auctions - 221:01
DSA-1: discussion21:17
Task allocation - 121:36
ABT: Nogood Resolution21:42
Task allocation - 222:41
Maximum Gain Message (MGM-1)22:57
Coalition Formation Stages - 323:00
Task allocation - 323:32
How ABT works23:42
Combinatorial exchanges23:52
Multi-unit auctions - 324:22
MGM-1: Example24:41
Multi-unit auctions - 424:44
Local greedy approaches25:18
Weighted knapsack problem (example)25:44
Task allocation Combinatorial exchange - 125:49
Task allocation Combinatorial exchange - 226:00
GDL based approaches26:04
Combinatorial exchanges26:19
ABT: Messages26:20
Multi-unit auctions allow more complex bids26:45
Winner determination problem27:26
Bidding languages27:29
Fairness and Coalitional Stability28:20
Bidding language examples28:30
ABT: Data Structures28:50
Max-sum28:51
Outline - 629:09
Purchasing process29:34
Weighted knapsack problem29:53
ABT: Graph Coloring Example30:58
Algorithms31:14
ABT: Example31:39
Reverse auctions for industrial procurement31:49
Outline - 531:59
Max-Sum on acyclic graphs32:33
Coalition Formation Stages - 432:43
Coalition Structure Generation32:52
Reverse auctions for industrial procurement [Bichler et al. 2006]33:35
Max-sum Performance34:00
Supply chain formation34:05
ABT: Why AddLink?34:43
ABT: Correctness / Completeness34:50
ABT: Termination35:01
Evaluation Measures35:12
Production process example35:17
Max-Sum for low power devices35:28
Purchasing (Buy)36:27
Make-or-Buy - 137:17
From DisCSPs to DCOPs37:58
Make-or-Buy - 238:04
Max-sum on hardware38:18
Make-or-Buy-or-Collaborate - 138:22
The Set Partitioning Problem38:28
Make-or-Buy-or-Collaborate - 239:00
Coalition Structure - 339:25
Coalition Structure Generation - 139:28
Combinatorial auctions for supply chain formation [Walsh et al., 2000] - 139:50
Max-Sum for UAVs40:38
Combinatorial auctions for supply chain formation [Walsh et al., 2000] - 240:46
Synchronous BnB40:59
Combinatorial auctions for supply chain formation [Walsh et al., 2000] - 341:41
Mixed Multi Unit Combinatorial Auction (MMUCA)42:22
Inneficient Asynchronous DCOP43:17
Quality guarantees for approx. techniques43:31
MMUCA43:38
ADOPT: Asynchronous Distributed Optimization44:23
MMUCA Bidding language44:28
ADOPT: DFS tree (pseudotree)45:11
Coalition Structure Generation - 245:21
MMUCA Solvers [Giovannucci 2008]45:54
ADOPT Description47:19
MMUCA generator [Vinyals et al. 2008]48:07
ADOPT Messages48:39
MMUCA resolution time49:33
ADOPT Data Structures50:02
ADOPT Bounds51:12
Analysing MMUCA hardness: Empirical findings [Almajano et. al, 2010]51:15
Off-Line guarantees51:59
K-Optimality framework52:04
K-Optimal solutions53:05
Analysing MMUCA hardness: Theoretical results [Fionda & Greco, 2009]53:25
ADOPT: Value Assignment54:20
Part 354:25
ADOPT: Properties54:26
ADOPT: Example - 154:27
Bounds for K-Optimality54:30
K-Optimality Discussion55:32
ADOPT: Example - 255:40
Sequential MMUCA [Mikhaylov 2011]55:51
Advanced Coalition Formation56:06
Trade-off between generality and solution quality - 157:33
Task Allocation via Coalition Formation57:44
Robocup Rescue Simulation - 158:42
Trade-off between generality and solution quality - 258:43
Robocup Rescue Simulation - 258:54
Off-Line Guarantees: Region Optimality59:32
Outline - 759:51
Robust auctions01:00:31
Size-Bounded Distance01:00:53
Max-Sum and Region Optimality01:01:54
BnB-ADOPT01:02:08
Spatial and Temporal Constraints01:02:30
Task Allocation with Execution Uncertainty01:02:37
BnB-ADOPT: Description01:03:01
Trust-based task allocation01:03:08
Bounds for Max-Sum01:03:30
Variable Disjoint Cycles01:04:02
BnB-ADOPT: Messages01:04:08
BnB-ADOPT: Example01:04:22
The example of the Ambulance Allocation problem01:04:37
Efficiency vs Revenue-maximisation - 101:04:38
Efficiency vs Revenue-maximisation - 201:04:39
Trust-based task allocation - 101:04:40
On-Line guarantees01:04:40
Trust-based task allocation - 201:05:22
Bounded max-sum01:05:37
Trust-based task allocation - 301:06:35
BnB-ADOPT: Performance01:07:17
Trust-based task allocation Formal Model01:07:20
Computing the weights01:07:28
Optimal Algorithm for Ambulance Allocation01:07:40
BnB-ADOPT: Redundant Messages01:08:08
A New Strategy01:08:50
Representing the space of allocations - 101:09:05
Representing the space of allocations - 201:09:36
Representing the space of allocations - 301:09:57
Results (Random Binary Network)01:10:04
CFST01:10:45
Representing the space of allocations - 401:10:49
Representing the space of allocations - 501:10:50
DPOP: Dynamic Programming Optimization Protocol01:10:57
Discussion01:11:27
DPOP phases/messages01:11:45
Representing the space of allocations - 601:12:12
Representing the space of allocations - 701:12:20
Future Challenges for DCOP01:13:25
Representing the space of allocations - 801:13:51
DPOP: DFS tree phase01:13:56
DFS phase: Example01:14:16
Representing the space of allocations - 901:14:24
Representing the space of allocations - 1001:14:28
DPOP: Util phase01:14:37
Representing the space of allocations - 1101:14:47
Challenging domains: Robotics01:14:48
Representing the space of allocations - 1201:14:52
DPOP: util phase example01:15:39
Representing the space of allocations - 1301:15:43
Virtual Power Plants in The Smart Grid01:15:43
Challenging domains: Energy01:16:12
Trust-based task allocation01:17:08
References - 101:17:17
Uncertainty and Dynamism01:17:37
DPOP: Value phase01:17:44
DTREE01:18:30
Integer Programming formulation01:18:31
Initial Solutions01:19:42
DPOP: Example01:20:05
Now, you should be able to:01:20:15
Worst-case empirical analysis01:20:30
DPOP: Performance01:21:38
Payment (utility transfer) function01:22:44
Mending auctions [Muñoz 2011]01:25:15
Robustness for CA - 101:26:31
Robustness for CA - 201:27:26
Boolean satisfiability01:28:32