Unmanned surface vehicles path planning with improved sparrow search algorithm

Abstract

To enable optimal navigation for unmanned surface vehicle (USV), we proposed an adaptive hybrid strategy-based sparrow search algorithm (SSA) for efficient and reliable path planning. The proposed method began by enhancing the fitness function to comprehensively account for critical path planning metrics, including path length, turning angle, and navigation safety. To improve search diversity and effectively avoid premature convergence to local optima, chaotic mapping was employed during the population initialization stage, allowing the algorithm to explore a wider solution space from the outset. A reverse inertia weight mechanism was introduced to dynamically balance exploration and exploitation across different iterations. The adaptive adjustment of the inertia weight further improved convergence efficiency and enhanced global optimization performance. In addition, a Cauchy-Gaussian hybrid update strategy was incorporated to inject randomness and variation into the search process, which helped the algorithm escape local minima and maintain a high level of solution diversity. This approach significantly enhanced the robustness and adaptability of the optimization process. Simulation experiments confirmed that the improved SSA consistently outperformed benchmark algorithms such as the original SSA, PSO, and WMR-SSA. Compared with the three algorithms, in the simulated sea area, the path lengths of the proposed algorithm are reduced by 21%, 21%, and 16%, respectively, and under the actual sea simulation conditions, the path lengths are reduced by 13%, 15%, and 11%, respectively. The results highlighted the effectiveness and practicality of the proposed method, providing an effective solution for intelligent and autonomous USV navigation in complex ocean environments.

Keywords

fitness function / steering angle / chaotic mapping / inverted inertia weights / Cauchy distribution / sinusoidal chaotic mapping

References

[1] TANG G, TANG C, CLARAMUNT C, et al. Geometric a-star algorithm: an improved a-star algorithm for AGV path planning in a port environment. IEEE Access, 2021, 9: 59196-59210.

[2] CAI X, WU L, ZHAO T, et al. Dynamic adaptive multi-objective optimization algorithm based on type detection. Information Sciences, 2024, 654: 119867.

[3] HE Z, LIU C, CHU X, et al. Dynamic anti-collision a-star algorithm for multi-ship encounter situations. Applied Ocean Research, 2022, 118: 102995.

[4] WU Z, MENG Z, ZHAO W, et al. Fast-RRT: A RRT-based optimal path finding method. Applied Sciences, 2021, 11(24): 11777.

[5] JAIN M, SAIHJPAL V, SINGH N, et al. An overview of variants and advancements of PSO algorithm. Applied Sciences, 2022, 12(17): 8392.

[6] XU K, CHEN Y, ZHANG X, et al. Improved sparrow search algorithm based on multistrategy collaborative optimization performance and path planning applications. Processes, 2024, 12(12): 2775.

[7] XUE J, SHEN B. A novel swarm intelligence optimization approach: sparrow search algorithm. Systems Science & Control Engineering, 2020, 8(1): 22-34.

[8] ZHANG Z, HE R, YANG K. A bioinspired path planning approach for mobile robots based on improved sparrow search algorithm. Advances in Manufacturing, 2022, 10(1): 114-130.

[9] LIU L, LIANG J, GUO K, et al. Dynamic path planning of mobile robot based on improved sparrow search algorithm. Biomimetics, 2023, 8(2): 182.

[10] CHEN Y D, WANG P L, LIN Z C, et al. Global path planning method by fusion of A-star algorithm and sparrow search algorithm//2022 IEEE 11th Data Driven Control and Learning Systems Conference, August 3-5, 2022, Chengdu, China. New York: IEEE, 2022: 205-209.

[11] HE Y, WANG M. An improved chaos sparrow search algorithm for UAV path planning. Scientific Reports, 2024, 14: 366.

[12] LIU G Z, ZHANG S, MA G J, et al. Path planning of unmanned surface vehicle based on improved sparrow search algorithm. Journal of Marine Science and Engineering, 2023, 11(12): 2292.

[13] GAO B, SHEN W, GUAN H, et al. Research on multistrategy improved evolutionary sparrow search algorithm and its application. IEEE Access, 2022, 10: 62520-62534.

[14] ZHU B, BEDEER E, NGUYEN H H, et al. UAV trajectory planning in wireless sensor networks for energy consumption minimization by deep reinforcement learning. IEEE Transactions on Vehicular Technology, 2021, 70(9): 9540-9554.

[15] HE L, AOUF N, SONG B. Explainable deep reinforcement learning for UAV autonomous path planning. Aerospace Science and Technology, 2021, 118: 107052.

[16] ZHAO Y, MA Y, HU S. USV formation and path-following control via deep reinforcement learning with random braking. IEEE Transactions on Neural Networks and Learning Systems, 2021, 32(12): 5468-5478.

[17] YANG C, YANG H, ZHU D, et al. Chaotic sparrow search algorithm with manta ray spiral foraging for engineering optimization. Systems Science & Control Engineering, 2023, 11(1): 2249021.

[18] GAO Q, ZHENG J, ZHANG W. Research on optimization of manned robot swarm scheduling based on ant-sparrow algorithm. Journal of Physics: Conference Series, 2021, 2078(1): 012002.

[19] QIN H, SHAO S, WANG T, et al. Review of autonomous path planning algorithms for mobile robots. Drones, 2023, 7(3): 211.

[20] ÖZTÜRK Ü, AKDAĞ M, AYABAKAN T. A review of path planning algorithms in maritime autonomous surface ships: navigation safety perspective. Ocean Engineering, 2022, 251: 111010.

[21] KARUR K, SHARMA N, DHARMATTI C, et al. A survey of path planning algorithms for mobile robots. Vehicles, 2021, 3(3): 448-468.

[22] SHI Y, EBERHART R. A modified particle swarm optimizer//IEEE International Conference on Evolutionary Computation Proceedings. IEEE World Congress on Computational Intelligence,May 4-9, 1998, Anchorage, AK, USA. New York: IEEE, 1998: 69-73.

[23] SHI Y, YANG X, ZHANG Z. Construction of a new time-space two-grid method and its solution for the generalized burgers’ equation. Applied Mathematics Letters, 2024, 158: 109244.

[24] LIU Y, HE W, ZHANG H. Grid: guided refinement for detector-free multimodal image matching. IEEE Transactions on Image Processing, 2024, 33: 5892-5906.

[25] HE Y, HU X, ZHANG J, et al. Tower crane path planning based on improved ant colony algorithm. Journal of Measurement Science and Instrumentation, 2024, 15(4): 509-517.

[26] SHI Y, YANG X. A time two-grid difference method for nonlinear generalized viscous burgers’ equation. Journal of Mathematical Chemistry, 2024, 62(6): 1323-1356.