多智能體動態(tài)目標協(xié)同搜索策略研究

趙梓良，劉 洋，李博倫，馬力超，張志彥

（北京機械設備研究所，北京 100039）

0 引言

隨著建圖定位、目標識別、機器學習和通信組網(wǎng)等技術的成熟，無人智能體以其運算速度快、運動速度快、能長時間作業(yè)、能在極端環(huán)境下作業(yè)等特點，在目標搜索課題中受到青睞，被期望替代人類在危險、惡劣環(huán)境中高效長時間執(zhí)行巡邏、偵察和搜救任務[1]。而多智能體的集群協(xié)作作業(yè)又能大大提升目標搜索任務的完成效率。

多智能體集群搜索策略是多機器人領域中一個重要的研究課題，通過一個顯示控制平臺和多個智能單體（如無人機）之間的協(xié)同策略規(guī)劃，完成對一定區(qū)域內的靜止、運動目標的搜索任務[2?7]。多智能體集群搜索策略設計主要包括2個步驟，一是智能體對待搜索環(huán)境場景的理解與建圖，二是智能體對待搜索環(huán)境場景的協(xié)同搜索策略設計。

目前環(huán)境地圖的典型表示方法包括尺度地圖和拓撲地圖2種。其中尺度地圖基于直接度量信息表示環(huán)境細節(jié)，為地圖中最小單位區(qū)域（柵格）賦值，如用0表示自由空間而用1表示障礙物。拓撲地圖則是提取自由空間中的關鍵節(jié)點，并用邊連接相鄰的節(jié)點，形成拓撲網(wǎng)絡結構[8]。與尺度地圖相比，拓撲地圖表示相同環(huán)境地圖所需的數(shù)據(jù)信息更少，因此更適合在大型、復雜環(huán)境下執(zhí)行目標搜索和巡邏等任務[8?10]。

圖2 由示例場景尺寸地圖提取出的拓撲地圖

目前在多智能體對環(huán)境區(qū)域進行協(xié)同搜索的研究成果中，2種典型的搜索策略為：基于貪心算法的路徑規(guī)劃策略[11?13]與基于拓撲地圖區(qū)域劃分和分區(qū)最優(yōu)回路求解的多級子圖巡邏(MSP)策略[14?16]?；谪澬乃惴ǖ穆窂揭?guī)劃策略將路徑點盡量平均地分配給每個智能體，使完成各自路徑需要耗費的時間中最長的智能體的時間最短。應用該類方法的搜索系統(tǒng)在理論上能完成對區(qū)域的快速覆蓋搜索，但由于各智能單體的規(guī)劃路徑中首末位置距離較遠，在搜索環(huán)境較復雜、搜索場景中障礙物較多的情況下，智能體返回起點過程容易宕機，因此不適用于長時間復雜環(huán)境的區(qū)域搜索和巡邏?；谕負涞貓D劃分和分區(qū)最優(yōu)回路求解的多級子圖巡邏策略首先根據(jù)多層k劃分法折疊頂點和邊來減小圖的大小，對較小的圖進行k劃分、再分解和細化后構建原始圖的k路區(qū)域劃分，最后對劃分后的子拓撲地圖求解最優(yōu)回路問題，依次判定是否存在歐拉回路、哈密頓回路、非哈密頓回路與最長搜索路徑，并作為子拓撲地圖內單體的搜索路線。應用該類方法的搜索系統(tǒng)解決了貪心算法規(guī)劃的路徑不閉合、巡邏過程易宕機問題，能長時間循環(huán)執(zhí)行搜索、巡邏任務，并在搜索靜態(tài)目標時有良好的表現(xiàn)。但該策略仍然存在在各智能單體負責的區(qū)域邊界地帶搜索效果不佳、巡邏路線過于規(guī)律、容易被目標人或具有感知和決策能力的目標智能體掌握并學習規(guī)避的問題。并且在實際場景中，智能體的故障會導致其負責巡邏的區(qū)域的搜索失效，該區(qū)域成為盲區(qū)。

目前搜索場景中動態(tài)目標的躲避策略方面的研究較少，動態(tài)目標多采取隨機運動策略或規(guī)律性巡線運動策略。而在被廣泛研究的追捕?逃跑模型課題中，模型中目標的逃跑策略則能為搜索場景下目標人或具有感知和決策能力的目標智能體的躲避策略設計提供參考。

