.png){kind=icon}
.png){kind=icon}
Return
Parallel Multi-Tree Graph: A Parallel Generalized Free Space Structuring Method and Efficient Path Planning Strategy
.png){kind=icon}
PRE
AI
DOI：10.1109/tase.2026.3715832.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Path planning in high-dimensional, complex environments is a crucial yet challenging task in robotics. Traditional graph search methods and sampling-based planners frequently face limitations in computational efficiency and convergence speed. Geometry-based space preprocessing techniques can significantly enhance planner efficiency. However, they are unsuitable for high-dimensional and complex configuration spaces. This paper introduces the Parallel Multi-Tree Graph (PMTG), a path planning framework that uses random trees to partition free space in arbitrary dimensions. PMTG forms a high-level topological representation of the environment. This approach allows each tree to independently expand and optimize within its local space through parallel computation, facilitating rapid space structuring and efficient initial pathfinding. A synchronization mechanism based on edge priority queues ensures consistent expansion speeds across trees, maintaining the quality of space partitioning. Moreover, PMTG accelerates path improvement during the planning phase by guiding a non-uniform sampling process. Simulations and real-world experiments demonstrate that PMTG delivers performance comparable to state-of-the-art path planning algorithms. By leveraging parallel computation to pre-structure the configuration space, PMTG achieves substantial wall-clock acceleration in path planning, especially under limited computational time budgets. While subject to the same dimensionality constraints as all sampling-based methods, PMTG consistently maintains competitive or superior practical efficiency across a wide range of tasks, particularly excelling in the dimensional range typical of complex real-world robotic systems. Note to Practitioners—This paper introduces the Parallel Multi-Tree Graph (PMTG), a method designed to improve path planning performance for agents operating in high-dimensional and complex configuration spaces. Traditional sampling-based planners can be computationally intensive and slow to converge, particularly in challenging environments with high-dimensional free spaces. PMTG addresses these issues by creating a structured representation of the free space, using multiple random trees to partition it and enable efficient, parallelized path search. The method incorporates a synchronization mechanism to maintain consistent expansion across multiple trees, thereby improving planning efficiency and accuracy. While PMTG performs well across high-dimensional tasks, the computational demands for constructing PMTG in real-time may be high in very large spaces. In static or predominantly static environments, PMTG can be pre-constructed once and loaded from memory, enabling real-time planning with millisecond-level responsiveness. When the environment undergoes permanent, large-scale structural changes (e.g., building renovation), re-executing the full construction phase is recommended. For local changes, only the affected subtrees need to be reconnected or their inter-tree edge costs updated numerically, without full reconstruction. Transient dynamic obstacles are best handled by a dedicated local planner and do not require PMTG restructuring. This method is proven to be probabilistically complete and almost-surely asymptotically optimal. Simulations and real-world experiments demonstrate that it achieves excellent efficiency across various high-dimensional and complex path planning tasks, showing strong potential especially in applications with limited computational resources and predominantly static environments.
Keywords:
Space structuring
parallel multi-tree graph
robotics
sampling-based planners
Journal
IF:
6.4
Papers:
4.9K
Citations:
1.6W
View more organizations