多智能體系統任務分配實驗設計與實現

張 佳， 任親浩

（北京理工大學，自動化學院，北京100081）

0 引 言

多智能體系統（Multi-Agent Systems，MAS）是指一群具有局部范圍信息感知、處理和通信能力的自主移動智能體，通過系統間高效的協同合作能力，實現單個智能體所不能完成的各種艱巨、復雜的任務［1-2］。多智能體系統分布式協同控制是人工智能研究的熱點，也是智能機器人的一個重要研究方向，其相關的教育是培養信息技術、智能技術及工程技術類人才的有效手段，已成為國際教育界關注的熱點［3-4］。對自動化領域人才培養，增強學生綜合實踐能力和處理復雜工程問題的能力，培養拔尖、創新人才具有重要意義，是提高人才培養質量重要的一環［5-6］，其實驗、實踐教學在學生自主工程能力的培養中占有重要位置［7］。為讓學生能掌握多智能體系統相關方面的最新研究動向，多智能體的協同控制在高校教學中已逐步滲透至研究生和本科生，出現在控制專業的課堂上，但配套的相關實驗屈指可數。

結合多智能體系統在實際問題中的應用，構建分布式多機器人系統仿真平臺，設計并實現分布式多智能體系統協同探測［8］任務分配的仿真，便于學生將理論與應用相互結合、融會貫通，培養學生的實踐能力。配合以問題為導向（Problem-Based Learning method，PBL）教學方式，該仿真平臺可以開展機器人、多智能體系統相關課程的配套實驗，促使學生從以往的被動式學習向以探究科學知識、解決復雜工程問題為目標的主動式學習快速轉變［9］。

1 多智能體探測任務分配實驗設計

1.1 仿真環境構建

本實驗環境構建采用AnyLogic［10］8.5.2專業版。用柵格化地圖構建多機器人探測任務的仿真環境，并對相應柵格的高度作出設置。假設每5單位距離為1 m，設置柵格大小50×50×10，即一個柵格的體積為200 m3?，F建立一個12×14×16的三維環境，即縱向共12個柵格，橫向共14個柵格，環境高度為6個柵格。實驗環境的平面效果、立體效果如圖1、2所示。實驗中共設計了4種高度，其中，白色方塊為邊界，綠色方塊為平地，黃色方塊高度為10，粉色方塊高度為20，紅色方塊高度為30，紅色圓點表示任務點。

圖1 平面地圖效果

圖2 立體地圖效果

1.2 協同探測任務分配實驗建模

基于機器人自身能力的限制，僅憑單個機器人難以完成對多個地區探測的任務，需要多個機器人進行協同探測。以分布式異構多智能體系統執行探測任務為背景，實驗內容是采用某種優化分配方法，為實現多個機器人協同探測任務開展任務分配工作，使系統中的多個機器人能夠協同工作，達到總體工作最優。

實驗環境中的已知信息包括任務點的位置、任務對探測能力的需求、多機器人系統的出發點、能力等，并且都不會發生變化。需要解決的問題描述為：給定N個能力異構的機器人和M個需求能力異構的任務點，如何進行探測任務的分配，能夠得到一個高效無沖突的分配方案，使得所有機器人執行任務的總航跡時間最短。

式中：Bi=｛B1，B2，…，Bj｝i=1，2，…，N為機器人i執行任務的集合；T=｛T1，T2，…，TM｝為所有探測任務的集合。實驗中，每個任務都是單機器人任務，即每個任務只會分配給一個機器人；所有機器人都是單任務機器人，它們可以擁有多個任務，但只能執行完一個任務后才能執行其他任務。

在多機器人系統進行任務分配的過程中，需要遵循以下規則：

（1）所有機器人執行任務時優先執行距離當前自身位置最近的任務；

（2）機器人能力足夠時才能獲得對應的任務，即自身能力滿足對應任務的需求。

用Li表示機器人i完成自己所有任務的總時間，xij為分配函數，機器人i∈U，U=｛1，2，…，NU｝，任務j∈G，G=｛1，2，…，MG｝。所有機器人執行任務的時間要求最短，即

任務j分配給機器人i時分配函數xij的值為1，否則為0，即

每個任務只分配給1輛機器人，即

所有的任務都會被執行，

多機器人任務分配的目標函數值z，由所有機器人執行任務時間的集合中的最大值決定。即在同時滿足任務分配無沖突以及所有任務都有機器人完成這2個約束條件的前提下，盡量使得z的取值最小，z越小表示所有機器人完成任務的時間越短。

