雷佳，劉航

（西北工業(yè)大學(xué) 自動(dòng)化學(xué)院，陜西 西安 710072）

一種基于濾波的分布式任務(wù)分配算法

雷佳，劉航

（西北工業(yè)大學(xué) 自動(dòng)化學(xué)院，陜西 西安 710072）

盡管同步模式協(xié)同算法允許團(tuán)隊(duì)在許多通用網(wǎng)絡(luò)拓?fù)渲羞_(dá)成一致?tīng)顟B(tài)感知并執(zhí)行任務(wù)分配，但收斂到一致?tīng)顟B(tài)感知需要花費(fèi)大量時(shí)間，傳輸大量數(shù)據(jù)。在低帶寬環(huán)境中這會(huì)導(dǎo)致嚴(yán)重的潛在問(wèn)題，增加求解任務(wù)方案時(shí)間。分析了現(xiàn)存協(xié)同拍賣(mài)算法例如、CBBA，HIPC等的優(yōu)缺點(diǎn)，并對(duì)HIPC進(jìn)行改進(jìn)。采用將濾波框架引入分布式協(xié)同拍賣(mài)的方法，在建立任務(wù)束階段采用濾波算法對(duì)局部狀態(tài)感知進(jìn)行估計(jì)。打破了HIPC對(duì)局部場(chǎng)景感知的完美假設(shè)，使得新算法可以在局部感知不可靠條件下良好運(yùn)行，該算法可以異步進(jìn)行并行任務(wù)分配和沖突分解。通過(guò)試驗(yàn)得出相比于HIPC，新算法減少了任務(wù)沖突次數(shù)，縮短任務(wù)執(zhí)行時(shí)間。

協(xié)同任務(wù)分配；信息不確定性；分布式拍賣(mài)算法；濾波框架；多代理協(xié)同

許多任務(wù)分配問(wèn)題要求自治代理團(tuán)隊(duì)保持高度協(xié)同來(lái)有效執(zhí)行期望任務(wù)。例如編隊(duì)分散執(zhí)行復(fù)雜或長(zhǎng)期任務(wù)，部署代理持續(xù)跟蹤重要目標(biāo)，分配代理從不同方向提供負(fù)載，確保與基站的魯棒通信鏈路。處理環(huán)境性能不確定性時(shí)，獲得期望水平的協(xié)同面臨多方面挑戰(zhàn)，例如通信存在干擾，環(huán)境狀態(tài)或目標(biāo)區(qū)域不可達(dá)、不可靠，存在高延遲、高代價(jià)。這些考慮引出了對(duì)分布式算法使用的興趣。

近來(lái)，對(duì)如何設(shè)計(jì)分布式或集中式任務(wù)分配算法存在如下范例。具有全局狀態(tài)感知的分布式算法[1-3]通過(guò)分享團(tuán)隊(duì)內(nèi)集中計(jì)算的規(guī)劃方案移除了延遲，但導(dǎo)致編隊(duì)內(nèi)代理間通信量激增。對(duì)策論方法和集中式拍賣(mài)方法[4-5]在通信、機(jī)載計(jì)算能力充足條件下工作良好。但該范例依賴(lài)于團(tuán)隊(duì)內(nèi)廣泛通信，所以在網(wǎng)絡(luò)全連通假設(shè)不滿(mǎn)足時(shí)性能受到影響；文獻(xiàn)[6-7]利用貪婪拍賣(mài)來(lái)為每個(gè)代理產(chǎn)生多任務(wù)方案，并產(chǎn)生與特定收益函數(shù)最優(yōu)解相比很好的方案[8]。HIPC[9]構(gòu)建與CBBA算法框架基礎(chǔ)上，在建立任務(wù)束階段用局部任務(wù)分配算法替換貪婪選擇，更加充分地利用了連通鄰居間的局部狀態(tài)信息，可得出更合理的任務(wù)方案。但HIPC假設(shè)MAV具有其連通鄰居的完美局部狀態(tài)感知，這一假設(shè)在實(shí)際動(dòng)態(tài)不確定網(wǎng)絡(luò)中很難滿(mǎn)足。在動(dòng)態(tài)不確定網(wǎng)絡(luò)中HIPC算法性能較低。

