分布式約束滿足問題及其在ＭＡＳ任務分配中的應用
2009-01-01 00:00:00劉鴻福陳璟沈林成
計算機應用研究 2009年2期
（國防科學技術大學 機電工程與自動化學院， 長沙 410073）
摘 要：針對多智能體系統(MAS)任務分配問題中多個任務與MAS兩者的分布式特征，將任務分配問題形式化為分布式約束滿足問題(DCSP)進行求解，分別建立了以任務為中心和以agent為中心兩種MAS任務分配模型，基于改進的DCSP分布式并行求解算法，提出了基于DCSP的MAS任務分配問題求解框架。該方法適合求解agent間通信有隨機延遲以及agent間存在多約束的問題，應用實例的求解表明了其實用性與有效性。
關鍵詞：分布式約束滿足問題；多智能體系統；任務分配；并行動態回溯算法；求解框架
中圖分類號：TP391 文獻標志碼：A
文章編號：10013695(2009)02051503
Distributed constraint satisfaction problem and its application to multiagent system task allocation
LIU Hongfu，CHEN Jing，SHEN Lincheng
(College of Mechatronics Automation， National University of Defense Technology， Changsha 410073， China)
Abstract:The problem of multiagent system task allocation was studied considering it to be formed into a distributed constraint satisfaction problem. Both multiple tasks and MAS were distributed， they could build taskcentered and agentcentered two kinds of constraint network construction model. Utilized the improved ConcDB algorithm，provided a framework of multi-agent task allocation which based on DCSP. This approach adapts to solution the problem when agents are in uncertain environment or there are a lot of constraints between agents. Its solving instance indicates that this approach is available.
Key words:DCSP(distributed constraint satisfaction problem);MAS(multiagent system);task allocation;ConcDB(concurrent dynamic backtracking)algorithm;solution frame
0 引言
隨著越來越多問題的形式表現為分布式的特征，在約束滿足問題之上，分布式約束滿足問題(DCSP)被提出。分布式約束滿足問題的變量以及變量間的約束均分布在不同自治agent中；每個agent控制一個或多個變量；一般在agent內和agent間都存在約束關系；各agent通過搜索與通信，試圖對變量賦值并滿足所有這些約束。對于多agent間存在某種約束或者需要協同決策的問題，都可以形式化為分布式約束滿足問題[1]。
多智能體系統(MAS)的任務分配問題是一類具有廣泛應用背景的理論問題，其任務分配機制也是MAS研究的熱點之一[2]。任務分配的方式有集中式和分布式兩種。集中式通常由一個agent(用server表示)掌握當前任務和各agent的信息，然后經過統一的計算與搜索來給各agent分配任務。在分布式方式下，各agent間任務的劃分和分配、共享資源的分配和管理、沖突的協調、行為的一致性等，都是由各agent通過彼此的相互作用和對所處環境的感知，經過相互通信和分布式的計算，各自獨立并行地做出決策。分配方案是各agent部分方案的集合。
針對這種多agent協同任務分配問題，已有的研究方法包括合同網、網絡流量圖法、基于MAS滿意決策的方法等[3]?；诤贤W的任務分配機制要求agent間保持良好的通信連接，在環境不確定時，性能不穩定，并且它們都無法表達agent間本身的約束，如通信連接的約束、資源占用關系的約束等。
MAS任務分配問題的形式本身是分布式的，使得任務分配適合被形式化為分布式約束滿足問題。當agent處于不確定環境時，agent間的通信連接可能出現延遲或者中斷，這將使得agent間協商困難。若采用分布式約束滿足的方法，由于并行求解算法能夠充分地利用可能的通信連接，快速地適應變化，并且算法可收斂[4]，在通信隨機延遲的情況下亦能有效地進行任務分配。對于各agent間存在的相互約束，而這些約束本身就是分布式的。
本文在對分布式約束滿足問題和MAS任務分配問題研究的基礎上，提出一種新的研究思路，即使用分布式約束滿足模型與求解方法，來討論MAS任務分配問題。
1 分布式約束滿足問題
約束滿足問題是由一系列變量、變量相應的值域以及變量之間的約束關系組成，目標是為這些變量找到一組或多組滿足所有約束關系的賦值。傳統的約束滿足求解算法都是集中式地進行搜索、一致性檢查、回溯與約束傳播，這也是由問題定義的形式所決定的。隨著計算機網絡、計算機通信和分布式程序設計技術的發展，越來越多的應用問題處在分布式的計算環境中，分布式人工智能也逐漸成為一個十分重要的研究熱點[5]。比如多傳感器網絡、分布式資源配置、空中交通管制等問題，本質上都可以形式化為一類多智能體系統，各agent控制變量，變量有一個取值范圍，變量之間存在著某種約束，求解的過程就是各agent為所有變量尋求滿足所有約束的取值。在這種情形下，集中式的求解算法存在控制復雜、信息傳遞負擔增加、信息安全無保證、信息延時長、算法魯棒性差等問題。分布式約束滿足結合了約束滿足技術與多agent技術，在求解大規模、多約束、分布式問題時表現出很強的生命力，因此成為人工智能領域的一個研究熱點，研究人員對其求解算法、形式化與應用、信息負載與安全、分布式約束程序設計等方面做了大量的研究工作。
分布式約束滿足問題是變量和變量之間的約束都分布在不同自治agent中的約束滿足問題[6]。分布式約束滿足問題的形式化定義為:n個agent的集合記為A={A1，A2，…，An}，n∈Z+；每個agent Ai擁有變量集合Vi記為Vi={Vi1，Vi2，…，Vipi}；變量值域的集合Di記為Di={Di1，Di2，…，Dipi}，i∈[1，n]，pi∈Z+，pi為agent Ai擁有的變量個數；變量間的約束記為C={C1，C2，…，Cm}，m∈Z+；當Ai知道約束關系Ck時，表示為known(Ck，Ai)。分布式約束滿足問題的解形式化定義為：Ai，Vij，當Vij的賦值是dij∈Dij時，Ck，Ai，known(Ck，Ai)都有Ck被滿足，即對問題中所有變量的賦值滿足所有agent間及agent內的約束。問題的完整解由各agent的部分解組成。
分布式約束滿足問題主要包括兩個方面：將實際問題形式化為DCSP與求解DCSP。DCSP借鑒了多智能體系統的思想，將問題形式化為agent、agent控制的變量及其值域、agent內及agent間的約束，從而構成了一種多智能體系統。問題的求解包括兩個步驟：首先求解agent內的約束，通過agent自己的計算和約束滿足來處理；然后滿足agent間的約束，不僅需要agent計算，更需要agent間的通信來處理。
2 MAS任務分配問題
多agent協同任務分配是多個任務分配給多個agent，一個任務可以由多個agent協同完成，一個agent在其自身能力范圍內也可以同時執行多個任務，是多對多的問題；同時，由于任務、資源、約束具有時間屬性，且還是動態的。多agent的協同體現在三個方面：a)協同求解任務分配。在滿足任務約束和各agent能力約束的前提下，更好地配置資源。b)協同執行任務。在一定的通信機制和約束條件下，多個agent協同地執行多個任務。c)協同任務重分配。如在任務變化、資源缺失、通信延遲的情況下，通過agent的協作快速地進行任務重分配。
MAS任務分配本質上是建立任務空間到agent空間的映射，以能力/資源集合為紐帶，一個任務需要某些資源，而多個agent協同分布式地提供這些資源。圖1(a)為任務空間，刻畫了各決策時刻點上待分配的任務，用Dt=Gt{Tt，CT，t，RT，t}表示。其中：Tt={T1，t，T2，t，…，T|Dt|，t}表示t時刻需要分配的任務集合；CT，t={（Ti，t，Tj，t)|constr Ti，t，Tj，t}表示任務集合中各個任務相互之間的約束關系；RT，t={(r1，1，t，…，r1，l，t)，(r2，1，t，…，r2，m，t)，…，(r|Dt|，1，t，…，r|Dt|，n，t)}表示t時刻各任務所需資源/能力的集合。圖1(b)為能力/資源的集合，表示為Rt={r1，r2，…，rk}，雙邊的映射都需要滿足資源的約束。圖1(c)為多智能體系統，刻畫了執行任務的系統成員及其通信連接，表示為Ot=Ht{At，CA，t，RA，t}。其中：At為agent的集合；CA，t表示agent間的約束；RA，t表示t時刻各agent所具有的資源/能力的集合。
3 基于DCSP的MAS任務分配問題求解框架
3.1 MAS任務分配的分布式約束滿足模型
首先討論如何將問題形式化為分布式約束滿足問題，在MAS任務分配的問題域中，有agent和任務兩個主體，且都具有分布式約束的特征。因此有兩種建模思路：a）以agent為中心，將各agent映射為DCSP中的變量，任務分配圍繞agent進行，以各agent所能提供的能力/資源集合為分配的約束，是否將某任務分配給一個agent為取值；b)以任務為中心，將待分配的任務映射為DCSP中的變量，各個agent以任務為中心進行分配，以任務為中心的方式是在任務間約束基礎上疊加任務分配的約束，這樣有利于任務間的約束首先被滿足。
以agent為中心，將被分配任務的各agent映射為DCSP中的變量，相應地，把任務分配的各種約束映射為變量間的約束。在這種DCSP模型中，agent就是任務分配中的agent，每個agent有一個能力集合，一般地，能力也就是各個agent所具有的資源，只有這個agent具有某個任務所必需的能力時，才有可能將這個任務分配給該agent。如圖2(a)中矩陣所示，一行表示某agent被分配任務的情況，當某任務分配給agent時記為1；否則記為0。Ai所具有的能力集合的約束表示為R(Ai)≥mk=1R(Tk)×rik，系數rik表示Tk是否分配給Ai；一列表示一個任務的分配情況，該任務由哪些agent協同來完成，任務的約束也必須同時得到滿足。A1，A2，A3的能力/資源能夠滿足T4的需要，因此可以協同完成任務，如虛線圈所示。
以任務為中心，將待分配的任務映射成DCSP中的變量，任務的依賴關系映射成變量之間的約束。如果一個變量被賦值，這個值滿足與之相關的所有約束，也就是這個變量代表的任務被分配給了合適的agent，稱這個變量是滿足的。由前述任務分配問題的分析可知，每個任務有一個所需資源的集合，執行該任務的agent必須具備的這些資源。如圖2(b)中矩陣所示，一行表示一個子任務的分配，當agent被分配給某任務時記為1；否則記為0。任務Tk所需能力集合的約束表示為R(Tk)≤ni=1R(Ai)×rik，系數rik表示Tk是否分配給Ai；一列表示一個agent的任務分配情況，即哪些子任務被分配給Ai，Ai必須能夠滿足這些任務的資源需求。A2，A3的能力/資源能夠滿足T3的需要，因此可以協同完成任務T3，如虛線圈所示。
參照分布式約束滿足問題的形式化模型，以agent為中心和以任務為中心兩種模型的對比如表1所示。以agent為中心的模型是在agent間約束的基礎上疊加任務分配的約束，因此更適合對agent間多約束的問題進行建模。以任務為中心的模型則可以首先滿足任務間的約束，適合于任務集多約束的問題。
表1 兩種模型的對比
DCSP模型以agent為中心的模型以任務為中心的模型
agent分配任務的agent待分配的任務
變量待分配的任務分配任務的agent
agent內的約束agent所具有資源的約束，即R（Ai）≥mk=1R(Tk)×rik
任務所需資源的約束，即R（Tk）≤ni=1R(Ai)×rik
agent間的約束協同agent的資源集合滿足各任務的要求，即
ni=1R(Ai)×rik≥R(Tk)
任務的資源需求滿足各agent的資源約束，即
mk=1R(Tk)×rik≤R(Ai)
3.2 分布式并行求解算法
分布式約束滿足問題的求解算法一直是DCSP研究的一個重要方面，經典的求解算法[6]包括異步回溯、分布式逃逸和異步弱授權。這三種算法的基本思路都是agent按照一定的順序，異步地計算和搜索合適的取值，求解過程是分布式的，但不是并行的，只有單一進程進行搜索和無解空間的裁剪。DCSP本質上是由多個agent和變量構成的分布式問題，其每個agent變量值的搜索過程，若由每個agent并行地進行計算將更加高效，從而能縮短求解整個問題的計算時間。Zivan等人[4]提出了一種并行搜索的方法，即并行動態回溯算法(concurrent dynamic backtracking，ConcDB)。該算法由多個并行執行的搜索過程和掃描解空間的不相交子空間組成。每個搜索過程都有惟一的數據結構，此數據結構包含一個并行部分賦值(current partial assignment，CPA)，CPA在多個不同的agent之間進行計算。
并行動態回溯算法的第一步是劃分搜索空間，就是將變量的值域劃分為多個子域，每個子域定義一個惟一的子搜索空間和惟一的CPA在這個搜索空間中傳遞。同時算法采用了基于動態回溯的回跳方法，當agent的當前值域為空時，agent從無解空間的集合構建一個回溯消息。當并行動態搜索中的其他agent收到回溯消息時，刪除接收到CPA的搜索過程，發送一系列的消息給該CPA前面路徑的agent，并創建新的搜索過程和CPA繼續搜索。算法框架如下：
基于多CPA的并行搜索算法通過動態劃分子空間和動態回溯兩種有效途徑，極大地提高了求解搜索的效率。基于ConcDB算法進行改進，以適于任務分配問題的求解，可以獲得良好的算法性能。下面針對建立的兩種任務分配模型，分別給出算法及其求解過程的描述。
求解以agent為中心模型的算法，CPA定義為二元組〈Ai，Xi〉的列表，其中Xi={Tm，…，Tn}表示分配給Ai的任務集。假設A1作為初始agent發起搜索，可以預先選擇約束連接最多的agent作為A1。首先進行解空間的劃分；其次，在并行搜索時，先滿足agent間本身的約束，然后再滿足表1所定義的任務分配的約束集合。CPA在多個agent間傳遞，當無解時則發生動態回溯，進行動態劃分，并定義新的CPA和子搜索過程，直到所有的任務被分配且滿足所有約束時算法終止。
求解以任務為中心模型的算法，CPA定義為二元組〈Ti，Yi〉的列表，其中Yi={Al，…，Ak}表示協同執行任務Ti的agent集合。假設從T1發起搜索，首先進行解空間的劃分；然后多個搜索過程并發搜索，先滿足任務間的約束，再以各agent的資源擁有量作為全局約束，搜索求解合適的agent集合來執行每個任務。
這兩種改進的算法都借鑒了并行動態算法的框架。ConcDB算法的優點之一就是在通信具有隨機延遲時，仍能充分利用部分連通的agent進行動態劃分并發起新的搜索過程，放棄通信延遲的CPA，創建新的CPA進行并行搜索，并沒有從根本上影響算法的性能。因此，這種基于DCSP的任務分配方法適合于agent間通信有隨機延遲以及agent間存在多約束的情形。
3.3 任務分配應用實例
首先，假定一個MAS任務分配集合，包括agent集、任務集、資源集和相應約束的集合，這里列舉有四個agent、六個任務、包含五種資源的任務分配實例。表2為各agent擁有的能力資源列表，表3為任務所需的能力資源列表。
表2 各agent擁有的能力/資源列表
這里以第一種建模及其求解算法為例，首先以agent為中心對問題進行形式化，得到如圖3(a)所示的分布式約束滿足網;然后采用基于模型改進的并行動態搜索算法，對問題進行求
解，可以很快得到問題的約束滿足解，如圖3(b)所示為問題的一個解。
4 結束語
分布式約束滿足問題是分布式人工智能研究的一個重要方面，分布式環境下多智能體系統的多種應用都可以形式化為分布式約束滿足問題，它還特別適合應用于多agent之間需要協同的問題，具有廣泛的應用背景。本文對分布式約束滿足問題及其求解算法進行了研究，結合MAS任務分配問題的應用背景，建立了基于DCSP的任務分配問題求解框架。通過分析和實例解算表明了該方法的快速性以及在通信延遲時的穩定性，給MAS任務分配的研究提供了一種新的途徑。進一步的研究工作將討論在agent之間和任務集之間都存在強約束條件下的分配問題;同時，測試與改進算法的性能也是一個重要的方面。
參考文獻：
［1］
FALTINGS B，YOKOO M.Introduction:special issue on distributed constraint satisfaction[J].Artificial Intelligence，2005，161(12):15.
[2]石純一， 張偉.基于agent的計算[M]. 北京: 清華大學出版社， 2007.
[3]LONG Tao， ZHU Huayong， SHEN Lincheng. Negotiation based distributed task allocation for cooperative multiple unmanned combat aerial vehicles[J].Journal of Astronautics，2006，27(2): 457462.
[4]ZIVAN R，MEISELS A.Concurrent search for distributed CSPs[J].Artificial Intelligence，2006，170(45): 440461.
[5]WEISS G.Multiagent systems:a modern approach toartificial intelligence[M].Massachusetts:MIT Press，1999.
[6]YOKOO M，HIRAYAMA K.Algorithms for distributed constraint satisfaction:a review[J].Autonomous Agents and MultiAgent Systems，2000，3(2):185207.
