朱大奇， 龐 文， 任科蒙

（1. 上海理工大學 機械工程學院，上海 200093；2. 上海海事大學 物流工程學院，上海 201306）

深海水下目標搜索既是水下機器人（unmanned underwater vehicle，UUV）的重要應用領域，也是現(xiàn)代智能信息處理的重要應用領域，是一多學科交叉的高新技術，基于自治水下機器人（autonomous underwater vehicle，AUV）的深海水下搜救術已成為航運與海洋工程領域的研究熱點。相比于地面與空中智能搜索，由于水下環(huán)境的復雜多變，以及AUV 自身與水下感知傳感器的約束，使得“多AUV 水下協(xié)作搜索控制研究”成為一個極具挑戰(zhàn)性的研究領域。

由于AUV 自帶動力，無纜自治，掩蔽性能好，搜索范圍廣，無論在民用海洋領域，還是在海防軍事領域都有著十分廣泛的應用前景，特別是深海水下搜索領域，AUV 幾乎是其唯一的選擇。早在1963 年就有美國“阿爾文”號與“科夫”號水下機器人協(xié)作搜尋、打撈出西班牙海溝失落氫彈的成功案例；2014 年初的馬航MH370 失聯(lián)客機印度洋海底大搜索中，美國人動用了“藍鰭金槍魚”號AUV 在4 500 m 的深海進行了大規(guī)模水下搜索，但在歷時多月的搜索中未見國產AUV 身影。

隨著AUV 搜索任務復雜性的不斷增加, 在單一AUV 難以完成任務的情況下，多AUV 系統(tǒng)已成為水下機器人發(fā)展的重要研究方向[1-2]。相比于單一AUV 系統(tǒng)，多AUV 系統(tǒng)能夠提供更多的解決方案，具有更高的工作效率，更高的智能水平，更好的容錯性能。多AUV 協(xié)作搜索是多AUV 系統(tǒng)研究的重要內容，在民用深海搜救和國家海防安全建設上有著重要而不可替代的作用。多AUV 水下協(xié)作搜索控制是針對大規(guī)模、多地點的可疑深海水域，研究多AUV 群體高效的水下搜索方法。其相關研究不僅牽涉單AUV 水下作業(yè)的共性技術，如：水下環(huán)境感知技術、水下導航定位技術及水下軌跡跟蹤控制技術等，而且更需研究多AUV 水下協(xié)作控制的關鍵核心問題：多AUV多目標水下搜索任務分配技術、AUV 全局點-點路徑規(guī)劃與安全避障技術、具體搜索水域的全覆蓋水下搜索路徑規(guī)劃技術等。

1 自治水下機器人協(xié)作搜索控制研究現(xiàn)狀

圖1 為多AUV 多水域搜索場景。首先，需要在綜合考慮水下搜索環(huán)境、海流大小方向、障礙物與禁止航區(qū)、待搜索目標的中心位置等各類因素前提下，將各個待搜索的水域合理分配給各個AUV，即水下搜索任務分配問題。接著需要解決獲得任務目標的AUV 全局路徑規(guī)劃問題，即如何規(guī)劃一條安全最優(yōu)的路徑，使AUV 能快速安全可行地到達待搜索的目標水域。最后，需要實現(xiàn)對目標水域的全覆蓋高效搜索的路徑規(guī)劃，并實現(xiàn)對可疑目標物全面搜索。

圖1 多AUV 多水域搜索場景Fig.1 Multi-AUV multi-water area search scenario

1.1 多AUV 多目標水下搜索任務分配

早期多機器人系統(tǒng)任務分配大多采用基于行為任務分配策略[3-7]，前者主要模仿動物行為進行任務分配。例如：Mataric[5]提出了一種基于動物行為模型的算法，用于控制動物的各種不同的行為，包括分散、聚集等；Parkers[6]提出了一種分布式的，基于行為的軟件控制系統(tǒng)；Miyata 等[7]提出了一種控制機器人組按時間的先后順序，彼此獨立執(zhí)行不同任務的行為算法。以上方法均是通過模仿動物（包括人類）的行為方式，來分配不同的任務?；谛袨榈娜蝿辗峙渌惴ㄖ苯?、簡單，幾乎沒有滯后。但是，這些算法存在的問題是沒有自我調節(jié)能力，機器人之間協(xié)作較少，優(yōu)化能力弱，效率較低。

