基于滚动时域四叉树和连续时间验证的无人水面车辆的动态路径规划

《Ocean Engineering》：Dynamic path planning for unmanned surface vehicles with rolling horizon spatiotemporal quadtrees and continuous time verification

　　•CF-STQP 在五个规划器中实现了最低的平均总运行时间，适用于两个港口。•C-AAESC 根据速度、遭遇风险和海图 clearance 自动调整安全轮廓。•两阶段 PCTR 在基于 AIS 记录参数化的 307 个场景中得到了验证。•PCTR 的确定性达到了 99.35%，且没有出现错误的安全/违规判断。

引言
受限的港口水域对海上自主系统提出了严格的要求。港池、入口通道和泊位前方水域具有复杂的海岸线、受限的通航空间以及有限的操纵余地。无人水面船（USV）必须在有限的计算预算内找到几何上可行的路径。它还必须考虑静态海岸线、动态目标船只、有限的船体尺寸和连续的转向动作。Vagale（Vagale 等，2021）将自主水面船路径规划与碰撞、搁浅和航行延误风险联系起来。?ztürk（?ztürk 等，2022）指出缺乏对安全间隔、避碰操作和航行规则整合的统一处理。因此，在受限港口中的动态规划需要的不仅仅是可达性。规划器必须高效生成可执行的轨迹，并提供连续的时间安全证据。
在船舶运动控制和系统识别方面的互补进展加强了自主导航的建模基础。Zhang（Zhang 等，2019）开发了一种简洁的鲁棒积分器反步控制器用于保持船舶航向，并使用非线性装饰来减少控制努力。Song 等人利用全尺寸试验的数据识别了一个具有四个自由度的非线性船舶操纵模型（Song 等，2022a）。在相关研究中，他们开发了一种改进的扩展卡尔曼滤波器，结合非线性创新实时预测耦合的升沉和俯仰运动，并使用全尺寸测试的数据进行了验证（Song 等，2022b）。对于在恶劣海况中的大型船舶，Song（Song 等，2024）将参数漂移的处理与非线性创新识别相结合。在协同控制层面，Zhang（Zhang 等，2024）为海上放牧自主船舶开发了编队控制和多任务切换引导，使用结构同步的动态事件触发器。这些研究推进了船舶运动控制、协同指导和船舶模型识别，但没有解决多尺度搜索、自适应安全几何和在受限港口中连续轨迹验证的规划层面耦合问题。
USV 规划方法包括图搜索、基于采样的规划、速度障碍方法、优化和基于学习的决策制定。Xing（Xing 等，2023）将这些方法分为全局、局部和混合框架。他们确定动态障碍、环境不确定性和运动约束是影响实际应用的关键因素。图搜索对于受海图约束的规划仍然很重要，因为其状态是明确的，其约束也很容易纳入。Samet（1984）提供了对四叉树及相关层次数据结构的研究。这项工作支持了靠近海岸线的精细空间表示和开阔水域中的状态压缩。
目标船舶运动的不确定性对海上自主系统提出了另一个挑战。Zhang（Zhang 等，2023）将不确定的目标船舶操纵纳入基于模型预测控制（MPC）的滚动决策系统，用于实时多船避碰。Wang（Wang 等，2023）使用数据驱动的轨迹预测器量化时变运动不确定性并估计多船碰撞概率。这些研究明确解决了预测不确定性问题，而本研究则关注在规定的视界内目标轨迹下的确定性规划和验证；目标船舶预测在每个滚动视界周期开始时根据新观测进行重新初始化。
将时间直接添加到统一的空间网格中可以大大扩大搜索空间。Phillips 和 Likhachev（2011）提出了安全区间路径规划（SIPP），它用配置安全区间对替换了时间索引的状态。Narayanan（Narayanan 等，2012）开发了 Anytime SIPP，首先产生一个可行解，然后随着更多计算资源的可用性对其进行改进。Yakovlev 和 Andreychuk（2017）扩展了 SIPP 以支持任意角度的转换。Kim（Kim 等，2025）将最大转弯速率约束纳入任意角度安全区间路径规划（AA-SIPP），用于多 USV 协调。他们的方法在满足基本转向约束的同时保持了连续的时间间隔。然而，这些方法通常使用固定分辨率的网格和预定义的最小间隔距离。
港口水域通常结合了大面积的开阔区域、长海岸线和狭窄的局部通道。因此，多尺度空间表示和船舶域为风险评估和规划约束提供了有用的几何基础。Szlapczynski（Sz?apczyński 和 Sz?apczyńska，2017）表明船舶域在定义、安全标准和参数来源上有所不同。他们的边界通常取决于方向。Li（Li 等，2025）进一步指出，海上安全域正从基于固定规则的几何形状转向由船只、环境和交通条件驱动的动态不规则区域。Wang（2013）开发了一个动态四元数船舶域（QSD），将船舶操纵性、导航员状态和航行环境映射到域的规模和形状。Silveira（Silveira 等，2022）根据自动识别系统（AIS）基于的相对交通密度推导出多边形域，并允许不同象限中有独立的参数。Chen（Chen 等，2024a）进一步从历史 AIS 数据中推导出概率船舶域，并将域重叠与繁忙水域的碰撞风险和时间预警相结合。这些研究表明，船舶安全边界是不对称的、依赖于具体场景的，并且对底层数据源敏感。与这些基于 AIS 的经验或概率域不同，这里介绍的 C-AAESC 并不是从遭遇频率推断出来的。相反，它根据物理船体几何、船舶速度、船头制动需求、船尾超越风险和局部海图 clearance 构建了一个确定性的规划框架。相同的函数形式用于搜索阶段的筛选和重建后的验证，每个阶段的速度输入分别进行评估。
轨迹安全检查也受到离散化的困扰。Sutulo（Sutulo 等，2002）将船舶路径预测方法分为动态或运动学类型，并指出了模型复杂性和在线效率之间的权衡。Yuan（Yuan 等，2014）表明，带有航向和转弯速率的传播遵循非线性圆弧运动。在这种运动下，相邻航点之间的直线弦无法完全捕捉船头、船尾或不对称安全轮廓的扫掠运动。Redon（Redon 等，2002）引入了首次接触时间以连续检测刚体的碰撞。Tang（Tang 等，2009）扩展了保守的推进方法，引入了扫掠球层次结构和运动界限。Snyder（1992）使用包含函数和分支定界程序来计算非线性函数的界限。Wang（Wang 等，2021）还强调了连续碰撞检测中正确性、效率和保守性之间的权衡。最近，Chen（Chen 等，2024b）为移动参数表面开发了一个基于时间的包含函数 CCD 框架，提供了无需显式时间划分的连续运动表示。这些通用的 CCD 方法为规定的刚性或参数几何建立了连续的接触谓词，但它们并不是围绕一个随船舶速度、海图 clearance 和遭遇条件变化的海上安全框架来构建的。因此，这里考虑的验证问题结合了连续的 PCTR 运动和时变不对称安全轮廓，而不是直接应用固定几何的 CCD 测试。
基于采样和反应式的规划器为动态海上导航提供了互补的机制。Chiang 和 Tapia（2018）开发了 COLREG-RRT，通过联合模拟自身船舶和周围船舶来生长基于采样的树，而 Hu（Hu 等，2023）将改进的 A-star 算法与动态窗口方法（DWA）结合用于在船舶运动和 COLREGs 约束下的局部避碰。Lyu（Lyu 等，2024）将精确的环境势场建模与 QSD、一阶 Nomoto 动力学和 COLREGs 约束结合起来，用于复杂多船环境中的避碰。Han（Han 等，2024）整合了 Hybrid A*、虚拟障碍物、时空导航走廊和最优控制，生成适应 COLREGs 的避碰轨迹。
在 reviewers 的研究中，AA-SIPP（Kim 等，2025）、基于时间的包含函数 CCD 方法（Chen 等，2024b）、精确的环境势场方法（Lyu 等，2024）和适应 COLREGs 的框架（Han 等，2024）与 CF-STQP 的不同组件最为接近。AA-SIPP 将无碰撞时间范围表示为固定分辨率空间图上的安全区间，并施加最大转弯速率约束。Chen（Chen 等，2024b）解决了移动参数表面的通用连续碰撞检测问题。Lyu（Lyu 等，2024）和 Han（Han 等，2024）关注通过势场或基于优化的公式进行 COLREGs 约束下的操纵生成。CF-STQP 则将滚动视界搜索与基于 C-AAESC 的约束和保守的 PCTR 运动重建后的验证结合在一起。该方法不声称具有概率不确定性传播或明确的 COLREGs 合规性；其安全、违规和未解决的输出构成了基于规定目标船舶轨迹的规划层证据。
总的来说，这些研究在单一的规划和验证框架内留下了三个未解决的问题。首先，空间分辨率和时间扩展没有在预测视界范围内共同控制。其次，物理船体几何、船头制动需求、船尾超越风险和局部海图 clearance 没有整合到一个共同的时间变化不对称轮廓模型中，用于搜索阶段的筛选和重建后的验证。第三，离散或固定间距的碰撞检查没有为 PCTR 运动学下的圆弧运动和旋转扫掠提供区间级别的证据。这些问题激发了所提出的框架。
受之前研究的启发，本文解决了这三个相互关联的问题，并提出了认证快速时空四叉树规划器（CF-STQP）框架。虽然 Time-expanded A* 显式地在离散时间层上扩展了固定分辨率的网格，SIPP 将时间占用压缩到相同固定分辨率网格上的安全区间，RRT 通过随机采样探索状态-时间空间，DWA 反动态地搜索局部速度指令，CF-STQP 在滚动视界之间重用非均匀四叉树，并在扩展前动态剔除不可行的状态。

