多智能體動態目標協同搜索策略研究

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

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

0 引言

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

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

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

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

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

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

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

1 協同搜索策略

1.1 拓撲地圖提取

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

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

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

1.2 基于強化學習的協同搜索策略

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

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

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

2 動態目標的躲避策略

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

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

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

式中，F rep表示目標在ST位置受到的斥力。

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

圖3 動態目標基于動作的躲避策略示意圖

3 仿真校驗

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

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

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

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

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

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

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

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

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

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

4 結束語

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