水下搜救中基于先驗信息的AUV區域覆蓋路徑規劃

蔡 暢，陳建峰，劉 芬，周榮艷

（西北工業大學 航海學院，陜西 西安 710072）

0 引言

區域覆蓋路徑規劃（Coverage path planning，CPP）是指通過設計一條可行路徑達到完全覆蓋某一區域的目的，是機器人研究的基礎和關鍵領域[1-2]。CPP問題廣泛應用于海底地貌測繪[3]、排雷（mine countermeasures，MCM）[4]、搜救（search and rescue，SAR）[5]、管道檢測[6]和海底考古等領域。隨著自動化和自主機器人設備的發展，已有將自主水下機器人（autonomous underwater vehicle，AUV）應用到水下搜救任務中的案例[7]。本文針對使用配備側掃聲吶（side-scan sonar，SSS）的AUV進行搜救任務的背景，解決完全覆蓋搜索區域的路徑規劃問題。

大量的覆蓋路徑規劃算法及其分類已被系統性地研究[8-9]，其研究重點集中于環境未知[10]、姿態不確定[11]、區域形狀不規則[12]、導航不可靠[13]等方面。但在大規模搜救任務中應用CPP問題與傳統的CPP問題略有不同。在搜救任務中所使用的CPP問題有2個特點：一方面，海上搜救任務的覆蓋范圍可能非常大，容易出現任務失敗，而且操作成本高，因此，保證收集的數據質量是至關重要的；另一方面，救援專家可提供專業協助[14]，如預測目標信息等[15-16]，此類先驗知識可對路徑規劃提供依據。

不同于被廣泛研究的以目標搜索策略設計為重點的案例[17]，本文重點是完全覆蓋搜索區域，優先搜索目標可能出現區域的同時提高聲吶數據質量以便后續數據處理。大多數目標搜索問題致力于先驗信息或傳感器數據如何指導機器人的路徑規劃，而不是機器人的行為是否有利于進一步的目標檢測。然而，目前采集的原始側掃聲吶數據主要用于形成聲吶圖像，主要是人工判讀來識別目標[18]。因此，本文在路徑規劃方面，保持AUV航行穩定，即保持直線運動、穩定速度以及恒定高度，來保證獲得較高質量聲吶數據[19]。

雖然以往工作中的大部分覆蓋路徑規劃都可用于搜救任務，但是很少有研究考慮在可能出現失敗的大規模覆蓋任務中如何保證數據質量的問題。針對上述問題，本文提出了一種適用于大規模搜救任務的概率覆蓋路徑規劃算法SAR- A *。該算法基于預測的目標位置構造了目標存在概率圖，同時，考慮了環境、目標、聲吶和平臺等影響側掃聲吶探測能力的因素，在作業區域分解為均勻分布的路徑點，通過遍歷所有路徑點達到全覆蓋。

1 問題的定義與模型

1.1 問題的定義

全覆蓋路徑規劃通過遍歷工作區域中分布的所有路徑點來覆蓋整個區域。假設AUV是一個無動力學行為的質點，以固定的速度和高度在x–y平面上運動，忽略導航誤差。在AUV航行過程中，側掃聲吶沿軌跡生成聲吶圖像，帶有側掃聲吶的AUV及其覆蓋條帶如圖1所示，且設側掃聲吶盲點已被補償。針對搜救任務，我們假設由救援專家提供目標位置、移動軌跡和搜索范圍的預測。該假設合理，且可能為航行提供有用的信息。

圖1 側掃聲吶系統的3D模型Fig.1 3D model of a SSS system

將Lw×Ww的工作區域W定義為一個障礙物的開放平坦海域，被分解為Nc個小網格單元，表示為Call={c1,c2,???,cNc}，即

式中，Ci表示第i個單元格。

為了快速有效地完成搜救任務，在考慮側掃聲吶技術指標和先驗知識的前提下，設計了目標函數h。生成的路徑點用Pa={pa1,pa2,???,paNc}表示，其中pai表示第i個路徑點。每個單元格在生成的路徑中只能出現一次，直到所有網格單元都包含在Pa中：