基于上述目標搜索方法的啟發(fā)，本文提出了一種防具備躲避策略的動態(tài)目標的協(xié)同搜索策略。運用強化學習框架使多智能體和具備躲避策略的目標進行對抗性的搜索訓練，讓多智能體集群搜索系統(tǒng)不斷訓練、修正和優(yōu)化搜索策略，提高針對動態(tài)目標的搜索效率和應對單體宕機問題的魯棒性。

1 協(xié)同搜索策略

1.1 拓撲地圖提取

如前文所述，拓撲地圖相比于尺度地圖，表示環(huán)境所需的數(shù)據(jù)信息更少，更適用于目標搜索任務，其數(shù)據(jù)信息可以表示為G=(V，E)，其中V表示地圖中的關鍵節(jié)點集合，而E表示連接關鍵節(jié)點的邊以及該條邊的長度[8]。而實際建圖的激光雷達等傳感器獲取的是占據(jù)柵格地圖，因此首先需要將原始的柵格地圖轉換成拓撲地圖[17]。圖1?2展示了從尺度地圖提取出拓撲地圖的示例效果。

圖1 gmapping算法建圖獲得的場景尺寸地圖

上述拓撲地圖提取的方法是通過對環(huán)境區(qū)域進行廣度優(yōu)先搜索，先計算地圖中自由空間的連通區(qū)域，根據(jù)智能體的尺寸對柵格地圖中的障礙物邊緣輪廓進行填充擴展，確保智能體既能在最終拓撲地圖相鄰的節(jié)點間通行又不會與障礙物邊緣碰撞；再通過擴展泰森多邊形圖（EVG）的方法以均勻的節(jié)點和邊表示環(huán)境地圖的拓撲信息[8，17]。

1.2 基于強化學習的協(xié)同搜索策略

對于優(yōu)化具有躲避策略的動態(tài)目標的協(xié)同搜索效率問題，難點在于智能體對環(huán)境場景的搜索經驗的缺失。而Q-learning強化學習框架可以不要求先驗數(shù)據(jù)，通過訓練不斷優(yōu)化搜索策略。在該強化學習系統(tǒng)中，決策者通過觀察環(huán)境，根據(jù)當前狀態(tài)下的觀測信息做出動作嘗試，并接受環(huán)境對動作嘗試的獎勵和懲罰反饋來獲得學習信息并不斷更新搜索策略的Q值表。Q值表的行索引對應決策者所處的狀態(tài)，列索引對應在某一狀態(tài)下執(zhí)行的動作嘗試，更新對應行列的Q值會不斷修正決策者進行動作嘗試的概率。在這個過程中符合設計目的的動作會獲得獎勵，決策者再次遇到同樣場景會更傾向于采取這一動作，而與設計目的不符的動作則會得到懲罰，決策者會盡量避免這樣的動作。經過若干次嘗試，決策者對其所處的環(huán)境有了充分的理解，知道在某一狀態(tài)下獲得盡可能大的獎勵的動作[18?20]。Q-learning強化學習框架中策略的更新可以表示為：

式中，S表示智能體當前狀態(tài)，A表示智能體在S狀態(tài)下采取的動作，Q(S,A)表示在S狀態(tài)下采取A動作的Q值，R(S,A)表示在S狀態(tài)下采取A動作的即時獎勵，S′表示在S狀態(tài)采取A動作后的下一狀態(tài)，α為學習率，γ為折扣因子。

在本文提出的協(xié)同搜索策略中，智能體所處狀態(tài)的集合（狀態(tài)空間）為拓撲地圖中關鍵節(jié)點集合V。而智能體在每一狀態(tài)下可采取的動作集合（動作空間）為拓撲地圖中與該狀態(tài)對應的節(jié)點相連通的節(jié)點，表示由當前狀態(tài)對應的節(jié)點向可通行的下一節(jié)點運動的動作。初始策略設置為隨機搜索，智能體隨機選擇在各個狀態(tài)下的動作，該策略表示為值均為0的Q值表。獎勵在一次搜索完成后反饋給智能體搜索到目標必要路徑上的所有狀態(tài)，以激勵決策者在后續(xù)到達這些狀態(tài)時盡可能選擇發(fā)現(xiàn)目標概率更大的動作。在多智能體系統(tǒng)中，智能單體在各個狀態(tài)下選擇動作的策略具有共通性，因此設計系統(tǒng)中的智能體共用一個Q值表，增加訓練效率。而為了避免所有智能單體根據(jù)Q值表采取相同動作，參考基于節(jié)點空閑時間的巡邏策略[18,21]對即時策略做出調整。基于節(jié)點空閑時間的巡邏策略提出由主控平臺發(fā)布拓撲地圖中各節(jié)點的空閑時間信息，各智能體自由搶占附近空閑時間長的節(jié)點作為目標點。參照此方法中節(jié)點空閑時間設置方式，對任一智能體，將空閑時間不超過某一閾值的節(jié)點，即剛被訪問過的節(jié)點的Q值即時調整為0，以避免多智能體互相跟隨或在局部回路轉圈等問題。