任務分配的另一個常見方法是市場機制算法[8-10]。在以市場機制為基礎的系統(tǒng)中，多機器人系統(tǒng)視為一個經濟體，每個機器人視為一個代理商。例如，Wahl[8]提出的多任務分配的拍賣算法，就是用最少的總消耗換來最大的總體及個人利益。這種算法使每個機器人不斷計算和比較訪問指定目標點的消耗，以此來平衡交易。盡管算法很好地解決了已知目標數(shù)的任務分配，但是對于目標數(shù)量未知的情況，市場經濟算法不能保證任務分配的最優(yōu)化。

智能優(yōu)化任務分配方法是多機器人系統(tǒng)任務分配的一個重要策略，如粒子群算法PSO（particle swarm optimization）、遺傳算法GA（genetic algorithm）、蟻群優(yōu)化算法ACO（ant colony optimization）等[11-13]。它們的共同特點是將搜尋路徑的總長度和搜索能耗作為優(yōu)化計算的目標函數(shù)，并通過各類迭代計算尋找最優(yōu)任務分配解。由于神經網絡的競爭特性和自學習能力，近些年來自組織神經網絡已被應用于機器人系統(tǒng)的路徑規(guī)劃與任務分配中。自組織神經網絡SOM（self-organizing map）算法由Kohonen[14]于20 世紀80 年代提出，該算法主要用于對輸入向量進行動態(tài)的區(qū)域分類，將這種算法應用于多任務分配后，目標點會被自動地歸納、劃分，并分配給合適的機器人。2006 年，Zhu 等[15]首次將自組織神經網絡應用于多移動機器人系統(tǒng)的任務分配與路徑規(guī)劃中，提出的算法在保證多機器人系統(tǒng)以最少的總消耗遍歷所有目標的前提下，每個機器人都能沿著最短路徑到達目標。其后， Zhu 等[16]在原有算法的基礎上進一步改進，給定移動機器人運行時的最大轉向角以及最大轉向半徑，在完成多任務作業(yè)的基礎上，控制移動機器人沿著平滑的弧線到達目標點。

上述的研究成果都是針對地面移動機器人的任務分配和路徑規(guī)劃，由于水下環(huán)境復雜多變、水下機器人自身的非線性、強耦合與弱感知特性，導致有關水下機器人任務分配研究報道還不多。但隨著海洋科技的快速發(fā)展，近些年水下機器人任務分配研究已得到廣泛關注。2009 年，Chow[17]提出了一個改進后的K-均值算法，用來解決靜態(tài)海流環(huán)境下的多AUV 系統(tǒng)的任務分配問題。這個算法結合了Dubins 模型、AUV 動態(tài)模型以及靜態(tài)海流模型，其中改進后的Dubins 模型使水下機器人在常值海流環(huán)境下，沿弧線到達目標。算法的新穎之處在于將多AUV 系統(tǒng)的任務分配與路徑規(guī)劃結合到了一起。但是，該算法存在的問題是：K-均值在完成多任務作業(yè)時，對移動的目標物不敏感，算法沒有將二維靜態(tài)海流模型拓展到三維動態(tài)海流模型，降低了算法的適用性；另外，對于結合了時變海流和移動目標物的復雜情況，算法沒有給出有效的解決方案。

針對K-均值算法的缺點，2013 年，Zhu 等[18-19]首次將自組織神經網絡模型SOM 引入水下多AUV 系統(tǒng)，并將速度合成算法和SOM 算法相結合，研究多AUV 系統(tǒng)在三維時變海流環(huán)境中靜態(tài)和動態(tài)目標的任務分配與路徑規(guī)劃問題。圖2 為該自組織任務分配算法的原理。多AUV 目標搜索中的任務分配是在一個有限的工作區(qū)域內將隨機分布的一組AUV 分配給所有需要搜索的區(qū)域。每個搜索區(qū)域都需要分配AUV 對該區(qū)域執(zhí)行未知目標搜索任務。對于每個AUV 而言，其代價是由從起始位置航行到搜索區(qū)域所移動的距離來衡量，總代價定義為所有單個AUV 代價的總和。當所有搜索區(qū)域都分配有AUV 對其搜索，分配任務完成。