1.2 目標存在概率

根據救援專家的預測先驗信息，目標存在概率圖給出了目標存在于任意單元Ci的概率，用表示。將專業的搜救仿真結果和路徑規劃方法相結合，采用二元高斯分布估計目標在每個單元中存在的概率。圖2展示了一個典型的搜救范圍預測系統的仿真結果[20]。

圖2 典型的救援專家評估的目標軌跡和搜索區域Fig.2 Classical target trajectory and search area evaluated by rescue specialists

式中，xi和yi是區域Ci的坐標。

在該模型中，將N(L,μ,Σ)的參數選擇與目標的預測位置和估計軌跡相結合，通過等值線的形狀來反映。均值μ被設定為預測目標位置的橢圓的中心，Σ由下落軌跡決定。當只提供預測的目標位置時，Σ為對稱矩陣。

1.3 側掃聲吶探測能力

探測能力Pd是指系統能夠準確地探測和識別目標的綜合評價。對側掃聲吶探測能力進行量化，從弱到強，取值0～1，例如Pd=0.8，表示當前側掃聲吶的探測能力較好。在實際應用中，聲吶數據質量受多種因素影響，不同位置也會有不同的探測能力。

2 SAR-A＊路徑規劃算法

針對以上提出的問題和模型，本節詳細介紹了SAR-A*路徑規劃方法的定義和步驟，主要思想是不斷從未訪問的單元格中選出最優下一路徑點，從而實現區域全覆蓋，同時保證聲吶數據質量和重要區域優先訪問。

2.1 覆蓋區域分解

本文將覆蓋區域分解為正六邊形，如圖3所示。六邊形分解可以獲得更多候選方向較少，且移動距離相等，較傳統的四邊形分解更有優勢。因此，SAR-A*算法采用六邊形分解。

圖3 六邊形分解Fig.3 Hexagon decomposition

2.2 多目標優化

SAR-A*算法的核心是目標函數，其決定了路徑規劃算法質量。為了減少計算負擔，預計算的availableList是當前單元格的鄰居neighbors和未訪問單元格集合openList的交集。

第1個目標函數f1是避免不必要路程，選擇距離較短、距目標最可能出現位置最近的單元格

式中：cc為當前位置；ci為Cava中的候選單元格；ch為pe最大值所在單元格；d(ccci)和d(chci)分別表示ci到點cc和點ch的歐氏距離；d0表示與初始單元格c1的最大距離；dh表示含有最小值pe的單元格ck與含有最大值pe的單元格ch之間的最大距離；ωd0和ωdh是滿足ωd0+ωdh=1的權重。以圖4（a）為例，如果點C和點D沒有被訪問，那么在A點的AUV不應將B點作為下一個路徑點。

圖4 選擇下一個路徑點的標準Fig.4 Criteria for selecting the next waypoint

第2個目標函數f2是為了避免轉彎，因為轉彎會導致航行不穩定及聲吶圖像失真[9]。因此，更少的轉彎能在路徑規劃層次上提高聲吶數據質量。在圖4（b）中，當最后一次移動是從E～F時，下一個路徑點優先選擇點G，因為EF和FG在同一直線上，H和I是次優的。

式中：θa(ccci)和θa(cparcc)分別為ci到點cc和點cpar的候選方向和最后一個方向之間的夾角，cpar是cc的父單元格。

目標函數f3強調了更高目標定位概率。搜救任務的最終目的是在最短的時間內探測到目標，即確定目標位置。f3將目標定位概率pl（如公式（6）所示）與探測能力pd和目標存在概率pe相結合，即

圖4（c）中，從點J開始的下一步最可取的點是點K，因為點K目標定位概率最大

式中：plmin和plmax為pl的最小值和最大值。

在考慮上述3個準則的基礎上，將區域選擇策略表述為一個多目標優化問題。本文采用加權度量方法對單元格進行評估。單個目標函數的理想解為：f1*=1，f2*=0，f3*=1。最終多目標函數表示為

式中：h(ci)為候選單元格ci的最終評估得分；M=3；ωm為對應的權重。