2 動態(tài)目標的躲避策略

人工勢場法[22]及其優(yōu)化方法在局部路徑規(guī)劃和追捕?逃跑研究課題中被廣泛應用，該類方法根據(jù)物體當前位置及其周圍的障礙物、追捕者和目標點的位置關系，在目標周圍設置虛擬力場，其中障礙物、追捕者在物體的感知范圍內對物體產生斥力，而目標點對物體產生引力，且力場強度由物體之間相對距離決定。物體在該虛擬力場影響下進行局部路徑規(guī)劃，避開障礙物和追捕者向目標點移動。但在多智能體集群搜索策略研究中，上述基于相對位置關系的人工勢場法并不適用。與追捕?逃跑問題中追捕者根據(jù)逃跑者的位置進行包圍不同，搜索場景下搜索者在搜索到目標前并不能獲知目標的位置和與目標的距離。因此以與搜索者的距離作為影響動態(tài)目標的躲避策略的依據(jù)與實際情況不符。

考慮在實際搜索場景中，目標人物與作為搜索者的智能單體（如無人機）觀測、識別距離相近，而目標人物可以依據(jù)無人機運行過程中旋翼的槳葉發(fā)出的聲音判斷其感知范圍內有無搜索者靠近或遠離，然后進行躲避的行為，設置了一種基于動作（位置變化）的人工勢場法的躲藏策略。該策略中目標不僅感知一定范圍內的搜索者的位置，同時感知該范圍內的搜索者較自己執(zhí)行的動作（靠近或遠離），僅計算靠近的搜索者施加的斥力作為躲避動作的決策依據(jù)。目標感知范圍內搜索者對目標的斥力場[23]可以表示為：

式中，U rep表示該位置的斥力場大小，ST為目標位置，SN為N號搜索者位置，η為斥力尺度因子，ρ為2點之間的距離，ρ0為搜索者影響半徑。目標受斥力大小則是其感知范圍內斥力場的梯度,可以表示為：

式中，F(xiàn) rep表示目標在ST位置受到的斥力。

圖3給出了該躲避策略的示意圖。目標當前所處位置為ST，圓內區(qū)域為目標ST的當前感知范圍，S1—S5表示其周圍搜索者的位置，實線箭頭方向為目標感知的搜索者動作方向。在該狀態(tài)下，目標ST僅考慮觀測范圍內向其靠近的搜索者S2和S3的動作進行躲避，圖中虛線表示的向量示意了這一躲避策略的決策過程。

圖3 動態(tài)目標基于動作的躲避策略示意圖

3 仿真校驗

為驗證動態(tài)目標躲避策略的效果和經過對抗訓練得到的協(xié)同搜索策略的有效性，在三維仿真平臺Gazebo中分別設置靜態(tài)目標搜索和動態(tài)目標搜索仿真實驗，校驗選用圖1的場景進行，場景總面積為450.0 m2，其中可通行區(qū)域約317.9 m2，障礙物區(qū)域面積約132.1 m2。圖4展示了場景和場景中4個初始狀態(tài)的智能體、1個隨機目標的仿真可視化實景。

圖4 Gazebo平臺中仿真場景和場景中4個位于初始區(qū)域的智能體（左上黑點）及1個位于隨機位置的目標（右上藍點）

對于靜止目標搜索，在環(huán)境地圖中同一初始區(qū)域（搜索出發(fā)區(qū)）內，分別加載1—10個配置有定位、感知與識別、決策與驅動等功能模塊的無人機模型作為搜索者，以及1個初始位置隨機的目標人物模型作為目標。搜索者同時從搜索出發(fā)區(qū)出發(fā)，分別對整個區(qū)域按照文獻[14]提出的多級子圖巡邏策略和本文提出的訓練后協(xié)同策略（Q值表）展開搜索。當目標人物位置與任一搜索者距離小于1 m且不被遮擋時，視為發(fā)現(xiàn)目標并完成一個校驗回合，同時記錄本次校驗的搜索時間。由于在本文校驗中選用的拓撲地圖邊長相近（平均邊長0.499 m，標準差0.031 m）、智能體在各節(jié)點停留的時間相近但難以測算，因此統(tǒng)計搜索者搜索的節(jié)點數(shù)量（即步數(shù)）表示搜索時間，提高訓練速度。搜索者數(shù)量從1個依次增加至10個，分別重復10 000個校驗回合。

