面向多機器人動態任務分配的事件驅動免疫網絡算法

曹鵬飛，郝礦榮，丁永生

由于多機器人系統可以更好地實現信息和資源共享，具有更高的并行性和魯棒性，可以完成更加復雜的任務，已經被應用到智能生產、未知環境探測、搬運清理、服務行業、搜索搜救、遠程通信等很多領域中，具備很好的實用價值[1-2]。而一種良好的任務分配策略對整個系統起著重要的作用，因而成為學者們的研究熱點。

針對不同的應用場景，國內外學者提出了許多有效的任務分配算法，大多都是基于行為機制、獎賞機制、市場機制以及群體智能[3-5]。袁等[6-7]提出改進的免疫網絡算法解決了未知環境中機器人搬運箱子問題，取得一定效果。但以上算法大都適用于靜態或任務信息事先已知的場景中，對于隨著時間動態產生，且事先只能感知任務位置，無法具體判斷任務量，需要機器人在任務執行時自主協作的場景中存在較大的局限。

生物免疫系統維持著生物系統的動態平衡，具有較強的學習性、記憶性和自適應性[8-9]。受此啟發，本文借鑒獨特型免疫網絡，將多機器人系統和免疫系統進行類比，構建任務分配與協作模型，并利用事件驅動機制實現了多機器人動態的任務分配與協作，并引入焦躁模型來解決任務死鎖問題，使多機器人系統能夠在動態任務、且任務量無法事先確定的復雜場景中實現任務自適應分配與自主協作，構建一個智能協同的機器人網絡[10]。將本文算法應用于需要協作的清理搜集任務中，仿真和實驗表明本文算法能夠有效解決此類動態任務分配問題。

1 多機器人任務分配與協作的免疫網絡模型

1.1 生物免疫網絡

生物免疫系統維持著整個生物系統的動態平衡，非常適合于動態和魯棒性系統研究，將其應用到實際工程，可以增強系統的穩定性。

1974年Jerne提出的獨特型網絡假說認為，生物系統可以維持本身的均衡，通過細胞間的相互作用，利用濃度最大的抗體消滅抗原[11]。

在此基礎上，Farmer等[12]提出了相應的動態方程，并將免疫系統應用于工程應用。

式中：Ai(t)和ai(t)為分別為t時刻抗體i的激勵水平和濃度；α、β為作用系數；ki表示抗體的消亡；N為抗體數目；mji和mik分別表示抗體間的激勵和抑制；gi表示抗體和抗原間激勵。

受此啟發，為了實現的任務動態環境中的多機器人任務分配，參照生物免疫網絡機理，將免疫網絡與實際的多機器人系統進行類比，映射關系如表1，提出一種多機器人任務分配與協作模型。

1.2 任務分配與協作模型

針對一定區域內的松散型清理搜集任務，需要通過多個同構或異構機器人獨立或協作完成。設環境中存在m個機器人Ri()和n個任務Tj()，機器人Ri具有相應的能力值fi和速度值vi，每項清理任務具有能力值和服務時間要求，監測節點可以實時監測系統中動態產生任務的位置，但無法獲得任務的具體信息，任務是否需要多機器人協作，需要在任務執行過程中動態判別，通過多機器人協作完成區域內的清理搜集任務，可根據機器人和任務屬性定義模型[5]。

表 1 機器人系統與生物免疫網絡的映射關系Table 1 Mapping relationship between robot system and biological immune network

1) 抗體與抗原激勵

在初始時刻，機器人間的任務分配，主要是根據任務對機器人的激勵進行選擇，某個任務對某個機器人的激勵較高，則其獲得該任務的概率就較大。設第i個機器人Ri和第j個任務Tj之間的激勵為gij，將其定義為

式中：λ1、λ2、λ3相應部分調整系數，fi和 vi為相應機器人Ri的能力值和速度大小，dij為機器人Ri和任務Tj之間的距離大小，pj為任務Tj的優先等級。

2) 抗體與抗體激勵

根據獨特型免疫網絡，抗體之間也存在激勵。在機器人到達相應任務點后，若機器人Ri需要得到幫助，則其需要激勵另外機器人，以使其盡快得到協作。若機器人Ri可以單獨的執行被分配的任務，則其將會對其他機器人產生抑制作用，便不會產生激勵作用。設機器人Ri對機器人Rj產生的激勵為mij，將其定義為

