Abstract
This paper presents a new approach to learning for motion planning (MP) where critical regions of an environment are learned from a given set of motion plans and used to improve performance on new environments and problem instances. We introduce a new suite of sampling-based motion planners, Learn and Link. Our planners leverage critical regions to overcome the limitations of uniform sampling, while still maintaining guarantees of correctness inherent to sampling-based algorithms. We also show that convolutional neural networks (CNNs) can be used to identify critical regions for motion planning problems. We evaluate Learn and Link against planners from the Open Motion Planning Library (OMPL) using an extensive suite of experiments on challenging motion planning problems. We show that our approach requires far less planning time than existing sampling-based planners.
Introduction
Finding a collision-free path for a robot in a complex environment is a fundamental challenge in robotics. Sampling-based motion planners (SMPs), such as Rapidly-exploring Random Trees (RRT) and Probabilistic Roadmaps (PRM), have become the standard solution due to their ability to handle high-dimensional spaces. However, these algorithms typically rely on uniform sampling, which creates a significant bottleneck when the environment contains narrow corridors or small openings.
In such scenarios, the probability of randomly sampling a point within a narrow passage is extremely low. Consequently, planners spend the majority of their computational budget exploring open areas while failing to find the critical connections necessary to reach the goal. This paper introduces "Learn and Link," a framework that combines deep learning with robust local planning to identify and exploit these critical regions, drastically improving efficiency without sacrificing the mathematical guarantees of traditional SMPs.
The Learn and Link Framework
The Learn and Link approach consists of two primary phases: identifying high-value regions in the environment and effectively connecting them to form a valid path.
1. Learning Critical Regions
The authors utilize a 14-layer fully convolutional encoder-decoder neural network to predict "critical regions"—areas like doorways or narrow hallways that are essential for successful navigation. The network takes a 2D top-down raster image of the environment as input and generates a pixel-wise classification mask. This mask serves as a heuristic to bias the sampling process toward the most important parts of the map.
2. The Linking Strategy
A key insight of this research is that simply sampling inside a narrow passage is insufficient; standard planners often fail to connect these isolated points to the broader environment because their local planners are too simplistic. To address this, the authors introduced a suite of planners: LLP (for single-query tasks) and LL-RM (for multi-query roadmaps).
Unlike standard PRM, which uses simple straight-line checks, the Learn and Link planners treat every sample in a predicted critical region as the root of its own subgraph. It then employs a tree-based local planner, inspired by RRT-Connect, to aggressively grow and link these subgraphs. Crucially, by maintaining a baseline of uniform sampling alongside this targeted approach, the planners remain probabilistically complete, ensuring they will eventually find a solution if one exists.
Data Generation and Training
To train the CNN, the authors developed a custom dataset based on 14 distinct 2D environments. They generated ground-truth labels through a multi-step process:
- Trace Generation: Running RRT-Connect multiple times to find successful paths.
- Criticality Calculation: Determining "$μ$-criticality" based on the frequency of path occupancy.
- Saliency Mapping: Applying a visual saliency model (Itti’s model) to smooth these traces into clean, binary labels (high vs. low saliency).
This process resulted in a dataset of 10,024 training images, allowing the CNN to learn the geometric features that define a bottleneck.
Experimental Results
The Learn and Link (LL) planners were benchmarked against standard OMPL implementations, including RRT, RRT-Connect, and PRM, across both 2D and high-dimensional tasks.
- SE(2) Domain (Mobile Robots): In the most challenging environments, standard RRT and RRT-Connect often failed to find solutions within a 60-second limit (0% success rate). In contrast, LL planners achieved a 100% success rate. For instances where standard planners did succeed, LL reduced planning time by 64% to 99%.
- 10-DOF Domain (Mobile Manipulator): The framework was tested on a Barrett WAM arm mounted on a mobile base. Despite the CNN only seeing 2D images, the LL planners achieved 99% to 100% success rates, requiring 88% to 92% less time than the best-performing OMPL baselines. This demonstrates that 2D heuristics can effectively guide high-dimensional robots by prioritizing base placement.
Conclusion and Future Work
Learn and Link demonstrates that integrating machine learning with traditional sampling-based planning can yield massive performance gains. The research highlights that the "Link" phase—how we connect samples—is just as critical as the "Learn" phase.
While the current implementation relies on 2D top-down imagery, which may limit its application in complex 3D environments (e.g., reaching under furniture), the underlying framework is generalizable. Future research may explore 3D representations, such as voxel grids or point clouds, to extend these benefits to fully three-dimensional manipulation tasks.
Summary updated