1.3 探測任務分配方法

實驗采用改進的合同網拍賣算法［11-12］進行任務分配。實驗分為2個階段，第1階段為機器人選擇任務以及報價，每個機器人根據自身能力的強弱選擇能夠執行的任務，然后更新自身的信息，計算其選擇了的任務的出價；第2階段為沖突消解［13］，各機器人之間對于選擇的相同任務進行出價比較，出價最高者得到該任務，競標失敗的機器人從自身移除該任務。

多機器人任務分配的步驟如下：

步驟1初始化參數。包括各機器人的能力系數集合、出發點等信息，以及任務的所需能力系數集合、位置等信息；

步驟2構建任務集。對于每個機器人而言，若任務滿足條件CT≤CR，那么該機器人將此任務加入自身的任務集之中；

步驟3構建路徑集和時間集。根據就近原則重新排列任務集得到路徑集，基于路徑集的執行任務順序信息計算出時間集；

步驟4計算出價。根據出價公式得到每個機器人對于路徑集中各任務的出價，更新自身的勝者集和價格集；

步驟5沖突消解。根據貪心算法［14］解決旅行商問題［15］，對于所有任務進行順序排列，隨后按照此順序依次進行沖突消解。每個機器人之間互相通信協商，進行出價對比，價格最高者保留任務，其余價低者刪除任務集中的該任務。所有機器人之間協商結束后，重新進行步驟3直至所有任務完成沖突消解，算法結束，得到最終任務分配結果。

該步驟的流程圖如圖3所示。

圖3 探測任務分配流程圖

1.3.1 信息結構

在多智能體系統的任務分配過程中，每個機器人的地位都是平等的，它們之間都可進行通信。定義機器人的集合為U=｛1，2，…，N｝，任務點的集合為T=｛1，2，…，M｝，即表示系統中有N個機器人以及M個任務。每個任務根據所需求的能力不同，定義任務j所需能力系數集合為CTj=｛C1，C2，…，Ck｝，Ck為任務對于探測能力的需求能力系數，Ck越大表示該任務點對于探測能力的需求越高。通過不同的需求能力系數組合，就能表示能力需求異構的任務。對于每個機器人，都包含以下幾個信息：

（1）能力系數集合CR。定義CRi=｛C1，C2，…，Cn｝為機器人i的能力系數集合，對應探測能力的強弱。根據機器人系統任務分配規則，只有當機器人的能力系數集合中每一項元素都大于對應任務的所需能力系數集合的對應元素時，該機器人才能對此任務進行選擇并加入自己的任務集合里面。當Cn=0時，表示該機器人不具備該種探測能力，Cn越大表示機器人該種能力越強。

（2）任務集Bi。定義Bi=｛B1，B2，…，Bj｝，Bj為任務j，該集合表示機器人i的可執行任務集合，即該機器人通過對能力系數進行比較，將所需能力系數不超過自身能力系數的任務都加入自身的任務集中。

（3）路徑集Pi。定義Pi=｛P1，P2，…，Pj｝，Pj為第j個執行任務，Pj=｛1，2，…，M｝為任務的編號，該集合表示機器人i執行任務的順序。

（4）時間集ti。定義ti=｛t1，t2，…，tj｝，該集合為機器人i按照路徑集的順序從起始點到達任務j的時間。由于具體環境的不確定性，該集合是根據機器人到任務點的空間直線距離以及機器人的行駛速度進行計算的。由于該集合是基于路徑集計算的，每一個路徑集元素對應一個時間，所以該集合元素的數量與路徑集相等。當考慮時間時，該集合作為機器人出價的重要參考因素。

（5）勝者集Wi。定義Wi=｛U1，U2，…，Ui｝，Ui=｛1，2，…，N｝。該集合共有M個元素，對應M個任務，表示機器人i認為的目前系統的分配結果，第n個元素Ui為第n個任務分配給機器人i執行，其中0＜n＜M+1。

（6）價格集Yi。定義Yi=｛Y1，Y2，…，Yj｝，該集合為目前每個任務對應的最高價格，如果在機器人的認知里，某個任務目前還沒有分配給任何機器人，那么對應元素為0。它和勝者集是對應的，勝者集表示任務分配給哪個機器人，價格集為對應機器人的出價。

1.3.2 選擇任務

每個機器人根據自身的能力系數集合，選擇可以執行的任務，并且將這些任務加入自己的任務集當中。通過貪心算法對任務集進行重新排列得到路徑集，根據路徑集的順序和速度等相關參數計算出自身的時間集。對路徑集中的任務進行報價

