應急管理中自組織任務分配的博弈模型與應用

蘇軍 陳怡林 張東煜

摘 要：非常規(guī)的突發(fā)事件發(fā)生后，群眾的各種自組織救災活動發(fā)揮著至關重要的作用。應用合作博弈刻畫自組織活動中群眾的策略選擇與協(xié)作機制，研究群眾如何根據(jù)特定目標自發(fā)建立聯(lián)盟并實現(xiàn)最優(yōu)的任務分配。首先在群眾的自組織任務分配過程中引入多Agent系統(tǒng)（MAS），以自治Agent的交互行為與合作策略模擬群眾聯(lián)盟形成與任務分配的過程，通過定義分布式社交網(wǎng)絡結構，以圖限制下的合作博弈為分析工具，構造帶技能的聯(lián)盟形成博弈模型，確定任務與Agent聯(lián)盟之間的映射。其次引入系統(tǒng)效用函數(shù)和偏好順序，在聯(lián)盟形成博弈模型的基礎上建立優(yōu)化模型，通過求解該優(yōu)化模型獲得最優(yōu)的聯(lián)盟結構及任務分配方案。最后介紹聯(lián)盟結構形成和優(yōu)化的相關算法，在自組織救災案例“互聯(lián)網(wǎng)人YO！群”中驗證模型和算法的合理性。結果表明：應急管理中群眾的自組織任務分配過程可在MAS中建模為帶技能的聯(lián)盟形成博弈，該博弈模型可實現(xiàn)任務與Agent聯(lián)盟之間的一一對應，通過進一步優(yōu)化可找到使得系統(tǒng)效用最大的聯(lián)盟結構及最優(yōu)的任務分配方案。

關鍵詞：合作博弈；應急管理；多Agent系統(tǒng)；自組織；任務分配

中圖分類號：N 94；F 224

文獻標志碼：A

文章編號：1672-9315（2022）05-1046-08

DOI：10.13800/j.cnki.xakjdxxb.2022.0525開放科學（資源服務）標識碼（OSID）：

Game model and application of self-organized task allocation in emergency management

SU Jun，CHEN Yilin，ZHANG Dongyu

（College of? Sciences，Xi’an University of Science and Technology，Xi’an 710054，China）

Abstract：After unconventional emergencies，various self-organized disaster relief activities of the masses play a vital role.The cooperative game was applied to describe the strategy selection and cooperation mechanism of the masses in self-organized activities，and to study how the masses spontaneously establish coalitions according to specific goals with the optimal task allocation achieved.Firstly，multi-agent system（MAS）was introduced into the process of mass self-organized task allocation.The process of mass coalition formation and task allocation was simulated by the interaction behavior and cooperation strategy of autonomous agents.By determining the structure of distributed social network and using the cooperative game under graph constraints as an analysis tool，a skilled coalition formation game model was constructed，and the mapping between tasks and agent coalitions was confirmed.Secondly，the system utility function and preference order were introduced，an optimization model was established based on the coalition formation game model，and the optimal coalition structure and task allocation scheme were obtained by solving this optimization model.Finally，an introduction was made to the relevant algorithms for the formation and optimization of the coalition structure，and the rationality was verified of the model and algorithm in the self-organized disaster relief case“Internet people yo！ Group”.The results show that the self-organized task allocation process of the masses in emergency management can be modeled in MAS as a skilled coalition formation game model.The game model can realize one-to-one correspondence between tasks and agent coalitions.Through further optimization，the coalition structure and the optimal task allocation scheme that maximize the system utility can be found out.

Key words：cooperative game；emergency management；Multi-Agent System；self-organization；task allocation

0 引 言

新冠疫情爆發(fā)以來，中國部分城市在必要時緊急采取封城管理，會導致決策遲緩、行動低效、物資調(diào)配困難等問題。群眾自發(fā)組織快遞人員及志愿者，根據(jù)防控態(tài)勢自行確定“任務”，能有效地保障部分市民的交通、餐飲等各項服務。上述案例說明：在非常規(guī)突發(fā)事件發(fā)生后的短時間內(nèi)，群眾可通過自發(fā)、自愿組織形成團隊并完成應急任務，這一基于自組織的應急管理方式發(fā)揮著至關重要的作用，進一步提高應急管理的時效性和科學性。

