基于多種群協同進化的多逃逸者圍捕任務分配

高子璇,張國富,2,3,4,蘇兆品,2,3,4,李 磊

(1.合肥工業大學 計算機與信息學院,安徽 合肥 230601;2.大數據知識工程教育部重點實驗室(合肥工業大學),安徽 合肥 230601;3.智能互聯系統安徽省實驗室(合肥工業大學),安徽 合肥 230009;4.工業安全應急技術安徽省重點實驗室(合肥工業大學),安徽 合肥 230601)

0 引 言

隨著機器人在軍事、工業領域中的應用,機器人追逃問題[1-2]已成為人工智能和機器人領域中的研究熱點之一,其研究類型主要分為對單逃逸者的追逃問題和對多逃逸者的追逃問題。自Isaacs[3]為兩個參與者制定追逃策略以來,對單追捕-單逃逸者之間的博弈進行了詳細的研究。單追捕-單逃逸者的情況是一個零和博弈,可以用著名的貝爾曼方程[4]的擴展來解決。Jia等[5]提出用連續時間馬爾可夫決策過程(CTMDP)來解決一個追擊者和一個逃逸者的追逃問題中的不確定性。Pan等[6]提出了一種基于區域的中繼追擊方案,在追捕的過程中可以更換主動追擊者,來使追擊時間縮短。Kokolakis等[7]提出了一種基于關鍵強化學習(RL)的算法用于在線學習,并在有限時間內學習追擊策略,從而實現對逃逸者的有限時間捕獲。

在多追捕-單逃逸者的追逃問題中,Lin等[8]研究了一類線性二次多追捕-單逃逸者微分對策,逃逸者實施傳統的反饋納什策略,而追捕者基于最佳可實現性能指標的新概念實施納什策略。Kumkov等[9]為對象組的沖突互動制定了特殊的公式和方法來解決對象太多時相位向量的維數很高時帶來的困難。

近年來,現代交互多智能體系統推動了對多追捕-多逃逸者追逃問題的研究,該研究涉及到圍捕任務的分配,主要解決如何分配若干個機器人進行協同圍捕逃逸者的問題。圍捕機器人在障礙物環境下的實時移動大多采用人工勢場法[10]等來確定。在多追捕-多逃逸者的追逃問題的研究中,Stipanovic等[11]通過將水平集函數定義為玩家的目標來確定確保捕獲或規避的條件,提供了一種在具有多個參與者的追逃游戲中設計保證捕獲或保證規避策略的方法。胡俊和朱慶保[12]為圍捕任務的分配設計了一種“協商分配法”,李瑞珍[13]沿用了“協商分配法”并應用于全方位的圍捕系統中,但并沒有在逃逸機器人數量較多的情境下進行更深入的實驗與研究。徐望寶等[14-15]提出了一種基于人工力矩的自組織圍捕方法,并設計了一種圍捕機器人吸引點基于局部信息的確定與調整方法;文獻[16]提出了一種鏈陣方法,計算復雜度高,圍捕團隊數目可以不相同并且可以隨時加入或退出,在圍捕者改變圍捕目標后,圍捕效率不夠理想。高曉陽[17]提出了一種分配原則,使圍捕機器人依次選擇離自己最近的圍捕點,喪失了對所有機器人一視同仁的公平性。張紅強等[18]提出了一種基于圍捕者面對多目標中心方向180度范圍內的兩最近鄰進行任務分配的分配方法,減少運動距離和能量消耗。

Lopez等[19]設計了一種規則,圍捕者先選擇距離自己最近的圍捕點,如果兩個圍捕者有相同的最接近的逃逸者,將距離最短的圍捕者的目標更改為其第二個最近的逃逸者,可以解決任務分配沖突的問題。陳銘治和朱大奇[20]將每個圍捕者到逃逸者的預估時間編為矩陣,根據圍捕一個逃逸者所需圍捕者的數目計算該逃逸者被圍捕所需的最短總時間,圍捕者優先圍捕具有最小預估時間的逃逸者。

需要指出的是,上述已有研究大都采用距離優先分配的策略,在逃逸者數量較多的情況下,難以實現圍捕任務的均衡分配,降低了系統圍捕的效率。為此,該文在總結和分析前人工作的基礎上,構建了一種全方向的群機器人逃逸圍捕任務分配數學模型,然后基于遺傳算法和多種群協同進化提出了一種多逃逸者圍捕任務分配算法,設計了相應的編碼方式、交叉和變異策略。最后,在開發的群機器人逃逸圍捕仿真平臺上測試了算法的有效性。

1 問題描述

