Neural Path Planning: Fixed Time, Near-Optimal Path Generation via Oracle Imitation

Mayur J. Bency, Ahmed Hussain Qureshi, Michael C. YipIROS 2019 · OpenReview

TL;DR

This paper introduces OracleNet, a novel neural network approach for generating near-optimal robot paths in fixed time, even in complex, high-dimensional environments. By imitating an "oracle" planner, OracleNet offers a significant speedup over traditional methods like A and RRT without sacrificing path quality, making it suitable for real-time applications.

What Problem Does This Paper Address?

Motion planning, the task of finding a collision-free path for a robot from a start to a goal configuration, is a fundamental challenge in robotics. Traditional algorithms like A and RRT struggle with increasing dimensionality and environmental complexity, leading to exponentially longer computation times. Storing all possible paths beforehand is infeasible due to memory constraints. This creates a trade-off: find an optimal path slowly, or find a feasible path quickly but sub-optimally. The paper aims to bridge this gap by providing a method that is both fast and generates near-optimal paths, even in high-dimensional configuration spaces.

Methods

The core of the proposed solution is OracleNet, a Recurrent Neural Network (RNN) that learns to generate motion plans. Instead of performing a search, OracleNet iteratively predicts the next waypoint in a path, guided by the desired goal location as an auxiliary input. This "stepping" approach mimics an ideal "oracle" planner that can instantly provide optimal paths.

Key methodological aspects include:

  • Recurrent Neural Networks (RNNs) with LSTMs: The network uses stacked Long Short-Term Memory (LSTM) layers to maintain temporal dependencies and preserve information over the path sequence.
  • Oracle Imitation: The training data consists of optimal paths generated by an "expert" planner (A* in this case). The network learns to replicate this expert behavior.
  • Fixed-Time Execution: A significant advantage is that OracleNet's execution time is largely independent of the environment's complexity, offering a consistent performance.
  • Bi-directional Path Generation: To improve convergence and robustness, the planning process starts from both the start and goal points simultaneously, with the two branches meeting in the middle.
  • Repair and Rewire Module: To handle occasional deviations from optimal paths or minor inaccuracies, a repair module corrects waypoints that fall into obstacles, and a rewire module smooths the path by removing unnecessary waypoints.

Datasets

The paper does not introduce new benchmark datasets. Instead, it focuses on generating training data for various environments:

  • 2D Gridworld: For simpler environments, A* was used to generate 20,000 valid paths on a 100x100 grid.
  • Multi-Link Manipulators (3, 4, and 6-DOF): For higher dimensions, training sets were generated using A* on discretized configuration spaces. The number of nodes varied, with millions of paths generated for the 6-DOF case.
  • 7-DOF Baxter Robot: For this complex robot, RRT-Connect was used to generate a dataset of 40,000 paths.

The training data was split into 80% for training and 20% for testing to control for overfitting.

Key Insights and Ideas

  • Neural Networks as "Oracles": The core idea of training a neural network to imitate an optimal planner, rather than performing a search itself, is a powerful paradigm shift. This allows for fast, online path generation.
  • Fixed-Time Execution is Achievable: The paper demonstrates that it's possible to achieve near-fixed execution times for path planning, regardless of environmental complexity, by leveraging learned policies. This is a critical advantage for real-time robotics.
  • Scalability with Dimensions: OracleNet shows remarkable scalability in higher dimensions, outperforming traditional methods that suffer from exponential complexity increases.
  • Bi-directional Planning Enhances Robustness: Using a bi-directional approach not only speeds up convergence but also makes the path generation more robust by allowing the network to target a shifting goal.
  • Repair and Rewire are Crucial Post-processing Steps: While the neural network is the primary planner, the repair and rewire modules are essential for ensuring path feasibility and smoothness, especially when dealing with complex environments or slight network inaccuracies.

Key Results

  • Speed: OracleNet consistently outperforms A and RRT in completion time across various environments. For example, in the 2D Gridworld, OracleNet's completion time is around 0.13-0.24 seconds, compared to A's 0.05-0.09 seconds and RRT's 0.93-8.79 seconds. In higher dimensions (6-DOF), OracleNet achieves completion times of around 1.24 seconds, while RRT* takes over 29 seconds.
  • Optimality: OracleNet generates paths that are near-optimal, with optimality ratios (OracleNet path length / benchmark path length) close to 1. For instance, in the 2D Gridworld, the ratio is around 0.96-0.99 compared to A, and 0.84-0.89 compared to RRT. In higher dimensions, it maintains similar optimality.
  • Consistency: The paper highlights OracleNet's consistent performance, evidenced by a low standard deviation in execution times, unlike A and RRT which show much wider spreads.
  • Success Rate: With the repair and rewire modules, OracleNet achieved a 100% success rate in finding feasible paths in the tested environments.

Limitations and Future Work

  • Static Environments: The current OracleNet is designed for static environments. Adapting it to dynamic environments where obstacles move or appear unexpectedly is a significant area for future work.
  • Training Data Dependency: OracleNet requires training on a dataset of expert paths for each new environment. The cost of generating this data and training the network is an offline overhead.
  • Environment Encoding: While OracleNet implicitly learns obstacle encodings, explicitly encoding environment information, especially for multi-DOF systems, remains a challenge.
  • Future Work: The authors suggest exploring transfer learning to adapt to unseen environments, improving sampling strategies for training data, and developing OracleNet as a local planner component for task-based planners. They also mention the possibility of contextualizing path generation on obstacle representations for dynamic environments.

Summary updated

Abstract

Fast and efficient path generation is critical for robots operating in complex environments. This motion planning problem is often performed in a robot's actuation or configuration space, where popular pathfinding methods such as A*, RRT*, get exponentially more computationally expensive to execute as the dimensionality increases or the spaces become more cluttered and complex. On the other hand, if one were to save the entire set of paths connecting all pair of locations in the configuration space a priori, one would run out of memory very quickly. In this work, we introduce a novel way of producing fast and optimal motion plans for static environments by using a stepping neural network approach, called OracleNet. OracleNet uses Recurrent Neural Networks to determine end-to-end trajectories in an iterative manner that implicitly generates optimal motion plans with minimal loss in performance in a compact form. The algorithm is straightforward in implementation while consistently generating near-optimal paths in a single, iterative, end-to-end roll-out. In practice, OracleNet generally has fixed-time execution regardless of the configuration space complexity while outperforming popular pathfinding algorithms in complex environments and higher dimensions
BibTeX
@inproceedings{bency2019neural,
  author = {Mayur J. Bency and Ahmed Hussain Qureshi and Michael C. Yip},
  title = {{Neural Path Planning: Fixed Time, Near-Optimal Path Generation via Oracle Imitation}},
  booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=-mbIua0-LWR},
}
Figure