多Agent系統(tǒng)（multi-agent system，MAS）是一種以社會形式出現(xiàn)的分布式結構自組織系統(tǒng)，系統(tǒng)中沒有中央權威或領導者，各Agent之間地位和作用平等、可以相互交流與合作，能有效地實現(xiàn)目標、共享資源和解決沖突。應急管理中的群眾參與過程具有MAS的自組織特性，各方往往會通過相互合作形成聯(lián)盟，為社會產(chǎn)生最大利益。聯(lián)盟形成博弈正是模擬這種行為的自然方式，但在聯(lián)盟形成博弈或MAS的相關文獻中，很少有研究將應急管理自組織的問題與二者聯(lián)系起來，文中的研究就是為了更好地建立這種聯(lián)系。

Agent的聯(lián)盟形成通常涉及3個過程：首先，每個Agent使用一些談判程序自主加入聯(lián)盟；其次，解決每個聯(lián)盟的優(yōu)化問題，使其效用最大化；最后，將每個聯(lián)盟的價值公平分配給聯(lián)盟中的成員。自組織的聯(lián)盟形成問題最突出的一類是任務分配問題，即Agent之間如何自發(fā)形成最大化系統(tǒng)效用或最小化偏離聯(lián)盟動機的聯(lián)盟結構，使得聯(lián)盟結構中每個聯(lián)盟各自對應一項或多項任務。任務分配問題在眾多背景中得到應用：ZHU等將復雜任務劃分為多個子任務并提出一個實用的任務調(diào)度方案，包括任務調(diào)度機制、贏家聯(lián)盟形成機制和報酬共享機制，實現(xiàn)有限云資源的合理調(diào)度；YIN等在聯(lián)盟形成的任務分配中考慮任務利潤隨時間流逝的情況，通過設計一種“退出-選擇”機制以形成更多的聯(lián)盟，從而提高系統(tǒng)的整體效用；SUN等通過將多衛(wèi)星系統(tǒng)中的自組織任務分配問題公式化為一個勢博弈，提出一種基于博弈的分布式任務分配算法并證明博弈的每個納什均衡是最大化執(zhí)行任務數(shù)量的一個任務覆蓋。

在應急管理自組織系統(tǒng)中，Agent存在于一個特定的社交網(wǎng)絡中，在無法獨立完成某項任務時通常會充分調(diào)動自身資源，發(fā)動那些自己認識且有能力完成任務的Agent形成聯(lián)盟，因此任意2個Agent之間并非彼此分散，而存在著一定的潛在關系，例如通信距離、信用度或組織層級等，可能會對博弈的效用和其他特征產(chǎn)生重大影響。為刻畫Agent之間的潛在關系及限制聯(lián)盟形成過程的信息交互，文中在聯(lián)盟形成過程中引入社交網(wǎng)絡結構。此外，許多現(xiàn)有的研究中假設每個Agent有且只能加入一個聯(lián)盟并完成一項任務，但實際上系統(tǒng)中的部分Agent并沒有貢獻任何技能或資源，部分還有冗余，一對一的任務分配方式會導致大量資源浪費，因此在聯(lián)盟形成過程中還考慮聯(lián)盟的重疊屬性，用于解決傳統(tǒng)的聯(lián)盟形成過程中存在的問題并改進任務分配的結果。

筆者在應急管理自組織的大背景下，以合作博弈理論與MAS為基礎，提出基于聯(lián)盟形成的任務分配機制，通過找到使得系統(tǒng)效用最大的聯(lián)盟結構，實現(xiàn)最優(yōu)的任務分配，并設計聯(lián)盟形成和優(yōu)化的相關算法，最后在實際應用中檢驗模型和算法的可行性。

由上述隨機數(shù)據(jù)組，通過算法1得到初始聯(lián)盟結構∏=（CA，CB，CC，C0），各聯(lián)盟分別為CA={a21，a31，a14}，CB={a32，a42，a51}，CC={a85，a62，a74}，C0={a41，a11，a22，a72，a53，a13，a73，a33，a75，a35，a66，a76，a56，a26}。即任務A由a1，a4完成、任務B由a1，a2完成、任務C由a2，a4，a5完成，而a3，a6目前對任務沒有任何貢獻，將其暫時放入空閑聯(lián)盟C0，分配結果如圖4所示。