圖2 SOM 神經網絡任務分配基本原理Fig. 2 Task allocation principle of SOM neural network

SOM 神經網絡可以實現(xiàn)輸入數(shù)據(jù)的聚類，將其應用到多AUV 多目標任務自組織分配，主要有兩個功能：一是競爭分配功能：將搜索區(qū)域的中心坐標作為SOM 輸入神經元，執(zhí)行任務的AUV坐標作為輸出神經元的權值，在SOM 神經網絡學習競爭過程中，按輸入坐標與輸出神經元權值的歐式距離最小選出獲勝神經元，即把輸入的目標分配給距離最小競爭獲勝的輸出神經元（對應具體獲勝AUV）；二是獲勝AUV 的全局路徑規(guī)劃功能：對獲勝神經元權值（對應獲取任務的AUV 坐標）不斷學習調整，輸出神經元（已分配任務的AUV）分別趨向于輸入神經元所在的區(qū)域，實際場景中就是使其與目標距離不斷減小，直至到達目標搜索區(qū)域的中心。

該算法不僅能解決三維時變海流環(huán)境中多AUV 任務分配和路徑規(guī)劃問題，并對每個AUV的工作量進行了優(yōu)化均衡，不會出現(xiàn)個別AUV 任務過重導致搜索任務失敗的情況。而且，將多AUV任務分配與路徑規(guī)劃合為一體，通過SOM 的權值更新，實現(xiàn)每個AUV 的路徑規(guī)劃與航行。但早期算法都將AUV 看成理想的質點，完全沒有考慮AUV 的實際航行條件，任務分配的競爭距離完全按照AUV 與目標坐標的直線距離計算，這與實際的水下目標搜索情況不一樣。對此，文獻[20]進一步研究了海流環(huán)境下AUV 自然曲線航行的SOM 競爭自組織任務分配算法，使該任務分配算法更接近實際應用。

表1 總結了深海水下多AUV 多任務分配算法的研究現(xiàn)狀，由表1 可見，以上的多AUV 多任務分配算法都有各自的特性優(yōu)勢與不足，但對多AUV水下任務分配研究來說，仍然有兩個重要問題沒有解決[21-22]：

表1 深海水下多AUV 多任務分配算法研究現(xiàn)狀Tab.1 Research status of deep-sea multi-AUV multi-task allocation algorithm

a. AUV 自身的異質特性?，F(xiàn)有的分配算法均假設所有AUV 是同質的，即性能完全一樣，這與實際情況有很大差別。實際的多AUV 系統(tǒng)是異質的，各個AUV 的航行速度、航行的安全距離都不一樣，甚至還有不同類的水下機器人協(xié)同搜索，如AUV 與ROV（remote operated vehicle）的協(xié)作搜索?？紤]到這些實際因素，應用歐式距離的競爭分配是不合適的，需要找到更合適和有效的分配條件，如航行時間、安全距離等。

b. 任務分配與路徑規(guī)劃的環(huán)境因素?，F(xiàn)有的分配算法大多沒有考慮實際水下環(huán)境的障礙物和海流大小對AUV 航行能力的影響，SOM 自組織任務分配與規(guī)劃就無法解決安全避障問題。另外，在權值調整路徑規(guī)劃算法中，當任務目標點與AUV 距離較大時，根據(jù)SOM 原理需要AUV 提供幾公里甚至幾十公里的時速，這遠遠大于AUV的最大航行速度。因此，存在AUV 航行速度“跳變”問題，實際上是無法實現(xiàn)的。

1.2 AUV 點-點全局路徑規(guī)劃

在多AUV 多目標水下搜索研究中，一旦AUV獲得具體海域的目標任務后，接著AUV 就需要直接航行到目標海域，并展開對具體可疑海域的全覆蓋搜索。此處關鍵問題是搜索路徑規(guī)劃，包括AUV 初始點到目標海域的點對點全局路徑規(guī)劃和具體目標水域的全覆蓋路徑規(guī)劃。

