PaperlayerView exact revision on arXiv

Source-linked AI summary

Unmanned Surface Vehicle Path Planning from the Perspective of Multi-Modality Constraints: A Comprehensive Analysis

Chunhui Zhou, Shangding Gu, Yuanqiao Wen, Zhe Du, Changshi Xiao, Liang Huang, Man Zhu

arXiv:2007.01691v3cs.RO

TL;DR

USVs have important maritime roles, but their civil applications remain limited and research is comparatively sparse. This paper reviews their path planning through a multi-modality-constraint framework, organizing it into three stages. It concludes that full autonomous USV motion planning has not yet been achieved and identifies directions for future development.

  • Problem

    USVs have important maritime roles, yet their civil applications remain limited and research is comparatively sparse.

    Source: §1.1 · p. 2

  • Method

    The paper reviews USV path planning by analyzing its constraints and organizing research methods into Route Planning, Trajectory Planning, and Motion Planning.

    Source: ARTICLE · p. 6, §6 · p. 27

  • Results

    The review concludes that full autonomous USV motion planning has not yet been achieved.

    Source: §6 · p. 28

  • Takeaways & Limitations

    Future development should integrate perception, robust control, intelligent decision-making, task execution, and complex-environment adaptation.

    Source: §6 · p. 29

    Full autonomous USV motion planning remains unachieved.

    Source: §6 · p. 28

Abstract

from arXiv · show

The essence of the path planning problems is multi-modality constraint. However, most of the current literature has not mentioned this issue. This paper introduces the research progress of path planning based on the multi-modality constraint. The path planning of multi-modality constraint research can be classified into three stages in terms of its basic ingredients (such as shape, kinematics and dynamics et al.): Route Planning, Trajectory Planning and Motion Planning. It then reviews the research methods and classical algorithms, especially those applied to the Unmanned Surface Vehicle (USV) in every stage. Finally, the paper points out some existing problems in every stage and suggestions for future research.

1. INTRODUCTION.

The introduction situates USVs within the wider development of unmanned vehicles, noting their important maritime applications alongside relatively limited civil use and research. It presents path planning as a key part of vehicle autonomy and frames USV planning through four questions and a comparative account of vehicle types and automation levels.

1.1 BACKGROUND INTRODUCTION

  • USV civil applications remain limited and research on them is comparatively sparse and began later than for other unmanned vehicles.Source: §1.1 · p. 2
  • USVs support ocean sampling, seabed mapping, network monitoring, search and rescue, and harbor patrolling, and have potential in urban-waterway cargo transport.The paper also describes USVs as an important tool for ocean exploration.Source: §1.1 · p. 2
  • Autonomy includes planning and executing actions without human intervention, and safe path planning is a key technology for USVs’ complex tasks.Source: §1.1 · p. 2
  • The introduction replaces the traditional three planning questions with four USV-focused questions and presents comparisons of vehicle types, USV applications, and automation levels.It also says the automation and intelligence level classification was expanded and refined.Source: §1.1 · p. 3, Table 1 · p. 3, Table 2 · p. 4

ARTICLE

The article reviews USV path planning through a multi-modality-constraint lens, organizing its methods and problems into three stages. Its structure moves from constraint elements to the stages and then to a synthesis and future directions.

ARTICLE

  • The article analyzes USV path-planning constraints and reviews progress, methods, and classical algorithms across Route Planning, Trajectory Planning, and Motion Planning.The review focuses especially on USV applications and research from the past two decades.Source: ARTICLE · p. 6

1.3 THE MAIN STRUCTURE OF THE ARTICLE

  • The article first analyzes modality constraints, then treats the three planning stages, and concludes with a synthesis and future directions.Source: §1.3 · p. 6

2. THE PROGRESS OF PATH PLANNING.

The section frames USV path planning as a progression of constraint scope, organized around planning space, time, behavior, and criterion. Its three stages distinguish route, trajectory, and motion planning by the constraints each considers.

2. THE PROGRESS OF PATH PLANNING.

  • USV path planning is divided into route, trajectory, and motion planning according to varying modality constraints and application scenarios.The framework identifies planning space, time, behavior, and criterion as basic ingredients.Source: §2 · pp. 7, 9
  • Route planning treats the USV as a particle, prioritizes geography and path quality, and seeks an optimal route without accounting for scale or dynamic performance.The ship-routing example contrasts large-scale routing with detailed consideration of how the ship reaches its destination.Source: Figure 1 · p. 8, §2 · p. 9
  • Trajectory planning adds selected dynamic and environmental constraints, such as shape, kinematics, channel width, speed, and angular velocity, to seek an optimal trajectory.The port-entry example considers vessel size and kinematics while leaving out some factors such as moments and forces.Source: §2 · pp. 8–10
  • Motion planning combines path planning with control under more comprehensive dynamic constraints to produce a practical motion path.The berthing example considers force, inertia, kinematics, and vessel size for precise steering.Source: §2 · pp. 8, 10

