協同任務規劃仿真實驗系統的設計與實現

張 佳 辛 斌 杜 鑫 曹志強

(1. 北京理工大學 自動化學院, 北京 100081)

(2. 中國航天科技工業集團, 北京 100036)

人才培養是新工科建設中最重要、最核心的任務。依據新工科培養目標的特點[1],學生在掌握專業理論知識的基礎上,必須加強實驗教學,優化實驗教學體系[2]。利用各種新技術建設和完善實驗平臺,是新工科實踐教育發展的重要基礎和保障[3]。虛擬仿真實驗教學是國家信息化教育戰略的重要實踐內容[4]。與實物實驗相比,虛擬仿真實驗在實驗教學方面具有人機交互性好、利用率高、易維護等諸多優點。

多智能體系統協同任務規劃[5-6]是當前人工智能[7]研究的熱點問題。隨著科技成果向教學轉化的不斷深入,多智能體系統協同任務規劃的相關知識在高校教學中已經逐步滲透至研究生和本科生,出現在控制專業的課堂上,但是配套的實驗課程卻屈指可數。機器人、無人機等設備價格昂貴,同時這類設備對實驗場地要求較高,極易發生碰撞、墜毀等事故,不易于在高校針對學生開展大范圍的實物實驗,也不易于在實體實驗室里同時開展各種不同研究方向的多智能體協同任務規劃實驗。因此,借助仿真手段是開展多智能體分布式協同任務規劃教學實驗的最佳途徑。

在目前“新工科”建設的形勢下,我國高校缺乏對多智能體系統協同任務規劃方面高層次人才培養的必要實驗手段,實驗研究非常薄弱,亟需開展這方面的工作。為了研究出適合碩士生及本科高年級學生開展的多智能體協同任務規劃的虛擬仿真實驗環境,本文開展了相關工作。開發了可以進行多智能體協同任務規劃的仿真實驗系統,可以面向多智能體的任務分配和路徑規劃[8]開展仿真實驗,為機器人控制相關的研究人員提供了一種便于開展相關教學和探索研究的工具和手段,為相關實驗教學提供可視化、友好人機交互的仿真實驗系統。同時,也為學生開展探究性學習、自主實驗和創新實踐提供先進手段和開放平臺。

1 “智能體-環境-任務”模塊化建模

為了讓實驗者能夠在本實驗系統上開展多智能體協同任務規劃策略的實驗研究,在構建仿真系統時需要對智能體所處的任務環境以及任務進行建模,為協同任務規劃提供依據。

智能體、環境與任務這三個要素是仿真系統的基礎,三者之間需要通過高效、統一的接口進行互通互聯。因此,應考慮這三個要素之間的協同建模問題。單個智能體通過通信模塊與環境、任務及其他智能體進行信息交互,因此需要按照圖1所示模型構架設計三個基本要素之間的接口標準及數據傳輸的參數。

圖1 智能體的信息傳遞

多智能體分布式協同的基礎是智能體之間的信息交互,因此圖1中單個受控智能體通過通信與交互模塊作為接口,與環境信息、其他智能體信息以及任務信息進行交互。信息通過傳感器、控制器、執行器進而傳送給受控智能體。

1.1 智能體建模

智能體模型應具有可組合性,方便實驗者根據不同的協同任務有針對性地選取仿真組件,通過多個組件的組合實現所需多智能體的功能。以仿真系統中模塊化、可組合的智能體為例,至少應具備傳感器模塊、控制模塊、執行模塊和通信模塊這四種基本模塊。每個智能體都是由多個基本模塊構成的,將不同的基本模塊進行組合形成不同種類的智能體模型。

為了實現模塊組合后的可用性,應首先確定智能體模塊的內部邏輯然后將其封裝,設計輸入、輸出接口與外界交互。使用者可通過輸入接口改變模塊內部參數,提高模塊適用性。輸出接口與其他模塊的輸入接口連接,負責信息傳遞,如圖2所示。模塊邏輯主體負責實體流和信息流的邏輯流轉、分配、再處理等過程,與輸出接口模塊相連接,將信息或任務輸入至特定接口。