所謂水下機器人全局路徑規(guī)劃是指AUV 通過自身傳感器對水下環(huán)境的感知，從起始點到目標點自行規(guī)劃出一條安全優(yōu)化的行駛路徑。AUV 全局路徑規(guī)劃主要完成3 個目標任務：a. 使AUV 可以從起始點運動到目標點；b. 通過特定的算法使AUV 能避開障礙物；c. 在完成以上任務的前提下，盡可能規(guī)劃出一條最優(yōu)路徑。傳統(tǒng)的路徑規(guī)劃方法主要包括可視圖法、柵格地圖法、自由空間法、拓撲法、模板匹配法及人工勢場方法等。隨著現(xiàn)代人工智能技術的快速發(fā)展與突破，路徑規(guī)劃研究也在不斷發(fā)展，一些新型AUV 路徑規(guī)劃方法得到深入研究，典型的方法有智能優(yōu)化路徑規(guī)劃方法、神經網絡路徑規(guī)劃方法、啟發(fā)式搜索路徑規(guī)劃方法等。

1.2.1 模板匹配路徑規(guī)劃方法

模板匹配方法(template approach)是將機器人當前所處的狀態(tài)與過去經歷的狀態(tài)相比較，找到最接近的狀態(tài)，修改這一狀態(tài)下的路徑，就可以得到一條新的路徑[23-24]。即首先利用路徑規(guī)劃所用到或已產生的信息建立一個模板庫，庫中任一模板包含每一次規(guī)劃的環(huán)境信息和路徑信息，這些模板可以通過特定的索引取得；將當前規(guī)劃任務和環(huán)境信息與模板庫中的模板進行匹配，以尋找出一個最優(yōu)匹配模板，然后對該模板進行修正，并以此作為最后的結果。模板匹配技術在環(huán)境確定情況下，有較好的應用效果。如Vasudevan 等[25]和Milmaz 等[26]提出的基于案例的自治水下機器人AUV 路徑規(guī)劃方法；Liu 等[27]和Carvalho 等[28]提出的清潔機器人模板匹配路徑規(guī)劃方法等，都是環(huán)境確定已知狀況下的路徑規(guī)劃。為了提高模板匹配路徑規(guī)劃技術對環(huán)境變化的適應性，部分學者提出將模板匹配與神經網絡學習相結合的方法，如：Ram 等[29]將基于事例的在線匹配和增強式學習相結合的路徑規(guī)劃方法；Arleo 等[30]將環(huán)境模板與神經網絡學習結合的路徑規(guī)劃方法；Yu 等[31]將三維環(huán)境匹配與小波分析結合的路徑規(guī)劃方法等。相關研究提高了模板匹配規(guī)劃方法中機器人的自適應性能，使機器人能部分地適應環(huán)境的變化。

模板匹配路徑規(guī)劃方法原理簡單，在匹配成功時效果很好。但這一方法致命缺陷是依賴機器人過去的經驗，如果案例庫中沒有足夠的路徑模板，就可能找不到與當前狀態(tài)相匹配的路徑。該方法主要適用于靜態(tài)環(huán)境的路徑規(guī)劃，一旦環(huán)境動態(tài)變化，一般難以找到匹配的路徑模板。這些不足嚴重限制模板匹配路徑規(guī)劃技術的深入研究與推廣應用。

1.2.2 人工勢場方法

人工勢場 (artificial potential field，APF)是一種基于虛擬力場的方法，APF 的基本思想是將智能體在工作環(huán)境中的運動，設計成一種抽象的人造“力場”中的運動，這個“力場”包括引力場和斥力場，如圖3 和圖4 所示。引力場是目標點對移動智能體產生的，通過對智能體與目標點位置相關引力函數(shù)的建模，其引力Fatt可影響AUV 的移動速度v，而Fatt的大小與目標之間的距離相關，距離越長則受到的引力越大；而斥力場是由障礙物對AUV 產生的，同樣斥力函數(shù)的建模是與障礙物位置相關的，機器人受到的斥力Frep大小與目標距離的長短有關，距離越短則斥力越大，從而達到智能體躲避障礙物的效果。障礙物與目標物在空間中產生相應的勢場，其梯度的相反數(shù)就是相應的斥力或引力，二者合力使得智能體遠離障礙物，向目標點運動。

