🤖 machine learning

Convex-Neural RRT*: Fast and Reliable Learning-Guided Sampling for High-Quality Robot Path Planning

This paper introduces Convex-Neural RRT*, a learning-guided path planning algorithm that extracts convex candidate regions from neural predictions to significantly reduce computation time and improve path quality compared to existing neural and classical sampling-based methods while maintaining high success rates.

Original authors: Hichem Cheriet, Badra Khellat Kihel, Samira Chouraqui, Bara J. Emran

Published 2026-05-26

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Hichem Cheriet, Badra Khellat Kihel, Samira Chouraqui, Bara J. Emran

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to guide a robot through a giant, cluttered maze filled with furniture, walls, and tricky corners. The robot's job is to get from point A to point B as quickly and smoothly as possible without bumping into anything.

This paper introduces a new method called Convex-Neural RRT* to help the robot solve this maze much faster and better than before. Here is how it works, broken down into simple concepts:

The Problem: The "Random Walk" Struggle

Traditional robot planners (like the standard RRT*) work a bit like a person trying to find their way through a dark forest by throwing darts at a map. They pick a random spot, try to walk there, and if they hit a tree, they try again. They keep doing this thousands of times until they finally stumble upon a path.

The downside: This is slow. The robot wastes a lot of time exploring empty spaces or dead ends that don't lead anywhere useful.

The Solution: A "Smart Guide" with a "Safety Net"

The authors created a hybrid system that combines two powerful ideas: Neural Learning (a smart guide) and Convex Geometry (a safety net).

1. The Neural Guide (The "Experienced Hiker")

The robot uses a trained AI (a U-Net model) that has "seen" thousands of mazes before.

What it does: Instead of guessing where to go, the AI looks at the map and says, "Hey, the best path usually goes through these specific yellow zones." It predicts where the "waypoints" (turning points) of a good path are likely to be.
The Analogy: Imagine a hiker who has walked this trail before. They don't need to check every bush; they know the path usually winds around the big rocks.

2. The Convex Corner Extraction (The "Geometric Safety Net")

Here is the clever twist. The AI isn't perfect; sometimes it might point to a spot that is actually a wall. If the robot blindly followed the AI, it might crash.

What it does: The system looks at the AI's prediction and filters it through a strict geometric rule. It only pays attention to the "corners" of the obstacles (the sharp points sticking out).
The Analogy: Think of the obstacles as islands in a river. The AI suggests a general area to swim. The "Convex" rule says, "Okay, but we will only aim for the tips of the islands (the corners) because we know the shortest path always hugs the tips of the islands." This turns the AI's vague "yellow zone" into a specific list of safe, strategic targets.

3. The Hybrid Strategy (The "Balanced Approach")

The robot doesn't just follow the AI blindly, nor does it just throw darts randomly. It uses a mix:

Exploitation (70% of the time): It focuses on the AI's predicted "corner" targets to zoom in on the best path quickly.
Exploration (30% of the time): It still throws a few random darts to make sure it doesn't miss a secret shortcut or get stuck if the AI was wrong.
Early Stopping: The robot has a "patience meter." Once it finds a path that is good enough and stops getting significantly better, it stops working immediately. It doesn't waste time polishing a path that is already perfect.

The Results: Faster and Smoother

The authors tested this new method against older, standard methods on 18 different maps ranging from open fields to dense, cluttered jungles.

Speed: The new method was 30% to 75% faster than other smart learning-based methods and up to 98% faster than some older, heavy-duty methods. It's like switching from walking to driving a sports car.
Quality: The paths it found were about 5% shorter and much smoother (fewer sharp, jerky turns) than the standard robot planners.
Reliability: It succeeded in finding a path 99% of the time, even in very messy environments where other methods sometimes gave up.

In Summary

Convex-Neural RRT* is like giving a robot a map drawn by an expert hiker (the Neural Network) but forcing that map to follow strict geometric rules (the Convex Corners) to ensure safety. This allows the robot to stop wandering aimlessly and zoom straight toward the best solution, saving time and energy while avoiding crashes.

Technical Summary: Convex-Neural RRT* for Learning-Guided Path Planning

Problem Statement

Sampling-based path planning algorithms, such as RRT*, offer probabilistic completeness and strong empirical convergence in diverse environments. However, in practice, these methods often require a large number of iterations to generate high-quality solutions, particularly in cluttered or complex environments. Traditional uniform sampling allocates resources inefficiently, often exploring geometrically irrelevant regions. While learning-based variants (e.g., Neural RRT*, Neural Informed RRT*) have been proposed to guide sampling toward promising regions, they face limitations including reliance on dense path predictions that may be sparse or disconnected, generalization issues in unseen environments, and the potential for prediction errors to mislead exploration. Furthermore, purely geometric methods like LTA* can be computationally expensive in complex 3D scenarios. The core challenge addressed is balancing computational efficiency with solution quality and robustness in high-dimensional, cluttered spaces without sacrificing probabilistic completeness.

Methodology

The paper proposes Convex-Neural RRT, a structured learning-guided sampling framework that integrates neural waypoint prediction with convex obstacle geometry within the RRT planning process. The methodology consists of four primary components:

1. Neural Guidance for Informative Regions

