PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Hao Jiang, Yinghan Wang, Jianping He, Xiaoming Duan

arXiv:2609.30599v1cs.RO

TL;DR

Collision detection is costly in sampling-based planning, while phase-based methods typically leave narrow-phase checks in the broad-phase traversal order. The paper predicts collision probabilities to reorder exact mesh checks using an approximation of an expected-time-optimal criterion, and reports faster detection and improved planner efficiency and success rates in cluttered environments.

  • Problem

    In cluttered environments, many object pairs can remain after broad-phase pruning, and default narrow-phase ordering can leave expensive mesh checks as a significant detection-time cost.

    Source: §I · p. 1, A. Phase-based Collision Detection · p. 3

  • Method

    The method derives an expected-time-optimal check-ordering criterion and uses a hypernetwork to predict priors that approximate the order while retaining exact mesh checks.

    Source: §I · p. 2

  • Results

    The method substantially reduces phase-based collision-detection time in cluttered environments and improves sampling-based planners’ efficiency and success rate.

    Source: §I · p. 2, §V · p. 9

  • Takeaways & Limitations

    Reordering exact narrow-phase checks offers a way to accelerate phase-based collision detection without replacing the underlying geometric checker.

    Source: §I · p. 2, §V · p. 9

Abstract

from arXiv · show

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.

I. INTRODUCTION

Collision detection can consume substantial planning time because mesh checks are expensive, and clutter can leave many object pairs for the narrow phase. The paper optimizes narrow-phase check order using predicted collision probabilities while retaining exact mesh checks.

I. INTRODUCTION

  • Mesh checks require many triangle-triangle intersection computations, making collision detection a substantial computational cost in sampling-based planning.Each sampled configuration may require checks across many object pairs.Source: §I · p. 1
  • In phase-based detection, broad-phase geometric tests discard clearly collision-free pairs, while mesh checks handle the remaining pairs in the narrow phase.The methods primarily differ in their broad-phase representations and exclusion strategies.Source: §I · p. 1
  • Default broad-phase traversal order is not explicitly optimized, and clutter can leave enough expensive mesh checks for the narrow phase to occupy a significant share of detection time.This motivates optimizing narrow-phase ordering for further acceleration.Source: §I · p. 1
  • The paper derives a check-ordering criterion that minimizes expected narrow-phase time and uses a hypernetwork to predict the priors needed to approximate that order.The learned model guides the order of exact mesh checks rather than replacing them.Source: §I · p. 2
  • The method accelerates phase-based collision detection in cluttered environments and improves sampling-based planners’ efficiency and success rate.The proposed model predicts collision probabilities to approximate an optimal order; exact mesh checks remain the narrow-phase operation.Source: §I · p. 2, Figure 1 · p. 2

II. BACKGROUND

Collision-detection acceleration methods either reduce the number of mesh checks through phase-based pruning or reduce the cost of individual checks with learned predictions. The paper targets the usually unoptimized order of narrow-phase checks while preserving deterministic collision-checking results.

II. BACKGROUND

  • Phase-based methods prune clearly noncolliding pairs in a broad phase, but typically run remaining mesh checks in broad-phase traversal order without optimizing that order.BVH, Octrees, and Spatial Hashing use different coarse representations and exclusion strategies.Source: §II · p. 2
  • Learning-based collision predictors can be faster but may err, and prior methods can generalize poorly beyond fixed environments.Prior approaches include learned collision boundaries, stored collision results, and predictors over configuration-space subspaces.Source: §II · pp. 2–3
  • The proposed approach predicts priors to approximate an expected-time-optimal narrow-phase order, rather than replacing exact mesh checks with learned predictions.This distinguishes it from surface-area and distance heuristics, which use geometric proxies without an explicit expected-time model.Source: §II · p. 3

III. NARROW-PHASE OPTIMIZATION IN PHASE-BASED COLLISION DETECTION

The section lays out a progression from phase-based detection to an expected-time criterion and a hypernetwork that predicts priors for approximating the optimal check order.

