分布式人工智能

第一部分分布式人工智能簡介
1 概述
（安波，新加坡南洋理工大學(xué)）
1.1 研究背景3
1.1.1 前深度學(xué)習(xí)時代 3
1.1.2 深度學(xué)習(xí)時代6
1.2 主要研究領(lǐng)域8
1.2.1 算法博弈論8
1.2.2 分布式問題求解9
1.2.3 多智能體規(guī)劃10
1.2.4 多智能體學(xué)習(xí) 11
1.2.5 分布式機(jī)器學(xué)習(xí) 12
1.3 相關(guān)應(yīng)用14
1.3.1 足球14
1.3.2 安全博弈15
1.3.3 撲克和麻將 16
1.3.4 視頻游戲 17
1.4 當(dāng)前熱點(diǎn)與挑戰(zhàn)18
1.4.1 超大規(guī)模分布式人工智能系統(tǒng) 18
1.4.2 分布式人工智能系統(tǒng)的魯棒性和安全性 19
1.4.3 分布式人工智能決策的可解釋性 19
1.4.4 將傳統(tǒng)和深度學(xué)習(xí)的方法結(jié)合 20
參考文獻(xiàn)
第二部分分布式規(guī)劃與優(yōu)化
2 分布式規(guī)劃
（吳鋒，中國科技大學(xué)）
2.1 研究背景 9
2.2 分布式規(guī)劃的決策模型31
2.3 分布式規(guī)劃的離線算法36
2.3.1 離線精確規(guī)劃算法37
2.3.2 離線近似規(guī)劃算法 39
2.4 分布式規(guī)劃的在線算法46
2.4.1 在線協(xié)調(diào)機(jī)制 46
2.4.2 在線通信策略 48
2.5 當(dāng)前熱點(diǎn)與挑戰(zhàn) 52
參考文獻(xiàn) 54
3 分布式約束優(yōu)化
（陳自郁，重慶大學(xué)）
3.1 研究背景58
3.2 分布式約束優(yōu)化問題59
3.2.1 約束網(wǎng)絡(luò)59
3.2.2 基礎(chǔ)概念 60
3.3 求解算法分類63
3.4 完備求解算法65
3.4.1 基于搜索的完備求解算法：ADOPT 65
3.4.2 基于推理的完備求解算法：DPOP 69
3.5 非完備求解算法72
3.5.1 基于決策的局部搜索算法72
3.5.2 基于信念傳播的推理算法：Max-sum 75
3.6 基準(zhǔn)測試問題和典型應(yīng)用 80
3.6.1 基準(zhǔn)測試問題和評價指標(biāo) 80
3.6.2 典型應(yīng)用 82
3.7 當(dāng)前熱點(diǎn)與挑戰(zhàn)85
參考文獻(xiàn) 86
第三部分多智能體博弈
4 納什均衡求解
（鄧小鐵，北京大學(xué)；劉正陽，北京理工大學(xué)）
4.1 研究背景 93
4.2 正規(guī)形式博弈94
4.3 納什均衡與納什定理95
4.4 二人博弈納什均衡求解算法97
4.4.1 二人博弈的表示形式 98
4.4.2 支持枚舉算法 98
4.4.3 Lemke-Howson 算法 99
4.4.4 Lipton-Markakis-Mehta 算法103
4.4.5 三種算法的總結(jié)與對比106
4.5 納什均衡的計(jì)算復(fù)雜性106
4.6 當(dāng)前熱點(diǎn)與挑戰(zhàn)108
參考文獻(xiàn) 110
5 機(jī)制設(shè)計(jì)
（沈蔚然，中國人民大學(xué)；唐平中，清華大學(xué)）
5.1 研究背景112
5.2 什么是機(jī)制 113
5.2.1 社會選擇函數(shù) 113
5.2.2 機(jī)制的實(shí)現(xiàn)與顯示原理113
5.3 拍賣機(jī)制設(shè)計(jì) 118
5.3.1 性質(zhì)與設(shè)計(jì)目標(biāo) 119
5.3.2 社會福利最大化機(jī)制：VCG 機(jī)制 121
5.3.3 收益最大化機(jī)制：最優(yōu)拍賣 123
5.4 付費(fèi)搜索拍賣128
5.5 當(dāng)前熱點(diǎn)與挑戰(zhàn)130
參考文獻(xiàn)131
6 合作博弈與社會選擇
（王崇駿，南京大學(xué)）
6.1 研究背景133
6.2 合作博弈論135
6.2.1 合作博弈論的提出 135
6.2.2 合作博弈的一般表示 136
6.2.3 合作博弈的解 138
6.3 核與穩(wěn)定集 139
6.3.1 核的提出139
6.3.2 核的計(jì)算方式 140
6.3.3 穩(wěn)定集 141
6.4 核仁143
6.4.1 核仁的提出 143
6.4.2 核仁的計(jì)算方式 144
6.4.3 計(jì)算實(shí)例 145
6.5 Shapley 值150
6.5.1 Shapley 值的提出 150
6.5.2 Shapley 值的計(jì)算方式 151
6.5.3 計(jì)算實(shí)例 152
6.6 社會選擇153
6.6.1 社會選擇理論的提出 155
6.6.2 阿羅不可能性定理156
6.6.3 森的帕累托自由不可能定理 158
6.7 應(yīng)用場景 161
6.7.1 合作博弈應(yīng)用場景 161
6.7.2 社會選擇應(yīng)用場景 163
6.8 當(dāng)前熱點(diǎn)與挑戰(zhàn)164
6.8.1 合作博弈研究趨勢165
6.8.2 社會選擇研究趨勢 167
參考文獻(xiàn)170
7 博弈學(xué)習(xí)
（高陽、孟林建、葛振興，南京大學(xué)）
7.1 不完美信息擴(kuò)展式博弈177
7.2 均衡計(jì)算179
7.2.1 納什均衡 179
7.2.2 納什均衡的計(jì)算 181
7.2.3 線性規(guī)劃求解 182
7.2.4 遺憾最小化算法182
7.2.5 虛擬遺憾最小化算法 185
7.2.6 基于深度學(xué)習(xí)的方法 190
7.3 對手利用191
7.3.1 對手建模 192
7.3.2 對手利用的安全性 197
7.4 小結(jié)199
參考文獻(xiàn)200
第四部分多智能體學(xué)習(xí)
8 單智能體強(qiáng)化學(xué)習(xí)
（章宗長、俞揚(yáng)，南京大學(xué)）
8.1 研究背景207
8.2 強(qiáng)化學(xué)習(xí)的基本設(shè)定208
8.2.1 強(qiáng)化學(xué)習(xí)模型 208
8.2.2 馬爾可夫決策過程 210
8.3 動態(tài)規(guī)劃212
8.3.1 值迭代 213
8.3.2 策略迭代 214
8.4 表格式的強(qiáng)化學(xué)習(xí)215
8.4.1 免模型的學(xué)習(xí) 215
8.4.2 基于模型的學(xué)習(xí)217
8.5 深度強(qiáng)化學(xué)習(xí)219
8.5.1 基于值函數(shù)的深度強(qiáng)化學(xué)習(xí) 220
8.5.2 基于策略梯度的深度強(qiáng)化學(xué)習(xí) 227
8.5.3 基于行動者-評論家的深度強(qiáng)化學(xué)習(xí) 230
8.6 基準(zhǔn)測試平臺與實(shí)際應(yīng)用234
8.6.1 基準(zhǔn)測試平臺 234
8.6.2 實(shí)際應(yīng)用 237
8.7 當(dāng)前熱點(diǎn)與挑戰(zhàn)238
8.8 小結(jié) 242
參考文獻(xiàn)243
9 基于模型的強(qiáng)化學(xué)習(xí)
（張偉楠，上海交通大學(xué)；汪軍，倫敦大學(xué)學(xué)院）
9.1 Dyna：基于模型的強(qiáng)化學(xué)習(xí)經(jīng)典方法 249
9.2 打靶法250
9.3 基于模型的策略優(yōu)化方法253
9.4 基于模型的方法：從單智能體到多智能體255
9.4.1 自適應(yīng)對手智能體推演策略優(yōu)化算法（AORPO） 256
9.4.2 其他多智能體強(qiáng)化學(xué)習(xí)的基于模型的方法258
9.5 小結(jié)260
參考文獻(xiàn)262
10 多智能體合作學(xué)習(xí)
（張崇潔，清華大學(xué)）
10.1 研究背景263
10.2 合作學(xué)習(xí)問題描述265
10.3 基于值函數(shù)的合作多智能體強(qiáng)化學(xué)習(xí)算法265
10.3.1 值分解學(xué)習(xí)框架 266
10.3.2 線性值分解 268
10.3.3 單調(diào)值分解 269
10.3.4 IGM 完備值分解 270
10.4 基于策略的合作學(xué)習(xí)算法272
10.4.1 反事實(shí)策略梯度 272
10.4.2 多智能體深度確定性策略梯度 275
10.4.3 可分解的離策略多智能體策略梯度 277
10.5 基準(zhǔn)測試集280
10.5.1 多智能體小球環(huán)境MPE 280
10.5.2 星際爭霸Ⅱ 多智能體挑戰(zhàn)SMAC 280
10.5.3 谷歌足球 281
10.5.4 多智能體合作測試集MACO 282
10.6 當(dāng)前熱點(diǎn)與挑戰(zhàn)282
10.6.1 探索282
10.6.2 學(xué)習(xí)交流 283
10.6.3 共享學(xué)習(xí) 285
10.6.4 分層多智能體強(qiáng)化學(xué)習(xí) 286
10.6.5 離線多智能體強(qiáng)化學(xué)習(xí) 287
10.6.6 基于模型的多智能體合作學(xué)習(xí) 287
10.6.7 多智能體合作學(xué)習(xí)的理論分析 288
10.7 小結(jié)289
參考文獻(xiàn)290
11 多智能體競爭學(xué)習(xí)
（郝建業(yè)、鄭巖，天津大學(xué)）
11.1 研究背景298
11.2 競爭式問題描述 299
11.3 基于對手建模的競爭學(xué)習(xí)算法300
11.3.1 隱式的對手建模方法 300
11.3.2 顯式的對手建模方法 309
11.4 基于群體自博弈的競爭學(xué)習(xí)算法315
11.4.1 自博弈機(jī)制 315
11.4.2 聯(lián)盟訓(xùn)練 318
11.5 實(shí)際應(yīng)用319
11.6 小結(jié)321
參考文獻(xiàn)322
第五部分 分布式人工智能應(yīng)用
12 安全博弈
（安波，新加波南洋理工大學(xué)；甘家瑞，牛津大學(xué)）
12.1 研究背景327
12.2 安全博弈模型與均衡329
12.2.1 Stackelberg 均衡 330
12.2.2 均衡求解333
12.2.3 Stackelberg 安全博弈模型及求解 334
12.2.4 安全博弈實(shí)例 337
12.3 復(fù)雜環(huán)境下的安全博弈 339
12.3.1 信息不完全與不確定性 339
12.3.2 復(fù)雜策略空間的處理 343
12.3.3 動態(tài)安全博弈 346
12.4 實(shí)際應(yīng)用與成功案例349
12.4.1 重要基礎(chǔ)設(shè)施保護(hù) 349
12.4.2 交通系統(tǒng)安保調(diào)度 351
12.4.3 打擊環(huán)境資源犯罪與城市犯罪353
12.4.4 打擊犯罪網(wǎng)絡(luò) 354
12.4.5 其他應(yīng)用354
12.5 當(dāng)前熱點(diǎn)與挑戰(zhàn)354
12.5.1 研究熱點(diǎn) 355
12.5.2 未來研究方向 357
12.5.3 未來應(yīng)用領(lǐng)域 359
參考文獻(xiàn)360
13 社交網(wǎng)絡(luò)中的機(jī)制設(shè)計(jì)
（趙登吉，上?？萍即髮W(xué)）
13.1 研究背景367
13.2 傳播網(wǎng)絡(luò)與傳播機(jī)制369
13.3 VCG 在網(wǎng)絡(luò)上的擴(kuò)展373
13.3.1 具有傳播激勵的VCG 拍賣 373
13.3.2 傳播拍賣的不可能性定理 374
13.4 基于關(guān)鍵傳播路徑的拍賣機(jī)制375
13.4.1 關(guān)鍵傳播序列 375
13.4.2 信息傳播機(jī)制 376
13.4.3 關(guān)鍵傳播機(jī)制 378
13.4.4 閾值鄰接機(jī)制 380
13.5 當(dāng)前熱點(diǎn)與挑戰(zhàn) 381
參考文獻(xiàn)382