Organizations: Department of Automation, Shanghai Jiao Tong University, and Key Laboratory of System Control and Information Processing, Ministry of Education of China, Shanghai, China.
Collision detection is critical for ensuring the safety of planned paths. However, it imposes a non-negligible computational burden on motion planners, motivating extensive studies on collision-detection acceleration. In commonly used phase-based collision-detection methods, the broad phase employs hierarchical structures to rapidly discard object pairs that are clearly collision-free, while the subsequent narrow phase performs detailed collision checks on the remaining object pairs whose collision status cannot be determined by the broad phase. Although these methods effectively reduce the number of detailed checks through broad-phase pruning, the narrow phase is usually executed in the default order returned by the broad phase, with little explicit optimization of the check order. This leaves room for further acceleration, especially in cluttered environments where many object pairs may remain after the broad phase and the narrow phase can account for a significant portion of the total detection time. In this work, we propose a learning-based method to accelerate phase-based collision detection by optimizing the check order in the narrow phase. We first formulate the expected time cost of the narrow phase and derive an optimal check-ordering criterion that minimizes this expectation. Since the priors required by this criterion are difficult to obtain in advance, we design a hypernetwork-based model to predict collision probabilities, which are then used to approximate the optimal check order. The resulting order guides the execution of exact mesh checks in the narrow phase, thereby reducing detection time without replacing the underlying geometric collision checker. Simulation results show that our method effectively accelerates phase-based collision detection and improves the efficiency and success rate of sampling-based motion planning, especially in cluttered environments.
Figures & tables
Fig. 1: Overview of this research. As the environment becomes increasingly cluttered, collision detection accounts for a growing proportion of the total computational cost in sampling-based motion planning, with the narrow phase becoming a major bottleneck. To address this issue, we propose a learning-based method to accelerate the narrow phase by optimizing its check order. Specifically, a hypernetwork-based model predicts collision probabilities for object pairs, which are used to approximate the optimal check order and enable earlier termination in collision cases, thereby improving the efficiency of the overall detection process.
Fig. 2: Collision detection based on BVH. (a) The Franka Emika Panda robot model, which consists of nine components. (b) An environment with four obstacles, where AABBs are used as the bounding volumes to construct the hierarchy. A root box encloses all obstacles; box1 and box2 enclose the left and right obstacle groups, respectively; and box3 to box6 enclose individual obstacles. (c) The broad phase forms a BVH tree and performs box checks along the tree. If a parent node, such as box1, does not overlap with link1_box, then its child nodes, box3 and box4, can be excluded. In the subsequent narrow phase, leaf nodes that still overlap with link1_box, such as box5 and box6, are checked by mesh checks on the corresponding object pairs, pair1 and pair2, to determine whether an actual collision occurs.
Fig. 3: Spearman rank correlation [ 20 ] between the check order obtained by sorting object pairs by p^i in descending order and the optimal check order σo . The correlation remains above 0.98 across 10000 randomly generated narrow-phase cases on Apple M3.
Order similarity (Spearman rank correlation [ 20 ] )
1/t vs. p^/t
p^ vs. p^/t
1/t vs. p^/t
p^ vs. p^/t
Intel i7-11800H
0.265
0.883
0.605
0.998
AMD 9950X3D
0.171
0.799
0.495
0.994
Apple M3
0.323
0.841
0.469
0.997
TABLE I: [Validation of Approximating p^/t with p^ ] Average variable correlation and order similarity across different CPUs.
Fig. 4: Structure of the hypernetwork-based model. MeshNet* is a lightweight variant of MeshNet [ 22 ] , where only one MeshConv layer is retained and the dimensions of its three outputs are reduced to 32 for lower computational complexity. This simplification is feasible because MeshNet* is used for compact mesh-feature extraction rather than the original shape-classification task.
Fig. 5: The proposed learning-accelerated method for phase-based collision detection in sampling-based motion planning.
Fig. 6: Simulation models of the robots. The Panda robot is used during training, while the UR5 robot is treated as an unseen robot to further evaluate the generalization capability of the proposed hypernetwork-based model.
Fig. 7: Representative meshes from the ModelNet40 dataset.
Fig. 8: Average detection time and its decomposition for all sampled poses in each environment: BVH alone vs. BVH combined with our method. The average time is calculated for all detection operations of both approaches, and further separately for the collision and non-collision cases. Within the decomposition for collision and non-collision cases: “mesh checks” refers to the time cost of executing the narrow phase; for BVH-only, “others” corresponds to the time cost of broad phase; for BVH combined with our method, “others” includes the time costs of the broad phase, prediction based on the hypernetwork-based model, and check-order construction based on the predictions.
Predictor
Obstacles
Accuracy
TPR
TNR
Time
Fastron
seen
0.866
0.816
0.917
5.693μs
unseen
0.723
0.802
0.644
Hypernetwork-based model
seen
0.938
0.972
0.880
1.966μs
unseen
0.926
0.965
0.861
TABLE II: [Prediction Comparison on Seen and Unseen Object Pairs] The prediction performance of each predictor with Panda
Robot
Obstacles
Accuracy
TPR
TNR
Time
UR5 (unseen)
seen
0.893
0.912
0.851
1.977μs
unseen
0.878
0.907
0.823
1.993μs
TABLE III: [Prediction of the UR5 without Additional Training] prediction accuracy and runtime in each dataset part
Environment
Method
Time
Acceleration ratio vs. Octree
50 obstacles
Octree
33.19μs
-
Octree + our method
25.23μs
23.98%
70 obstacles
Octree
52.01μs
-
Octree + our method
36.68μs
29.47%
TABLE IV: [Phase-based Collision Detection in the environments] Average detection time of Octree-based collision detection with and without our method
Environment
Collision detection
Average time
Acceleration ratio vs. BVH
100 obstacles
BVH
245.86μs
-
BVH + our method
175.15μs
28.76%
120 obstacles
BVH
257.19μs
-
BVH + our method
186.99μs
27.29%
TABLE V: [Collision Detection Time of UR5] Average detection time of UR5 with and without our method
Method
Time
Acceleration ratio vs. BVH
Order similarity Spearman coefficient vs. our method
BVH
33.65μs
-
-
BVH + DBH
31.19μs
7.31%
0.587
BVH + SAH
29.75μs
11.58%
0.595
BVH + our method
25.68μs
23.69%
-
TABLE VI: [Comparison with the heuristic check-ordering methods] Time cost in the environment with 50 obstacles
Motion planner
Collision detection method
Time cost
Success rate
RRT
BVH
1.703 s
78.34%
BVH + our method
1.558 s
81.10%
RRT-Connect
BVH
0.321 s
98.51%
BVH + our method
0.251 s
99.46%
BIT*
BVH
0.737 s
93.02%
BVH + our method
0.635 s
96.50%
TABLE VII: [Performance Comparison in Motion Planning] Average planning time and success rate of each planner with and without our method
Motion planning through narrow passages remains a core challenge: sampling-based planners rarely place samples inside these narrow but critical regions, and even when samples land inside a passage, the straight-line connections between them run close to obstacle boundaries and are frequently rejected by collision checking. Decomposition-based planners resolve both issues by partitioning free space into convex cells -- every passage is captured exactly as a cell boundary, and any path within a cell is collision-free by construction. However, the number of candidate corridors through the cell graph grows combinatorially with environment complexity, creating a bottleneck in corridor selection. We present GNN-DIP, a framework that addresses this by integrating a Graph Neural Network (GNN) with a two-phase Decomposition-Informed Planner (DIP). The GNN predicts portal scores on the cell adjacency graph to bias corridor search toward near-optimal regions while preserving completeness. In 2D, Constrained Delaunay Triangulation (CDT) with the Funnel algorithm yields exact shortest paths within corridors; in 3D, Slab convex decomposition with portal-face sampling provides near-optimal path evaluation. Benchmarks on 2D narrow-passage scenarios, 3D bottleneck environments with up to 246 obstacles, and dynamic 2D settings show that GNN-DIP achieves 99--100% success rates with 2--280 times speedup over sampling-based baselines.
Peng Xie, Yanliang Huang, Wenyuan Wu +1
TUM School of Computation, Information and Technology, Department of Computer Engineering, Technical University of Munich, 74076 Heilbronn, Germany
Feedback motion planning over cell decompositions provides a robust method for generating collision-free robot motion with formal guarantees. However, existing algorithms often produce paths with unnecessary bending, leading to slower motion and higher control effort. This paper presents a computationally efficient method to mitigate this issue for a given simplicial decomposition. A heuristic is introduced that systematically aligns and assigns local vector fields to produce more direct trajectories, complemented by a novel geometric algorithm that constructs a maximal star-shaped chain of simplexes around the goal. This creates a large ``funnel'' in which an optimal, direct-to-goal control law can be safely applied. Simulations demonstrate that our method generates measurably more direct paths, reducing total bending by an average of 91.40% and LQR control effort by an average of 45.47%. Furthermore, comparative analysis against sampling-based and optimization-based planners confirms the time efficacy and robustness of our approach. While the proposed algorithms work over any finite-dimensional simplicial complex embedded in the collision-free subset of the configuration space, the practical application focuses on low-dimensional (d≤3) configuration spaces, where simplicial decomposition is computationally tractable.
Aref Amiri, Steven M. LaValle
The authors are with the Faculty of Information Technology and Electrical Engineering, University of Oulu, Oulu, Finland
Collision-free motion planning requires reliable collision models from sensed environments and validation of states along a continuous trajectory. To make this tractable, most planners check for collision at discrete states along continuous trajectories against a single determinized model of the environment, introducing a trade-off between safety and computational efficiency. While continuous collision checking approaches that approximate the swept volume of the robot exist, they are computationally expensive or overly conservative. Data-driven approaches can learn the swept volume; however, these neural models are susceptible to approximation errors and are therefore often limited to serving as coarse filters for downstream collision checkers. In this work, we propose to learn a signed distance function of the swept volume as a probabilistic field, enabling quantification of epistemic uncertainty, incorporation of perception noise, and eventual integration into a chance-constrained trajectory optimization framework. We demonstrate our approach on challenging high-dimensional manipulation problems with significant sensor noise, both in simulation and on real hardware.
Qingyi Chen, Kevin Zhang, Lucas Chen +1
Department of Computer Science, Purdue University, West Lafayette, IN, USA