III. NARROW-PHASE OPTIMIZATION IN PHASE-BASED COLLISION DETECTION

  • The method first introduces phase-based detection using BVH and identifies potential narrow-phase optimization.The BVH example provides the setup for the subsequent check-ordering method.Source: §III · p. 3
  • It then formulates a narrow-phase time-cost model and derives a criterion that minimizes expected cost.Source: §III · p. 3
  • A hypernetwork model learns and predicts priors for approximating the optimal check order, before the section summarizes the resulting method.Source: §III · p. 3

A. Phase-based Collision Detection

Phase-based detection uses hierarchical bounding volumes to eliminate pairs that are clearly collision-free, then applies mesh checks to unresolved pairs. The default narrow-phase order follows broad-phase traversal, leaving room for optimization, especially in clutter.

A. Phase-based Collision Detection

  • Bounding volumes and hierarchical structures let the broad phase exclude object pairs that are clearly collision-free before detailed mesh checks.BVH is used as the example; the broad phase can test simple boxes and exclude child nodes when parent volumes do not overlap.Source: A. Phase-based Collision Detection · p. 3
  • Overlapping leaf bounding volumes do not establish an actual collision, so the remaining object pairs require narrow-phase mesh checks.The broad phase cannot determine collision status for these pairs from box checks alone.Source: A. Phase-based Collision Detection · p. 3
  • The narrow phase checks remaining pairs in broad-phase traversal order, which is not explicitly optimized for collision checking.Existing phase-based methods mainly vary in their hierarchies, bounding volumes, and broad-phase exclusion strategies.Source: A. Phase-based Collision Detection · p. 3
  • In clutter, broad-phase pruning may leave many pairs, and expensive mesh checks can make the narrow phase a large share of detection time.This creates scope for further acceleration through narrow-phase optimization.Source: A. Phase-based Collision Detection · p. 3

B. Narrow Phase Modeling and Optimal Check Order

Because the narrow phase stops once a collision is detected, its expected cost depends on the order of mesh checks. The section models that cost and derives an optimal ordering that prioritizes pairs with higher collision probabilities and lower check costs.

B. Narrow Phase Modeling and Optimal Check Order

  • The expected cost favors checking pairs with higher collision probabilities and lower mesh-check costs earlier, enabling earlier termination after a collision.The narrow phase otherwise verifies all remaining pairs as collision-free.Source: B. Narrow Phase Modeling and Optimal… · p. 3
  • The derived optimal order prioritizes pairs with higher collision probabilities and lower check costs.The theorem states an optimal ordering criterion for minimizing expected narrow-phase time.Source: B. Narrow Phase Modeling and Optimal… · pp. 3–4
  • Assuming independent collision events, expected time weights each check cost by the probability that earlier checks found no collision.The order is a permutation of the object pairs requiring mesh checks.Source: B. Narrow Phase Modeling and Optimal… · p. 4
  • The proof compares orders by swapping neighboring pairs and repeats improving swaps until it reaches an optimal order.A neighboring swap lowers expected cost when the pairwise ordering condition is violated.Source: B. Narrow Phase Modeling and Optimal… · pp. 4–5

C. Hypernetwork-based model

The model approximates the optimal narrow-phase check order by sorting predicted collision probabilities, using those probabilities as a practical proxy for the probability-to-check-time score. Its MFN-CPN hypernetwork separates mesh processing from frequent pose-based prediction to balance generalization and computational cost.

C. Hypernetwork-based model

  • Sorting by predicted collision probability approximates the optimal score based on collision probability divided by check time, which is difficult to estimate and can vary across hardware.The predicted-probability ordering has high correlation with the optimal order; check-time variation is relatively small and does not substantially change the ordering.Source: C. Hypernetwork-based model · p. 5, Figure 3 · p. 5
  • MFN generates CPN parameters so mesh-related information and relative-pose information are handled separately, targeting a balance between prediction efficiency and generalization.Meshes are typically fixed while relative poses change frequently, so the pose-related component is invoked more often.Source: C. Hypernetwork-based model · pp. 5–6
  • MFN extracts features from both meshes, outputs CPN parameters and geometry-encoding key points, and stores outputs for mesh pairs with known meshes.MFN's forward pass is needed only when an object pair with previously unknown meshes appears.Source: C. Hypernetwork-based model · p. 5
  • CPN uses MFN-generated parameters and pose-transformed key points to predict collision probability for a specific mesh pair from its relative pose.This lets CPN model pose-dependent collision probability with a compact network.Source: C. Hypernetwork-based model · pp. 5–6
  • The method predicts probabilities for object pairs remaining after the broad phase, sorts them in descending order, then performs exact mesh checks in that order.MeshNet* retains one MeshConv layer and reduces its three output dimensions to 32 for compact mesh-feature extraction rather than shape classification.Source: C. Hypernetwork-based model · p. 6, Figure 4 · p. 6

