MIPLP: A Mixed-Integer Piecewise-Linear Programming Path-Planning Approach for the Three-Point Reeds–Shepp Problem

This paper studies an inspection path-planning task for cross-domain platforms, in which a Reeds–Shepp unmanned surface vehicle (USV) must plan the shortest curvature-constrained path from the starting configuration (e.g., the USV depot) to the intermediate inspection point and then to the terminal configuration (e.g., the technical facility). The problem emerges from cooperative inspection applications and can be formulated as a three-point Reeds–Shepp problem (3PRSP), where the heading at the intermediate point needs to be optimized. To the best of our knowledge, neither closed-form nor optimization-based solutions exist for this problem. We propose an approximation-and-optimization-based approach that approximates the trigonometric constraints arising from the Reeds–Shepp forward–backward motion kinematics using piecewise-linear formulations, enabling the resulting model to be effectively solved by mathematical programming solvers. Extensive simulations and comparisons with the three-point Dubins approach and related methods demonstrate the accuracy and computational efficiency of the proposed method.