時空約束下資源受限的多智能體柔性重疊組織建模

摘 要：在資源受限的多智能體系統(tǒng)中，智能體通常需要與其他智能體協(xié)作并獲取資源，從而實(shí)現(xiàn)增加總體收益或完成復(fù)雜任務(wù)的目的。而開放系統(tǒng)中資源需求和供應(yīng)的不確定性導(dǎo)致了信息不對稱和競爭加劇，從而增加了資源分配的復(fù)雜性和協(xié)作成本。因此，構(gòu)建時空約束下的柔性重疊組織框架。該框架一方面融合時空約束提升信息的時效性及資源分配的合理性，另一方面支持柔性重疊組織使智能體能夠同時訂閱多個資源，進(jìn)一步緩解資源受限的問題。此外，提出了時空約束下的資源選擇算法解決資源的不均衡使用；同時提出了協(xié)作策略生成算法來降低資源競爭。最后，在開放的多智能體系統(tǒng)仿真環(huán)境中對所提方法進(jìn)行評估，在不同資源需求、智能體流動性的情況下對任務(wù)完成數(shù)量、任務(wù)成功率和資源利用率進(jìn)行分析。實(shí)驗(yàn)結(jié)果表明，使用時空約束下的柔性重疊組織框架可以有效緩解資源受限問題并提高任務(wù)成功率和資源利用率。

關(guān)鍵詞： 多智能體系統(tǒng)； 資源受限； 時空約束； 柔性重疊

中圖分類號： TP311.5 文獻(xiàn)標(biāo)志碼： A 文章編號： 1001-3695（2025）02-030-0539-06

doi：10.19734/j.issn.1001-3695.2024.06.0283

Modeling of flexible overlapping organization in resource-constrained

multi-agent systems under spatio-temporal constraints

Guo Kao， Liu Wei^’， Wang Hongwei， Xu Fan， Wang Zihao

（School of Computer Science amp; Engineering， Wuhan Institute of Technology， Wuhan 430205， China）

Abstract：In resource-constrained multi-agent systems，agents often need to collaborate with other agents and acquire resources in order to increase overall utility or perform complex tasks.In open systems，uncertainty in resource demand and supply leads to information asymmetry and increased competition，which increases the complexity of resource allocation and the costs of cooperation.Therefore，this paper constructed a flexible framework of overlapping organisation under spatio-temporal constraints.This framework integrated spatiotemporal constraints to enhance the timeliness of information and the rationality of resource allocation，while supporting flexible overlapping organisation to allow agents to subscribe to multiple resources simultaneously，further alleviating resource constraints.In addition，it proposed a spatio-temporal constraint-based resource selection algorithm to address the problem of uneven resource utilization，and introduced a collaborative strategy generation algorithm to reduce resource competition.Finally，the proposed method was evaluated in an open multi-agent system simulation environment by analysing the task completion quantity，task success rate and resource utilisation under different resource demand and agent mobility scenarios.Experimental results show that using the flexible overlapping organization framework under spatio-temporal constraints can effectively alleviate resource constraints and improve task success rates and resource utilization.

Key words：multi-agent system; resource constraint; spatio-temporal constraint; flexible overlapping

0 引言

在多智能體系統(tǒng)中，智能體在無法預(yù)測其他智能體策略的情況下共享局部知識使用受限資源完成自身目標(biāo)^［1］，智能體會因?yàn)閺?fù)雜任務(wù)無法完成或?yàn)榱俗畲蠡傮w利益選擇和其他智能體進(jìn)行協(xié)商合作^{［2，3］}。智能體往往和所需要使用的資源間存在時空約束。時間約束為智能體獲得資源需要等待的時間，空間約束為智能體與所需使用資源存在一定物理空間距離，本文將其視為智能體到達(dá)資源所需的時間。面向時空數(shù)據(jù)的多智能體系統(tǒng)（spatio-temporal multi-agent systems）是一種集成了多智能體系統(tǒng)和時空數(shù)據(jù)分析技術(shù)的多智能體系統(tǒng)。在這種系統(tǒng)中，智能體需要完成的任務(wù)或使用的資源在空間中分布，并且這些數(shù)據(jù)會隨時間變化，數(shù)據(jù)的時間和空間維度往往關(guān)聯(lián)且有著復(fù)雜的關(guān)系。

電動汽車共享充電樁系統(tǒng)是一種典型的ST-MAS，在該系統(tǒng)中電動汽車作為智能體在開放和視野有限的環(huán)境中完成自己的目標(biāo)。電動汽車會根據(jù)資源可用性、距離和排隊(duì)時間等因素動態(tài)調(diào)整和選擇最合適的充電站，并與該地區(qū)的其他電動汽車協(xié)同完成任務(wù)。電動汽車會受到充電資源使用在時間或者空間維度的限制和約束。在這個場景中，空間范圍內(nèi)的電動汽車形成共享資源的組織，能夠最大化資源的利用率和個體目標(biāo)的完成數(shù)量。

一個成功的面向資源的協(xié)作組織需要在時間和空間維度上對資源需求和供應(yīng)的精確把握和一個能夠?qū)崟r應(yīng)對變化的資源分配策略。智能體對資源的使用應(yīng)該是重疊的，這意味著智能體能夠同時訂閱多個資源，一個資源可以供多個智能體同時/不同時使用。例如在拼車案例中，不同目標(biāo)的乘客可能會有重疊的路段，他們使用同一出行工具^［4］。需要一種模型或方法來監(jiān)測智能體與資源之間的時空關(guān)系，為智能體提供一個好的資源選擇策略。為了應(yīng)對資源或任務(wù)需求的變化，需要構(gòu)建一個柔性組織模型來允許智能體的隨時加入或離開?，F(xiàn)有多智能體資源分配文章^［5～7］考慮到響應(yīng)時間和應(yīng)急資源成本、高度動態(tài)環(huán)境導(dǎo)致資源不可用以及資源分配是一系列智能體本地協(xié)商的結(jié)果，但是并沒有考慮智能體與資源間的時空約束關(guān)系。

