An Optimal-Path-Planning Method for Unmanned Surface Vehicles Based on a Novel Group Intelligence Algorithm

Shitu Chen, Feng Ling, Xuteng Bao, Zhe Jiang, Bowen Xing, Jingxiang XuJournal of Marine Science and Engineering 2024 · DOI

TL;DR

This paper introduces a novel group intelligence algorithm, DOASO-IABC, for Unmanned Surface Vehicles (USVs) that excels at dynamic obstacle avoidance and smooth path planning in challenging aquatic environments. It significantly improves upon traditional methods by effectively handling water currents and moving obstacles, leading to safer and more efficient navigation.

What Problem Does This Paper Address?

Navigating the complex and dynamic underwater world presents a significant challenge for Unmanned Surface Vehicles (USVs). Efficient path planning is essential for their safe and effective operation, but existing algorithms often struggle with several key issues:

  • Dynamic Obstacle Avoidance: USVs must not only avoid static obstacles but also react to unpredictable moving objects in real-time.
  • Water Current Influence: The drag and push of water currents can significantly affect a USV's trajectory, making it difficult to maintain a planned path.
  • Path Smoothness: Abrupt turns and sharp inflections in planned paths can lead to increased energy consumption, reduced speed, and potential mechanical stress on the USV.
  • Integration of Global and Local Planning: Many algorithms focus on either global path planning (finding the overall route) or local path planning (real-time obstacle avoidance), but integrating these effectively in dynamic environments is complex.

This paper aims to address these challenges by developing a unified algorithm that can handle dynamic obstacles, water currents, and produce smooth, efficient paths for USVs.

Methods

The core of this research is the development of a novel group intelligence algorithm called Dynamic Obstacle Avoidance Strategy with Smooth Optimization for the Artificial Bee Colony (DOASO-IABC). This algorithm builds upon the Artificial Bee Colony (ABC) algorithm and incorporates several key enhancements:

  • Global Path Planning (Static Environments): For known static obstacle positions, the standard ABC algorithm is used to find the globally optimal path.
  • Dynamic Obstacle Avoidance and Current Resistance: When faced with moving obstacles and water currents, the algorithm integrates:
  • Dynamic Obstacle Avoidance Strategies: This includes methods for screening potential obstacles and predicting collision risks based on the USV's and obstacle's trajectories.
  • Eight-Directional Current Resistance: A novel approach to account for the influence of water flow from multiple directions, aiming to minimize its impact on navigation.
  • Advanced Path Smoothing: The paper utilizes an Advanced_sprcv optimization model, which is a refinement of Bezier curve smoothing techniques. This aims to create smoother paths by reducing sharp turns and inflections, thereby improving navigability and energy efficiency.
  • Hybrid Approach: The algorithm combines global path planning with real-time dynamic obstacle avoidance and current resistance strategies to achieve locally optimal paths.

Datasets

Not discussed in the paper. The experiments were conducted using simulated environments represented by grid maps.

Key Insights and Ideas

  • The "lost" state of traditional ABC: The paper highlights how traditional ABC algorithms are significantly affected by water flow, leading to random landing points and difficulty in determining optimal paths in dynamic aquatic environments.
  • "Unified" movement with improved ABC: The proposed DOASO-IABC algorithm demonstrates a more "unified" and controlled movement trajectory, effectively resisting water flow and finding better landing points.
  • The importance of considering water flow as a "traction" force: Unlike dynamic obstacles that primarily exert a "repulsion" effect, water flow can also exert a "traction" force, pushing the USV. The algorithm accounts for this dual nature.
  • Bezier curves alone are insufficient for dynamic environments: While Bezier curves can smooth paths, they may not guarantee obstacle avoidance in dynamic scenarios. The integration of the sprcv function is crucial for ensuring both smoothness and safety.
  • Trade-off between shortest path and energy consumption: The paper acknowledges that the shortest path might not always be the most energy-efficient due to variable water flow influences.

Key Results

The DOASO-IABC algorithm demonstrated significant improvements over traditional bee colony algorithms:

  • Path Length: Increased optimization path length by 8% (this seems to be a typo in the abstract, likely meaning improved path quality or efficiency, not necessarily longer path).
  • Optimization Time: Shortened optimization time by 50%.
  • Obstacle Avoidance: Achieved almost 100% avoidance of dynamic obstacles.
  • Smoothness: The improved algorithm significantly enhances path smoothness, reducing sharp turns and improving navigability.
  • Efficiency: The algorithm is shown to be more efficient in searching for the shortest path in dynamic environments.

Limitations and Future Work

  • Path Length vs. Energy Consumption: The paper notes that the shortest path may not always be the lowest energy consumption path, especially considering water flow. Future work could explore optimizing for energy efficiency more directly.
  • Generalizability: While the paper suggests applicability to underwater vehicles, UAVs, and other facilities, further validation in these diverse domains would be beneficial.
  • Real-world Testing: The study relies on simulations. Real-world testing with actual USVs would be crucial to validate the algorithm's performance in complex, unpredictable marine conditions.
  • Complex Dynamic Environments: While the algorithm handles dynamic obstacles, further research could explore scenarios with more complex interactions between multiple dynamic obstacles and varying environmental conditions.

Summary updated

Abstract

Path planning is crucial for unmanned surface vehicles (USVs) to navigate and avoid obstacles efficiently. This study evaluates and contrasts various USV path-planning algorithms, focusing on their effectiveness in dynamic obstacle avoidance, resistance to water currents, and path smoothness. Meanwhile, this research introduces a novel collective intelligence algorithm tailored for two-dimensional environments, integrating dynamic obstacle avoidance and smooth path optimization. The approach tackles the global-path-planning challenge, specifically accounting for moving obstacles and current influences. The algorithm adeptly combines strategies for dynamic obstacle circumvention with an eight-directional current resistance approach, ensuring locally optimal paths that minimize the impact of currents on navigation. Additionally, advanced artificial bee colony algorithms were used during the research process to enhance the method and improve the smoothness of the generated path. Simulation results have verified the superiority of the algorithm in improving the quality of USV path planning. Compared with traditional bee colony algorithms, the improved algorithm increased the length of the optimization path by 8%, shortened the optimization time by 50%, and achieved almost 100% avoidance of dynamic obstacles.
BibTeX
@article{chen2024optimal,
  author = {Shitu Chen and Feng Ling and Xuteng Bao and Zhe Jiang and Bowen Xing and Jingxiang Xu},
  title = {{An Optimal-Path-Planning Method for Unmanned Surface Vehicles Based on a Novel Group Intelligence Algorithm}},
  journal = {Journal of Marine Science and Engineering},
  year = {2024},
  doi = {10.3390/jmse12030477},
}
Figure