IV. SIMULATIONS

The simulations combine MoveIt! and ROS with FCL-based BVH collision detection and OMPL sampling-based planners. Training uses Panda components paired with ModelNet40 obstacles and FCL-generated collision labels.

IV. SIMULATIONS

  • Simulations use MoveIt! in ROS, FCL with default parameters for BVH-based collision detection, and OMPL for sampling-based planners.Runs use Ubuntu 20.04, an Intel Core i7-11800H CPU, 32GB RAM, and an NVIDIA RTX 3090 GPU.Source: §IV · p. 6
  • Training uses 9 Panda components and 252 randomly selected ModelNet40 obstacles to form 9 × 252 mesh pairs, with 100000 randomly generated relative poses per pair.FCL mesh checks provide the ground-truth collision labels.Source: §IV · p. 6
  • The model is trained with Adam for 1000 epochs at a learning rate of 10^-6, using mesh information and relative pose as test-time inputs.Relative pose is represented by a rotation matrix and translation vector.Source: §IV · p. 6

A. Performance of Hypernetwork-based Model

The hypernetwork model achieves higher prediction accuracy and lower prediction time than Fastron on seen and unseen Panda object pairs. Tests on the UR5 without additional training also demonstrate generalization across robot arms and environments.

A. Performance of Hypernetwork-based Model

  • The proposed model achieves higher prediction accuracy on seen and unseen Panda object pairs than Fastron while requiring less prediction time.The comparison evaluates accuracy, TPR, TNR, and average prediction time; the table covers seen and unseen object pairs.Source: A. Performance of Hypernetwork-based… · p. 7, Table II · p. 7
  • The model has higher TPR than Fastron and slightly lower TNR, indicating a more conservative tendency to detect potential collisions.Prediction errors affect checking efficiency rather than the final collision result because exact mesh checks remain in use.Source: A. Performance of Hypernetwork-based… · p. 7
  • The model effectively predicts collisions for the UR5 without additional training, on both seen and unseen obstacles.The evaluation replaces Panda links with the UR5's seven links and tests 2000 sampled relative poses per mesh pair.Source: A. Performance of Hypernetwork-based… · p. 7, Table III · p. 7

B. Acceleration on Phase-based Collision Detection

Reordering narrow-phase mesh checks reduces detection time, particularly in collision cases and cluttered environments. The method also transfers to Octree-based detection, an unseen robot arm, and outperforms the tested geometric ordering heuristics.

C. Acceleration for Sampling-based Motion Planning

The method was evaluated with RRT, RRT-Connect, and BIT* in a 50-obstacle environment under a five-second planning budget. All three planners saw lower average time to find a solution and improved success rates with BVH combined with the method.

V. CONCLUSION

The conclusion presents learned narrow-phase check ordering as an acceleration for phase-based collision detection that preserves the underlying detector. It reports improved detection and planning performance, and identifies frequent collision checking in applications such as manipulation and navigation as a potential use.

  • The method predicts priors to approximate an optimal narrow-phase check order, reducing phase-based detection time and improving planner efficiency and success rates in simulation.Source: §V · p. 9
  • The method can integrate into existing frameworks without modifying the collision detector, supporting straightforward deployment with minimal implementation effort.Source: §V · p. 9
  • Potential application settings include manipulation, navigation, and motion planning in confined spaces where collision checking is frequent.Source: §V · p. 10
Loading 2609.30599v1…