在多智能體協(xié)作領(lǐng)域中，聯(lián)盟（coalition）^［8］、團(tuán)隊(duì)（team）^［9］、協(xié)作社區(qū)（community）^［10］等通過構(gòu)建協(xié)作組織來獲取最大化個人效用或完成復(fù)雜任務(wù)，很少考慮到智能體隨時加入或離開協(xié)作組織的問題。多智能體強(qiáng)化學(xué)習(xí)技術(shù)在游戲中展現(xiàn)出色的性能，然而在現(xiàn)實(shí)環(huán)境中，由于受到資源使用限制和環(huán)境不確定性的影響，智能體難以有效協(xié)調(diào)資源的利用和通過構(gòu)建協(xié)作組織來最大化整體利益^［11］。盡管強(qiáng)化學(xué)習(xí)通過環(huán)境的轉(zhuǎn)變不斷學(xué)習(xí)優(yōu)化策略，但其環(huán)境轉(zhuǎn)移函數(shù)保持不變，這導(dǎo)致學(xué)習(xí)到的策略僅適用于相同的環(huán)境，無法在真正開放和未知的環(huán)境中應(yīng)用。

面向資源分配的自組織方法能夠動態(tài)調(diào)整資源分配策略并適應(yīng)變化，提高系統(tǒng)的可擴(kuò)展性和靈活性。目前面向資源分配的自組織方法存在許多問題：a）信息不對稱和資源供應(yīng)需求的變化導(dǎo)致資源分配決策的不準(zhǔn)確性和不公平性；b）時間、能源、帶寬等有限資源產(chǎn)生競爭與沖突影響智能體任務(wù)的完成情況及系統(tǒng)的整體收益；c）不同智能體之間不同的目標(biāo)或意圖產(chǎn)生的目標(biāo)沖突導(dǎo)致智能體協(xié)同困難。

為了解決上述問題，本文提出了一個時空約束的多智能體柔性重疊組織框架。采用訂閱/發(fā)布者模式構(gòu)建柔性重疊組織模型，使智能體能夠同時訂閱/退訂多個資源，從而降低有限資源使用過載的概率。融合時空約束建模預(yù)測資源分配情況，提出一種時空約束下的資源選擇算法解決資源需求和供應(yīng)的不確定性，并為智能體設(shè)計(jì)協(xié)作算法減少目標(biāo)沖突，提高任務(wù)成功率。最后，對該模型進(jìn)行了評估，將其與作為基線的協(xié)作和訂閱單一資源方法進(jìn)行比較。評估場景包括了6個資源社區(qū)、初始的100個智能體以及隨時間增長后續(xù)加入系統(tǒng)的智能體。完成任務(wù)的智能體被視為離開系統(tǒng)，并且智能體以不可預(yù)測的方式加入或離開系統(tǒng)。

1 相關(guān)工作

多智能體自組織是指在多個智能體相互作用完成目標(biāo)或任務(wù)的過程中，智能體自發(fā)地形成有序的結(jié)構(gòu)或者協(xié)作關(guān)系的現(xiàn)象，其中系統(tǒng)能夠在其執(zhí)行時間內(nèi)在沒有明確命令的情況下改變其組織^［12］。自組織基于自治智能體及其局部交互，并且全局目標(biāo)或者行為不能預(yù)先指定或預(yù)測^［13］。Macarthur等人^［14］提出了一種開放動態(tài)多智能體系統(tǒng)中的分布式隨時任務(wù)分配算法。文獻(xiàn)［15］提出了一種基于群體智能的動態(tài)多智能體系統(tǒng)任務(wù)分配的聚類算法。他們的算法都具有自組織性，但是未考慮任務(wù)分配過程中智能體之間的協(xié)作關(guān)系。文獻(xiàn)［16］指出協(xié)作任務(wù)分配是無人系統(tǒng)實(shí)現(xiàn)完全自主控制的關(guān)鍵功能。文獻(xiàn)［17］使用兩種智能體合作以找到問題的最佳解決方案，從而降低通信成本和變量數(shù)量，文獻(xiàn)［18］提出一種基于協(xié)商協(xié)議的多智能體合作方法，以緩解自主局部決策的資源競爭。文獻(xiàn)［19］提出一種基于概率時間自動機(jī)自適應(yīng)系統(tǒng)運(yùn)行時驗(yàn)證方法解決異構(gòu)多agent之間的復(fù)雜協(xié)作問題。

面向資源分配的多智能體系統(tǒng)旨在解決如何有效地分配和利用資源以實(shí)現(xiàn)特定的總體目標(biāo)和個人目標(biāo)或最大化系統(tǒng)整體性能和收益。這種資源可以是物理資源（如能量、原材料、存儲），也可以是抽象的資源（如計(jì)算資源、網(wǎng)絡(luò)資源）^［20］。系統(tǒng)通常面臨復(fù)雜和不確定的環(huán)境，其資源的可用性、需求和優(yōu)先級可能隨時變化。智能體之間可能存在協(xié)作和競爭關(guān)系，它們需要共享資源并協(xié)調(diào)行動，同時也需要競爭資源以實(shí)現(xiàn)個體的目標(biāo)。智能體之間良好的協(xié)作關(guān)系可以有效提高資源利用率，并且減少競爭沖突造成的不必要損失。同時，智能體通常具有分布式的決策能力，它們需要根據(jù)局部信息和目標(biāo)來制定資源分配策略。

