多仿生機器人協(xié)同編隊捕獲策略

楊 丹，馮世龍，石立偉，郭書祥

（北京理工大學，北京 100081）

0 引言

近年來，隨著全球人口不斷增加和陸地資源勘探的持續(xù)進行，人們開始將眼光轉(zhuǎn)移至海洋。作為海洋資源勘探和開發(fā)的得力助手，仿生機器人被廣泛應用。仿生機器人受益于生物的高度進化感知系統(tǒng)和智能決策能力，能夠模仿水下生物的外形和動作方式，從而更好地適應水下環(huán)境中的障礙物等未知因素。它們可以通過柔軟和靈活的身體結(jié)構(gòu)，在狹小空間中自如穿行，并有效地避開障礙物，實現(xiàn)更精確的編隊搜索任務。此外，仿生機器人可以借鑒生物界中生物群體的協(xié)同行為，實現(xiàn)高效的信息交流和協(xié)作。它們可以通過模擬生物間的非語言溝通方式，如振動、化學信號等，實現(xiàn)機器人之間的緊密配合和協(xié)同行動，提高編隊任務的效率和準確性。

現(xiàn)階段針對單一機器人的編隊研究已經(jīng)相對成熟，而多機協(xié)作任務成為了國內(nèi)外學者們關(guān)注的重點研究方向[1-4]。該技術(shù)的主要目標是實現(xiàn)多個機器人按照某一編隊策略，將目標機器人限制在一定預定大小的區(qū)域內(nèi)，使其無法逃逸，以達到對目標的捕獲目的。然而，由于水下環(huán)境具有復雜的障礙物和大量的未知因素以及水下機器人形體大小和計算能力的限制，多仿生機器人的編隊任務目前依然存在許多困難。因此，進行多仿生機器人協(xié)同編隊捕獲策略的研究具有重要意義。

目前，國內(nèi)外學者針對多機器人協(xié)同編隊策略已經(jīng)開展了大量的研究。路徑規(guī)劃部分，陳銘治和NI等[5-6]采用神經(jīng)網(wǎng)絡模型，通過改進神經(jīng)元的權(quán)值來使其更加適用于實時路徑規(guī)劃，但該算法需要大量的計算，對機器人計算性能具有較高的要求，不適用于小型水下仿生機器人。陳世健和趙文瑜等[1，7]采用BUG2算法，使機器人朝目標做直線運動或繞障礙物的靠邊運動，以移動到目的地，但該方法規(guī)劃出的路徑不一定具有最優(yōu)性，無法保證路徑長度最短。YU等[8]將RTT*算法進行改進，提出一種Cyl-HRRT*算法，通過將狀態(tài)偏向到圓柱形子集來引導采樣和擴展，以改善當前解決方案。雖然該算法考慮到小型球形機器人的機械結(jié)構(gòu)和自身動力學的限制，但反而會增加算法復雜度，導致計算效率降低。

多機器人編隊任務的成功關(guān)鍵除路徑的最優(yōu)性外還包括它們之間任務的分配及協(xié)調(diào)，協(xié)調(diào)策略的優(yōu)劣影響任務的整體效率。NI等[6]根據(jù)圍捕子區(qū)域與目標點間的距離進行目標捕獲點分配，該策略以距離最近為目標進行貪婪的分配，但會導致不同機器人到各自捕獲點的時間差較大，影響整個編隊捕捉任務的實時性和效率。劉云輝和陳陽舟等[9-10]采用“角度最小”原則，根據(jù)“目標–捕獲點”連線與“目標–機器人”連線的夾角最小進行貪婪的分配，但當2個機器人具有相同夾角的情況時，該分配策略會陷入死鎖問題。

本文旨在針對上述編隊策略及路徑規(guī)劃部分存在的問題提出了一種基于改進蟻群算法的安全域協(xié)商編隊捕獲策略。本文采用動態(tài)調(diào)整啟發(fā)式信息素因子的改進蟻群算法，以實現(xiàn)自適應避障的路徑規(guī)劃；采用安全域協(xié)商法實現(xiàn)目標機器人周圍期望捕獲點的實時分配[11]，并保證各機器人到達捕獲位置的時間盡量接近，以提高整體任務效率。本文的研究目標是實現(xiàn)多仿生機器人在水下障礙環(huán)境中的高效協(xié)同編隊，具有重要的理論意義和應用價值。