3. ROUTE PLANNING.

Route planning treats a USV as a particle in a large-scale environment and selects a route without accounting for its shape or dynamic constraints. The section reviews environment models and route-search methods, while noting that this abstraction is insufficient for scenarios requiring more precise planning.

3.1 TWO IMPORTANT PARTS OF ROUTE PLANNING

  • Classical route-planning algorithms generally separate the task into environment modeling and optimal-path searching.Environment modeling transforms and discretizes planning space; the search step finds a path through that representation.Source: §3.1 · p. 12, §3.1.1 · p. 12

3.1.1 ENVIRONMENT MODELING

  • Visibility graphs, Voronoi diagrams, and grid maps are common environment models, with grid maps widely used for route planning.Grid maps divide the planning space into rectangular cells; the models are assessed by search time, completeness, and optimality.Source: §3.1.1 · pp. 12–13
  • Voronoi paths are generally longer but farther from obstacles than visibility-graph paths, while grid paths can be jagged and nonoptimal without smoothing.Search-time trade-offs include visibility-graph complexity O(n^2), Voronoi complexity O(nlog(n)), and grid resolution choices that trade environmental detail against search cost.Source: §3.1.1 · pp. 13–14

3.1.2 OPTIMAL PATH SEARCHING

  • Route searches use heuristic, evolutionary, and potential-field algorithms, but each family has reported drawbacks in computation or local-optimum susceptibility.Heuristics can consume more time and memory as the search range grows; evolutionary methods may be stochastic and slow, and potential fields can also get stuck in local optima.Source: §3.1.2 · p. 14
  • USV examples combine electronic charts and radar with Dijkstra search, reinforcement learning, topological maps, A* smoothing, or artificial potential fields.Other route-planning approaches combine classical algorithms with marine instruments and regulations; reported approaches may omit moving obstacles or USV kinematics and dynamics.Source: §3.1.2 · pp. 15–16

3.2 SUMMARY OF ROUTE PLANNING

  • Route planning abstracts the USV as a particle and selects a reachable route, but ignoring its shape and dynamics limits precision in some real scenarios.Its planning space is constrained by environmental connectivity, and it does not specify how to execute the route.Source: §3 · p. 11, §3.1.2 · p. 15, §3.2 · p. 17

4. TRAJECTORY PLANNING.

Trajectory planning extends route planning by incorporating partial shape and dynamic constraints to produce smoother, continuous, more physically realistic paths. The paper reviews curve fitting and multi-constraint optimization, while noting that constraints remain incomplete and their interactions are neglected.

4. TRAJECTORY PLANNING.

  • Trajectory planning treats the USV as more than a particle, incorporating partial constraints such as size, speed, heading, and curvature to make paths smooth and continuous.The paper characterizes this stage as an improvement over route planning and a medium-modality constraint problem.Source: §4 · p. 18

4.1 TRAJECTORY PLANNING ANALYSIS

  • The two common approaches are curve fitting and multi-constraint optimization.Curve fitting makes a curve fit a planned polyline; multi-constraint optimization adds some dynamic constraints to route-planning algorithms.Source: §4.1 · pp. 18–20
  • Dubins paths connect starting and finishing poses with up to three straight-line or circular-arc pieces, but transitions between them can create curvature jumps.Fermat’s spirals, B splines, and Bessel curves are cited as alternatives for connecting successive straight lines without curvature discontinuities.Source: §4.1 · p. 19
  • Examples add heading, size, speed, or curvature constraints, while other approaches address dynamic obstacles, COLREGs, or USV kinematics.The review describes Finite A* with heading and size constraints, relative-speed planning, COLREGs-based collision avoidance, and Q-learning using USV features.Source: §4.1 · pp. 20–21

4.2 SUMMARY OF TRAJECTORY PLANNING

  • Trajectory planning is framed as reachability under partial constraints, with discrete planning time and an objective of optimizing a trajectory that satisfies environmental connectivity and selected USV constraints.The constraints include environmental connectivity, some size and dynamic constraints, and behavior requirements such as speed and heading.Source: §4.2 · pp. 21–22
  • The considered dynamic constraints remain incomplete and independent, so their interactions are neglected and trajectory planning does not specify how to execute the path.The paper presents motion planning as the next stage addressing how to reach the goal.Source: §4.2 · p. 22