Anders等人^［21］為解決開放系統(tǒng)中的動態(tài)資源分配問題，提出了一種基于信任和合作的算法。許多學(xué)者致力于使用調(diào)度策略、強(qiáng)化學(xué)習(xí)找到最優(yōu)分配策略。文獻(xiàn)［22］提出了一個長期能源約束下的在線聯(lián)合卸載和資源分配框架來保證最終用戶的QoE。王志宏等人^［23］提出了一種結(jié)合仿生學(xué)和多智能體獨(dú)立強(qiáng)化學(xué)習(xí)的多任務(wù)資源分配策略來解決重復(fù)的感知資源以及多任務(wù)間的計(jì)算資源供需不平衡造成的額外計(jì)算與通信開銷。也有學(xué)者通過改進(jìn)多智能體協(xié)作模型提高資源利用率，例如：文獻(xiàn)［4］針對共享資源受限和過載的問題，融入社會推理技術(shù)推斷智能體之間的依賴關(guān)系，以此促進(jìn)智能體協(xié)作并提高資源使用效率。為了進(jìn)一步提高智能體的資源訪問效率，許多學(xué)者考慮資源使用的重疊關(guān)系。例如：Zhang等人^［24］提出了一種基于社區(qū)間重疊和嵌入關(guān)系的資源分配轉(zhuǎn)移（TRA）方法。Qi等人^［25］提出一種考慮資源屬性與任務(wù)執(zhí)行順序的重疊互補(bǔ)關(guān)系的順序重疊聯(lián)盟形成（OCF）博弈來提高任務(wù)平均效用。

為了應(yīng)對高度不確定性和動態(tài)的環(huán)境，目前多數(shù)研究考慮到智能體之間的動態(tài)協(xié)作組織生成。Ramchurn等人^［26］開發(fā)了一種新的方法來評估不確定、動態(tài)和實(shí)時環(huán)境中的人機(jī)協(xié)作。文獻(xiàn)［27］討論了彈性無人機(jī)系統(tǒng)，其有效地定義了系統(tǒng)在正常運(yùn)行中處理中斷的能力。

在大規(guī)模場景下，智能體之間頻繁地進(jìn)行通信和信息交換會導(dǎo)致大量的通信開銷，各個智能體之間的交互和協(xié)作關(guān)系復(fù)雜導(dǎo)致管理困難。大規(guī)模多智能體自組織通常需要進(jìn)行分布式?jīng)Q策，根據(jù)局部信息和目標(biāo)制定決策策略來面對動態(tài)和不確定的環(huán)境。文獻(xiàn)［28］考慮了開放系統(tǒng)中的資源分配問題，但是僅考慮了智能體在某些時候被替換。文獻(xiàn)［29］提出了一種注意力溝通模型為大規(guī)模的多智能體合作帶來了高效和有效的溝通。文獻(xiàn)［30］提出了一種學(xué)習(xí)結(jié)構(gòu)化通信（LSC）的新框架來提高通信效率和全球協(xié)作能力。

當(dāng)前研究對資源分配的調(diào)度策略、強(qiáng)化學(xué)習(xí)算法、協(xié)作策略以及開放和大規(guī)模等問題進(jìn)行分析，并未考慮資源使用的時空約束。與其他研究不同的是，本文融合時空約束來建模和預(yù)測資源的分配情況，設(shè)計(jì)柔性重疊組織緩解資源限制的問題，并通過智能體之間的協(xié)作和自組織來面對資源供應(yīng)和需求的不確定性，從而增加資源的利用率。

2 時空約束下的柔性重疊組織框架

本文提出了一種時空約束下的多智能體柔性重疊組織（spatio-temporal flexible overlapping organization，STFOO）框架，主要包含兩個方面：

a）設(shè)置時空約束。時間約束指智能體排隊(duì)等待資源空閑的時間，而空間約束則是指智能體到達(dá)所需使用資源需要花費(fèi)的時間。時空數(shù)據(jù)通常具有復(fù)雜的關(guān)聯(lián)結(jié)構(gòu)，比如城市中不同區(qū)域之間的交通流量以及各區(qū)域電動汽車充電需求。

b）支持柔性重疊組織。柔性代表著智能體能夠隨時加入或離開資源社區(qū)，而重疊則體現(xiàn)在資源使用上，即智能體通過同時訂閱多個資源實(shí)現(xiàn)對多個資源的重疊使用。

STFOO的優(yōu)點(diǎn)在于解決了在時空約束下資源受限的協(xié)作組織形成問題，允許多個智能體同時訂閱同一資源。當(dāng)某個資源受限時，智能體可以通過資源需求轉(zhuǎn)移來減小資源過載的可能性?；诒疚哪Ｐ停?dāng)多個智能體在同一時間段要使用同一資源時，可通過計(jì)算時空約束對資源使用情況進(jìn)行預(yù)測，便于智能體選擇合適的資源社區(qū)以減少資源等待時間并增加協(xié)作的成功率。智能體確定所需使用的資源社區(qū)后，可與同一資源社區(qū)的其他智能體進(jìn)行協(xié)作。即使在有限資源的情況下，也能實(shí)現(xiàn)更多智能體的個人目標(biāo)，并提高資源的利用率。

STFOO是一個智能體相互作用并使用彼此的信息來協(xié)調(diào)自身行為的分布式框架。如圖1所示，以電動汽車充電樁為例，STFOO最底層為智能體層，用來描述單個智能體的行為，第二層為自組織層，表示智能體組織形式、協(xié)作策略和集體決策。STFOO有四個階段：第一個階段為資源社區(qū)成員更新，智能體通過訂閱或退訂決定加入或離開資源社區(qū)；第二個階段為時空約束下資源選擇，智能體分析自身到訂閱資源的時空約束，并根據(jù)資源未來的空閑情況選擇最合適的資源社區(qū)；第三個階段為協(xié)作策略生成，智能體分析自身目標(biāo)和同一資源社區(qū)的其他智能體目標(biāo)以及資源使用優(yōu)先級構(gòu)建協(xié)作策略；第四個階段為集體決策制定，根據(jù)上一步得出的協(xié)作策略和資源的使用情況制定決策。