1 問題描述與建模

1.1 多仿生機器人協(xié)同編隊搜索問題描述

整個問題建立在有邊界的多障礙物環(huán)境X中，設有n個搜索機器人R＝{R1,R2......Rn}對位置未知的移動目標點u進行捕獲。捕獲成功的條件為：搜索機器人在目標探測區(qū)域均勻分布或?qū)⒛繕藝г诃h(huán)境邊界。

1.2 仿生機器人水下運動方程

整個搜索過程中，需要對搜索機器人以及移動目標的運動速度及角度進行控制。設搜索機器人及目標點正常行進速度為v，目標點發(fā)現(xiàn)搜索機器人逃逸速度為1.1v。機器人在t時刻的運動模型可表示為下式：

式中：(x(t),y(t))為各機器人在t時刻的位置；v(t)為t時刻的速度；θ(t)為t時刻速度方向；ω(t)為t時刻的角速度。

1.3 目標點安全域位置

在編隊捕獲任務中，目標點具有逃逸能力，一旦目標點在可探測區(qū)域發(fā)現(xiàn)搜索機器人的位置，就會以1.1倍的速度進行逃跑行為，為避免該追逐階段增加捕獲成功的難度，引入安全域的概念，在所有機器人均到達所分配給它們的捕獲點之前，不允許某一搜索機器人單獨進入安全域，以避免目標逃逸。

胡俊等[12]將整體搜索環(huán)境采用柵格法表示，將安全域設計為方形，由于本文環(huán)境未進行柵格化處理，所以將安全域定義如下[13]：

式中：SD為目標的安全域；(x,y)為安全域內(nèi)任意一點坐標；(xm,ym)為目標點位置坐標；d為目標機器人可探測范圍。

1.4 目標的捕獲點模型

在搜索機器人進行目標搜索過程中，若iR發(fā)現(xiàn)目標點u的位置，就按照上面所述方法生成目標點的安全域。為防止目標丟失并提高編隊捕獲效率，第一個捕獲點1m應該位于目標機器人速度反方向與安全域的交點，這樣可以確保該捕獲點上的機器人與目標始終保持一定距離，并最大限度的減少目標逃逸的概率。其余捕獲點從1m開始在安全域圓上以順時針均勻分布，捕獲點的總數(shù)量與搜索機器人的數(shù)量保持一致。同時，為了更好地掌握目標點的動態(tài)變化，我們需要不斷地更新目標點的安全域，并對已有的捕獲點進行必要的調(diào)整，以確保任務成功實現(xiàn)。

所期望的捕獲點im的位置信息可用式（3）表示：

式中：i的取值范圍為(1,2,3,...,n)，(xmi,ymi)為捕獲點i的坐標；uθ為目標點的速度方向；iα為捕獲點im與捕獲點1m之間的夾角。

2 協(xié)同編隊捕獲任務

2.1 安全域協(xié)商的圍捕點分配策略

根據(jù)式（3）得到目標周圍期望捕獲位置后，需要對捕獲點進行分配。在實際應用中，目前常用的捕獲點分配策略包括角度優(yōu)先策略[1]和距離分配策略[14]，這2種方法均基于貪婪原則，分別以最小化搜索機器人與目標位置的角度或最小化距離作為分配依據(jù)，實現(xiàn)搜索機器人與期望捕獲位置的逐一對應。

圖4（a）為按角度優(yōu)先策略分配捕獲點的示意圖，該策略可以有效減少搜索機器人與目標位置之間的旋轉(zhuǎn)距離，在一定程度上提高編隊成功率，但當搜索機器人的“目標–分配點”與“目標–機器人”角度相同時，該分配策略會造成死鎖問題，如圖4（b）所示。

