0.25
0.5
0.75
1.25
1.5
1.75
2
Optimization in Multi-Agent Systems
Published on 2011-08-2312346 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
Presentation
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 to06:49:27
At the end of this talk, you will be able to:10:51:17
Schedule11:22:47
Approximate Algorithms: outline25:35:35
OPTMAS in different forms ...28:22:38
Distributed Algorithms29:15:42
Historical note30:14:21
Contents35:48:49
Why OPTMAS?40:09:52
Part 140:46:56
A definition of coalition formation - 141:19:09
Why Approximate Algorithms43:14:59
What is an auction?47:17:40
A definition of coalition formation - 248:25:19
Where are auctions used nowadays?62:31:08
Exemplar Application: Surveillance63:50:34
Synchonous vs Asynchronous65:54:49
Outline - 166:26:31
Coalition Formation and other coordination paradigms - 175:11:42
Combinatorial auctions - 280:22:21
Why auctions?87:14:38
Distributed Constraint Optimization Problem for Decentralized Decision Making92:12:45
At the end of this talk, you will be able to:99:20:29
From CSP to DisCSP103:43:06
Coalition Formation and other coordination paradigms - 2105:28:56
Valuation functions116:06:00
Single good auctions116:53:55
Cooperative Decentralized Decision Making120:47:40
There are diverse cooperative and competitive scenarios125:00:56
Surveillance demo128:26:27
Multi-unit auctions - 1136:31:44
DCOPs for DDM140:21:45
In cooperative settings we focus on optimisation144:13:49
Assumptions145:53:19
Multi-item auctions - 1146:57:40
Modeling Problems as DCOP153:52:52
Multi-item auctions - 2156:12:01
Target Tracking161:30:05
Reverse auctions164:05:13
In competitive settings we focus on stability166:31:14
Guarantees on solution quality178:31:03
CA in Transportation [Sheffi 2004]181:34:42
CA in Transportation - 1183:20:45
CA in Transportation - 2183:50:55
Transportation. Combinatorial bidding - 1184:02:19
Transportation. Combinatorial bidding - 2184:11:41
Valuation functions184:26:16
Winner determination problem184:39:49
Part 2187:34:51
Multi-attribute auctions191:44:19
Coalition Formation - 1192:15:14
Target Tracking - DCOP192:52:16
Synchronous Backtracking197:36:19
Coalition Formation - 2206:16:21
Meeting Scheduling218:00:47
Types of Guarantees222:32:52
Coalition Structure - 1223:48:26
Multidimensional Auctions224:43:05
Coalition Structure - 2229:06:16
Coalition Formation Stages - 1232:02:17
Bidding languages239:09:05
ABT: Asynchonous Backtracking239:56:24
Meeting Scheduling - DCOP246:00:19
Centralized Local Greedy approaches - 1247:39:33
Coalition Formation Stages - 2248:15:37
Coalition Value Calculation - 1249:00:23
Single-unit auction protocols251:17:07
ABT: Description259:20:49
OR language Winner Determination Problem276:41:37
Centralized Local Greedy approaches - 2281:52:48
Benchmarking problems284:53:30
Centralized Local Greedy approaches - 3298:56:55
ABT: Directed Constraints299:45:07
Graph Coloring308:24:51
Coalition Value Calculation - 2313:18:19
Auction rules - 1314:21:16
Graph Coloring - MaxCSP320:21:24
CATS – Testing WDP algorithms [Leyton-Brown 2006]320:32:19
Distributed Stochastic Algorithm324:49:12
Auction rules - 2330:51:02
ABT: Nogoods332:09:25
Weighted Graph Coloring - COP332:14:41
Winner Determination Problem (WDP)334:26:51
Distributed Constraint Optimization: Exact Algorithms343:20:19
DSA-1: Execution Example344:34:27
Multi-unit auctions - 2350:19:16
DSA-1: discussion354:52:43
Task allocation - 1360:00:13
ABT: Nogood Resolution361:54:13
Task allocation - 2378:17:27
Maximum Gain Message (MGM-1)382:43:13
Coalition Formation Stages - 3383:36:10
Task allocation - 3392:28:50
How ABT works395:05:38
Combinatorial exchanges398:03:18
Multi-unit auctions - 3406:21:02
MGM-1: Example411:28:54
Multi-unit auctions - 4412:18:40
Local greedy approaches421:45:53
Weighted knapsack problem (example)429:09:37
Task allocation Combinatorial exchange - 1430:17:38
Task allocation Combinatorial exchange - 2433:27:25
GDL based approaches434:41:19
Combinatorial exchanges438:46:52
ABT: Messages438:54:36
Multi-unit auctions allow more complex bids445:54:35
Winner determination problem457:23:18
Bidding languages458:10:44
Fairness and Coalitional Stability472:29:19
Bidding language examples475:02:46
ABT: Data Structures480:49:00
Max-sum480:50:54
Outline - 6485:56:13
Purchasing process492:48:40
Weighted knapsack problem498:10:17
ABT: Graph Coloring Example516:07:44
Algorithms520:43:23
ABT: Example527:30:01
Reverse auctions for industrial procurement530:26:02
Max-Sum on acyclic graphs542:36:54
Coalition Formation Stages - 4545:18:57
Coalition Structure Generation547:59:16
Reverse auctions for industrial procurement [Bichler et al. 2006]559:48:39
Max-sum Performance566:52:12
Supply chain formation568:13:43
ABT: Why AddLink?578:50:45
ABT: Correctness / Completeness580:36:50
ABT: Termination583:52:06
Evaluation Measures586:52:47
Production process example588:04:10
Max-Sum for low power devices591:19:05
Purchasing (Buy)607:31:44
Make-or-Buy - 1621:28:02
From DisCSPs to DCOPs632:47:42
Make-or-Buy - 2634:36:55
Max-sum on hardware638:22:11
Make-or-Buy-or-Collaborate - 1639:27:57
The Set Partitioning Problem641:16:56
Make-or-Buy-or-Collaborate - 2650:12:46
Coalition Structure - 3657:08:52
Coalition Structure Generation - 1657:47:24
Combinatorial auctions for supply chain formation [Walsh et al., 2000] - 1663:59:53
Max-Sum for UAVs677:25:19
Combinatorial auctions for supply chain formation [Walsh et al., 2000] - 2679:36:15
Synchronous BnB683:06:47
Combinatorial auctions for supply chain formation [Walsh et al., 2000] - 3694:46:56
Mixed Multi Unit Combinatorial Auction (MMUCA)706:22:36
Inneficient Asynchronous DCOP721:33:18
Quality guarantees for approx. techniques725:23:15
MMUCA727:17:26
ADOPT: Asynchronous Distributed Optimization739:53:10
MMUCA Bidding language741:19:35
ADOPT: DFS tree (pseudotree)753:17:02
Coalition Structure Generation - 2755:52:56
MMUCA Solvers [Giovannucci 2008]765:03:30
ADOPT Description788:40:03
MMUCA generator [Vinyals et al. 2008]802:09:25
ADOPT Messages811:02:08
MMUCA resolution time825:56:19
ADOPT Data Structures834:01:36
ADOPT Bounds853:31:50
Analysing MMUCA hardness: Empirical findings [Almajano et. al, 2010]854:21:58
Off-Line guarantees866:38:57
K-Optimality framework867:59:13
K-Optimal solutions884:58:46
Analysing MMUCA hardness: Theoretical results [Fionda & Greco, 2009]890:30:34
ADOPT: Value Assignment905:49:10
Part 3906:58:37
ADOPT: Properties907:27:00
ADOPT: Example - 1907:42:38
Bounds for K-Optimality908:33:21
K-Optimality Discussion925:48:50
ADOPT: Example - 2928:00:49
Sequential MMUCA [Mikhaylov 2011]930:57:48
Advanced Coalition Formation935:02:44
Trade-off between generality and solution quality - 1959:15:03
Task Allocation via Coalition Formation962:23:09
Robocup Rescue Simulation - 1978:20:35
Trade-off between generality and solution quality - 2978:53:01
Robocup Rescue Simulation - 2981:51:53
Off-Line Guarantees: Region Optimality992:22:16
Outline - 7997:44:07
Robust auctions1008:45:54
Size-Bounded Distance1014:46:51
Max-Sum and Region Optimality1031:46:04
BnB-ADOPT1035:43:48
Spatial and Temporal Constraints1041:54:11
Task Allocation with Execution Uncertainty1043:44:47
BnB-ADOPT: Description1050:22:10
Trust-based task allocation1052:27:51
Bounds for Max-Sum1058:21:20
Variable Disjoint Cycles1067:15:02
BnB-ADOPT: Messages1069:01:54
BnB-ADOPT: Example1073:01:43
The example of the Ambulance Allocation problem1077:01:48
Efficiency vs Revenue-maximisation - 11077:18:13
Efficiency vs Revenue-maximisation - 21077:39:00
Trust-based task allocation - 11077:51:29
On-Line guarantees1077:55:23
Trust-based task allocation - 21089:30:09
Bounded max-sum1093:52:20
Trust-based task allocation - 31109:47:06
BnB-ADOPT: Performance1121:29:02
Trust-based task allocation Formal Model1122:21:45
Computing the weights1124:35:03
Optimal Algorithm for Ambulance Allocation1127:54:32
BnB-ADOPT: Redundant Messages1135:46:24
A New Strategy1147:15:25
Representing the space of allocations - 11151:25:36
Representing the space of allocations - 21160:07:50
Representing the space of allocations - 31165:50:35
Results (Random Binary Network)1167:49:49
CFST1179:19:58
Representing the space of allocations - 41180:17:40
Representing the space of allocations - 51180:42:44
DPOP: Dynamic Programming Optimization Protocol1182:39:06
Discussion1190:52:05
DPOP phases/messages1196:03:40
Representing the space of allocations - 61203:20:49
Representing the space of allocations - 71205:49:20
Future Challenges for DCOP1223:43:48
Representing the space of allocations - 81230:55:50
DPOP: DFS tree phase1232:27:34
DFS phase: Example1237:47:24
Representing the space of allocations - 91240:08:38
Representing the space of allocations - 101241:19:20
DPOP: Util phase1243:52:13
Representing the space of allocations - 111246:24:39
Challenging domains: Robotics1246:53:47
Representing the space of allocations - 121247:57:14
DPOP: util phase example1261:05:51
Representing the space of allocations - 131261:59:40
Virtual Power Plants in The Smart Grid1262:11:27
Challenging domains: Energy1270:00:32
Trust-based task allocation1285:41:13
References - 11288:15:38
Uncertainty and Dynamism1293:49:48
DPOP: Value phase1295:44:17
DTREE1308:23:15
Integer Programming formulation1308:38:39
Initial Solutions1328:29:46
DPOP: Example1334:55:33
Now, you should be able to:1337:40:08
Worst-case empirical analysis1341:51:25
DPOP: Performance1360:41:37
Payment (utility transfer) function1379:07:51
Mending auctions [Muñoz 2011]1420:54:24
Robustness for CA - 11442:03:50
Robustness for CA - 21457:24:54
Boolean satisfiability1475:35:09