2.1 柔性重疊資源社區(qū)

在開放環(huán)境中，智能體頻繁且不可預(yù)測地加入或離開系統(tǒng)，智能體隨時會增加或減少對資源的需求。因此本文構(gòu)建一個柔性重疊的資源使用社區(qū)，即柔性重疊組織，使用訂閱/發(fā)布的設(shè)計(jì)模式來捕獲每個資源的需求，其中資源充當(dāng)發(fā)布者，智能體訂閱它們所需的資源。智能體可以同時訂閱多個資源，從而達(dá)到對資源的重疊使用。這種模式是分布式系統(tǒng)中一個成功的可擴(kuò)展解決方案，并且不會限制智能體進(jìn)出系統(tǒng)的靈活性。

R={r₁，r₂，…，r_n}（1）

r^t_i={Capacity^t_ri，Demand^t_ri，RC^t_ri}（2）

Capacity^t_ri={k，Cspare^t_ri，Ct^t_ri1，Ct^t_ri2，…，Ct^t_rik}（3）

定義1 資源（resource），定義改編自文獻(xiàn)［4］。R是資源合集，r為單一的資源，智能體訂閱同一r形成資源社區(qū)，用三元組r^t_i表示資源r_i在t時間的信息，其中Capacity^t_ri表示資源r_i在t時間的容量，Demand^t_ri表示資源r_i在t時刻的需求量，RC^t_ri為資源社區(qū)，表示在t時間訂閱資源r_i的智能體集合。為了更好表達(dá)資源的容量，將其離散化，k表示資源的總?cè)萘?，Cspare^t_ri為在t時間r_i空閑的單位資源數(shù)量，Ct^t_rij表示第j個離散化單位資源在未來需要使用的時間，Ct^t_rij=0表示單位資源空閑，下標(biāo)k為資源容量數(shù)。

RC^t_ri={A_ri，A^t_δ，Ext（A）}（4）

定義2 資源社區(qū)（resource community）。RC^t_ri表示在t時間訂閱資源r_i的智能體所形成的資源社區(qū)，由三部分組成：A_ri表示訂閱資源r_i的智能體集合，A^t_δ表示在時間t預(yù)定使用資源r_i的智能體集合，Ext（A）為訂閱資源r_i的智能體外部描述的集合。只要智能體訂閱了資源，它們就能在任何時間訪問資源中的信息，包括容量Capacity^t_ri和需求量Demand^t_ri。由于資源容量有限，資源在某個時間的需求量可能大于容量，容易發(fā)生資源過載，為了減少資源過載，智能體會根據(jù)資源使用情況和需求量選擇最合適的訂閱資源。

2.2 具有時空約束的智能體結(jié)構(gòu)模型

系統(tǒng)中智能體被定義為如圖2所示的結(jié)構(gòu)，分為外部描述和內(nèi)部結(jié)構(gòu)。智能體的外部描述是一個數(shù)據(jù)結(jié)構(gòu)，其中存儲著智能體的個人信息，資源社區(qū)中的所有智能體都能訪問。內(nèi)部結(jié)構(gòu)包含智能體的內(nèi)部狀態(tài)、決策單元和計(jì)劃。資源社區(qū)包含資源信息和訂閱資源的智能體外部描述，智能體可以通過訂閱同一資源社區(qū)實(shí)現(xiàn)局部知識共享。智能體通過與同一資源社區(qū)的其他智能體協(xié)同決策使用系統(tǒng)資源，從而改變外界環(huán)境，即改變資源的使用狀態(tài)。當(dāng)有智能體完成任務(wù)后，同一資源社區(qū)的其他智能體感知是否存在空閑資源，根據(jù)資源使用的變化情況重新調(diào)整計(jì)劃。

使用這種結(jié)構(gòu)，智能體能共享它們的一些信息，并存儲從資源社區(qū)中其他智能體獲得的數(shù)據(jù)。這種數(shù)據(jù)結(jié)構(gòu)使得智能體的內(nèi)部結(jié)構(gòu)和體系結(jié)構(gòu)保持分離。

Ext（a_i）={G_ai，δ^t_ai，P_ai，TRC_ai，SP_ai}（5）

G_ai={UseTime_ai，LastPoint_ai}（6）

P_ai={r_ij，Startpoint_ai，Endpoint_ai}（7）

TRC_ai={R_ai，TRC^r_j1ai，TRC^r_j2ai，…，TRC^r_jnai}（8）

定義3 外部描述（external description），定義改編自文獻(xiàn)［31］。Ext（a_i）為智能體a_i的外部描述，其中G_ai表示智能體a_i想要實(shí)現(xiàn)的個人目標(biāo)，δ^t_ai表示智能體a_i在時間t采取的動作，P_ai表示智能體a_i為實(shí)現(xiàn)目標(biāo)而定義的一系列策略，TRC_ai包含智能體a_i所訂閱資源集合及其空間約束，SP_ai為智能體a_i使用資源的優(yōu)先級。

G_ai由兩個部分組成，UseTime_ai為智能體a_i為完成目標(biāo)需要使用資源的時長，LastPoint_ai為智能體a_i完成任務(wù)的截止時間。P_ai主要是描述智能體a_i在某個時間段使用某個資源。r_ij表示資源r_i的第j個離散化單位資源。Startpoint_ai表示智能體a_i使用資源的起始時間，Endpoint_ai表示智能體a_i使用資源的終止時間。