式中：λ4、λ5、λ6為相應部分的調整系數，fi和 vi為相應機器人Ri的能力值和速度值，dij為兩機器人間的歐氏距離，當等待在某個任務處的機器人對空閑機器人激勵越大，其前往協作的概率越大。

3) 綜合激勵

當機器要再次進行任務選擇的時候，其需要根據受到的抗原和抗體的綜合激勵值來選擇。綜合激勵由某個任務對該機器人的激勵以及在該任務上處于等待的機器人對該機器人的激勵共同構成，以此來完成機器人的任務分配與協作，設Aij為任務Tj對機器人Ri的綜合激勵，將其定義為

式中：α、β為相應部分調整參數，N為在任務Tj上等待的機器人數目，mik為機器人間產生的激勵，gij為任務Tj和機器人Ri之間的激勵值。機器人根據模型選擇任務，如有任務處于待協作狀態，等待在某個任務上的機器人越多，此任務被選擇的概率越大，從而能盡快地得到協作。

2 事件驅動的多機器人動態任務分配算法

利用文中提出的分配和協作模型，能實現任務的一次分配，在此基礎上引入事件驅動的機制[13]，使多機器人系統可以自適應地處理動態任務，并引入焦躁模型來解決任務死鎖。

2.1 靜態任務分配

系統中設定機器人和任務的狀態轉移如圖1所示，任務狀態和機器人的狀態相互對應，待分配任務激勵空閑機器人轉變為已分配狀態，如果此機器人可以自行完成任務，則任務轉變為執行態；否則任務轉變為待協作，處于待協作狀態的任務獲得協作轉變為已分配狀態，若等待協作的機器人由于長時間沒有得到協作而放棄任務，則任務由待協作狀態重新回到待分配狀態。

圖1 機器人和任務狀態狀態轉移圖Fig. 1 Robot and task state transition diagram

初始時刻，所有任務處于未分配狀態，機器人都處于空閑狀態，每個機器人按照激勵值選擇最適合自己的任務，如果每個機器人選擇的任務都不重復，則直接獲得相應任務，轉變為被激勵態；如果出現沖突，則沖突的機器人中次優任務激勵低者獲得最優任務，次優任務激勵相同時，隨機分配最優任務，其余機器人重新選擇任務。在任務分配時，每個機器人同一時刻只能得到一個任務，且當機器人處于閑暇狀態時才能被任務所激勵，任務處于等待和空閑狀態時才可以對機器人產生激勵作用。

2.2 動態任務分配

靜態任務分配方法只可以解決多機器人任務的一次分配，在此基礎上引入事件驅動的機制，當系統需要再次進行任務分配或是有新的任務產生時，通過事件觸發重新進行分配，以滿足環境動態性的要求。

系統中，定義如下事件：

① 系統中有新的任務產生；

② 系統中有機器人狀態由工作轉變為空閑；

③ 系統中有機器人狀態由等待轉變為空閑；

④ 系統中有機器人狀態由被激勵轉變為等待；

⑤ 系統中有機器人發生故障。

根據事件驅動的機制，當系統中有如上事件發生時，觸發系統，處于空閑狀態的機器人進行再次任務選擇。

2.3 任務死鎖解除

對于一個多機器人系統而言，常常會發生任務死鎖，即區域中所有機器人都因無法完成任務而處于等待狀態[14]。對于智能系統而言，需要機器人能夠自主地解除死鎖，盡快恢復到工作狀態。

為了使機器人能夠自主解除死鎖狀態，引入一種焦躁模型。當機器人長時間由于無法完成任務而處于等待，激素分泌使其產生焦躁情緒，當達到一定的上限時，其將會放棄對該任務的等待，從而重新回到空閑狀態，使其能夠協助其余處于等待狀態的機器人完成任務。

借鑒L.S.Farhy提出的激素分泌的規律[15]，定義系統中引起焦躁情緒的激素分泌模型為

式中：T為閾值，t為時間變量，n為Hill系數，且n≥1。

機器人處于等待狀態而分泌激素，當其超過設定閾值C時，機器人會放棄等待的任務，回到空閑狀態，且機器人會對該任務產生記憶，避免在該任務處于未分配狀態時再次選擇，陷入循環死鎖狀態。若該任務處于協作狀態時，其對該機器人的激勵將會被弱化，表達式如式（7）所示：