圖5為按距離最短原則分配捕獲點示意圖，但該方法只考慮到搜索機器人與目標之間的直線距離，并未考慮到各機器人到達捕獲位置的時間不同步問題。

本文利用基于安全域協(xié)商法的捕獲點分配策略，在使各機器人到達捕獲點的時間差較小的條件下使總路徑最短。該算法實現(xiàn)步驟如圖6所示。

2.2 基于改進蟻群算法的路徑規(guī)劃策略

群智能算法目前已成為受自然啟發(fā)的熱門算法之一，被廣泛用于各種經(jīng)典NP問題的求解中，展現(xiàn)了它優(yōu)異的性能和廣泛適用性[15]。

在群智能算法中，蟻群算法是一種模仿螞蟻覓食行為的啟發(fā)式優(yōu)化算法，該算法計算成本低，對小型仿生水下機器人的路徑規(guī)劃問題具有良好適用性。本文引入啟發(fā)式信息對傳統(tǒng)的蟻群算法存在的易陷入局部最優(yōu)解以及收斂速度慢等問題進行了改進，以提高路徑規(guī)劃的性能。

在傳統(tǒng)蟻群算法中，螞蟻僅依靠信息素進行路徑選擇，容易陷入局部最優(yōu)解[16]。為了使螞蟻更好地探索整個搜索空間，本文引入啟發(fā)式信息作為路徑選擇的輔助條件。啟發(fā)式信息的計算公式如下：

式中：Hij為從位置i到位置j的啟發(fā)式信息濃度；Dij為從位置i到位置j的啟發(fā)式信息距離。

根據(jù)信息素濃度和啟發(fā)式信息，螞蟻計算下一步每個可移動方向的概率大小。為了保證方向的全面性和計算的便利性，下一步位置j可以是當前位置i上下左右以及斜對角線45°的8個方向之一，距離位置i的長度為機器人的步長，下一步方向j的概率密度可由公式（5）計算得到：

式中：Pij為從位置i到位置j的概率；ijτ為從位置i到位置j的信息素濃度；Hij為從位置i到位置j的啟發(fā)式信息濃度；Ni表示位置i的鄰居集合，共8個位置；α和β分別為信息素和啟發(fā)式信息的重要程度參數(shù)。

隨著螞蟻進行移動以及實際環(huán)境中信息素會揮發(fā)的情況，設置信息素的更新公式：

式中：ρ為信息素的揮發(fā)系數(shù)；Δτij(k)為第k只螞蟻在位置i到位置j的信息素變化量。

因此，路徑規(guī)劃部分的實現(xiàn)流程如圖7所示，整體捕獲流程如圖8所示。

3 仿真結(jié)果與分析

本文基于4個搜索機器人以及一個目標的情況對所提算法進行仿真驗證。實驗分別在有障礙物和無障礙物的2種環(huán)境下進行，由于無障礙物環(huán)境下捕獲時路徑較短，為使實驗結(jié)果清晰，將環(huán)境大小設置為400 m×400 m，復雜障礙物環(huán)境大小設置為800 m×800 m。

除環(huán)境大小外，兩種情況下進行仿真實驗的其余條件均相同，機器人及目標點的半徑為10 m，運動速度為10 m/s2，搜索機器人初始位置為（150，150）、（250，150）、（150，350）和（250，350），目標機器人初始位置為（100，50），可探測區(qū)域及安全域半徑為20 m，更新頻率為25 FPS。

下面對本文所提出的策略進行驗證，首先對路徑規(guī)劃改進蟻群算法部分參數(shù)設置進行說明：信息素重要程度參數(shù)α為1.0，啟發(fā)式信息重要程度參數(shù)β為12.0，信息素蒸發(fā)系數(shù)ρ為0.1，信息素增量參數(shù)Q為10.0。在避障判斷時，本文充分考慮機器人尺寸大小因素，避免運動中機器人邊緣部分與障礙物造成碰撞。圖9為無障礙物環(huán)境中的仿真結(jié)果，首先4個機器人進行分散搜索，當發(fā)現(xiàn)目標點后執(zhí)行追逐和編隊策略，最終成功捕獲目標。

