《Drones》：MIPLP: A Mixed-Integer Piecewise-Linear Programming Path-Planning Approach for the Three-Point Reeds–Shepp Problem
编辑推荐：
本文研究了一种跨域平台的检测路径规划任务，其中一艘Reeds-Shepp无人水面艇（USV）需规划从起始构型（例如USV母港）到中间检测点再到终点构型（例如技术设施）的最短曲率约束路径。该问题源于协同检测应用，可建模为三点Reeds-Shepp问题（3PRSP
本文研究了一种跨域平台的检测路径规划任务，其中一艘Reeds-Shepp无人水面艇（USV）需规划从起始构型（例如USV母港）到中间检测点再到终点构型（例如技术设施）的最短曲率约束路径。该问题源于协同检测应用，可建模为三点Reeds-Shepp问题（3PRSP），其中中间点的航向需优化。据研究人员所知，目前既无闭式解也无基于优化的解存在。研究人员提出了一种基于近似与优化的方法，该方法利用分段线性公式近似Reeds-Shepp前向-后向运动学中的三角函数约束，使所得模型能被数学规划求解器有效求解。大量仿真及与三点Dubins方法及相关方法的比较验证了所提方法的准确性与计算效率。
本研究聚焦于跨域平台协同检测任务中的路径规划问题，尤其针对无人水面艇（USV）在无人机-无人艇（UAV-USV）协同检测异常（如珊瑚礁环境监测）中的关键环节。在该场景中，USV需从已知起始构型（如母港）出发，经过中间未知航向的检测点，最终到达终点构型（如技术设施），完成曲率约束下的最短路径规划。现有研究存在明显不足：三点Dubins问题仅支持前向运动，无法处理后向机动；而两点Reeds-Shepp方法仅适用于固定航向，未能解决自由中间航向的三点问题。因此，研究人员首次将这一任务建模为三点Reeds-Shepp问题（3PRSP），并开发了混合整数分段线性规划（MIPLP）方法以联合优化路径几何与中间点航向。该方法统一了所有48种Reeds-Shepp路径类型，通过分段线性近似处理三角函数非线性约束，使问题可由商业求解器（如Gurobi）高效求解。实验结果表明，MIPLP在求解质量与计算效率上均优于三点Dubins方法及离散化启发式方法，填补了从两点RS到三点Dubins之间的理论空白。该研究发表在《Drones》期刊，为UAV-USV检测任务提供了可执行的路径规划基础。
为开展本研究，研究人员主要采用了以下关键技术方法：（1）参数化统一方法：通过二进制/整数变量表示每个运动基元的齿轮方向（前向/后向）与转向（左/右），将48种Reeds-Shepp路径类型统一在CCSCC-CCSCC五字母模板中，实现两段路径的联合建模。（2）分段线性近似（PWL）技术：对Reeds-Shepp运动学中的三角函数（sin、cos）进行分段线性化，将非线性约束转化为线性约束，使整体模型成为混合整数线性规划（MIPLP）问题。（3）模运算处理角度周期性：通过引入容差参数处理严格不等式，确保角度变量的连续性。（4）利用数学规划求解器（如Gurobi）进行分支定界优化。研究未涉及具体样本队列，所有实验基于归一化车辆参数（单位速度与最小转弯半径）进行仿真。
研究结果部分主要包含以下四个子部分：
**4.1 不需后向运动的两点问题结果**：将MIPLP应用于两点Dubins问题（无需后向运动）并与基准Dubins方法比较。结果表明，两者路径总长度、类型（LSR）及几何形态完全一致，验证了算法在前向运动场景下的正确性与无建模偏差。
**4.2 需要后向运动的两点问题结果**：将MIPLP应用于需要后向运动的两点Reeds-Shepp问题，并与基准RS方法及Dubins方法比较。结果显示，MIPLP路径长度与基准RS完全一致（相对误差在10
-7量级），且路径类型为包含尖点的“C|C|C|C|C”类型，优于强制前向的Dubins方法。这验证了算法对后向运动及尖点轨迹的建模精度。
**4.3 三点Reeds-Shepp问题结果**：在两种典型场景（无需后向运动与需后向运动）下比较MIPLP与三点Dubins解析解及离散化三点RS方法。在无需后向运动场景中，MIPLP与解析解一致（路径长度与中间航向完全相同）；在需后向运动场景中，三点Dubins因无法后向产生大幅绕行，离散化RS因缺乏全局优化导致航向突变，而MIPLP取得最短路径（长度11.0847）且中间航向连续，证明了其全局优化能力。
**4.4 参数研究**：通过改变分段长度（seglen）分析精度与效率权衡。结果显示，当seglen从0.05 m增至0.40 m时，求解时间从630 s降至10 s，而路径长度误差仍小于1%；当seglen增至0.80 m时，误差急剧升至9.9%。因此，选择0.40 m作为平衡点，可在保证精度的同时大幅提升计算效率。
讨论部分总结了方法的理论特性与局限。研究人员指出，3PRSP本质上是NP难的，但MIPLP通过混合整数分段线性近似使其在实际中可解，且能获得高质量解。分段线性引入的误差可通过细化离散化系统降低，使解接近真实Reeds-Shepp最优。方法对输入噪声不敏感，适应性强，但当前未考虑海洋洋流、波浪、障碍物、定位不确定性等实际因素。车辆模型简化为曲率约束运动，未来需扩展至障碍物丰富环境、动态扰动及多机器人协同场景。
研究结论部分翻译如下：本文提出了一种面向检测任务中三点Reeds-Shepp问题的基于优化的方法。通过将所有Reeds-Shepp运动基元统一纳入混合整数分段线性规划框架，所提方法实现了路径几何与中间点航向的联合优化，有效填补了从两点Reeds-Shepp规划到三点Dubins公式之间的长期空白。从理论角度看，这项工作为一类本质非凸且组合的曲率约束问题建立了可处理的优化框架；从实践角度看，该方法有望以可靠的计算性能获得高质量解，适用于复杂检测任务。未来工作将扩展该框架至障碍物丰富环境、动态与不确定场景以及协调多机器人Reeds-Shepp路径规划，并开展不同设置下的理论分析。