Instead of predicting dense, full-path regions (which can lead to fragmented guidance), the authors employ a U-Net model (with a frozen ResNet50 encoder) to predict inflated region masks around intermediate waypoints derived from LTA* paths.

Training Data: The network is trained on 40,000 labeled samples generated from procedurally created grid maps containing convex and concave polygonal obstacles.
Output: The model outputs a sparse binary mask representing "promising regions" near optimal waypoints, rather than a continuous path. This reduces label sparsity and focuses the learning on geometrically significant areas.

2. Convex Corner Extraction

To leverage the geometric structure of the environment, the algorithm extracts convex corners from the binary occupancy grid.

Detection: Using a 3×3 local neighborhood rule, free cells adjacent to exactly one inflated obstacle cell are identified as convex corners.
Role: These corners serve as structurally informative decision points where feasible paths often change direction. They form a sparse set of candidate points for sampling.

3. Convex-Neural Sampling Strategy

The core innovation is a hybrid sampling strategy that restricts the search space to a union of convex corners, guided by the neural predictions.

Hull Construction: A convex hull ( $H$ ) is constructed over the union of the predicted convex corners (filtered to lie within the neural-predicted regions), the start position, and the goal position.
Probabilistic Sampling: Samples are drawn from three subsets based on two parameters, $\alpha_{pred}$ $α_{p r e d}$ and $\alpha_{explore}$ $α_{e x pl or e}$ :
1. Predicted Corners ( $\mathcal{C}_p$ ): Convex corners inside the hull that lie within the neural-predicted regions.
2. Remaining Hull Corners ( $\mathcal{C}_{ri}$ ): Convex corners inside the hull but outside the predicted regions.
3. Exploration Corners ( $\mathcal{C}_{ro}$ ): Convex corners outside the hull.
Mechanism: The algorithm samples from $\mathcal{C}_p$ with probability $(1-\alpha_{explore})\alpha_{pred}$ , from $\mathcal{C}_{ri}$ with probability $(1-\alpha_{explore})(1-\alpha_{pred})$ , and from $\mathcal{C}_{ro}$ with probability $\alpha_{explore}$ . This balances focused exploitation of learned regions with global exploration to mitigate prediction errors.

4. Early Stopping Mechanism

To further improve efficiency, an adaptive termination criterion is introduced. The search terminates when the best path cost ( $c_k$ ) does not improve significantly over the last $t_{stop}$ iterations (i.e., $|c_k - c_{k-t_{stop}}| < \epsilon$ ). This prevents unnecessary iterations once the solution stabilizes.

Key Contributions

Structured Neural Guidance: The introduction of a U-Net model that predicts sparse, inflated waypoint regions rather than dense paths, providing a geometrically interpretable supervision signal for sampling.
Convex-Guided Hybrid Exploration: A novel sampling strategy that extracts convex corners from predicted regions and uses a convex hull to guide RRT* expansion. This balances local exploitation of promising areas with global exploration, maintaining robustness even with imperfect predictions.
Adaptive Termination: An early-stopping mechanism based on cost stabilization that reduces computational overhead by avoiding redundant iterations.
Comprehensive Validation: Extensive experimental evaluation across 18 benchmark maps with varying obstacle densities (sparse, medium, high) against classical RRT*, Neural RRT*, Neural Informed RRT*, and LTA*.

Experimental Results

The algorithm was evaluated on 224×224 grid maps across three difficulty levels. Key findings include:

Computational Efficiency: Convex-Neural RRT* reduced computation time by 30–75% compared to neural-guided variants (Neural RRT*, Neural Informed RRT*) and by 88–98% relative to LTA* in medium and hard environments. Execution times were consistently below 0.5s in most scenarios.
Path Quality: The method achieved an average path length reduction of approximately 5% compared to classical RRT*, with larger improvements (up to ~22%) in complex, high-density environments. Path lengths were competitive with LTA*, differing by an average of only 1.49%.
Smoothness: The proposed method produced significantly smoother paths, reducing smoothness cost by approximately 56% compared to classical RRT* on average.
Reliability: The algorithm maintained an overall success rate of >99% across varying obstacle densities. In contrast, classical RRT* and some neural variants showed reduced success rates (dropping to 60–90%) in highly cluttered "Hard" maps.
Robustness: Sensitivity analysis demonstrated that the method remains robust under Gaussian shift noise and random deletion of predicted corners, with path length variations remaining below 1.4% even in hard environments under significant perturbation.

Significance and Claims

The paper claims that Convex-Neural RRT* provides an effective balance between computational efficiency and solution quality. By integrating neural guidance with explicit geometric reasoning (convex corners), the method overcomes the limitations of purely learning-based approaches (which can be brittle in unseen environments) and purely geometric approaches (which can be computationally heavy).

The authors assert that this approach is particularly suitable for time-sensitive robotic navigation tasks where rapid generation of high-quality, smooth paths is required. The method's ability to maintain high success rates and low execution times across diverse obstacle configurations suggests its applicability to real-world scenarios, including UAV navigation and manipulator motion planning. The paper concludes that convex-guided neural sampling is a viable strategy for enhancing sampling-based planners without compromising the theoretical guarantees of probabilistic completeness.