2 問(wèn)題公式化

本節(jié)對(duì)問(wèn)題進(jìn)行了全面陳述，公式化了文中使用的變量。給定代理列表和個(gè)任務(wù)，任務(wù)分配算法的目標(biāo)是找到一個(gè)最大化全局收益的無(wú)沖突任務(wù)代理匹配對(duì)。無(wú)沖突任務(wù)方案意味著沒(méi)有多個(gè)代理被分配給同一個(gè)代理。每個(gè)代理的局部目標(biāo)函數(shù)定義了給定代理作為任務(wù)集合的子集附加到編隊(duì)的收益。該任務(wù)分配問(wèn)題可用如下公式混合整數(shù)規(guī)劃來(lái)描述：

其中 X∈{0，1}Na×Nt為 Na×Nt維的二元決策變量集合，xij被用來(lái)表示任務(wù) j是否被分配給代理 i；τ∈{R+∪φ}Na×Nt正實(shí)數(shù)決策變量集合，τij表示代理i將執(zhí)行已分配任務(wù)j；Fij為基于全局方案代理i執(zhí)行任務(wù)j的收益函數(shù)；帶d=[d1，…，dNc]T的H=[h1，…，hNc]T，定義Nc集合可能的非線性約束格式為捕獲動(dòng)力學(xué)轉(zhuǎn)換和資源約束等的hk（X，τ）≤dk。該基本問(wèn)題公式可以適應(yīng)一些通常用于多代理決策問(wèn)題中的不同目標(biāo)和約束設(shè)計(jì)。在公式（1）中，收益和約束方程顯式依賴(lài)于決策變量X和τ?；谠撎匦缘木€性系統(tǒng)內(nèi)部依賴(lài)性使得基本混合整數(shù)規(guī)劃問(wèn)題難以解決（NP-hard）[10]。

3 算法描述

3.1 基于濾波的分布式拍賣(mài)算法

HIPC-KF算法流程如表1所示，是向HIPC算法流程中建立任務(wù)束階段引入FETA濾波框架[11]，對(duì)分布式團(tuán)隊(duì)中代理的狀態(tài)進(jìn)行有效估計(jì)，利用估計(jì)得到的一致信息集進(jìn)行任務(wù)分配。因?yàn)镠IPC假設(shè)代理對(duì)自己的一跳鄰居具備完美場(chǎng)景感知。這一假設(shè)在無(wú)線網(wǎng)絡(luò)中并不合理，考慮到延遲、丟包、投遞率等因素，應(yīng)該將局部網(wǎng)絡(luò)看作是不完美的，并對(duì)存在的不確定因素進(jìn)行處理、削弱。所以文章在建立任務(wù)束階段采用信息濾波器對(duì)局部狀態(tài)感知進(jìn)行估計(jì)。

表1 基于濾波的協(xié)同拍賣(mài)算法流程Tab.1 Flow of filter embedded task allocation algorithm

3.2 有效地估計(jì)狀態(tài)信息

1）MAV 運(yùn)動(dòng)模型

Ωmax是MAV的最大轉(zhuǎn)彎速率。要注意的是，假定在速率分量上的噪聲具有一些不確定性，例如，風(fēng)的影響。假設(shè)每架MAV知道它的隊(duì)友的控制動(dòng)作，因?yàn)樗鼈兊乃行袆?dòng)是基于相同的協(xié)同團(tuán)隊(duì)任務(wù)分配規(guī)劃的。然而，由于所有MAV采用的是杜賓最優(yōu)航跡，這些控制被限制在如下集合之內(nèi)u∈{-1，0，1}。

2）有效的計(jì)算信息濾波器

