基于多種群協(xié)同進(jìn)化的多逃逸者圍捕任務(wù)分配

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

(1.合肥工業(yè)大學(xué) 計算機與信息學(xué)院,安徽 合肥 230601;2.大數(shù)據(jù)知識工程教育部重點實驗室(合肥工業(yè)大學(xué)),安徽 合肥 230601;3.智能互聯(lián)系統(tǒng)安徽省實驗室(合肥工業(yè)大學(xué)),安徽 合肥 230009;4.工業(yè)安全應(yīng)急技術(shù)安徽省重點實驗室(合肥工業(yè)大學(xué)),安徽 合肥 230601)

0 引 言

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

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

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

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

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

1 問題描述

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

圖1 安全域及Fk示意圖

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

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

(1)

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

2 基于多種群協(xié)同進(jìn)化的多逃逸者圍捕任務(wù)分配策略求解

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

圖2 基于多種群協(xié)同進(jìn)化的任務(wù)分配算法流程

多種群協(xié)同進(jìn)化遺傳算法的過程如下:

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

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

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

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

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

2.1 個體編碼

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

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

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

(2)

每一組的任務(wù)和圍捕者均不會重復(fù),即對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個種群相互獨立,各自進(jìn)行交叉變異選擇的過程,互不干擾。

2.2 種群初始化

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

2.3 適應(yīng)度函數(shù)

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

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

(4)

適應(yīng)度函數(shù)越小,圍捕效果越好,在選擇過程中選擇適應(yīng)度函數(shù)值更小的個體來進(jìn)行下一次的交叉和變異。

2.4 交叉算子

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

圖4 交叉示意圖

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

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

按照所需的基因位長度ew從前到后對重復(fù)或多余的基因進(jìn)行剔除。

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

2.5 變異算子

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

(5)

2.6 選擇操作

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

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

3.1 圍捕方法

機器人圍捕過程如下:

step1:構(gòu)建圍捕地圖環(huán)境,隨機生成障礙物和各機器人,相互之間不重合,并獲取位置坐標(biāo)。

step2:根據(jù)逃逸者的坐標(biāo)生成期望圍捕點。

step3:用多種群協(xié)同進(jìn)化遺傳算法選擇最優(yōu)任務(wù)分配策略。

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

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

step6:判斷所有圍捕機器人是否到達(dá)對應(yīng)的圍捕點,若是,則圍捕成功,圍捕結(jié)束;若否,則繼續(xù)進(jìn)行圍捕。

3.2 仿真平臺

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

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

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

4 仿真實驗與分析

為了驗證所提算法的有效性,結(jié)合第三節(jié)中的仿真平臺,首先給出初始參數(shù)設(shè)置,然后對比分析所提算法在目標(biāo)函數(shù)上的優(yōu)勢,最后將設(shè)計的多種群協(xié)同優(yōu)化遺傳算法與算法1和算法2進(jìn)行深入的對比分析。

4.1 參數(shù)設(shè)置

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

表1 不同參數(shù)下的目標(biāo)函數(shù)均值

表2 不同交叉、變異概率下的目標(biāo)函數(shù)均值

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

圖6表示在逃逸者數(shù)量n為16時,執(zhí)行一次多種群協(xié)同優(yōu)化算法的收斂曲線,在迭代次數(shù)達(dá)到200時算法進(jìn)入非常穩(wěn)定的狀態(tài),因此將遺傳算法的最大迭代次數(shù)G設(shè)為200。

圖6 收斂曲線

4.2 目標(biāo)函數(shù)對比

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

表3 不同分配算法下的目標(biāo)函數(shù)值(均值±標(biāo)準(zhǔn)差)

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

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

4.3 圍捕步數(shù)對比

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

4.3.1 障礙物對圍捕步數(shù)的影響

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

圖7 障礙物對圍捕步數(shù)的影響

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

4.3.2 不同逃逸者數(shù)量下的圍捕步數(shù)對比

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

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

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

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

5 結(jié)束語

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