智能體完成目標(biāo)需要一定的資源，考慮到智能體對資源的使用存在時間和空間上的約束。時間約束為智能體排隊(duì)等待資源空閑的時間，不與具體的某個智能體的屬性綁定，通過定義1中的Ct^t_rij即可獲取資源r_i的第j個單位資源在時間t的等待時間?？臻g約束為智能體與所需使用資源有一定的物理空間距離，本文將其表示為到達(dá)資源所需時間，這與智能體所在地理位置有關(guān)?？臻g約束如定義3中的TRC_ai所示，智能體對每個訂閱資源都存在空間約束，TRC_ai包含智能體a_i所訂閱資源集合及其空間約束，即智能體a_i到達(dá)所訂閱的資源所在地所需時間的集合。

算法1資源社區(qū)更新，當(dāng)智能體加入或離開資源社區(qū)時，智能體就會獲得或失去資源社區(qū)的訪問權(quán)。首先需要更新自身外部描述中的空間約束信息TRC_ai（第3行），然后更新資源社區(qū)中訂閱資源的集合A_ri以及訂閱資源r_i的智能體的外部描述的集合Ext（A）（第4行）。

算法1 資源社區(qū)更新

輸入：初始智能體訂閱資源社區(qū)RC^t_ri。

輸出：更新后智能體訂閱資源社區(qū)RC^t_ri。

1 procedure resource community-update

2

if a_i join or leave then

3 update （TRC_ai） //更新智能體空間約束信息

4 update （RC^t_ri） //更新資源社區(qū)

5

end if

6 end procedure

2.3 時空約束下資源選擇算法

智能體通過分析每個訂閱資源的時空約束來預(yù)測未來資源的空閑情況，以便選擇當(dāng)前最適合的資源社區(qū)。智能體通過更新其外部描述來調(diào)整其對資源的依賴關(guān)系。同一資源社區(qū)中的智能體能夠相互訪問對方的外部描述。一旦智能體確定要使用某個資源，通過識別資源社區(qū)中其他智能體的信息，便可與同一資源社區(qū)的其他智能體進(jìn)行協(xié)作。

算法2時空約束下的資源選擇。首先，對于智能體a_i訂閱的所有資源，計(jì)算其未來資源需求程度（第3、4行）。根據(jù)當(dāng)前的時間約束限制以及a_i與其空間約束，計(jì)算未來時刻（a_i到達(dá)資源所在地時）的空閑資源數(shù)量k（第3行）。然后用k除以資源候選智能體集合A^t_δ中資源使用時長的總和（第4行），以此來反映資源需求程度。然后，a_i選擇資源需求程度最小的資源社區(qū)，并將a_i加入資源候選智能體集合A^t_δ（第6、7行）。最后，a_i退訂其他資源社區(qū)并更新空間約束，其他資源社區(qū)將a_i從訂閱集合和外部描述集合中移除，空間約束中只保留所選資源（第8～11行），此時智能體便可向資源移動。

算法2 時空約束下的資源選擇

輸入：智能體a_i空間約束TRC_ai及其訂閱資源社區(qū)RC^t_ri。

輸出：資源候選智能體集合A^t_δ。

1 procedure resource-selected

2 for all r_i∈R_ai do

3

k=Ct^t_rim-TRC^r_iaj //計(jì)算未來空閑資源數(shù)量k

4

DoR=k/∑a_i∈AtδUseTime_ai //計(jì)算未來資源需求程度DoR

5 end for

6 a_i選擇min（DoR）的資源社區(qū)r_min

7 更新資源社區(qū)r_min的A^t_δ=A^t_δ+a_i

8 for all r_i∈R_ai-r_min do

9

RC^t_ri=RC^t_ri-a_i //退訂資源社區(qū)

10 end for

11 update （TRC_ai） //更新空間約束

12 return A^t_δ

2.4 優(yōu)先級評估和協(xié)作策略生成算法

當(dāng)智能體到達(dá)資源所在地后，若存在空閑資源，智能體可直接使用資源，若不存在空閑資源，智能體與同一資源社區(qū)等待資源空閑的其他智能體協(xié)商使用資源。因?yàn)榭臻g約束導(dǎo)致智能體在達(dá)到資源所在地之前無法使用資源，智能體的協(xié)作對象為訂閱資源社區(qū)中候選智能體集合A^t_δ中空間約束為零的其他智能體。智能體通過訪問資源社區(qū)獲取其他智能體的外部描述信息，從而獲取其目標(biāo)信息，再根據(jù)目標(biāo)信息制定資源使用策略。

算法3協(xié)作策略生成。首先，對資源所在地的候選智能體按優(yōu)先級進(jìn)行排序，優(yōu)先級取決于智能體G_ai中的LastPoint_ai和UseTime_ai，一般認(rèn)為智能體的目標(biāo)截止日期越小，目標(biāo)的優(yōu)先級越高，當(dāng)截止日期相同時，任務(wù)需要使用資源時間越長能貢獻(xiàn)出來的時間就越短，智能體傾向協(xié)作的可能性就越?。ǖ?～5行）。然后，智能體等待資源空閑，在等待途中若存在新加入的智能體，可通過資源社區(qū)中的外部描述向優(yōu)先級比自己低的智能體申請先使用資源，被申請智能體會判斷退讓資源是否會影響自身目標(biāo)完成來決定是否同意申請（第6～11行）。當(dāng)存在空閑資源時，優(yōu)先級最高的智能體集開始使用資源并更新自身策略P_Aj和資源容量情況Capacity^t_ri（第12、13行）。

算法3 協(xié)作策略生成

