Motion Plan of Maritime Autonomous Surface Ships by Dynamic Programming for Collision Avoidance and Speed Optimization

Xiongfei Geng, Yongcai Wang, Ping Wang, Baochen Zhang2019 · DOI

TL;DR

This paper tackles the complex challenge of enabling Maritime Autonomous Surface Ships (MASS) to navigate safely and efficiently alongside conventional vessels. They introduce a novel dynamic programming approach that optimizes collision avoidance and speed, outperforming greedy methods in simulations by significantly reducing collision rates and improving efficiency.

What Problem Does This Paper Address?

Maritime Autonomous Surface Ships (MASS) promise to revolutionize maritime transportation, offering enhanced safety and efficiency. However, ensuring their safe and efficient operation in dynamic, crowded waterways, especially when interacting with conventional ships, remains a significant challenge. Unlike ground robots, MASS have substantial inertia and hydrodynamic forces, requiring more predictive motion planning. Furthermore, while MASS can leverage advanced sensors like radar, LiDAR, and AIS for rich environmental awareness, effectively integrating this information into real-time motion planning to balance safety, speed, and smoothness is an open problem. Existing methods often struggle with the predictive nature required for large vessels and the complexities of multi-agent interactions in a 3D maritime environment.

Methods

The authors propose a multi-faceted approach to MASS motion planning:

  • Velocity Obstacle (VO) Model: They extend the traditional Velocity Obstacle model to represent collision-free regions for both dynamic and static obstacles (ships, shorelines, islands). This model considers the relative velocities of surrounding objects.
  • Greedy Motion Planning: A basic greedy algorithm is introduced, which makes decisions based on the immediate next interval. However, the paper highlights its limitations, showing it can fail in complex scenarios.
  • Greedy-Risk Algorithm: To address the greedy algorithm's shortcomings, a "way-blocking metric" is introduced. This metric quantifies the risk of becoming trapped in a region surrounded by obstacles, allowing the greedy algorithm to consider future collision risks.
  • Dynamic Programming (DP) for Multi-Interval Optimization: The core contribution is a dynamic programming approach. This method assumes constant velocities for surrounding ships to predict future VOs and then uses a recursive cost function to find an optimal multi-interval motion plan. This DP approach aims to optimize for safety, efficiency (time to destination), and smoothness (avoiding sharp turns/accelerations).
  • Discretization of Feasible Accelerations: To manage the computational complexity of the DP approach, feasible acceleration vectors are discretized, creating a set of candidate actions.

Datasets

Not discussed in the paper. The simulations were conducted using MATLAB, with scenarios generated based on defined parameters for ship density, velocities, and environmental conditions.

Key Insights and Ideas

  • Predictive Planning is Crucial for MASS: The significant inertia and hydrodynamic forces of large vessels necessitate motion planning that looks beyond the immediate time step, unlike many ground robot approaches.
  • VO Model's Adaptability: The Velocity Obstacle model, when extended and adapted, proves effective for representing collision avoidance constraints in a dynamic maritime environment.
  • Greedy Algorithms' Limitations: Simple greedy approaches, while computationally efficient, can lead to suboptimal or even unsafe situations by failing to anticipate future consequences.
  • Way-Blocking Metric Enhances Risk Awareness: Incorporating a "way-blocking metric" significantly improves the risk assessment of greedy algorithms, making them more robust.
  • Dynamic Programming for Global Optimality: The DP approach, by considering multiple future intervals, offers a more globally optimal solution for balancing safety, efficiency, and smoothness, especially when surrounding ship behavior can be reasonably predicted.
  • Trade-offs Exist: While DP provides superior performance, it requires more accurate information about surrounding ships and has higher computational demands.

Key Results

  • The proposed DP algorithm demonstrated the lowest collision rate overall compared to the greedy and greedy-risk algorithms in extensive simulations.
  • The DP algorithm also achieved better sailing efficiency (faster time to destination) than the greedy approaches.
  • The greedy-risk algorithm showed improved collision avoidance over the basic greedy algorithm, especially when higher weights were assigned to the way-blocking metric.
  • The performance of all algorithms was evaluated under varying ship densities and velocities, with DP consistently showing superior safety and efficiency.

Limitations and Future Work

  • Assumption of Constant Velocity: The DP approach assumes surrounding ships maintain constant velocities, which may not always hold true in real-world scenarios.
  • Computational Complexity of DP: Inferring VOs for all possible future scenarios in the DP approach can be computationally intensive. The paper suggests discretizing the map or limiting the number of future intervals to mitigate this.
  • Need for Interval-Based Greedy for Unpredictable Ships: The paper acknowledges that if surrounding vessels' motions are not captured by AIS or are highly unpredictable, the interval-based greedy method might still be necessary for local collision avoidance.
  • Future Work: The authors plan to investigate the joint work of DP and locally-greedy algorithms to combine the strengths of both approaches. They also aim to address scenarios where AIS information is not available for all vessels.

Summary updated

BibTeX
@misc{geng2019motion,
  author = {Xiongfei Geng and Yongcai Wang and Ping Wang and Baochen Zhang},
  title = {{Motion Plan of Maritime Autonomous Surface Ships by Dynamic Programming for Collision Avoidance and Speed Optimization}},
  year = {2019},
  doi = {10.3390/s19020434},
}
Figure