蔡 畅，陈建峰，刘 芬，周荣艳

（西北工业大学 航海学院，陕西 西安 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集群应用到大规模搜救任务中来提高任务效率。