式中：gij為抗原對抗體的激勵表達式；η為調整參數，0＜η＜1。

2.4 算法流程

在多機器人系統中，采用混合式的結構實現文中算法，服務端通過多進程模擬機器人，實現任務的分配，可以降低網絡通信消耗，每個進程與一個實際的機器人通過網絡通信，保持狀態同步，多個機器并行運行。算法步驟如下：

① 初始化系統抗原抗體信息；

② 計算空閑機器人與待分配任務和待協作任務的綜合激勵值；

③ 各機器人自主解除沖突，選擇合適的任務，并向任務處移動；

④ 機器人判斷能否完成任務，若能跳到⑥，否則轉到⑤；

⑤ 機器人狀態更改，事件觸發，轉到②，等待合適的空閑機器協作；

⑥ 機器人獨自或協作完成相應任務；

⑦ 系統終止，否則轉到⑧；

⑧ 狀態更新，事件觸發，轉到②。

算法的程序流程圖如圖2所示：

圖2 多機器人動態任務分配流程Fig. 2 Multi-robot dynamic task allocation

2.5 算法性能分析

多機器人系統的通信和計算消耗是任務分配算法中重要的衡量指標[14]，對于維持整個系統的穩定起著重要的作用。為了和其他算法進行比較，以機器人數量n和任務量m的函數形式O(·)來描述通訊量和計算量。

通訊量表示機器人在一次任務選擇時的信息交互量。從通信量來看，由于本系統采用混合式結構實現，每一個機器人都擁有服務子進程專門服務，每個服務子進程為相應機器人選擇當前最合適的任務，在服務端進行任務沖突解決，并不需要機器人實際通信解除沖突。只在任務的下達和任務反饋時需要進行通信，所以一次任務分配中每個機器人的通信量是O(1)。

計算量表示機器人選擇一次任務所需要計算的時間復雜度。機器人每次選擇任務，都需要進行m次綜合激勵計算，選擇合適的任務，然后需要進行n次比較解決任務沖突問題，當有k個機器人任務沖突，需要2k次計算解決任務沖突，故計算量是O(m+n+2k)。

按照任務分配類型，文中算法滿足“同時”、“再分配”，“同時”指可以考慮多個待分配任務，“再分配”指任務能夠進行重分配[16]。這種任務分配方法明顯優于“順序”、“無再分配”、無法適應動態環境的算法，故不做對比。本文算法ALLIANCE[4]、BLE[17]性能比較如表 2所示。

表 2 任務分配算法性能Table 2 Task allocation algorithm performance

3 仿真與實驗結果分析

為了驗證基于事件驅動免疫網絡算法的有效性，在MATLAB 2012b平臺上，設置動態的清理搜集，進行多機器人實驗。設計不同場景，分別驗證文中算法的動態任務分配和協作性能，以及系統自主處理任務死鎖能力。系統監測節點可以實時感知任務是否產生及產生的位置，而任務能否獨自完成需要機器人任務執行過程中進行判斷，事先無法獲知。

3.1 仿真實驗及其結果分析

3.1.1 實驗環境參數

仿真環境設定為10 m×10 m的區域，實驗中以圓形“○”代表機器人，以正方形“□”表示任務，R1/1代表1號機器人，且其能力值為1，T1/1代表任務1，且其完成需要的能力值為1，機器人的移動速率設為v=0.1 m/s(可自行設定)，任務優先級設為p=1(可自行設定，不失一般性)。算法中參數設置為：λ1=0.6，λ2=0.4，λ3=0.2，λ4=0.5，λ5=0.5，λ6=0.2，α=0.6，β=0.4，η=0.6，C=0.6，T=5，n=5。

設定兩種仿真實驗環境，環境1中，初始設定6個靜態任務：T1/1，坐標(3, 2.5)；T2/2，坐標(2,7)；T3/1，坐標 (5.5, 4)；T4/1，坐標 (7, 2)；T5/1，坐標(6, 6)；T6/1，坐標 (8, 8.5)，在機器人運行過程中，設定兩個動態任務：T7/1，坐標(5, 2)；T8/1，坐標(8,6)。在環境中設有4個同構機器人，分別放置在不同的位置：R1/1，坐標 (0.1, 0.1)；R2/1，坐標 (9.9,0.1)；R3/1，坐標 (9.9, 9.9)；R4/1，坐標 (0.1, 9.9)。