圖2 模塊封裝與信息傳遞

由于智能體的模塊連接方式已基本確定,如對于地面智能體來說,測距傳感器模塊與地面智能體基本模塊必須連接,故輸出接口已寫入模塊連接語句。但由于模型中同類型的模塊可能不止一個,例如有的智能體需要連接激光測距儀,有的智能體需要連接超聲波傳感器,故對每個智能體實際需要連接的模塊需進一步確定。在輸入接口中設計模塊編號參數,同種類型的模塊編號不同,通過輸入接口寫入模塊自身的編號和與之連接的模塊編號以完成模塊柔性連接,如圖3所示。

圖3 可組合模塊的柔性連接

1.2 任務環境建模

任務環境對智能體的任務執行能力、移動能力、通信能力等能力特征有至關重要的影響。本實驗系統所實現的任務環境建模主要針對地圖尺寸大小、障礙物數量和障礙物位置等。

1.3 任務建模

當智能體被分配給某項任務時,該任務通常可以看作多項基礎子任務的集合,其中第i項任務對應的基礎子任務集合記為Mi={mi1,mi2,…,mij},j為基礎子任務的數量,基礎子任務中包含的屬性有:任務規模、任務處理的時間要求、任務的區域位置、任務的優先級以及任務需求下智能體之間的通信交互頻率。

任務規模由所需的智能體數量進行表征。基礎子任務所需時間要求通過時間窗口進行描述,記基礎子任務mij的時間需求為mtij,實際任務完成時間為rtij,當mtij>rtij時認為任務被成功處理。任務位置是任務區域的中心坐標位置,以坐標形式表示,mij的任務區域位置可表示為(xij,yij)。基礎子任務的優先順序表示為基礎子任務執行的序列關系,基礎子任務間可能存在串行或并行關系,不允許存在循環鏈接,因此基礎子任務間的序列關系可采用圖表示。

智能體協同執行任務過程中,通常需要多種智能體具備的不同能力相互配合。因此,采用能力需求矢量表示一個多基礎子任務的能力需求。對一次具體的任務,基礎子任務在能力需求上與全部智能體具備的能力分類相一致,即矢量維度與智能體能力劃分種類相同。記第i項父類任務的第j項基礎子任務能力需求向量Dij=[tij1,tij2,…,tijn],其中tijp表示第j項基礎子任務對第p種能力的需求,n為能力的種類。

相應地,每種智能體具有不同的能力,代表其適合完成某項任務的情況。每類智能體具有的不同能力由能力向量C表示,Ck=[mk1,mk2,…,mkn],其中mkp表示智能體k的第p項能力,當mkp>0時,表示智能體k具備該項能力,否則智能體k不具有該項能力,即不適于參加某項基礎任務。

2 仿真系統架構

為了讓學生能夠更加直觀和方便地開展多智能體協同任務規劃仿真實驗,本文基于AnyLogic軟件進行了二次開發,設計并實現了一個多智能體仿真實驗系統。用戶可以選擇不同的任務場景,控制和調整仿真參數,實時觀察仿真過程、任務狀態等,根據實驗結果反饋更好地理解算法并改進算法。整個系統主要包含以下幾個模塊:

2.1 場景設計模塊

多智能體協同任務規劃主要包括任務分配和路徑規劃兩大類問題,兩類問題涉及的智能體主體、環境參數和任務類型都不相同。本文中的實驗系統設計了任務分配和全覆蓋路徑規劃兩個場景。

2.2 環境設計模塊

環境設計模塊包括地圖尺寸大小、障礙物數量和障礙物位置等。用戶可以簡單地通過交互式方法,例如鼠標點擊、滑動等操作,自定義不同等環境參數,測試算法在不同環境約束下的性能。該模塊是仿真系統的重要組成部分,是算法仿真的前提和基礎。

2.3 參數設計模塊

仿真系統中任務和智能體的參數都能自定義設置。智能體是任務執行的主體,用戶可以根據需求自定義智能體的數量、初始位置、運動速度、搜索半徑、通訊半徑和能力大小等。任務參數則包括任務數量、初始位置和危險程度等。