2.3 基于A＊算法的覆蓋路徑規劃

SAR-A*路徑規劃算法是為完全覆蓋大規模搜救區域而設計的，其主要步驟如圖5所示。該算法首先將搜索區域分解為大量的六邊形單元格，通過遍歷所有單元格來實現搜索區域全覆蓋。然后，建立目標存在概率圖和探測能力模型，作為搜索的基礎。該方法的主循環是基于多目標函數的 A*算法框架，將模型和目標函數結合到AUV路徑規劃中，直到實現全覆蓋。

圖5 SAR-A＊算法路徑規劃過程的流程圖Fig.5 Flow diagram describing the path planning process with the SAR-A* algorithm

A*算法是一種常見的圖遍歷和路徑搜索算法[21-22]。被應用的A*算法體系結構可以保證生成的路徑中沒有重復的單元格。下一個路徑點選擇策略的偽代碼在圖6中說明。

圖6 下一個路徑點選擇策略Fig.6 The next waypoint selection strategy

3 仿真結果

本文提出的路徑規劃方法在探測能力不均勻場景下進行了仿真。假設存在有利于探測的區域（見圖7（a）的淺藍色矩形）和不利于探測的區域（見圖7（a）的黃色帶狀區域）。其對應的探測能力的準確分布如圖7（b）所示，其中凸起區域和凹陷區域分別對應圖7（b）中的淺藍色區域和黃色區域。目標存在概率模型如圖 8所示，基本參數列于表1。仿真結果與幾種同類型算法進行了對比，包括割草機算法（LM）、隨機規劃算法（Rnd）、距離優先算法（Dist）、目標搜索概率優先算法（Pl）。

表1 默認參數Tab.1 Default Parameters

圖7 工作區域和非均勻探測能力Fig.7 Workspace and nonuniform detective ability map

圖8 目標存在概率分布和預測目標位置Fig.8 Target presence probability distributionand predicted target position

提出的方法所生成的路徑如圖9所示。可以看出，AUV首先對目標定位概率高、探測能力強的區域進行探測。考慮非均勻探測能力下，5種不同方法的累積目標定位概率（置信度）如圖10所示。可見，目標定位概率隨著步數的增加而迅速增加，SAR-A*算法（綠線）和Pl算法可以相對較少的步數快速提高置信度。但 Pl算法只考慮目標定位的概率，在整體目標函數上有明顯不足。圖11給出了5種方法的目標函數值。從圖中可以看出，SAR-A*算法的目標函數值整體保持低于其他方法。圖11（b）的柱狀圖說明了5種方法的累計目標函數值。SAR-A*算法的目標函數值比LM算法小43%，證明SAR-A*達到了預期效果。

圖9 由SAR-A＊路徑規劃算法在非均勻探測能力場景中生成的跟蹤Fig.9 Trace generated by the SAR-A* path planner in the nonuniform detective ability scenario

圖10 非均勻探測能力場景下5種不同算法定位目標的置信度Fig.10 Confidence of locating the target with five different methods in the nonuniform detective ability scenario

圖11 5種算法目標函數值性能Fig.11 Objective function value performance of five algorithms

由以上討論可知，SAR-A*算法在目標定位概率及整體目標函數值上都有很好的性能。使用SAR-A*算法可快速搜索更高的目標定位概率。

4 結束語

本文針對AUV進行搜救任務的場景，提出了一種全覆蓋路徑規劃方法SAR-A*。該方法將工作區域進行六邊形分解，并充分利用了先驗目標信息，建立目標存在概率圖，同時對側掃聲吶探測能力進行量化。利用多目標函數不斷對候選單元格進行評估，不斷確定最優下一路徑點，引導AUV進行區域的覆蓋。仿真結果表明：所設計的SAR-A*路徑規劃算法能夠完全覆蓋搜索區域，并能快速覆蓋目標定位置信度高的區域，從傳感器的探測能力和先驗目標信息2方面獲取高質量的數據。下一步擬將AUV集群應用到大規模搜救任務中來提高任務效率。