圖3 引力場示意圖Fig.3 Schematic diagram of gravitational field

圖4 斥力場示意圖Fig.4 Schematic diagram of repulsion field

早期人工勢場路徑規(guī)劃是一種靜態(tài)環(huán)境的人工勢場。為解決動態(tài)環(huán)境中機器人的路徑規(guī)劃問題， Conn 等[32]（1998）在研究人工勢場方法時，將時間看成規(guī)劃模型的一維參量，而移動的障礙物在擴展的模型中被看成靜態(tài)的，這樣動態(tài)路徑規(guī)劃仍可運用靜態(tài)路徑規(guī)劃方法來實現(xiàn)，這是一種相對動態(tài)人工勢場方法。Ko 等[33]（1996）將障礙物速度參量引入到斥力勢函數(shù)的構造中，提出動態(tài)環(huán)境路徑規(guī)劃策略，但他們僅考慮環(huán)境中障礙物的運動速度，未考慮機器人的運動速度，是一個不完整的動態(tài)環(huán)境。為此， Ge 等[34-35]（2002）進一步將機器人與目標物的相對位置與相對速度引入吸引勢函數(shù)，將機器人與障礙物的相對位置與相對速度引入排斥勢函數(shù)，提出動態(tài)環(huán)境下的機器人路徑規(guī)劃算法；王超等[36]（2015）在此基礎上，考慮到深海海流對AUV 路徑規(guī)劃的影響，針對常值海流模型，將海流速度合成方法和人工勢場路徑規(guī)劃相結合，提出AUV 集成人工勢場路徑規(guī)劃策略，以期解決水下海流產生的航行路徑增加的問題。

人工勢場路徑規(guī)劃原理簡單，虛擬合力的計算便于底層的實時控制。但人工勢場路徑規(guī)劃方法通常存在局部極小點，盡管也有不少針對局部極小的改進方法，不過到目前為止，還未找到完全滿意的答案。另外，引力和斥力場設計還存在人為不確定因素，在障礙物較多時還存在計算量過大等問題。

1.2.3 智能路徑規(guī)劃方法

目前，現(xiàn)代人工智能技術已經廣泛應用于移動機器人的路徑規(guī)劃中，并進一步擴展到水下機器人路徑規(guī)劃中，常見的人工智能路徑規(guī)劃技術運用了包括進化計算、群體智能、人工神經網絡等方法。

較早應用于AUV 路徑規(guī)劃的是遺傳算法和蟻群算法。遺傳算法GA 是對自然選擇和生物進化過程模擬得到的一種進化算法，該算法及其派生算法已被應用到變海流水下環(huán)境的路徑規(guī)劃與安全避障之中（2004, 2012）[37-38]。蟻群算法ACO 是通過模擬螞蟻覓食的生物機制進行路徑生成，它在AUV 全局路徑規(guī)劃中有較好應用（2007, 2008）[39-40]；之后，基于群體演化的粒子群優(yōu)化搜索算法PSO也被用于AUV 路徑規(guī)劃（2015, 2010）[41-42]。由于粒子群優(yōu)化具有原理簡單易實現(xiàn)、算法簡潔、收斂速度快和魯棒性強的特點，使其在滿足AUV 路徑規(guī)劃實時性方面表現(xiàn)出色，但是也存在容易陷入局部最優(yōu)，造成算法過早收斂的問題，甚至無法生成優(yōu)化路徑，或者在到達目標位置前過早停止。