實驗結果表明，互聯(lián)網(wǎng)人YO！群的任務分配機制可在MAS中建模為一個帶技能的聯(lián)盟形成博弈，其中的社交網(wǎng)絡結構充分反映社會分布式網(wǎng)絡環(huán)境的真實情況、降低聯(lián)盟結構形成的復雜度、加快優(yōu)化過程的收斂速度；同時，通過算法1可找到合理的初始聯(lián)盟結構，實現(xiàn)任務與聯(lián)盟的一一對應，從而驗證算法的有效性和模型的適用性。

應急管理中群眾的自組織救災機制不同于傳統(tǒng)的自上而下管理機制，盡管自組織系統(tǒng)本身是雜亂無章的，但帶技能的聯(lián)盟形成博弈模型要求群眾根據(jù)任務的技能需求形成對應聯(lián)盟，其實質(zhì)是自組織系統(tǒng)中遵循的一種特定規(guī)則，可使得系統(tǒng)從無序走向有序、從低效走向高效，符合應急管理的宏觀秩序，能為組織化救援創(chuàng)造一定的緩沖時間。同時，該模型也實現(xiàn)了應急管理、博弈論和人工智能3個領域的結合。

4 結 論

1）突發(fā)事件應急管理中的自組織任務分配問題可引入MAS中考慮，圖博弈與帶技能的聯(lián)盟形成博弈的結合，刻畫社交網(wǎng)絡中的自組織群體合作完成任務的過程。基于Agent的群體理性，通過構建系統(tǒng)效用函數(shù)，在聯(lián)盟形成博弈模型的基礎上建立優(yōu)化問題，可找出使得系統(tǒng)效用最大的聯(lián)盟結構和任務分配方案。

2）從互聯(lián)網(wǎng)人YO！群的實例分析中可以看出，算法1對任務導向的初始聯(lián)盟形成具有較好的求解效果。通過定義Agent的偏好順序，利用算法2可實現(xiàn)聯(lián)盟的動態(tài)更新與優(yōu)化，進一步驗證了模型的可行性，也為突發(fā)事件應急管理中的群眾自組織救災工作提供了理論指導。

3）文中的任務分配機制是基于最大化系統(tǒng)效用的并行分配，而在現(xiàn)實情況中各項任務的緊急程度與難易程度不同，后期的研究可以在分配過程中考慮任務的完成順序和完成效率，以期提高任務分配的有效性和科學性。

參考文獻（References）：

[1]聶磊.透析危機管理中的自組織現(xiàn)象[J].社會科學，2011（6）：84-89.NIE Lei.Study on phenomena of self-organization in crisis management[J].Journal of Social Sciences，2011（6）：84-89.

[2]李琦.自組織視閾下應急管理的社會參與[J].理論月刊，2016（8）：130-134.LI Qi.Social participation in emergency management from the perspective of self-organization[J].Theory Monthly，2016（8）：130-134.

[3]龔志文，劉太剛.公共危機中民眾的自組織機制及其約束——以抗擊新冠肺炎疫情為例[J].天津行政學院學報，2021，23（2）：11-23.GONG Zhiwen，LIU Taigang.Social self-organization mechanism and constraits in public crisis management：Taking the prevention of the COVID-19 as an example[J].Journal of Tianjin Administration Institute，2021，23（2）：11-23.

[4]伏明蘭.聯(lián)盟技能博弈中自利agent的協(xié)作與任務分配研究[D].合肥：合肥工業(yè)大學，2018.FU Minglan.Research on collaboration and task allocation of self-interested agents in coalitional skill games[J].Hefei：Hefei University of Technology，2018.

[5]SU X，WANG Y C，JIA X B，et al.Two innovative coalition formation models for dynamic task allocation in disaster rescues[J].Journal of Systems Science and Systems Engineering，2018，27（2）：215-230.

[6]STALLINGS R A，QUARANTELL E L.Emergent citizen groups and emergency management[J].Public Administration Review，1985，45：93-100.

[7]周躍進，郝巳玥，張連敏，等.自組織團隊特征分析[J].管理學報，2010，7（8）：1159-1164，1170.ZHOU Yuejin，HAO Siyue，ZHANG Lianmin，et al.Feature analysis of self-organizing teams[J].Chinese Journal of Management，2010，7（8）：1159-1164，1170.

[8]SIMS M，GOLDMAN C V，LESSER V.Self-organization through bottom-up coalition formation[C]//Proceedings of the second international joint conference on Autonomous agents and multiagent systems.2003：867-874．

