楊 丹，馮世龍，石立偉，郭書(shū)祥

（北京理工大學(xué)，北京 100081）

0 引言

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

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

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

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

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

1 問(wèn)題描述與建模

1.1 多仿生機(jī)器人協(xié)同編隊(duì)搜索問(wèn)題描述

整個(gè)問(wèn)題建立在有邊界的多障礙物環(huán)境X中，設(shè)有n個(gè)搜索機(jī)器人R＝{R1,R2......Rn}對(duì)位置未知的移動(dòng)目標(biāo)點(diǎn)u進(jìn)行捕獲。捕獲成功的條件為：搜索機(jī)器人在目標(biāo)探測(cè)區(qū)域均勻分布或?qū)⒛繕?biāo)圍困在環(huán)境邊界。

1.2 仿生機(jī)器人水下運(yùn)動(dòng)方程

整個(gè)搜索過(guò)程中，需要對(duì)搜索機(jī)器人以及移動(dòng)目標(biāo)的運(yùn)動(dòng)速度及角度進(jìn)行控制。設(shè)搜索機(jī)器人及目標(biāo)點(diǎn)正常行進(jìn)速度為v，目標(biāo)點(diǎn)發(fā)現(xiàn)搜索機(jī)器人逃逸速度為1.1v。機(jī)器人在t時(shí)刻的運(yùn)動(dòng)模型可表示為下式：

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

1.3 目標(biāo)點(diǎn)安全域位置

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

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

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

1.4 目標(biāo)的捕獲點(diǎn)模型

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

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

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

2 協(xié)同編隊(duì)捕獲任務(wù)

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

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

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

圖5為按距離最短原則分配捕獲點(diǎn)示意圖，但該方法只考慮到搜索機(jī)器人與目標(biāo)之間的直線距離，并未考慮到各機(jī)器人到達(dá)捕獲位置的時(shí)間不同步問(wèn)題。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖3 期望捕獲點(diǎn)分配情況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 改進(jìn)蟻群算法流程Fig.7 Improving ant colony algorithm

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

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

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

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

圖11 改進(jìn)人工勢(shì)場(chǎng)仿真結(jié)果Fig.11 Simulation results of improved potential field

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

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

機(jī)器人捕獲時(shí)間大于25 s視為任務(wù)失敗，表2為不同環(huán)境下捕獲目標(biāo)點(diǎn)成功率的對(duì)照結(jié)果。

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

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

4 結(jié)束語(yǔ)

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

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