由于模糊邏輯在不確定性信息處理方面的極好表現(xiàn)，而水下機器人傳感器采集的環(huán)境信息又存在不確定性和不完整性，使得模糊邏輯在AUV 路徑規(guī)劃和安全避障研究中也取得了較好的效果（Bui[43], 2006）。高劍等[44]（2012）針對AUV 避障行為，根據(jù)前視聲納探測到的障礙物距離和方位信息，采用模糊推理方法計算AUV 的轉動方向和角度以避開障礙物。Ali 等[45]（2015）利用二型模糊本體語義知識實現(xiàn)AUV 路徑規(guī)劃與安全避障。模糊邏輯算法是建立在人類經驗的基礎上，無需建立精確的數(shù)學模型，能夠邊規(guī)劃邊控制AUV 的運動，克服人工勢場路徑規(guī)劃方法易陷入局部最優(yōu)解的問題，實時性比較高。但是因為模糊控制規(guī)則是專家經驗的總結，本身就存在近似，甚至錯誤；另外，當水下環(huán)境復雜多變時，僅憑專家經驗很難構造出全面的模糊規(guī)則庫，因此，其適應能力較差[46]。

圖5 生物啟發(fā)路徑規(guī)劃原理Fig.5 Bio-inspired path planning principle

生物啟發(fā)神經網絡路徑規(guī)劃同樣適應于AUV[51-52]，只是水下環(huán)境更加復雜，而且是三維立體地圖和神經網絡。同時，該方法被進一步應用到多AUV自組織任務分配路徑規(guī)劃之中，用以解決自組織SOM 路徑規(guī)劃初始航行距離與速度“跳變”和安全避障問題[53-54]。

生物啟發(fā)神經網絡路徑規(guī)劃算法具有在線自適應規(guī)劃特性，但是，它同樣存在環(huán)境需要已知，地圖已構建的前提。由于水下環(huán)境的動態(tài)性、信息的不確定性和不完全性，在AUV 實際航行過程中，當先前未知的靜態(tài)或動態(tài)障礙物出現(xiàn)時，使得生物啟發(fā)神經網絡算法不能滿足動態(tài)時變的水下環(huán)境、實時情況下的AUV 路徑規(guī)劃要求[55-56]。此時，使用啟發(fā)式增量搜索的LPA*算法[57]和D*Lite 算法[58]較為有效，它是利用先前的搜索信息來提高AUV 當前搜索的效率，不僅適應動態(tài)環(huán)境，而且具備較快的重新規(guī)劃能力，一定程度上可以滿足前述路徑規(guī)劃方法的不足。表2 給出了AUV 水下目標搜索全局路徑規(guī)劃方法的總結。

表2 AUV 水下目標搜索全局路徑規(guī)劃方法Tab.2 Global path planning method of AUV underwater target search

1.3 AUV 全覆蓋水下目標搜索路徑規(guī)劃

當AUV 到達待搜索的具體海域后，就需要對可疑水域進行全覆蓋水下搜索，其規(guī)劃的主要指標就是覆蓋率高、重復率小、搜索路徑短。為此，需要研究多AUV 單目標海域的全覆蓋自主搜索路徑規(guī)劃方法。

2002 年，Maxim 等[59]提出一種未知環(huán)境中多機器人合作全覆蓋算法，該算法無需提前獲取工作環(huán)境全局信息，機器人之間也不會發(fā)生碰撞。但是，該算法并未具體規(guī)劃機器人的全覆蓋路徑，各個機器人均是采取隨機覆蓋策略遍歷工作區(qū)域，故容易造成路徑雜亂、重復率高等問題，而且也無法保證實現(xiàn)可疑區(qū)域的完全覆蓋。

2009 年，Parlaktuna 等[60]提出一種基于在線傳感器的多機器人全覆蓋路徑規(guī)劃算法。采用廣義Voronoi 圖對工作區(qū)域進行建模并初始化出一條區(qū)域全覆蓋路徑，通過限量弧路由算法劃分初始路徑。該算法能夠通過對全覆蓋路徑的合理劃分來實現(xiàn)目標區(qū)域的全覆蓋，但是其僅適用于機器人單向行走即可實現(xiàn)路徑全覆蓋的狹窄路徑的情況，對于較寬敞的環(huán)境，則難以保證全覆蓋[61]。