5. MOTION PLANNING.

Motion planning is the final, fine-control stage: it treats the USV as a rigid body and accounts for its dynamic constraints. The review covers control-theory and random-sampling approaches, while noting that full autonomous motion planning remains unresolved.

5. MOTION PLANNING.

  • Motion planning treats the research object as a rigid body and considers all dynamic constraints to determine whether its control system can realize a planned path.The paper describes this as the final stage and goal of path planning, focused on fine control.Source: §5 · pp. 22–23

5.1 TWO SYSTEMS OF MOTION PLANNING

  • Fully actuated systems can control all motion poses through dynamic equations, whereas underactuated USVs cannot attain every motion state and require reachability analysis.The distinction follows from whether the degree of control equals or falls below the degree of freedom.Source: Figure 12 · p. 23, §5.1 · p. 23

5.2.1 BASED ON CONTROL THEORY

  • Control-theory methods first plan a collision-free route, then use a controller based on the object’s mathematical model to produce the final path.The controller includes kinematics and dynamics constraints and reconstructs or approximates the initially planned path.Source: §5.2.1 · p. 24

5.2.2 BASED ON RANDOM SAMPLING

  • Random-sampling methods address higher-dimensional motion-planning problems with PRM roadmaps or RRT trees whose states and transitions represent feasible poses and motions.RRT can incorporate control inputs and kinetic models, and the review notes its use in dynamic environments.Source: §5.2.2 · p. 25
  • Robotics motion-planning methods need improvement for USVs because water inertia, resistance, and response time make their control more complex than for UGVs or UAVs.The paper also notes the need for more precise steering as water-traffic density increases and sailing areas shrink.Source: §5.2.2 · p. 26

5.3 SUMMARY OF MOTION PLANNING

  • Motion planning is framed as reachability under environmental, size, and dynamic constraints, with behavior specified by control instructions such as power and rudder angles.Its criterion is a path with behavioral instructions that reaches the target while meeting environmental connectivity and USV constraints.Source: §5.3 · pp. 26–27
  • For a harbor collision-avoidance approach, the review says it remains unclear how candidate trajectories are generated and how the USV should be controlled to follow the selected path.The cited method predicts possible trajectories and uses min-max game-tree search to select one with the smallest collision probability.Source: §5.3 · p. 27

6. CONCLUSION AND OUTLOOK.

The conclusion organizes USV path planning into route, trajectory, and motion stages and identifies unresolved challenges across them. It recommends research on integrated perception, control, decision-making, task execution, and environmental adaptation, alongside specific short- and long-term research directions.

6. CONCLUSION AND OUTLOOK.

  • The paper divides USV path planning into route, trajectory, and motion stages and reviews each stage’s methods, constraints, problems, and algorithms.The stages are organized by multi-modality constraints.Source: §6 · p. 27
  • Route-planning research rarely combines navigation rules and semantic rules with route planning, while trajectory planning still needs work to achieve real-time operation.The review identifies both as remaining research needs for their respective stages.Source: §6 · p. 28
  • The paper says full autonomous USV motion planning has not yet been achieved.It also states that an effective way to guide the USV’s control systems to reach a goal autonomously remains to be developed.Source: §6 · p. 28
  • USV planning challenges differ by stage: route planning faces weather hazards, trajectory planning must avoid static and dynamic obstacles, and motion planning must manage precise steering and environmental effects.The examples span large-scale routing, medium-scale port navigation, and small-scale maneuvers such as berthing.Source: §6 · pp. 28–29
  • The authors call for integrating perception, robust control, intelligent decision-making, task execution, and adaptation to complex environments.They also identify hydrodynamic effects and multi-objective concerns including rudder smoothness, navigation distance, economy, and safety as issues for further work.Source: §6 · p. 29
  • Short-term directions include quantifying navigation rules, studying semantic situations, applying advanced control methods, and planning routes and motion commands in complex sea conditions.The paper notes that semantic planning and control are rarely seen in USV path planning and that USV navigation is nonlinear and uncertain.Source: §6 · pp. 29–30
  • Long-term directions include autonomous berthing, coordinated USV formations, group navigation in complex environments, and cooperation among USVs, UAVs, and submarines.The review identifies current, wind, and shore-wave effects as challenges for autonomous berthing and complex environments as an open issue for formation navigation.Source: §6 · p. 30
Loading 2007.01691v3…