圖10為在不同大小的障礙物環(huán)境下的仿真結(jié)果，可以看出本文所提策略能夠使得搜索機器人在整個任務期間有效躲避障礙物并進行編隊達到目標位置。

圖1 使用Cyl HRRT＊在搜索過程中執(zhí)行子集收縮[8]Fig.1 Using Cyl-HRRT* to perform subset contraction during search

圖2 最終效果示意Fig.2 Schematic diagram of final effects

圖3 期望捕獲點分配情況Fig.3 Expected allocation of capture points

圖4 角度優(yōu)先分配原則Fig.4 Principle of priority allocation of angles

圖5 距離最短分配原則Fig.5 Principle of shortest distance allocation

圖6 安全域協(xié)商分配算法流程Fig.6 Security domain negotiation allocation algorithm process

圖7 改進蟻群算法流程Fig.7 Improving ant colony algorithm

圖8 整體實現(xiàn)流程Fig.8 Overall implementation process

圖9 無障礙物環(huán)境仿真結(jié)果Fig.9 Simulation of obstacle free environment

圖10 不同大小障礙物環(huán)境仿真結(jié)果Fig.10 Simulation results of obstacles of different sizes

為對路徑規(guī)劃算法進行評估，本文在初始位置與障礙物位置完全相同的環(huán)境下，將改進蟻群算法與改進人工勢場算法進行比較。圖11（a）、（b）分別為無障礙物環(huán)境下以及復雜障礙物環(huán)境下基于改進人工勢場算法編隊搜索結(jié)果。

圖11 改進人工勢場仿真結(jié)果Fig.11 Simulation results of improved potential field

此外，我們將算法耗時及成功率作為性能指標進行量化分析，由于蟻群算法為隨機性算法，為使結(jié)果更具說服力，本文進行了多次仿真實驗。下面結(jié)果均為取自40次試驗結(jié)果的平均值。表1為無障礙物和隨機生成障礙物環(huán)境中2種算法耗時情況的對照結(jié)果。

表1 不同環(huán)境下2種算法耗時情況Table 1 Time consumption of 2 algorithms in different environments

機器人捕獲時間大于25 s視為任務失敗，表2為不同環(huán)境下捕獲目標點成功率的對照結(jié)果。

表2 不同環(huán)境下2種算法捕獲成功率Table 2 Success rates of 2 algorithms in different environments

從表2中的數(shù)據(jù)可以看出，在2種環(huán)境中均是使用改進蟻群算法規(guī)劃出的航跡長度更短，運行平均耗時更小，尤其在多障礙物環(huán)境中，本文所提出的策略會表現(xiàn)出更高的捕獲成功率，能夠更好的完成任務。對比結(jié)果表明：本文所提出的協(xié)同編隊策略整體具有較優(yōu)的性能，能夠有效地解決二維復雜水下環(huán)境中仿生機器人的協(xié)作編隊捕獲任務。

4 結(jié)束語

在多仿生機器人系統(tǒng)水下環(huán)境中，協(xié)同編隊策略是解決目標對象追蹤和捕捉的關(guān)鍵問題之一。由于水下環(huán)境的復雜性和不確定性，傳統(tǒng)的捕捉策略在實際應用中充滿著挑戰(zhàn)。本文旨在提出一種基于安全域協(xié)商各改進蟻群算法的編隊策略，以解決多機器人的協(xié)同捕捉問題。

為了提高任務成功率，建立目標點位置的安全域，并采用安全域協(xié)商策略實現(xiàn)對期望捕獲點的實時分配，在此基礎上，采用改進的人工蟻群算法實現(xiàn)機器人到捕獲位置的路徑避障規(guī)劃。仿真結(jié)果證明：該協(xié)同編隊算法在二維復雜環(huán)境中能夠成功實現(xiàn)對目標點的編隊捕捉且具有較好的性能表現(xiàn)，對實際海洋資源探測和機器人編隊搜索任務具有參考意義。后續(xù)將對三維環(huán)境中的算法性能需要進一步探究，并針對實物仿生機器人展開實驗。