假設(shè)每個(gè)代理從其隊(duì)友那里接受同步更新的速率為f2，f2＜f1。發(fā)送或接受的數(shù)據(jù)可以是原始的測(cè)量數(shù)據(jù)；在集散估計(jì)中信息濾波器（IF）[12]是眾所周知的一項(xiàng)技術(shù)。它在代數(shù)上等價(jià)于以增加時(shí)間更新過(guò)程的復(fù)雜性為代價(jià)，在計(jì)算上簡(jiǎn)化了兩側(cè)更新過(guò)程的卡爾曼濾波（KF）。卡爾曼濾波算法產(chǎn)生狀態(tài)的估計(jì)量，由＾表示，同時(shí)產(chǎn)生估計(jì)量的協(xié)方差，由P表示。信息濾波器，從信息的角度對(duì)卡爾曼濾波器的一種表示，使用如下定義

其中Y是所謂的費(fèi)舍爾信息矩陣，y＾是新的狀態(tài)估計(jì)量，I是每隔兩側(cè)都具有的先驗(yàn)期望信息，而i是單個(gè)量測(cè)具有的驗(yàn)后真實(shí)信息。

時(shí)間更新方程：

相應(yīng)地，φk，Bk和 Γk是公式（2）中 A，B 和 G 的離散形式；ukj是對(duì)代理i∈U已知的代理j∈U的控制動(dòng)作，因?yàn)樗写矶甲袷叵嗤娜蝿?wù)分配規(guī)劃。

量測(cè)更新方程：

由于假設(shè)從每架代理獲得的信息質(zhì)量是相同的，因此信息矩陣也是相同的。這樣，對(duì)于所有的濾波方程僅需計(jì)算一次即可，以減少計(jì)算量。

每個(gè)代理也運(yùn)行另外一個(gè)使用自身量測(cè)，已更新速率f1＞f2來(lái)對(duì)自身狀態(tài)進(jìn)行估計(jì)的濾波器。對(duì)于狀態(tài)向量為yi，信息矩陣為Yi的濾波器，其方程為

時(shí)間更新方程：

給團(tuán)隊(duì)發(fā)送的信息是ijk和Ijk。如果該信息是當(dāng)前量測(cè)值，那么相應(yīng)地，Ijk和 ijk可有式（5）和（6）計(jì)算得出。 但是，在上一次信息傳遞之后，發(fā)送所手機(jī)的全部信息會(huì)更有用。這樣的信息可由下式計(jì)算：

注意，與全部的Nu個(gè)團(tuán)隊(duì)成員狀態(tài)濾波器相比，該有效算法導(dǎo)出相同的通信負(fù)載但減少了計(jì)算負(fù)載 （因?yàn)閮H對(duì)式（8）到式（10）和式（12）進(jìn)行計(jì)算）。 這種減少不會(huì)影響估計(jì)的精度。

3.3 數(shù)字仿真及結(jié)果分析

1）仿真公式

現(xiàn)在，假設(shè)每個(gè)代理從隊(duì)友那里接受異步地更新值。這些更新值，Ijk和ijk，基于代理j∈U有代理i∈U估計(jì)的作為代理j∈U所期望的當(dāng)前狀態(tài)的估計(jì)量。因此，只有滿(mǎn)足eTjEej＞ε時(shí)代理j∈U才給團(tuán)隊(duì)成員發(fā)送信息，其中

ε是一個(gè)設(shè)計(jì)參數(shù)，選擇E的目的是使誤差定義在信息估計(jì)量之間。運(yùn)行在每架代理i∈U的基于通信信息的Nv個(gè)濾波器方程為

時(shí)間更新方程：

2）結(jié)果分析