式中：Cij為機器人i對于任務j的出價；CRi、CTj分別為機器人i的能力系數集合以及任務j的所需能力系數集合，|CRi-CTj|=（CR1-CT1）2+（CR2-CT2）2+…+（CRk-CTk）2為機器人與任務的匹配程度，該值越小表示兩者匹配程度越高，最佳匹配表現為該結果為0；tj為機器人按照當前路徑集到達任務j的時間，即時間集中對應的元素；λ1、λ2分別為機器人和任務匹配程度的影響權重系數以及時間的影響權重系數，它們的大小視具體情況而定。

每個機器人計算出價后，都會更新自身的勝者集和價格集。在初始化參數階段，對于自己選擇的任務，先認定自己為勝者，價格集對應元素也為自己的出價，對于未選擇的任務，勝者集和價格集都認先設定為0，即目前沒有分配任務給機器人。

1.3.3 沖突消解

在所有機器人都完成任務選擇后，機器人之間開始通信協商以達到解決沖突的目的，得到最后的任務分配結果。由于在“選擇任務”階段中，每個機器人得到的路徑集以及時間集等集合都是基于距離最近原則構造的，在沖突消解階段同樣基于距離最近原則。依照貪心算法解決旅行商問題，將任務集中的所有任務都分別看作一個城市，假設一輛試驗車為商人，那么可以得到該試驗車遍歷所有任務的執行順序。通過該方法從起點開始，所有的任務都根據每次選擇距離當前點最近的任務點排列起來了，以此構成一個所有任務的路徑集合。根據該集合中的順序依次進行沖突消解，確保每個機器人的路徑集不會出現混亂，即每1次沖突消解時，機器人對于進行沖突消解的任務的出價都是當前階段該機器人能夠給出的最高價格，同理這也確保了每次任務都分配給了最高出價的機器人。每進行完機器人對于一個任務的出價比較后，價格最高的機器人得到任務，其余機器人從路徑集中刪除該任務。

每次完成一個任務的沖突消解后，所有機器人都會重新構造自己的路徑集、時間集等，根據新的時間集計算出價，再進行下一個任務的沖突消解。直到所有任務都完成了沖突消解，算法結束，得到最后的分配結果。

2 實驗數據及結果分析

2.1 任務點及機器人相關參數設置

給定5個異構能力的機器人以及10個所需能力不同的任務點，設定每個機器人的行駛速度為1 m/s，翻越能力為2 m。即在實驗中每次只能同高度移動或者移動到高度差為2 m的位置。根據能力異構，設置3種探測能力，即偵察、抗干擾和數字測繪，它們的上限都設定為4。各機器人參數和任務點參數見表1、2。

表1 各機器人的參數

各機器人其余參數如起點、速度和翻越能力等均相同，實驗僅考慮能力異構。表中CR1～CR3對應3種探測能力，各參數的大小表示對應能力的強弱。

表2 各任務點的參數 mm

2.2 實驗結果

考慮到任務匹配程度和時間對于機器人出價的影響，實驗中設置了不同的λ1和λ2，得出了如表3所示的分配結果。

表3 各機器人的路徑集

在權重系數各為0.5時，各機器人的時間集見表4。

表4 各機器人的時間集

由表4可知，地圖的執行任務時間為1 143.352 s。根據實驗結果可知，每個機器人路徑集中的任務都是符合自身能力的，并不存在某個任務同時出現在多個機器人的路徑集中。說明本實驗所采用分配方法的結果是合理、無沖突的。

由實驗結果可見，任務分配結果主要受匹配程度和時間集影響，當前者的權重系數大于后者時，任務的分配結果傾向于每個機器人執行與自己匹配程度高的任務，同時減小任務點之間距離對于分配結果的影響；當后者的權重系數大于前者時，任務的分配結果傾向于執行任務時間短，同時減小機器人與任務的匹配程度對于分配結果的影響。

3 結 語

本文設計并實現了多智能體系統協同探測任務分配實驗，其中任務分配算法既可以使用改進合同網拍賣算法，也可以讓學生自行選擇。實驗具有較強的可擴展性，探測任務分配完成后，后續還可進行機器人在執行探測任務時的路徑規劃實驗，根據不同的任務需求，不斷擴充實驗內容。該實驗可作為機器人、多智能體系統等理論課程的配套實驗，輔助理論教學，提高學生的理解能力、解決問題能力及創新能力。