[9]朱大奇，李欣，顏明重.多自治水下機器人多任務分配的自組織算法[J].控制與決策，2012，27（8）：1201-1205，1210．ZHU Daqi，LI Xin，YAN Mingzhong.Task assignment algorithm of multi-AUV based on self-organizing map[J].Control and Decision，2012，27（8）：1201-1205，1210.

[10]SAAD W，HAN Z，DEBBAH M，et al.Coalitional game theory for communication networks[J].IEEE Signal Processing Magazine，2009，26（5）：77-97.

[11]SAAD W，HAN Z，HJORUNGNES A，et al.Coalition formation games for distributed cooperation among roadside units in vehicular networks[J].IEEE Journal on Selected Areas in Communications，2010，29（1）：48-60.

[12]SAAD W，HAN Z，DEBBAH M，et al.Coalitional games for distributed collaborative spectrum sensing in cognitive radio networks[C]//Joint Conference of the IEEE Computer and Comunications Societics，2009：2114-2122.

[13]RAHWAN T，MICHALAK T P，WOOLDRIDGE M，et al.Coalition structure generation：a survey[J].Artificial Intelligence，2015，229：139-174.

[14]李勇.多Agent系統(tǒng)聯(lián)盟及任務分配的研究[D].合肥：合肥工業(yè)大學，2008.LI Yong.Research on coalition and task allocation in multi-agent system[D].Hefei：Hefei University of Technology，2008.

[15]周瑜.基于聯(lián)盟形成博弈的任務分配方法研究[D].揚州：揚州大學，2019.ZHOU Yu.Research on task allocation method based on coalition formation game[D].Yangzhou：Yangzhou University，2019.

[16]ZHOU Y，ZHANG Y，LI B.Coalition formation game for task allocation in the social network[C]//2018 IEEE 22nd International Conference on Computer Supported Cooperative Work in Design（CSCWD）.IEEE，2018：133-139.

[17]WANG L，WANG Z L.Ant colony optimization for task allocation in multi-agent system[J].China Communications，2013，10（3）：125-132.

[18]IIJIMA N，SUGIYAMA A，HAYANO M，et al.Adaptive task allocation based on social utility and individual preference in distributed environments[J].Procedia Computer Science，2017，112：91-98.

[19]SHEHORY O，KRAUS S.Methods for task allocation via agent coalition formation[J].Artificial Intelligence，1998，101（1）：165-200.

[20]ZHU J，SONG H，JIANG Y，et al.On complex tasks scheduling scheme in cloud market based on coalition formation[J].Computers & Electrical Engineering，2017，58：465-476.

[21]YIN X，LI B，LI D，et al.Task allocation via coalition formation in agent networks[J].Journal of Intelligent & Fuzzy Systems，2016，30（1）：197-210.

[22]SUN C，WANG X，QIU H，et al.Game theoretic self-organization in multi-satellite distributed task allocation[J].Aerospace Science and Technology，2021，112：106650.

[23]MARTIN H，DANIEL V，WAGNER L.Dynamics in matching and coalition formation games with structural constraints[J].Artificial Intelligence，2018，262：222-247.

[24]胡軍，張振興，鄒立.面向社交網(wǎng)絡基于協(xié)作度協(xié)商的聯(lián)盟形成機制[J].湖南大學學報（自然科學版），2015，42（2）：100-108.HU Jun，ZHANG Zhenxing，ZOU Li.Social network oriented collaboration degree based negotiation coalition formation mechanism[J].Journal of Hunan University（Nature Science），2015，42（2）：100-108.

[25]MAHDIRAJI H A，RAZGHANDI E，HATAMI-MARBINI A.Overlapping coalition formation in game theory：a state-of-the-art review[J].Expert Systems with Applications，2021，174：114752.

[26]MYERSON R B.Graphs and cooperation in games[J].Mathematics of Operations Research，1977，2（3）：225-229.

[27]王先甲，劉佳.具有外部性的合作博弈問題中的穩(wěn)定的聯(lián)盟結構[J].系統(tǒng)工程理論與實踐，2018，38（5）：1173-1182.WANG Xianjia，LIU Jia.Stable coalition structure in coooperative game with externalities[J].Systems Engineering Theory & Practice，2018，38（5）：1173-1182.