Multi-target point path planning algorithm for mobile robot based on probabilistic roadmap

doi:10.1007/s11370-025-00670-6

Return

Multi-target point path planning algorithm for mobile robot based on probabilistic roadmap

2025-12-19

PRE

Likun Hu

Zhe Kong *

DOI：10.1007/s11370-025-00670-6

Original

Original request for help

Save

Abstract

En 中文

This study proposes a novel hybrid algorithm named random walk-probabilistic roadmap and hybrid selection optimization hybrid algorithm (RPRM-HSO) for multi-target point path planning. This algorithm integrates the random walk strategy, hybrid selection optimization (HSO) algorithm, and probabilistic roadmap (PRM) algorithm. The RPRM-HSO algorithm consists of two main modules: the random walk-probabilistic roadmap (RPRM) module and the HSO module. The RPRM module employs the random walk strategy to guide sampling points from obstacle regions toward free spaces, enhances narrow passage detection through prolonged testing, and optimizes node spatial distribution via secondary normal-distribution-based fine sampling. The HSO module addresses multi-target point sequencing employing a random selection optimization algorithm and achieves path smoothing with quasi-uniform B-spline curves incorporating additional control points. Experiments demonstrate that in path searching, RPRM algorithm exhibits higher planning success rates and shorter paths compared to traditional PRM, Gauss-probabilistic roadmap and L & eacute;vy-probabilistic roadmap algorithms. For multi-target point optimization, HSO algorithm outperforms algorithms like self-organizing map, genetic algorithm-gray wolf optimizer in path quality, particularly excelling in small-to-medium datasets. The comprehensive experimental results demonstrate that the RPRM-HSO algorithm outperforms other algorithms such as the A*and ant colony hybrid algorithm, bidirectional rapidly-exploring random trees and ant colony hybrid algorithm, and twin delayed deep deterministic policy gradient algorithm in complex environments. Specifically, RPRM-HSO algorithm achieves a higher planning success rate, a shorter average path length, and reduced computational time. These results verify its superior performance in terms of convergence speed, planning quality, and stability.

Keywords:

Multi-target point path planning

Narrow passages sampling

Path smoothing

Hybrid selection optimization

Probabilistic roadmap algorithm