Abstract
Motion planning in dynamic, crowded environments remains a significant challenge for mobile robotics. Traditional sampling-based methods like Rapidly-exploring Random Trees (RRT) often suffer from inefficient, "blind" exploration. This paper presents Neural Adaptive Multi-directional Risk-based RRT (NAMR-RRT), a framework that integrates deep learning with adaptive sampling. By utilizing a PointNet++ backbone to predict promising heuristic regions and employing multi-directional search with risk-aware tree growth, NAMR-RRT achieves superior performance in terms of execution time, path optimality, and success rates compared to conventional planners.
Introduction
Navigating a robot through a busy shopping mall or a warehouse is notoriously difficult. While traditional algorithms like RRT are popular for their ability to handle high-dimensional spaces, they typically sample the entire environment randomly. This "blind" exploration wastes significant computation on areas that do not contribute to reaching the goal.
Informed versions of RRT use heuristics to focus the search, but these often rely on static regions. In dynamic environments where pedestrians move and paths open or close, static heuristics quickly become obsolete. NAMR-RRT addresses this by creating a planner that is both informed—knowing where to look—and adaptive—capable of updating its search strategy as the environment evolves.
Methodology
The NAMR-RRT architecture is built upon three primary pillars designed to enhance search efficiency and safety in dynamic settings.
1. Neural Adaptive Guiding
The system employs a PointNet++ backbone to process map data and infer a "heuristic region"—a set of points where a feasible path is most likely to exist. Crucially, this inference happens in parallel with the planning loop, preventing the robot from freezing during computation. The system uses iterative generation, expanding the search region if a path is not immediately discovered.
2. Multi-directional Searching
Rather than growing a single tree from start to goal, the algorithm grows multiple "subTrees" from the goal and intermediate waypoints. These trees eventually merge, significantly accelerating the discovery of a valid path.
3. Risk-aware Growing and Adaptive Sampling
The cost function for tree expansion incorporates a probabilistic model of collision risk for both static obstacles and moving pedestrians, predicted over a short time horizon. To maintain probabilistic completeness, the algorithm uses an adaptive sampling rate. It maintains a bias toward the neural-predicted region but automatically decays this bias toward broader random sampling if the tree fails to progress.
Experimental Evaluation
The framework was trained on 10,000 synthetic 2D environments using A* generated optimal paths as ground truth. Evaluation was conducted across three simulation maps representing warehouse, market, and urban environments, using real-world pedestrian movement patterns. Real-world testing was also performed on a mobile robot equipped with LiDAR and depth cameras.
Results and Discussion
NAMR-RRT consistently outperformed standard Risk-RRT and its variants. Key results include:
- Efficiency: The algorithm demonstrated the shortest execution times across all maps.
- Path Quality: Trajectory lengths were significantly closer to the theoretical optimum due to the focused search.
- Robustness: In complex dynamic scenarios, NAMR-RRT maintained a high success rate and low performance variance.
A notable visual result is the "clean" nature of the search tree. Unlike traditional RRTs that produce "hairy" trees filling the map, NAMR-RRT's tree is highly directed toward the goal, indicating minimal wasted computation. Furthermore, the adaptive nature of the heuristic allows the robot to quickly shift its search region when a pedestrian blocks a previously predicted path, a scenario where fixed-heuristic models often fail.
Conclusion
NAMR-RRT represents a significant step forward in real-time motion planning for dynamic environments. By combining the strengths of deep learning with the theoretical guarantees of sampling-based planners, it offers a robust solution for mobile robot navigation. Future work will explore more advanced neural models for refined heuristic generation and the integration of imperative learning to allow robots to improve strategies based on past experiences.
Summary updated