輸入：資源社區(qū)RC^t_ri。

輸出：智能體的策略P_Aj，資源社區(qū)RC^t_ri。

1 procedure collaboration-formulation

2 for all a_i∈A^t_δ and TRC^r_ai=0 do //按優(yōu)先級排序

3

按LastPoint_ai從小到大排序

4

如果LastPoint_ai相同，按UseTime_ai從大到小排序

5 end for

6 while Cspare^t_ri=0 do

7

等待資源空閑

8

if 新的a_j到達(dá)資源社區(qū)RC^t_ri then

9 a_j向A^t_δ中優(yōu)先級較低的智能體申請優(yōu)先使用資源

10 end if

11 end while

12 A^t_δ中優(yōu)先級最高的智能體集A_j開始使用資源

13 update （P_Aj） and （Capacity^t_ri） //更新策略和資源容量情況

14 return P_Aj，RC^t_ri

3 實(shí)驗(yàn)過程及分析

電動汽車共享充電樁系統(tǒng)面臨資源供應(yīng)和需求的不確定性挑戰(zhàn)。由于電動汽車與不同充電樁的距離各異，每個充電樁的等待時間也不同，用戶必須根據(jù)時空約束來選擇合適的充電樁。系統(tǒng)利用智能算法實(shí)時預(yù)測充電需求并優(yōu)化資源分配，使電動汽車能夠在最短時間內(nèi)找到并使用最優(yōu)的充電樁。這不僅減少了等待時間和行駛距離，還提升了充電樁的利用效率和整體用戶體驗(yàn)。本文實(shí)驗(yàn)場景基于上述場景，在該系統(tǒng)中電動汽車作為智能體需要使用充電樁資源完成充電目標(biāo)。目標(biāo)的完成情況受電動汽車與充電樁的距離、資源的排隊(duì)等待時間等因素影響?？臻g范圍內(nèi)的電動汽車形成共享資源的組織，能夠最大化資源的利用率和個體目標(biāo)的完成數(shù)量。

3.1 參數(shù)設(shè)置

本文采用GAMA作為仿真模擬器，該平臺具備原生GIS和集成數(shù)據(jù)庫管理功能，提供了多仿真、多層次、協(xié)同的開放環(huán)境建模支持。借助當(dāng)前基于智能體的模擬概念，本文在開放系統(tǒng)中構(gòu)建了柔性重疊組織模型，以實(shí)現(xiàn)所提出的多智能體協(xié)作算法。該模型允許智能體進(jìn)行交互，達(dá)成協(xié)作完成目標(biāo)。智能體可以同時訂閱多個資源，隨時加入或離開系統(tǒng)。STFOO的評估指標(biāo)為

a）智能體個體目標(biāo)完成情況。智能體使用共享資源完成其個體目標(biāo)的數(shù)量。該指標(biāo)主要用于追蹤已完成目標(biāo)（任務(wù)）的智能體總數(shù)。

b）任務(wù)成功率。該度量反映成功完成任務(wù)的比率。

c）各資源的利用率。利用率指各資源被使用的時長與總時長的比值。

智能體規(guī)模和初始資源社區(qū)設(shè)置：所有實(shí)驗(yàn)均基于一個開放的多智能體系統(tǒng)進(jìn)行。初始系統(tǒng)包含6個資源社區(qū)和100個智能體。智能體以隨機(jī)方式訂閱周圍的資源社區(qū)。鑒于開放環(huán)境下智能體可能隨時加入或離開系統(tǒng)，本文假設(shè)在一定時間間隔內(nèi)會出現(xiàn)一批新的智能體需要利用資源。它們對資源社區(qū)的訂閱也是隨機(jī)的。

資源設(shè)置：資源可分割且容量固定。每個時間步，每個智能體只能使用一個單位資源。資源需求密度描述了資源利用情況。當(dāng)資源容量足夠供應(yīng)所有訂閱的智能體使用時，資源需求密度為稀疏；當(dāng)資源容量足夠供應(yīng)80%訂閱的智能體使用時，資源需求密度為稠密。為增加資源容量密度，可通過增加智能體加入系統(tǒng)。

體的流動性：普遍情況下，智能體在資源社區(qū)停留的時間超過其所需資源的時間。通過減少智能體在資源社區(qū)停留的時間，可以增加其流動性。智能體的流動性增加表明其愿意合作的可能性降低，因?yàn)楹献骺赡軐?dǎo)致智能體在資源社區(qū)停留時間增加。

由于本文方法專注于解決智能體高度動態(tài)性以及資源供應(yīng)和需求的不確定性等問題，對智能體和資源的建模不同于其他多智能體資源分配的文章，所以難以通過算法對比來驗(yàn)證本文方法的有效性。為了對STFOO及其算法進(jìn)行有效評估，根據(jù)其特性設(shè)置了三種對比方法。

a）重疊非合作方法（overlap-non-competitive，ONC），其特點(diǎn)是智能體對資源的使用存在重疊，但備選智能體并不采用協(xié)作策略，而是根據(jù)個人需求獨(dú)立使用資源。

b）訂閱單一資源社區(qū)的協(xié)作方法（single-competitive，SC），智能體對資源的使用不重疊，每個智能體僅能訂閱單一資源進(jìn)行使用，備選智能體采用協(xié)作策略共同使用資源。

c）訂閱單一資源社區(qū)的非合作方法（single-non-competitive，SNC），智能體對資源的使用不重疊，每個智能體僅能訂閱單一資源進(jìn)行使用，備選智能體基于貪婪的策略使用資源，不與其他智能體協(xié)作。

3.2 智能體個體目標(biāo)完成情況