群機器人多逃逸者圍捕問題設定在二維受限環境,有m個圍捕機器人,用Q={q1,q2,…,qm}表示;有n個逃逸機器人,用P={p1,p2,…,pn}表示。對每個逃逸機器人pi(i=1,2,…,n),存在一個以逃逸者當前位置為中心,感知距離r為半徑建立的安全域,如圖1所示。在安全域邊界上設定e個均勻分布的圍捕點,每個圍捕點由一個圍捕機器人完成,當該逃逸機器人周圍的所有圍捕點均被圍捕機器人占領時,認為該逃逸機器人被圍捕成功,所有逃逸機器人均被圍捕成功時,停止追逃行為,判定群機器人圍捕系統圍捕成功。

圖1 安全域及Fk示意圖

將每一個逃逸機器人看作一個圍捕任務,則共有n個任務,設任務集為S={S1,S2,…,Sn},由圖1可知,每個任務由e個圍捕者共同完成。則圍捕點的集合為{Si1,Si2,…,Sie},即任務Si對應圍捕點集合{Si1,Si2,…,Sie}。

假設圍捕機器人qk(k=1,2,…,m)所對應的圍捕點為Sij(i=1,2,…,n;j=1,2,…,e),qk到Sij的距離Fk如圖1所示,并表示為公式1。

(1)

其中,(xk,yk),(xij,yij)分別為圍捕機器人qk和對應圍捕點Sij在地圖中對應的坐標。

2 基于多種群協同進化的多逃逸者圍捕任務分配策略求解

該文設計了一種基于多種群協同進化遺傳算法來求解群機器人多逃逸者圍捕任務的分配問題。為了保持種群的多樣性,先初始化生成D個不同的編碼組合,在每個組合里再將任務集合S進行合適的分組,一組代表一個種群,通過多種群協同進化的方式得到最終的分配方案,算法流程如圖2所示。

圖2 基于多種群協同進化的任務分配算法流程

多種群協同進化遺傳算法的過程如下:

(1)隨機生成D個不同的編碼組合,在這些組合里,任務集順序保持一致,圍捕者集合的順序隨機生成。

(2)將每一個組合中的編碼按同樣的分組方式對編碼進行劃分分組,來保持合適的編碼長度。

(3)分組后的每一組為一個獨立的種群,每個種群同時進行各自的初始化和交叉、變異、選擇等操作。

(4)將每個種群選擇的最優解按分組順序進行組合,得到最終解。

(5)每個組合均可得到一個最終解,再選擇D個組合中的最優解作為文中算法所得到的分配方案。該分配方案的適應度函數值的大小即為本次算法最終得到的目標函數值。

2.1 個體編碼

第h(h=1,2,…,L)組的個體編碼如圖3所示,每一個編碼表示種群中的一個個體。第一行表示任務Sha(a=1,2,…,w),第二行表示圍捕者qhb(b=1,2,…,ew)。

圖3 第h組個體編碼示意圖

Sha(a=1,2,…,w)為任務集S中按順序排序分配到各組中的任務,qhb(b=1,2,…,ew)為圍捕者集合Q中隨機選取的不重復圍捕者。所有組的任務組合起來為一個完整的任務集S,所有組的圍捕者組合起來為一個完整的圍捕者集合Q,如公式2所示。

(2)

每一組的任務和圍捕者均不會重復,即對L組中任意的兩組h1和h2,都有如下約束條件:

?h1,h2∈{1,2,…,L}{Sh11,Sh12,…,Sh1w}∩{Sh21,Sh22,…,Sh2w}=?

?h1,h2∈{1,2,…,L}{qh11,qh12,…,qh1ew}∩{qh21,qh22,…,qh2ew}=?

(3)

L個種群相互獨立,各自進行交叉變異選擇的過程,互不干擾。

2.2 種群初始化

為了保持種群個體多樣性,首先生成D個不同的組合,其中第一行編碼為任務集S的順序排列,第二行編碼為圍捕者集合Q的隨機亂序排列。將生成的長序列劃分為L個任務組,一組代表一個種群,每個種群由第二行編碼的染色體信息形成Z個不同的個體,表示圍捕任務的第一行編碼初始化后保持不變。

2.3 適應度函數

圍捕機器人完成全部圍捕任務所耗費的步長往往由距離圍捕點最遠的圍捕機器人所決定,對于群機器人多逃逸者圍捕的任務而言,任務分配的目標是使該距離越小越好,因此設定適應度函數Fit為該編碼個體中Fk的最大值。

Fit=max(Fk),k=1,2,…,ew

(4)

適應度函數越小,圍捕效果越好,在選擇過程中選擇適應度函數值更小的個體來進行下一次的交叉和變異。

2.4 交叉算子

如圖4所示,對每一個種群中所有個體各進行下述操作:

圖4 交叉示意圖

相鄰兩個父代個體兩兩為一組進行交叉,每個父代個體均選擇頭部作為交叉點;

設定Cr∈[0,1]為交叉概率,c←rand(0,1),若滿足c≤Cr,則在其中的一個父代個體中隨機選中一段基因位,然后插入到另一個父代個體的頭部,另一個父代個體也選擇相同位置的相同長度的基因段進行相同的操作;

按照所需的基因位長度ew從前到后對重復或多余的基因進行剔除。

在文中的編碼方式下,每個個體的基因位都是唯一且不可隨意缺失的,只可移動位置。僅用普通的交叉算法使兩個父代個體相互交換產生新個體,會導致個體中基因位的缺失或重復,因此采用上述交叉模式既可以保證這一編碼特性,又可為種群提供不同的基因位置組合。

2.5 變異算子

對每個父代個體和交叉產生的子代個體進行變異操作。以個體C為例,Cu和Cv分別表示個體C的第u個和第v個基因位,u為個體中除v以外的隨機位置,Gr←rand(0,1),g∈[0,1]為變異概率。若滿足g≤Gr,則互換Cu和Cv:

(5)

2.6 選擇操作

將初始種群與交叉變異后的進化種群組合在一起,按照適應度函數值由小到大進行排序,選取Z個最佳個體組成新的初始種群繼續進化,達到所設定的迭代次數G時停止進化。這樣,每一代都保留了種群中的優良個體,促使種群持續探索更好的解。

3 機器人圍捕方法和仿真平臺

3.1 圍捕方法

機器人圍捕過程如下:

step1:構建圍捕地圖環境,隨機生成障礙物和各機器人,相互之間不重合,并獲取位置坐標。

step2:根據逃逸者的坐標生成期望圍捕點。

step3:用多種群協同進化遺傳算法選擇最優任務分配策略。

step4:各圍捕機器人通過人工勢場法確定運動方向。

step5:每行走一步,更新各機器人位置信息。

step6:判斷所有圍捕機器人是否到達對應的圍捕點,若是,則圍捕成功,圍捕結束;若否,則繼續進行圍捕。

3.2 仿真平臺

基于Java語言在Windows 10環境下開發了一個群機器人多逃逸者圍捕仿真平臺,如圖5所示。所有機器人在二維平面內運動,撞到邊界則更換運動方向,目標機器人的運動方向設為隨機。目標安全域半徑r設為20,設定6個圍捕機器人圍捕1個逃逸機器人。在受限的地圖環境中,因為逃逸者永遠逃離不出地圖邊界,因此將圍捕者速度設為和逃逸者速度相等,設置所有機器人的運動步長t為4。在設定好機器人的初始位置和障礙物的位置后,打開仿真平臺會在界面上顯示每個個體的位置,其中小圓形表示圍捕者,小三角形表示逃逸者,障礙物用大圓形和大三角形表示。然后各機器人開始運動,待圍捕完成時,整個平臺所有個體暫停運動,結束圍捕。

圖5 仿真平臺中圍捕過程示意圖

以8個逃逸者為例,來演示仿真平臺從初始化生成到全部圍捕任務結束的過程,即n=8,m=48。障礙物個數設為10,隨機生成在地圖中,并不與機器人位置重合。其中圓形障礙物5個,三角形障礙物5個。當所有逃逸機器人均被圍住時,所有機器人才停止運動,圍捕結束,圍捕過程如圖5所示。

4 仿真實驗與分析

為了驗證所提算法的有效性,結合第三節中的仿真平臺,首先給出初始參數設置,然后對比分析所提算法在目標函數上的優勢,最后將設計的多種群協同優化遺傳算法與算法1和算法2進行深入的對比分析。

4.1 參數設置

對于多種群協同優化算法而言,不同參數的選取對其效果有著至關重要的影響。選取逃逸者數量n為16,且每組實驗都保證除所要探求的參數不同,其他完全相同,每組均做30組實驗求取目標函數平均值。表1表示每組任務數w、種群個體數Z和初始化時生成的編碼組合數D對實驗結果的影響,表2表示交叉概率Cr、變異概率Gr對實驗結果的影響。

表1 不同參數下的目標函數均值

表2 不同交叉、變異概率下的目標函數均值

種群個體數和編碼組合數過多也會增加算法計算量和復雜度,綜合考慮,每組的任務數目w設為4,種群個體數Z設為100,編碼組合數D設為10,交叉概率Cr設為0.9,變異概率Gr設為0.3較為合適。

圖6表示在逃逸者數量n為16時,執行一次多種群協同優化算法的收斂曲線,在迭代次數達到200時算法進入非常穩定的狀態,因此將遺傳算法的最大迭代次數G設為200。