另外，還有許多專家學者通過對單機器人全覆蓋路徑規(guī)劃算法進行改進或擴充，來解決多機器人間的合作全覆蓋問題。例如，Janchiv 等[62]將多方法融合應用到多機器人的全覆蓋路徑規(guī)劃中，利用單元分解法將任務區(qū)域分解為多個子區(qū)域，并根據(jù)各個子區(qū)域的情況選取合適的路徑模板，使得多機器人在規(guī)劃覆蓋路徑的過程中轉彎次數(shù)最少，進而提高全覆蓋效率，但是該算法并未考慮到多個機器人間的任務分配以及魯棒性的問題。Rekletis 等[63]將Boustrophedon 區(qū)域分解算法引入到多機器人的合作全覆蓋路徑規(guī)劃中，主要是通過該區(qū)域分解算法劃分工作區(qū)域，并利用貪婪拍賣機制算法解決多機器人的任務分配和協(xié)作問題。該算法可實現(xiàn)區(qū)域的完全覆蓋，但通常會出現(xiàn)機器人在覆蓋最右側的子區(qū)域后再返回覆蓋左側子區(qū)域的情況，即易產生大量的重復覆蓋。Hazon 等[64]在基于STC 的單機器人全覆蓋算法的基礎上，提出多機器人合作全覆蓋路徑規(guī)劃算 法MSTC（multi-robots spanning-tree coverage），有效地提高了機器人全區(qū)域遍歷的魯棒性，但并不能保證覆蓋時間接近最優(yōu)。對此，Zheng 等[65]和Zhao 等[66]對該算法進行改進，提出MFC（multi-robots forest coverage）算法，可以實現(xiàn)覆蓋時間接近最優(yōu)。Kapanoglu 等[67]提出一種基于遺傳算法和模板匹配的多機器人合作全覆蓋路徑規(guī)劃方法，主要是通過遺傳算法的尋優(yōu)能力來盡快尋找到與每個機器人最匹配的路徑模板，從而使得區(qū)域覆蓋時間最短、機器人能量消耗最少。但該算法更適合靜態(tài)環(huán)境，在動態(tài)變化的環(huán)境中，較難找到合適的路徑模板。Yang 等[49]利用生物啟發(fā)神經網絡算法解決了多個地面清掃機器人的合作全覆蓋路徑規(guī)劃問題，其中每一個機器人都將其他機器人當作移動障礙物，該算法可以保證機器人之間無碰撞的合作完成目標區(qū)域的全覆蓋工作，但是其并沒有解決生物啟發(fā)神經網絡算法計算量大等問題[68]。

從目前多機器人全覆蓋研究現(xiàn)狀來看，主要針對地面移動機器人的協(xié)作覆蓋，相關規(guī)劃方法存在不能完全覆蓋和重復覆蓋度高等問題，水下多AUV 的協(xié)同規(guī)劃覆蓋方法處于起步研究階段，如何實現(xiàn)快速全覆蓋和低重復是需要重點研究的問題。

2 多AUV 多目標水下協(xié)作搜索的發(fā)展

多AUV 系統(tǒng)在水下搜救、探測打撈、深海資源調查、海底線管巡查維修、海事執(zhí)法取證、科學研究和海軍防務等諸多領域有著廣泛的應用前景，雖然目前已有不少研究成果報道，但是，仍然存在大量問題需作系統(tǒng)深入的研究。

2.1 多AUV 水下協(xié)作搜索模式的發(fā)展

2.1.1 接近實際場景與實際AUV 的水下協(xié)作搜索

目前的研究大多將水下場景理想化，將AUV看成是完全自由控制的質點進行處理，這和實際的多AUV 水下協(xié)作搜索有較大的距離。和地面與空中環(huán)境相比，水下環(huán)境更加惡劣，不僅存在海流、海山、各類靜止與移動的障礙物，還有水下光線微弱、無線通信失效及諸多干擾。另外，AUV 系統(tǒng)不僅存在模型不確定，而在多AUV 系統(tǒng)中，還存在異質AUV 問題。不同AUV 的性能、模型參數(shù)、航行速度與安全距離均不相同，這些都需要在協(xié)作搜索時重點考慮。

2.1.2 多AUV 編隊搜索，包括異質異類海洋機器人的立體編隊搜索