2.4 綜合演示模塊

綜合演示模塊是多智能體協同任務規劃仿真系統的核心模塊,可根據用戶預設的場景和參數對算法進行仿真,提供可視化的仿真界面。仿真過程提供二維或三維動畫,可以實時觀察到智能體的位置、運動狀態、哪些區域任務未被完成、環境中障礙物的位置等信息。直觀、清晰的仿真過程更有利于用戶使用系統。用戶還能調整仿真運行的速度,隨時暫停觀察現象和參數變化,并導出相關數據。

2.5 數據導出模塊

系統在仿真過程中產生的所有數據均支持導出分析,包括智能體的決策方案,運動路徑和任務完成時間等。數據支持導出文本格式或Excel格式,圖片則支持JPG格式。該模塊能為進一步理解算法、改進算法提供有力數據支持。圖4是多智能體協同任務規劃仿真系統結構圖。

圖4 多智能體協同任務規劃仿真系統結構圖

3 系統仿真實驗

圣彼得堡工業大學分布式計算網絡研究團隊推出的AnyLogic軟件是一款運用廣泛、技術先進、功能強大的仿真工具,在公共交通建設、城市規劃、物流配送、軍事作戰、策略制定等多方面具有廣泛應用。本文的仿真系統設計采用了AnyLogic中基于智能體模型的仿真建模方式,在AnyLogic軟件的支撐下可以為學生提供多智能體協同的仿真實驗環境。

3.1 面向任務分配場景的仿真實驗

實驗以森林救火為任務背景。在該任務中,火災點的火勢隨時間改變,在起火點剛開始燃燒時,僅需要較少的救援力量即可撲滅火情。隨著時間的推移,如果不采取措施,火災點的火勢會逐漸變大,需要更多的救援力量、更長的救援時間才能撲滅。這個復雜任務可以用多點動態集結[9]的統一任務框架進行描述,其中的任務狀態或威脅度隨環境的改變而變化,是多智能體協同任務規劃的一種典型場景。在該任務中,多個位于不同位置的智能體通過協作、通信確定目標任務點,并向選定任務點集結,到達任務點的有效作用范圍后向其施加影響,使得每個任務的狀態或威脅度降到某個閾值以下,最終完成任務。

設區域中有M個智能體和N個任務。現以任務i和智能體k為例,任務狀態參數si表示任務的緊急或危險程度。狀態值參數越大,表示任務越緊急。以森林救火為任務背景,每個著火點是一個任務,任務點的火勢狀態將采取非線性變化形式,具體變化形式為指數形式。即任務點的模型為:

(1)

其中i=1,2,...,N,si(t+Δt)表示第i個任務點在t+Δt時刻的狀態值,λi(t)表示任務點i在t時刻的狀態變化率。

該多點動態集結任務的目標是讓所有任務狀況盡快下降到危險度閾值ε以下,即最快完成全部任務的時間,定義優化準則為

(2)

(3)

(4)

其中,n∈{1,2,…,N},xn(tn(W))是任務n在tn(W)時刻的狀態。任務n的狀態值下降到閾值 以下的最早時間是任務n的完成時間。

針對上述任務建立了如圖5所示的多智能體協作任務規劃實驗系統。左側是數據自定義配置區域,可以定義地圖環境的大小(包括地圖的高度和寬度、是否有障礙物等)、障礙物參數(包括障礙物的坐標和大小)智能體參數(包括智能體的數量、速度和能力值等)和任務參數(任務數量、任務初始化狀態值和任務威脅度等)等。仿真系統內置了多張地圖,用戶可以直接選中希望配置的地圖。

圖5 任務分配場景

實驗中內置了非線性MPDA的兩階段分布式任務分配算法[10]。當仿真程序開始運行后,仿真系統中二維動畫和三維動畫會實時顯示智能體和任務的狀態。仿真系統右半側為數據顯示區,可以實時顯示智能體和任務的關鍵行為數據。如圖6所示是某時刻數據顯示區的放大圖。用戶可以通過下拉框選擇需要查看的智能體或任務的相關信息,包括智能體的任務方案、到達任務時間、離開任務點時間。