圖6 收斂曲線

4.2 目標函數對比

為了保證實驗的合理性,在不同的逃逸機器人數量下,分別做10組不同的機器人初始坐標下的實驗,記錄目標函數的值,每組記錄30組數據,比較3種算法的效果。表3給出了3種算法在不同測試實例下的目標函數值(均值±標準差)。

表3 不同分配算法下的目標函數值(均值±標準差)

可以看出,在不同逃逸者數量的9個實例上,文中算法相比其他算法均獲得了更小的目標函數值,可見文中算法能極大地縮短圍捕機器人到對應圍捕點的移動距離。標準差的大小隨著n的增加逐漸降低,是因為隨著逃逸者數目的增加,在有限的地圖環境里各個機器人的分布逐漸密集,在每個區域內的機器人數量逐漸均衡,每種算法對不同初始坐標下的機器人所產生的目標函數越來越接近。

算法2整體差于算法1與文中算法,在逃逸機器人數量為2時,算法1與文中算法形成的分配策略的目標函數差異不明顯。隨著n的增加,文中算法的優勢逐漸體現出來,在逃逸者數目較多的情況下,文中算法能生成一個更優的分配策略,其對應的目標函數值相比于其他兩個算法均較小。

4.3 圍捕步數對比

以捕獲所有逃逸者時圍捕者的移動步數為指標,對于組建追捕團隊采取文中算法和算法1、算法2來測試3種策略對圍捕結果的影響。

4.3.1 障礙物對圍捕步數的影響

設置逃逸者數量為8,進行兩組實驗,一組是固定障礙物數量為10,在障礙物位置越來越擁堵的情況下進行10次實驗,結果如圖7(a)所示;另一組是障礙物數量從6增加到16,進行10次實驗,結果如圖7(b)所示。每次實驗的圍捕步數由30次不同機器人初始坐標下的實驗結果取均值來獲得。

圖7 障礙物對圍捕步數的影響

實驗結果表明,在障礙物更擁堵的情況下,在某些機器人行走到該障礙物區域時,機器人的避障行為增多,機器人移動的步數會略微增加,但障礙物的位置對實驗結果并不會造成很大的影響,文中算法仍占優勢。隨著障礙物數量的增加,3種算法下圍捕機器人的移動步數均會略微增加,是因為障礙物數量越多,機器人進行的繞行就越多,會增加機器人的移動步數。

4.3.2 不同逃逸者數量下的圍捕步數對比

對不同逃逸者數量n,在相同障礙物數量和位置下,采取人工勢場法[10]避障,分別做10組不同機器人初始坐標下的圍捕實驗,每組運行30次求均值,記錄圍捕機器人的最大移動步數。圖8給出了對應的結果。

圖8 采用人工勢場法,不同測試實例下的圍捕步數

文中算法在逃逸者數量從4增加到14的情況下,能夠有效縮短圍捕機器人系統的最大圍捕步數。算法1和算法2在本質上都是一種貪婪算法,其主要通過最小化圍捕機器人與目標的距離來實現分配。貪婪行為機制使其行為選擇是為了使自己的利益獲得最大,團隊成員之間沒有協作,這樣形成的分配策略非常不均衡。文中的任務分配策略通過遺傳算法綜合判斷和選擇不同團隊可能性,形成合理的追捕團隊,并考慮團隊成員之間相互協調,提高捕獲效率。相比算法1和算法2,文中算法考慮了團隊協作,避免了分配策略不均衡導致整體圍捕效率降低的問題,表現更優。

以上仿真實驗證明,文中算法在不同初始化環境和不同障礙物勢態下均有優勢,完成同樣的圍捕任務下,與算法1相比圍捕步數差最高可達約60步,與算法2相比圍捕步數差最高可達約90步,有效地提高了圍捕效率。在完成圍捕任務所耗費的步數上比算法1最多降低了約15%,圍捕效率最大提高了約18%;比算法2最多降低了約20%,圍捕效率最大提高了約25%。

5 結束語

該文研究群機器人協同圍捕多逃逸者問題,提出了一種基于多種群協同進化的多逃逸者圍捕任務分配算法,根據該算法對目標函數進行優化,在理論上通過計算目標函數值來證明該算法的有效性,在仿真實驗中通過對圍捕步數的比較證明該算法的可行性,并在不同的仿真環境中進行實驗,證明該算法的通用性。該算法實現了圍捕任務的均衡分配,提高了整個群機器人圍捕系統的圍捕效率。在今后的研究工作中,如果障礙物不是靜止而是處于運動狀態,該如何避障進行路徑規劃,這將是下一步研究的重點內容。