1）本文采用滚动视界时空四叉树，将预测的目标船舶占用映射到非均匀叶节点的时间层。规划器在候选边扩展期间应用动态硬剪枝并评估风险成本。
2）本文采用与海图 clearance 相结合的自适应不对称船舶安全轮廓（C-AAESC），使用物理船体作为不可收缩的几何基线。它考虑了船舶速度、船头制动需求、船尾超越风险和局部海图 clearance。
3）本文采用连续时间间隔验证方法，使用非线性 PCTR 运动学。保守的间隔界限建立了区间级别的安全证据。同步的几何重叠提供了违规证据。靠近边界的区间如果证据不足，则保持未解决状态。违规和未解决的区间随后限制了局部重新规划，从而完成了搜索-验证-修复循环。

问题表述和整体框架
考虑一个二维受限港口工作空间 ????2，它包括可航行水域 ??f 和静态不可航行区域 ??s：??=??f∪??s，??f∩??s=?，其中 ??s 包括海岸线、码头、岛屿和其他在一个规划视界内保持静态的障碍物。海图被转换为本地东-北坐标系中的二进制占用网格。该网格支持四叉树构建和搜索空间表示。随后的轨迹验证使用度量距离变换。

实验设置
主要实验使用了美国佛罗里达州 Port Everglades Harbor 的国家海洋和大气管理局（NOAA）电子导航图单元 US5PEFBA。该图被转换到本地东-北坐标系，并二值化为静态占用环境。然后使用欧几里得距离变换构建了度量清晰度场。连续时间验证使用占用单元的完整几何形状，而不是单元中心近似。

结论
本文提出了 CF-STQP，用于受限港口水域中无人水面船舶的动态路径规划。它结合了滚动视界时空四叉树搜索和动态占用剪枝，以及基于 C-AAESC 和 PCTR 的连续时间三状态验证。C-AAESC 根据船舶速度、遭遇风险和海图 clearance 自动调整规划边界，而 PCTR 通过保守的间隔证据和同步的精确几何形状保留安全、违规和未解决的结果。

CRediT 作者贡献声明
Tianchen Hao：撰写——审查与编辑、撰写——原始草稿、软件、方法论。
Chunyu Song：监督、方法论、形式分析、数据管理。

资助
2026 年辽宁省普通高校研究项目；100/11562520631 吸引具有博士学位的启动人才项目；辽宁省校企合作教育项目（790825206）；大连市高层次人才创新计划（2024RQ070）；辽宁省科学技术项目：渔业作业中无人船舶的协同控制与识别（600024003）。

利益冲突声明
作者声明他们没有已知的财务利益或个人关系可能影响本文报告的工作。

Tianchen Hao|Chunyu Song