圖3～6展示了不同資源需求和智能體流動性情況下任務(wù)完成數(shù)量隨時間變化的曲線。STFOO表現(xiàn)明顯優(yōu)于其他三種方法。當(dāng)智能體訂閱的資源社區(qū)需求量超過容量時，STFOO使得智能體將資源需求轉(zhuǎn)移到其他訂閱的資源社區(qū)，以增加資源的利用率，從而緩解資源需求不平衡的問題。當(dāng)智能體訂閱的資源社區(qū)都需要排隊(duì)等待時，通過協(xié)作策略減少任務(wù)失敗率，進(jìn)而提高總體收益。SNC中智能體訂閱單一資源且不采用協(xié)作策略，結(jié)果幾乎總是最差的。

值得注意的是，在資源需求稠密時，即需求大于供應(yīng)時，柔性重疊組織能夠有效緩解這種情況。正如圖3、4所示，此時ONC優(yōu)于SC。圖4中SC比圖3的效果好，當(dāng)智能體流動性減小時，智能體更傾向于停留在資源社區(qū)內(nèi)，從而增加協(xié)作產(chǎn)生收益的機(jī)會。在資源需求稀疏時，資源的需求和供應(yīng)相當(dāng)，因此重疊組織的作用變得不太明顯。盡管如此，智能體協(xié)作策略仍能在一定程度上提高任務(wù)完成數(shù)量。在圖5、6中，SC優(yōu)于ONC，尤其在流動性較低時更為顯著。STFOO綜合了兩種方法的優(yōu)勢，在絕大多數(shù)情況下都表現(xiàn)出更好的性能。

3.3 智能體任務(wù)成功率

圖7為某次結(jié)果的任務(wù)成功率，表1為十次結(jié)果的平均任務(wù)成功率。STFOO依據(jù)其重疊組織和協(xié)作策略的特性，任務(wù)成功率明顯優(yōu)于其他三種方法，SNC未使用重疊組織且不采取協(xié)作策略，任務(wù)成功率最低。在絕大多數(shù)情況下，ONC的任務(wù)成功率優(yōu)于SC，因?yàn)槠涫褂弥丿B組織充分利用資源，從而提高了任務(wù)成功率。然而，在資源需求稠密且智能體流動性低的情況下，由于資源緊缺和智能體停留在資源社區(qū)的時間較長，促使智能體之間通過協(xié)作策略能夠有效緩解資源緊缺，從而提高任務(wù)成功率。在這種情況下，SC優(yōu)于ONC。

3.4 資源利用率

圖8為某次結(jié)果的資源利用率，表2為十次結(jié)果的平均資源利用率。STFOO相較于其他三種方法，資源利用率明顯提升，SNC未使用重疊組織且不采取協(xié)作策略，資源利用率最低。當(dāng)資源受限時，智能體通過資源依賴轉(zhuǎn)移，減少了排隊(duì)等待時間，增加了對空閑資源的利用。采用柔性重疊組織有效地提高了資源利用率，STFOO和ONC在所有情況下的資源利用均優(yōu)于SC。由于其協(xié)作策略進(jìn)一步提高了資源利用率，STFOO的效果優(yōu)于ONC。

4 結(jié)束語

針對開放系統(tǒng)中資源供應(yīng)和需求的不確定性問題，本文提出了一種全新的重疊組織，旨在提高智能體的任務(wù)成功率和資源利用率。該方法通過對時空約束進(jìn)行建模來預(yù)測資源的使用情況，并采用柔性重疊組織對開放環(huán)境進(jìn)行建模，使智能體能夠同時訂閱多個資源社區(qū)。通過對資源社區(qū)的訂閱或退訂來捕獲智能體加入或離開系統(tǒng)的情況，以解決資源受限的問題。為了減少資源過載，智能體會根據(jù)資源使用情況和需求量選擇最合適的訂閱資源。此外，智能體能通過同一資源社區(qū)其他智能體外部描述與其建立協(xié)作關(guān)系，以此來提高資源利用率和任務(wù)成功率。

隨著研究的不斷深入，重疊組織中仍存在許多待解決的問題。例如：是否可以預(yù)測智能體的組織結(jié)構(gòu)；當(dāng)資源社區(qū)發(fā)生故障時，智能體的資源選擇和協(xié)作策略將受到何種影響，應(yīng)該如何解決。這些問題都是開放多智能體系統(tǒng)中值得深入研究的問題，也是未來的關(guān)注重點(diǎn)。

參考文獻(xiàn)：

［1］Fu Fang，Zhou Hong.A combined multi-agent system for distributed multi-project scheduling problems［J］.Applied Soft Computing，2021，107：107402.

［2］Torreno A，Onaindia E，Komenda A，et al.Cooperative multi-agent planning：a survey［J］.ACM Computing Surveys（CSUR），2017，50（6）：1-32.

［3］Canese L，Cardarilli G C，Di Nunzio L，et al.Multi-agent reinforcement learning：a review of challenges and applications［J］.Applied Sciences，2021，11（11）：4948.

［4］Golpayegani F，Dusparic I，Clarke S.Using social dependence to enable neighbourly behaviour in open multi-agent systems［J］.ACM Trans on Intelligent Systems and Technology，2019，10（3）：1-31.

［5］Su Zhaopin，Zhang Guofu，Liu Yang，et al.Multiple emergency resource allocation for concurrent incidents in natural disasters［J］.International Journal of Disaster Risk Reduction，2016，17：199-212.

［6］Briola D，Mascardi V，Martelli M，et al.Dynamic resource allocation in a MAS：a case study from the industry［C］//Proc of the 10th Workshop “From Objects to Agents”.［S.l.］：Seneca Edizioni Torino，2009：125-133.

