一種基于濾波的分布式任務分配算法

雷佳，劉航

（西北工業大學 自動化學院，陜西 西安 710072）

一種基于濾波的分布式任務分配算法

雷佳，劉航

（西北工業大學 自動化學院，陜西 西安 710072）

盡管同步模式協同算法允許團隊在許多通用網絡拓撲中達成一致狀態感知并執行任務分配，但收斂到一致狀態感知需要花費大量時間，傳輸大量數據。在低帶寬環境中這會導致嚴重的潛在問題，增加求解任務方案時間。分析了現存協同拍賣算法例如、CBBA，HIPC等的優缺點，并對HIPC進行改進。采用將濾波框架引入分布式協同拍賣的方法，在建立任務束階段采用濾波算法對局部狀態感知進行估計。打破了HIPC對局部場景感知的完美假設，使得新算法可以在局部感知不可靠條件下良好運行，該算法可以異步進行并行任務分配和沖突分解。通過試驗得出相比于HIPC，新算法減少了任務沖突次數，縮短任務執行時間。

協同任務分配；信息不確定性；分布式拍賣算法；濾波框架；多代理協同

許多任務分配問題要求自治代理團隊保持高度協同來有效執行期望任務。例如編隊分散執行復雜或長期任務，部署代理持續跟蹤重要目標，分配代理從不同方向提供負載，確保與基站的魯棒通信鏈路。處理環境性能不確定性時，獲得期望水平的協同面臨多方面挑戰，例如通信存在干擾，環境狀態或目標區域不可達、不可靠，存在高延遲、高代價。這些考慮引出了對分布式算法使用的興趣。

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

2 問題公式化

本節對問題進行了全面陳述，公式化了文中使用的變量。給定代理列表和個任務，任務分配算法的目標是找到一個最大化全局收益的無沖突任務代理匹配對。無沖突任務方案意味著沒有多個代理被分配給同一個代理。每個代理的局部目標函數定義了給定代理作為任務集合的子集附加到編隊的收益。該任務分配問題可用如下公式混合整數規劃來描述：

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

3 算法描述

3.1 基于濾波的分布式拍賣算法

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

表1 基于濾波的協同拍賣算法流程Tab.1 Flow of filter embedded task allocation algorithm

3.2 有效地估計狀態信息

1）MAV 運動模型

Ωmax是MAV的最大轉彎速率。要注意的是，假定在速率分量上的噪聲具有一些不確定性，例如，風的影響。假設每架MAV知道它的隊友的控制動作，因為它們的所有行動是基于相同的協同團隊任務分配規劃的。然而，由于所有MAV采用的是杜賓最優航跡，這些控制被限制在如下集合之內u∈{-1，0，1}。

2）有效的計算信息濾波器

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

其中Y是所謂的費舍爾信息矩陣，y＾是新的狀態估計量，I是每隔兩側都具有的先驗期望信息，而i是單個量測具有的驗后真實信息。

時間更新方程：

相應地，φk，Bk和 Γk是公式（2）中 A，B 和 G 的離散形式；ukj是對代理i∈U已知的代理j∈U的控制動作，因為所有代理都遵守相同的任務分配規劃。

量測更新方程：

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

每個代理也運行另外一個使用自身量測，已更新速率f1＞f2來對自身狀態進行估計的濾波器。對于狀態向量為yi，信息矩陣為Yi的濾波器，其方程為

時間更新方程：

給團隊發送的信息是ijk和Ijk。如果該信息是當前量測值，那么相應地，Ijk和 ijk可有式（5）和（6）計算得出。 但是，在上一次信息傳遞之后，發送所手機的全部信息會更有用。這樣的信息可由下式計算：

注意，與全部的Nu個團隊成員狀態濾波器相比，該有效算法導出相同的通信負載但減少了計算負載 （因為僅對式（8）到式（10）和式（12）進行計算）。 這種減少不會影響估計的精度。

3.3 數字仿真及結果分析

1）仿真公式

現在，假設每個代理從隊友那里接受異步地更新值。這些更新值，Ijk和ijk，基于代理j∈U有代理i∈U估計的作為代理j∈U所期望的當前狀態的估計量。因此，只有滿足eTjEej＞ε時代理j∈U才給團隊成員發送信息，其中

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

時間更新方程：

2）結果分析

區域中隨機布置20個任務，5個代理按預定搜索模式啟動，如表2所示為仿真參數。任何其他任務規模會得出相似的結論。通過提升每個代理的通信半徑構建通信網絡，直到每個代理達到最小網絡度數，網絡就是全連通的。在圖中，最小網絡度數從1（每個代理至少有一個鄰居）變到全連通網絡（每個代理都與其他4各代理連通）。每個代理可以獲得其鄰居的場景感知（位置和收益函數）。但在動態不確定網絡拓撲中，特定代理鄰居的狀態是變化的。對每個最小網絡度數值，運行50輪隨機構造的迭代之后求平均，結果如下圖。圖2中，協同網絡與場景感知網絡是等價的。這意味著網絡中存在通信延遲，這定義了數據在代理之間是如何傳遞的。

表2 仿真參數表Tab.2 Simulation argument

圖1 任務沖突次數Fig.1 Task conflicts times

圖2 算法迭代次數Fig.2 Algorithms iterate times

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

4 結 論

傳統解決分布式任務分配問題的方法基于場景感知協同或方案協同。當編隊可以簡單的全局溝通時相關元參數時場景感知協同工作良好，每個代理可以獨立構建團隊任務方案并獨立執行自身的部分任務。如果在團隊的子集中構建協同場景感知是可能的，則代理可以和這些代理進行隱式協同，同時方案協同也可以確保團隊內全局無沖突的任務方案。文章打破完美局部場景感知這一假設，向分布式協同拍賣算法中引入濾波模型，對不確定狀態信息進行有效估計。實驗結果證明了所設計算法能夠在動態不確定場景中提升分布式協同算法性能。

[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 稿件編號：201402220

愛生無人機創新基金（GCKY3002）；西北工業大學研究生創業種子基金（Z2013112）

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