區(qū)域中隨機(jī)布置20個(gè)任務(wù)，5個(gè)代理按預(yù)定搜索模式啟動(dòng)，如表2所示為仿真參數(shù)。任何其他任務(wù)規(guī)模會(huì)得出相似的結(jié)論。通過(guò)提升每個(gè)代理的通信半徑構(gòu)建通信網(wǎng)絡(luò)，直到每個(gè)代理達(dá)到最小網(wǎng)絡(luò)度數(shù)，網(wǎng)絡(luò)就是全連通的。在圖中，最小網(wǎng)絡(luò)度數(shù)從1（每個(gè)代理至少有一個(gè)鄰居）變到全連通網(wǎng)絡(luò)（每個(gè)代理都與其他4各代理連通）。每個(gè)代理可以獲得其鄰居的場(chǎng)景感知（位置和收益函數(shù)）。但在動(dòng)態(tài)不確定網(wǎng)絡(luò)拓?fù)渲校囟ù磬従拥臓顟B(tài)是變化的。對(duì)每個(gè)最小網(wǎng)絡(luò)度數(shù)值，運(yùn)行50輪隨機(jī)構(gòu)造的迭代之后求平均，結(jié)果如下圖。圖2中，協(xié)同網(wǎng)絡(luò)與場(chǎng)景感知網(wǎng)絡(luò)是等價(jià)的。這意味著網(wǎng)絡(luò)中存在通信延遲，這定義了數(shù)據(jù)在代理之間是如何傳遞的。

表2 仿真參數(shù)表Tab.2 Simulation argument

圖1 任務(wù)沖突次數(shù)Fig.1 Task conflicts times

圖2 算法迭代次數(shù)Fig.2 Algorithms iterate times

圖1、2顯示了場(chǎng)景感知網(wǎng)絡(luò)和協(xié)同網(wǎng)絡(luò)被定義為最小網(wǎng)絡(luò)度數(shù)的結(jié)果。HIPC在完美完美局部感知條件下性能最好，而在局部場(chǎng)景感知非完美條件下HIPC性能較差，任務(wù)沖突次數(shù)和算法迭代倫次顯著增多。FEHIPC（基于濾波的HIPC）可對(duì)場(chǎng)景中不確定信息進(jìn)行估計(jì)，有效地矯正了HIPC的任務(wù)分配方案，減少了任務(wù)沖突次數(shù)和算法迭代次數(shù)，提升了算法性能。圖1中場(chǎng)景感知網(wǎng)絡(luò)稀疏時(shí)（最小網(wǎng)絡(luò)度數(shù)為1），非完美感知條件下，F(xiàn)EHIPC相較于HIPC獲得的提升是平均任務(wù)沖突次數(shù)從23減小到14。隨著最小網(wǎng)絡(luò)度數(shù)增長(zhǎng)，平均任務(wù)沖突次數(shù)正如所期望的收斂于較小值。圖2中非完美場(chǎng)景感知條件下，F(xiàn)EHIPC迭代次數(shù)總是小于HIPC。而在最小網(wǎng)絡(luò)度數(shù)等于4時(shí)（網(wǎng)絡(luò)全連通），非完美局部感知條件下FEHIPC的性能接近完美局部感知條件下的HIPC性能，說(shuō)明FEHIPC可以有效減弱場(chǎng)景中不確定狀態(tài)信息對(duì)任務(wù)協(xié)同分配的影響。

4 結(jié) 論

傳統(tǒng)解決分布式任務(wù)分配問(wèn)題的方法基于場(chǎng)景感知協(xié)同或方案協(xié)同。當(dāng)編隊(duì)可以簡(jiǎn)單的全局溝通時(shí)相關(guān)元參數(shù)時(shí)場(chǎng)景感知協(xié)同工作良好，每個(gè)代理可以獨(dú)立構(gòu)建團(tuán)隊(duì)任務(wù)方案并獨(dú)立執(zhí)行自身的部分任務(wù)。如果在團(tuán)隊(duì)的子集中構(gòu)建協(xié)同場(chǎng)景感知是可能的，則代理可以和這些代理進(jìn)行隱式協(xié)同，同時(shí)方案協(xié)同也可以確保團(tuán)隊(duì)內(nèi)全局無(wú)沖突的任務(wù)方案。文章打破完美局部場(chǎng)景感知這一假設(shè)，向分布式協(xié)同拍賣(mài)算法中引入濾波模型，對(duì)不確定狀態(tài)信息進(jìn)行有效估計(jì)。實(shí)驗(yàn)結(jié)果證明了所設(shè)計(jì)算法能夠在動(dòng)態(tài)不確定場(chǎng)景中提升分布式協(xié)同算法性能。