［7］Nair A S，Hossen T，Campion M，et al.Multi-agent systems for resource allocation and scheduling in a smart grid［J］.Technology and Economics of Smart Grids and Sustainable Energy，2018，3：article No.15.

［8］Ray D，Vohra R.Coalition formation［J］.Handbook of Game Theory with Economic Applications，2015，4：239-326.

［9］Wi H，Oh S，Mun J，et al.A team formation model based on knowledge and collaboration［J］.Expert Systems with Applications，2009，36（5）：9121-9134.

［10］Iniguez G，Kertész J，Kaski K K，et al.Opinion and community formation in coevolving networks［J］.Physical Review E，2009，80（6）：066119.

［11］Dulac-Arnold G，Levine N，Mankowitz D J，et al.Challenges of real-world reinforcement learning：definitions，benchmarks and analysis［J］.Machine Learning，2021，110（9）：2419-2468.

［12］Serugendo G D M，Gleizes M P，Karageorgos A.Self-organization in multi-agent systems［J］.The Knowledge Engineering Review，2005，20（2）：165-189.

［13］Gorodetskii V I.Self-organization and multiagent systems：I.models of multiagent self-organization［J］.Journal of Computer and Systems Sciences International，2012，51：256-281.

［14］Macarthur K，Stranders R，Ramchurn S，et al.A distributed anytime algorithm for dynamic task allocation in multi-agent systems［C］//Proc of AAAI Conference on Artificial Intelligence.Palo Alto，CA：AAAI Press，2011：701-706.

［15］Dos Santos D S，Bazzan A L C.Distributed clustering for group formation and task allocation in multiagent systems：a swarm intelligence approach［J］.Applied Soft Computing，2012，12（8）：2123-2131.

［16］Zhang Jun，Xing Jiahao.Cooperative task assignment of multi-UAV system［J］.Chinese Journal of Aeronautics，2020，33（11）：2825-2827.

［17］Li Kaixuan，Liu Qingshan，Yang Shaofu，et al.Cooperative optimization of dual multiagent system for optimal resource allocation［J］.IEEE Trans on Systems，Man，and Cybernetics：Systems，2018，50（11）：4676-4687.

［18］Li Feifei，Xu Zhe，Li Haitao.A multi-agent based cooperative approach to decentralized multi-project scheduling and resource allocation［J］.Computers amp; Industrial Engineering，2021，151：106961.

［19］穆勇安，劉瑋，高勝，等.基于概率時間自動機(jī)的異構(gòu)多agent自適應(yīng)運(yùn)行時驗(yàn)證［J］.計(jì)算機(jī)應(yīng)用研究，2023，40（12）：3728-3735.（Mu Yongan，Liu Wei，Gao Sheng，et al.Runtime verification of hetero-geneous multi-agent self-adaptive based on probabilistic timed auto-mata［J］.Application Research of Computers，2023，40（12）：3728-3735.）

［20］Afrin M，Jin J，Rahman A，et al.Resource allocation and service provisioning in multi-agent cloud robotics：a comprehensive survey［J］.IEEE Communications Surveys amp; Tutorials，2021，23（2）：842-870.

［21］Anders G，Stegh?fer J P，Siefert F，et al.A trust-and cooperation-based solution of a dynamic resource allocation problem［C］//Proc of the 7th International Conference on Self-Adaptive and Self-Organizing Systems.Piscataway，NJ：IEEE Press，2013：1-10.

［22］Jiang Hongbo，Dai Xingxia，Xiao Zhu，et al.Joint task offloading and resource allocation for energy-constrained mobile edge computing［J］.IEEE Trans on Mobile Computing，2023，22（7）：4000-4015.

［23］王志宏，冷甦鵬，熊凱.面向無人機(jī)集群協(xié)同感知的多智能體資源分配策略［J］.物聯(lián)網(wǎng)學(xué)報，2023，7（1）：18-26.（Wang Zhihong，Leng Supeng，Xiong Kai.Multi-agent resource allocation strategy for UAV swarm-based cooperative sensing［J］.Chinese Journal on Internet of Things，2023，7（1）：18-26.）

［24］Zhang Jinyu，F(xiàn)eng Kexiang，Ge Xinyu，et al.Transfer of resource allocation between overlapping and embedded communities in multiagent social networks［J］.Knowledge-Based Systems，2021，226：107081.

［25］Qi Nan，Huang Zanqi，Zhou Fuhui，et al.A task-driven sequential overlapping coalition formation game for resource allocation in heterogeneous UAV networks［J］.IEEE Trans on Mobile Computing，2022，22（8）：4439-4455.

［26］Ramchurn S D，Wu Feng，Jiang Wenchao，et al.Human-agent collaboration for disaster response［J］.Autonomous Agents and Multi-Agent Systems，2016，30：82-111.

［27］Phadke A，Medrano F A.Towards resilient UAV swarms—a breakdown of resiliency requirements in UAV swarms［J］.Drones，2022，6（11）：340.

［28］Dorri A，Kanhere S S，Jurdak R.Multi-agent systems：a survey［J］.IEEE Access，2018，6：28573-28593.

［29］Jiang Jiechuan，Lu Zongqing.Learning attentional communication for multi-agent cooperation［C］//Proc of the 32nd International Confe-rence on Neural Information Processing Systems.Red Hook，NY：Curran Associates Inc.，2018：7265-7275.

［30］Sheng Junjie，Wang Xiangfeng，Jin Bo，et al.Learning structured communication for multi-agent reinforcement learning［C］//Proc of International Conference on Autonomous Agents and Multiagent Systems.Richland，SC：International Foundation for Autonomous Agents and Multiagent Systems，2023：436-438.

［31］Lau B P L，Singh A K，Tan T P L.A review on dependence graph in social reasoning mechanism［J］.Artificial Intelligence Review，2015，43：229-242.