A Path-Planning Strategy for Unmanned Surface Vehicles Based on an Adaptive Hybrid Dynamic Stepsize and Target Attractive Force-RRT Algorithm

Zhen Zhang, Defeng Wu, Jiadong Gu, Fusheng LiJournal of Marine Science and Engineering 2019 · DOI

TL;DR

This paper introduces a novel path-planning algorithm, AHDSTAF-RRT, for Unmanned Surface Vehicles (USVs). By adaptively combining dynamic step sizes and target attractive forces, it significantly improves USV navigation in complex environments, outperforming existing RRT-based methods in both path length and computational speed.

What Problem Does This Paper Address?

The increasing use of Unmanned Surface Vehicles (USVs) in diverse applications like marine exploration, search and rescue, and coastal patrolling necessitates robust and efficient path-planning capabilities. While the Rapidly-exploring Random Tree (RRT) algorithm is a popular choice due to its simplicity and speed, it suffers from drawbacks such as high randomness, inflexible step sizes, and slow calculation, particularly in complex environments with narrow passages and open areas. This paper aims to address these limitations by developing an enhanced RRT algorithm that can navigate these challenging terrains more effectively and efficiently.

Methods

The core of this research is the development of the Adaptive Hybrid Dynamic Stepsize and Target Attractive Force-RRT (AHDSTAF-RRT) algorithm. This algorithm builds upon the basic RRT by incorporating two key enhancements:

  • Dynamic Stepsize: The step size for tree growth is dynamically adjusted. In narrow areas, a smaller step size is used to improve maneuverability and avoid obstacles. In open areas, a larger step size is employed to increase exploration speed.
  • Target Attractive Force: A force is introduced to bias the tree's growth towards the goal. This helps reduce randomness and shorten path lengths, especially in open areas.

The "adaptive hybrid" aspect is crucial. The algorithm intelligently switches between or combines these mechanisms based on the local environment. Specifically:

  • In narrow areas, the attractive force's influence is reduced or removed to prevent premature collisions, while the dynamic stepsize is prioritized.
  • In open areas, both the dynamic stepsize and the target attractive force are utilized, with the attractive force's weight increased to accelerate convergence.

This adaptive strategy is implemented through a CheckObstacle function that determines the proximity to obstacles, guiding the algorithm's behavior.

Datasets

The paper uses a processed map of the Xinglin Gulf near Xiamen, China, as its simulation environment. This map was extracted from a map network and processed into a 1500x1500 pixel binary image, where white represents collision-free space and black represents obstacles. The authors note that this map processing method is specific to the simulation experiment and other methods would be required for real-world tasks.

Key Insights and Ideas

  • The "Adaptive" Nature is Key: Simply combining dynamic stepsize and attractive force isn't enough. The paper's core insight is that how these are combined and adapted to the environment (narrow vs. open areas) is critical for optimal performance.
  • Narrow Areas Require Caution: The attractive force, while beneficial in open spaces, can hinder navigation in narrow passages by causing premature collisions. Reducing its influence in these areas is a crucial design choice.
  • Balancing Speed and Precision: The algorithm successfully balances the need for rapid exploration in open areas with the precision required for navigating confined spaces.
  • RRT's Versatility: Even with its limitations, RRT remains a strong foundation. The paper demonstrates how targeted enhancements can significantly boost its performance without fundamentally altering its tree-extending nature.

Key Results

The AHDSTAF-RRT algorithm was compared against the basic RRT, DS-RRT (Dynamic Stepsize-RRT), TAF-RRT (Target Attractive Force-RRT), and DSTAF-RRT (Dynamic Stepsize and Target Attractive Force-RRT) on the Xinglin Gulf map.

  • Path Length: The AHDSTAF-RRT achieved the shortest average path lengths across all tested paths, outperforming the basic RRT by a significant margin. For example, for path 6, AHDSTAF-RRT achieved 1737.9915, while basic RRT achieved 2203.9932.
  • Number of Branches (Computational Cost): The AHDSTAF-RRT generally produced fewer branches, indicating a more efficient search and thus lower computational time. It had the lowest average number of branches for several paths, demonstrating its improved computational efficiency.
  • Performance in Narrow Areas: The paper highlights that the TAF-RRT and DSTAF-RRT performed poorly in narrow areas, confirming the authors' hypothesis. The AHDSTAF-RRT, by adaptively reducing the attractive force, showed superior performance in these challenging regions.

Limitations and Future Work

  • Simulation-Focused: The map processing and validation were conducted solely within a simulation environment. Real-world testing with actual USVs is necessary to confirm these findings.
  • Further Enhancements: The authors suggest incorporating more advanced mechanisms to further improve path-planning performance and computational speed.
  • Complex Environments: While the Xinglin Gulf map presents a complex terrain, studying the algorithm's performance in even more intricate environments is a future direction.
  • Motion Control Integration: The paper focuses on path generation. Integrating this with motion control for curved sliding after path generation is identified as a significant area for future work.

Summary updated

Abstract

It is well known that path planning has always been an important study area for intelligent ships, especially for unmanned surface vehicles (USVs). Therefore, it is necessary to study the path-planning algorithm for USVs. As one of the basic algorithms for USV path planning, the rapidly-exploring random tree (RRT) is popular due to its simple structure, high speed and ease of modification. However, it also has some obvious drawbacks and problems. Designed to perfect defects of the basic RRT and improve the performance of USVs, an enhanced algorithm of path planning is proposed in this study, called the adaptive hybrid dynamic stepsize and target attractive force-RRT(AHDSTAF-RRT). The ability to pass through a narrow area and the forward speed in open areas of USVs are improved by adopting the AHDSTAF-RRT in comparison to the basic RRT algorithm. The improved algorithm is also applied to an actual gulf map for simulation experiments, and the experimental data is collected and organized. Simulation experiments show that the proposed AHDSTAF-RRT in this paper outperforms several existing RRT algorithms, both in terms of path length and calculating speed.
BibTeX
@article{zhang2019path,
  author = {Zhen Zhang and Defeng Wu and Jiadong Gu and Fusheng Li},
  title = {{A Path-Planning Strategy for Unmanned Surface Vehicles Based on an Adaptive Hybrid Dynamic Stepsize and Target Attractive Force-RRT Algorithm}},
  journal = {Journal of Marine Science and Engineering},
  year = {2019},
  doi = {10.3390/jmse7050132},
}

Loading related content...

Figure