在環境2中，主要是為了驗證算法的自主解死鎖能力，不失一般性，在環境中設置兩個靜態任務：T1/2，坐標 (2, 2)；T2/3，坐標 (6, 4)。設置兩個機器人：R1/1，坐標 (0.1, 0.1)；R2/2，坐標 (9.9, 0.1)。

3.1.2 仿真實驗結果分析

如圖3(a)所示為環境1的仿真結果。圖中虛線代表前去協作過程，實線代表首次被某任務激勵而前往過程。根據本文算法，在初始時刻，每個機器人被相應的任務所激勵，機器人R1/1前往T1/1，R2/1前往 T4/1，R3/1前往 T6/1，R4/1前往 T2/2，當機器人執行任務時，會判斷是否可以獨立完成，如果可以獨自完成則開始執行任務，否則更改狀態，觸發請求協作。在第1次任務分配中，由于機器人速度相同，機器人R2/1和R3/1先于R1/1完成任務，進行第2次任務選擇，而此時R4/1機器人在T2/2處等待協作，由于距離較遠，機器人R2/1和R3/1被任務T3/1和T5/1所激勵，R1/1完成T1/1后，初始的靜態任務只剩下處于等待協作的T2/2，其被激勵前往協作。在所有機器人都處于二次激勵時，系統產生動態任務T7/1和T8/1，觸發請求任務分配，然而此時沒有處于閑暇狀態的機器人，任務暫時不會被分配，在R2/1和R3/1完成T3/1和T5/1后被T7/1和T8/1再次激勵，前往任務處進行處理。

如圖3(b)所示為環境2的仿真結果。初始時刻，機器人R1/1和R2/2分別被T1/2和T2/3所激勵，機器人R1/1先到達任務處進行協作等待，同時開始分泌激素，R2/2隨后到達T2/3，亦處于協作等待，同時開始分泌激素，隨著時間的增加，機器人R1/1產生焦躁情緒而放棄等待，同時標記任務T1/2，隨后R1/1前往協作處理T2/3，機器人R2/2得到協作，在任務T2/3完成后，機器人R2/2受到T1/2任務激勵，前往完成，結果表明，系統能夠可以成功解除死鎖。

多次實驗驗證表明，基于事件驅動的免疫網絡算法能夠實現動態任務場景中多機器人的任務自主分配與協作，具有較強的適應性和魯棒性。

圖3 仿真結果Fig. 3 Simulation result

3.2 多器人系統實驗及其結果分析

為了驗證文中算法在實際多機器人動態任務分配系統中的有效性，利用多個khepera機器人，搭建多機器人障礙物環境，利用攝像頭進行環境監測，當監測到系統中有任務(以紅色物品代替)產生時，利用文中算法，激勵相應的機器人前往完成任務，并采用人工勢場法使機器人可以避開障礙，安全到達任務點。系統中機器人間利用網絡與服務器通信。

圖4(a)為系統中機器人系統初始圖，當在系統中放置相應物品，將會觸發系統進行任務分配，圖4(b)為機器人被相應任務激勵前往目標示意圖。

圖4 實際機器人系統仿真圖Fig. 4 Actual robot system simulation

經過多次實驗，設置不同任務，系統都能快速反應，激勵相應的機器人進行任務的執行與協作，驗證了文中算法在實際多機器人動態任務分配系統中具有較高的可行性。

4 結束語

針對一類復雜的松散型動態任務，文中基于免疫網絡和事件驅動機制，提出一種動態任務分配算法，解決了多機器人的動態任務分配與自主協作問題，并利用焦躁模型解決了任務分配過程中的死鎖問題，仿真和實驗表明本文算法在一類需要協作的動態任務分配問題中的有效性，具有較強的自適應性。將文中算法應用于實際場景的多機器人系統中，取得了較好的效果，表明將本文算法應用到實際的多機器人系統中有較高的可行性。課題后續將把重點放在分配模型的優化和實際應用的拓展上，在提高算法性能的同時，能夠實現更大的實際價值。