Learning-Accelerated Narrow-Phase Collision Detection via Check Ordering for Sampling-Based Motion Planning

Hao Jiang; Yinghan Wang; Jianping He; Xiaoming Duan

cs.ROSep 24, 2026

Learning-Accelerated Narrow-Phase Collision Detection via Check Ordering for Sampling-Based Motion Planning

Authors: Hao Jiang, Yinghan Wang, Jianping He, Xiaoming Duan

Organizations: Department of Automation, Shanghai Jiao Tong University, and Key Laboratory of System Control and Information Processing, Ministry of Education of China, Shanghai, China.

Abstract

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.

Panel of Figure 2 — 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 $\hat{p}_{i}$ in descending order and the optimal check order $\bm{\sigma}^{o}$ . The correlation remains above $0.98$ across $10000$ randomly generated narrow-phase cases on Apple M3.

CPU	Variable correlation (Pearson coefficient [ 21 ] )		Order similarity (Spearman rank correlation [ 20 ] )
CPU	$1/t$ vs. $\hat{p}/t$	$\hat{p}$ vs. $\hat{p}/t$	$1/t$ vs. $\hat{p}/t$	$\hat{p}$ vs. $\hat{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

\hat{p}/t

with

\hat{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.

Panel of Figure 7 — 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\,\mu\mathrm{s}$
Fastron	unseen	0.723	0.802	0.644	$5.693\,\mu\mathrm{s}$
Hypernetwork-based model	seen	0.938	0.972	0.880	$1.966\,\mu\mathrm{s}$
Hypernetwork-based model	unseen	0.926	0.965	0.861	$1.966\,\mu\mathrm{s}$

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\,\mu\mathrm{s}$
UR5 (unseen)	unseen	0.878	0.907	0.823	$1.993\,\mu\mathrm{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\,\mu\mathrm{s}$	-
50 obstacles	Octree + our method	$25.23\,\mu\mathrm{s}$	$23.98\%$
70 obstacles	Octree	$52.01\,\mu\mathrm{s}$	-
70 obstacles	Octree + our method	$36.68\,\mu\mathrm{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\,\mu\mathrm{s}$	-
100 obstacles	BVH + our method	$175.15\,\mu\mathrm{s}$	$28.76\%$
120 obstacles	BVH	$257.19\,\mu\mathrm{s}$	-
120 obstacles	BVH + our method	$186.99\,\mu\mathrm{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\,\mu\mathrm{s}$	-	-
BVH + DBH	$31.19\,\mu\mathrm{s}$	7.31%	0.587
BVH + SAH	$29.75\,\mu\mathrm{s}$	11.58%	0.595
BVH + our method	$25.68\,\mu\mathrm{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%
RRT	BVH + our method	1.558 s	81.10%
RRT-Connect	BVH	0.321 s	98.51%
RRT-Connect	BVH + our method	0.251 s	99.46%
BIT*	BVH	0.737 s	93.02%
BIT*	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

GNN-DIP: Neural Corridor Selection for Decomposition-Based Motion Planning
Mar 12, 2026Peng Xie, Yanliang Huang, Wenyuan Wu +1Motion Planning
TUM School of Computation, Information and Technology, Department of Computer Engineering, Technical University of Munich, 74076 Heilbronn, Germany
Smooth Feedback Motion Planning with Reduced Curvature
Apr 2, 2026Aref Amiri, Steven M. LaValleMotion Planning Safe Motion Planning
The authors are with the Faculty of Information Technology and Electrical Engineering, University of Oulu, Oulu, Finland
Stochastic Neural Signed Swept Volume for Real-time Chance-Constrained Trajectory Optimization
Sep 18, 2026Qingyi Chen, Kevin Zhang, Lucas Chen +1Robot Motion Planning Robot Collision Avoidance
Department of Computer Science, Purdue University, West Lafayette, IN, USA

Mar 12, 2026J/K move · Enter open · S save

GNN-DIP: Neural Corridor Selection for Decomposition-Based Motion Planning

Peng Xie, Yanliang Huang, Wenyuan Wu, Amr Alanwar

TUM School of Computation, Information and Technology, Department of Computer Engineering, Technical University of Munich, 74076 Heilbronn, Germany

Motion Planning

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

GNN-DIP: Neural Corridor Selection for Decomposition-Based Motion Planning

Smooth Feedback Motion Planning with Reduced Curvature

Stochastic Neural Signed Swept Volume for Real-time Chance-Constrained Trajectory Optimization