對于動態(tài)目標搜索，只需在上述靜態(tài)目標搜索仿真校驗的基礎上為初始位置隨機的目標人物配置定位、感知與識別、躲避策略與驅動功能。同樣地將搜索者數(shù)量從1個依次增加至10個，重復10 000個校驗回合。

圖5展示了不同數(shù)量智能體應用文獻[14]提出的多級子圖巡邏策略，對靜止目標和具備本文提出的躲避策略的動態(tài)目標搜索的平均步數(shù)。校驗結果表明，本文提出的基于動作的人工勢場法的躲避策略會大大增加現(xiàn)有巡邏策略的搜索難度。原因是能精確判斷搜索者動作的目標可以在多個智能體各自負責的區(qū)域邊界間反復移動，規(guī)避搜索者。與隨機的靜止目標搜索相比，應用巡邏策略搜索具備躲藏策略的動態(tài)目標平均搜索步數(shù)增加了2.0倍，證明了動態(tài)目標躲避策略的有效性以及改進現(xiàn)有多極子圖巡邏策略的必要性。

圖5 巡邏策略對靜止目標和應用躲避策略的動態(tài)目標搜索結果對比

圖6展示了不同數(shù)量智能體應用多級子圖巡邏策略和訓練后的協(xié)同搜索策略（智能搜索策略）對于靜止目標搜索所需的平均步數(shù)。當智能單體搜索靜態(tài)目標時，巡邏策略表現(xiàn)更為優(yōu)秀。但當智能體數(shù)量大于1時，2種策略完成目標搜索的整體搜索效率相近。搜索者數(shù)量為3到10個時，2種策略平均搜索步數(shù)差值均在1.0步內，且隨著搜索者數(shù)量的增加，2種策略完成目標搜索的平均步數(shù)都呈下降趨勢，并最終收斂趨近于9.0步，證明對于靜態(tài)目標，2種搜索方式具備相近的整體表現(xiàn)。

圖6 靜止目標搜索效率仿真校驗

圖7展示了巡邏策略和智能搜索策略對于有躲避能力的動態(tài)目標進行搜索所需的平均步數(shù)。其中單個搜索者的情況下，智能搜索策略所需時間過長，視為無法完成搜索任務。對于有躲避能力的運動目標，智能搜索策略比巡邏策略整體表現(xiàn)更佳。當智能體數(shù)量大于1時，智能搜索策略較巡邏策略，平均搜索效率提升了48.5個百分點，且隨著搜索者數(shù)量的增加，2種策略完成目標搜索的平均步數(shù)都呈下降趨勢。

圖7 運動目標搜索效率仿真校驗

4 結束語

本文提出了一種在已知環(huán)境下搜索靜態(tài)目標和具備躲避能力的動態(tài)目標的協(xié)同搜索策略。在該搜索策略中，地圖信息的提取采用了拓撲地圖，以較少的數(shù)據(jù)量表示環(huán)境信息。初始搜索策略采用隨機搜索策略，通過Q-learning強化學習框架不斷訓練更新并基于節(jié)點空閑時間即時調整。目標的躲避策略參照路徑規(guī)劃和追捕問題中基于位置的人工勢場法設計了基于動作的人工勢場法。通過仿真校驗，校驗了動態(tài)目標躲避策略的有效性，并通過與現(xiàn)有多極子圖巡邏策略的對比仿真，證明了對于靜態(tài)目標，本文所提協(xié)同搜索策略與多級子圖巡邏策略整體表現(xiàn)相近，而對于具備躲避決策能力的動態(tài)目標，本文所提協(xié)同搜索策略的搜索效率有較大提升。同時協(xié)同搜索策略解決了多級子圖巡邏策略中單體故障會導致其轄區(qū)成為盲區(qū)的問題。后續(xù)將進行算法移植，開展實物驗證實驗，并針對優(yōu)化目標躲避模型或增加環(huán)境信息復雜度等方向開展進一步研究。■