关键词: 移动机器人, 多目标点, 路径规划, 概率路线图, 层次概率路线图, 旅行商问题

Abstract:

Path planning is a crucial and fundamental research direction in the field of mobile robotics. In practical engineering applications, mobile robots are often required to perform traversal tasks involving multiple target points, where the core challenge of obtaining the optimal traversal sequence lies in efficiently calculating the path cost between each pair of multi-goal points, constructing a reliable cost adjacency matrix, and further formulating the traversal problem as a Traveling Salesman Problem (TSP) for optimal solution. As a classic sampling-based motion planning algorithm, the Probabilistic Road Map (PRM) exhibits a distinct advantage of multiple query reuse after a single roadmap construction, making it suitable for batch computation of the adjacency matrix among multi-goal points. However, the conventional PRM approach suffers from an inherent trade-off between planning accuracy and computational efficiency, which severely restricts its practical application in complex multi-goal traversal scenarios. Specifically, a PRM with a high sampling density can achieve precise estimation of pairwise path costs, but it inevitably leads to excessive computational overhead and prolonged time consumption. In contrast, a PRM with a low sampling density significantly improves computational efficiency, yet it fails to ensure the feasibility of planned paths and the reliability of path cost estimation. To address the aforementioned contradiction between accuracy and efficiency, a Hierarchical Probabilistic Road Maps (HPRM) method was proposed to compute the path costs between multi-goal point pairs at differentiated precision levels. HPRM was composed of two core stages: the initial calculation stage and the recalculation stage. In the initial calculation stage, a low-sampling-rate PRM was constructed to preliminarily plan paths for all multi-goal point pairs, and an initial cost adjacency matrix was established based on the preliminarily calculated path costs. In the recalculation stage, the key multi-goal point pairs that were sensitive to the solution of the traversal order were identified and selected. For these sensitive point pairs, high-precision path replanning was performed on a high-sampling-rate PRM, and the initial adjacency matrix was updated synchronously with the refined path-cost values. Subsequently, the optimized adjacency matrix was utilized to construct the TSP model, and the optimal traversal sequence of multi-goal points was solved by TSP solvers. Finally, the global traversal path was generated by sequentially connecting each multi-goal point with the corresponding optimized local paths. To realize the rational and adaptive selection of multi-goal point pairs for recalculation, an adaptive point pair selection strategy was further proposed, integrating two sub-strategies: the path cost-based screening strategy and the multi-goal point clustering-based screening strategy. Taking the optimal clustering number of multi-goal points as the core decision criterion, this strategy employed a threshold-based judgment mechanism to identify the spatial distribution characteristics of the multi-goal point set, and adaptively selected the most appropriate sub-strategy to screen the sensitive point pairs. Comparative experiments were conducted in multiple complex simulation environments to verify the effectiveness and superiority of the proposed adaptive selection strategy. Experimental results demonstrated that, compared with the existing mainstream PRM-based multi-goal traversal methods, the path cost generated by the proposed algorithm was reduced by 0.5%~1.0%, while the computational time consumption was decreased by 20%~40%. These results indicated that the proposed HPRM algorithm effectively balanced the path planning accuracy and computational overhead, and possessed higher comprehensive computational efficiency and practical application potential in robot multi-goal path planning.

Key words: mobile robot, multi-goal, path planning, probabilistic roadmap, hierarchical probabilistic roadmap, traveling salesman problem