[1]McLain T W，Beard R W.Coordination variables，coordination functions，and cooperative timing missions[J].Journal of Guidance， Control， and Dynamics，2005，28（1）:150-161.

[2]Murphey J W C R.Simultaneous area search and task assignment for a team of cooperative agents[J].AIAA Guidance， Navigation， and Control Conference （GNC），2003，41（11）:135-141.

[3]Shima T，Rasmussen S J，Chandler P.UAV team decision and control using efficient collaborative estimation[J].Journal of Dynamic Systems， Measurement， and Control，2007，129（5）:609-619.

[4]Sariel S，Balch T.Real time auction based allocation of tasks for multi-robot exploration problem in dynamic environments[C]//Proceedings of the AAAI-05 Workshop on Integrating Planning into Scheduling，2005:27-33.

[5]Ahmed A M E，Patel A，Brown T，et al.Task assignment for a physical agent team via a dynamic forward/reverse auction mechanism [C]//Int’s Conf.of Integration of Knowledge Intensive Multi-Agent Systems （KIMAS 05:Modeling，Evolutions and Engineering），2004:311-317.

[6]Choi H L，Brunet L，How J P.Consensus-based decentralized auctions for robust task allocation [J].Robotics，IEEE Transactions on，2009，25（4）:912-926.

[7]Johnson L B，Ponda S，Choi H L，et al.Improving the efficiency of a decentralized tasking algorithm for UAV teams with asynchronous communications [C]//AIAA Guidance， Navigation， and Control Conference （GNC），2010，5（2）：5406-5411.

[8]Johnson L，Choi H L，Ponda S，et al.Allowing non-submodular score functions in distributed task allocation[C]//Decision and Control （CDC）， 2012 IEEE 51st Annual Conference on.IEEE，2012:4702-4708.

[9]Johnson L，Choi H L，How J P.Hybrid information and plan consensus in distributed task allocation[J].AIAA Guidance，Navigation， and Control Conference （GNC），2013，22（19）：724-735.

[10]Bertsimas D，Weismantel R.Optimization over Integers，Dynamic Ideas[M].Belmont， MA， 2005.

[11]Alighanbari M，Bertuccelli L F，How J P.Filter-embedded UAV task assignment algorithms for dynamic environments[C]//AIAA Guidance， Navigation， and Control Conference and Exhibit，2004:1-15.

[12]Maybeck P S.Stochastic models， estimation， and control[M].Academic Press，1982.

A filter embedded distributed task allocation algorith

LEI Jia，LIU Hang
（School of Automation， Northwestern Polytechnical University， Xi’an 710072， China）

Although consensus algorithms allow a fleet of vehicles to converge on the SA and perform an assignment over many generic network topologies，convergence to a consistent SA may take a significant amount of time and can often require transmitting large amounts of data to do so.This can cause severe latency in low-bandwidth environments and can substantially increase the time it takes to find an assignment for the fleet.This dissertation discuss advantages and disadvantages of extant distributed cooperative algorithms such as CBBA，HIPC.then extends HIPC by introducing filter into HIPC framework.This dissertation replaces TAA （task assignment algorithm） with FETA （filtered-embeded task assignment） during task bundle building phase of HIPC in order to estimate neighbours state information，which breaks the assumption of perfect local situation awareness and ensure the new algorithm running well under uncertainty.the new algorithm asynchronously assign task and resolve conflicts in parallel.Simulation result demonstrates when compared with HIPC，new algorithm can decrease task conflict times，shorten task execute time obviously.

cooperative task assignment algorithm；information uncertainty；distributed auction algorithm；filter framework；multi-agent cooperation

TN924+.2

A

1674-6236（2014）15-0019-04

2014-02-28 稿件編號(hào)：201402220

愛(ài)生無(wú)人機(jī)創(chuàng)新基金（GCKY3002）；西北工業(yè)大學(xué)研究生創(chuàng)業(yè)種子基金（Z2013112）

雷 佳（1989—），男，陜西渭南人，碩士。研究方向：多代理任務(wù)協(xié)同控制。