圖6 任務分配場景數據顯示區

智能體按照既定算法執行滅火任務,如圖7所示是執行任務過程中第17、49、106和180秒的狀態。未被完成的任務標記為藍色,已完成的任務標記為黃色。隨著仿真的進行,任務逐漸完成,到180秒,所有任務均被完成。此時可通過系統數據導出模塊,導出仿真相關數據,輔助用戶了解多智能體的協作過程,進一步改進或完善算法。

圖7 任務分配仿真過程狀態截圖

3.2 面向路徑規劃場景的仿真實驗

實驗以軍事搜索為任務背景,在作戰環境中,多無人機群對目標區域進行全覆蓋搜索,為作戰后方提供數據情報,搜索過程中需避開危險區域和敵方基地等。

約束條件為

P1UP2U…UPM=Env

(5)

?i={1,2,…,M},t∈{1,2,…,T}

(6)

?i,j={1,2,…,M},t∈{1,2,…,T}

(7)

(8)

(9)

針對上述任務建立了圖8的仿真實驗場景,通過二維動畫實時展現仿真運行進程。首先對地圖參數初始化,然后點擊“地圖柵格化”將環境進行柵格處理,劃分完成后設置智能體的參數,初始化全部完成后智能體開始進行全覆蓋搜索,在此過程中可以暫停觀察現象和查看數據,以便更好地理解算法流程和仿真過程。

圖8 全覆蓋路徑規劃場景實時顯示區

該實驗包含實時顯示區、參數設置區和數據顯示區三個界面,通過左上角的黃色按鈕進行三個界面的切換。在圖9的參數設置區,用戶可自定義地圖的大小,自主配置障礙物的數量、位置和大小。系統中內置了4張環境地圖,可通過下拉框進行選擇和配置。系統支持自定義智能體的數量和搜索范圍,在圖9右側的“設置智能體參數”區域,用戶可通過友好的交互界面設置每個智能體的通信范圍和速度等參數,以便觀察不同配置參數下的實驗效果。

圖9 全覆蓋路徑規劃場景參數設置區

圖10 全覆蓋路徑規劃場景數據顯示區

實驗中內置了基于混合策略的分布式全覆蓋路徑規劃算法,能夠用于解決本實驗中的路徑規劃問題。現按照以下參數對場景進行配置,以顯示具體的仿真過程。選擇內置1號地圖,地圖的寬度為13 km,地圖的高度為7 km,智能體為3架小型旋翼無人機,智能體初始位置在地圖的左上側,搜索半徑為200 m,通訊半徑為4000 m,飛行速度是8 m/s。參數配置完成后,仿真系統柵格化后的地圖的待搜索柵格數是65×35個,如圖11。

圖11 環境柵格化示意圖

覆蓋搜索過程中對仿真過程中對第273和297 min這2個時刻進行截圖,如圖12。其中藍色、紅色和黃色的線條表示3架無人機的運動路徑。隨著仿真時間的進行,區域覆蓋率逐漸增加。第297 min,區域實現了全覆蓋。

圖12 全覆蓋仿真過程截圖(2個時刻)

3 結語

論文設計了多智能體協同任務規劃仿真實驗系統的架構,并基于AnyLogic仿真平臺進行了開發,搭建了面向任務分配場景的仿真實驗和面向路徑規劃場景的仿真實驗。模塊化的實驗系統可以讓操作者快速完成多智能體在不同環境、任務中的配置,進而把精力集中在協同任務規劃方法的實驗中,有利于激發學生興趣,培養實踐能力和創新精神。系統具有友好的交互性及可視化仿真功能,有利于加強學生對理論知識的理解和掌握,有利于提高學生的工程能力和創新能力。該系統還可以為研究人員提供多智能體協同任務規劃的仿真驗證環境,用于驗證各關鍵技術算法的有效性,并與同類算法進行效率對比和分析,具有經濟性、開放性、針對性、安全性等優點。