編隊控制研究是無人系統(tǒng)協(xié)作控制的重要分支，其中多AUV 水下編隊搜索已得到廣泛關注[69-72]。并從同類同質AUV 編隊控制，向同類異質AUV編隊控制和異類異質海洋機器人方向拓展[72-73]。如圖6 所示的無人艇（unmanned surface vehicle，USV）與AUV 組合的立體異類異質編隊搜索。USV 既可進行水上搜索，又可進行GPS 準確定位，而AUV與水面USV 之間可以通過短基線定位系統(tǒng)進行信息交互，從而解決AUV 長時導航定位的難題。同時，可以利用USV 引導AUV 進行不同深度、大范圍的搜索。

圖6 USV 與AUV 編隊搜索Fig. 6 USV and AUV formation search

2.1.3 動態(tài)不合作逃逸目標的多AUV 水下協(xié)作圍捕搜索

目前的多AUV 水下搜索，極大多數(shù)研究水下靜態(tài)目標的搜索，如空難中水下失事飛機、海難沉船的搜尋。但是，在國防軍事領域的水下無人攻防博弈應用中，逃逸目標的跟蹤攔截與圍捕就是一個動態(tài)不合作目標搜索問題。它涉及多AUV圍捕聯(lián)盟生成（動態(tài)任務分配）、逃逸目標的智能特性、動態(tài)逃逸目標的規(guī)劃跟蹤、多AUV 對逃逸目標的最后圍堵等諸多問題，多AUV 水下目標圍捕是多AUV 系統(tǒng)研究的重要領域之一[74-76]。圖7是一個多AUV 多逃逸目標水下圍捕示意圖。圖中：R 表示水下機器人；E 表示逃逸目標。

圖7 圍捕聯(lián)盟示意圖Fig.7 Schematic diagram of capture alliance

2.2 水下搜索關鍵技術的發(fā)展

2.2.1 新型水下搜索路徑規(guī)劃與導航定位方法研究

水下導航定位技術是多AUV 水下搜索的前提，常規(guī)的慣性導航與基線導航定位系統(tǒng)都存在各自的缺陷，而現(xiàn)代GPS 導航定位在水下則會完全失效。因此，需要深入研究新型水下導航定位技術，如現(xiàn)代的磁導航技術[76]，水下SLAM 技術[77-78]等。新型的水下搜索路徑規(guī)劃研究是水下目標搜索的永恒主題，近些年來，一些新的智能規(guī)劃方法得到關注。如BINN(glasius bio-inspired neural networks)路 徑 規(guī) 劃[79-82]、 MPC(model predictive control)模型預測路徑規(guī)劃算法[83]以及深度強化學習路徑規(guī)劃方法[84-86]等。

2.2.2 水下搜索路徑跟蹤控制技術

路徑規(guī)劃雖然是水下協(xié)作搜索的核心問題，但是要真正使AUV 按照規(guī)劃的路徑航行搜索，就需要認真研究AUV 水下路徑跟蹤控制技術[86-87]。由于水下環(huán)境的復雜和AUV 自身的非線性及模型的不確定性，AUV 水下路徑跟蹤控制同樣具有挑戰(zhàn)性，它涉及AUV 運動學與動力學跟蹤控制，需要研究AUV 水下控制算法、AUV 動力學模型、海流的影響及推進器驅動飽和等系列問題[88-90]。

2.2.3 實時有效的水下目標識別技術

水下目標識別技術是多AUV 水下搜索追求的最后目標，由于海洋環(huán)境復雜，獲取水下目標信息的手段十分有限，主要傳感器有：微光TV、激光成像和各類聲吶傳感器。對深海目標搜索來說，主要是聲吶傳感器系統(tǒng)，它需要離線處理分析回放，才能得到實際目標圖像，目前還無法實現(xiàn)在線目標識別，如美國藍鯨金槍魚號系列AUV系統(tǒng)，不僅實時性差，而且識別效果也有待提高。因此，特別需要研究新型水下感知技術[91-93]、多傳感器信息融合識別技術[93-94]、智能深度圖像處理識別技術等[95-97]。