Waypoint Planning Networks

Alexandru-Iosif Toma, Hussein Ali Jaafar, Hao-Ya Hsueh, Stephen James, Daniel Lenton, Ronald Clark, Sajad Saeedi

Abstract

With the recent advances in machine learning, path planning algorithms are also evolving; however, the learned path planning algorithms often have difficulty competing with success rates of classic algorithms. We propose waypoint planning networks (WPN), a hybrid algorithm based on LSTMs with a local kernel - a classic algorithm such as A, and a global kernel using a learned algorithm. WPN produces a more computationally efficient and robust solution. We compare WPN against A, as well as related works including motion planning networks (MPNet) and value iteration networks (VIN). In this paper, the design and experiments have been conducted for 2D environments. Experimental results outline the benefits of WPN, both in efficiency and generalization. It is shown that WPN's search space is considerably less than A, while being able to generate near optimal results. Additionally, WPN works on partial maps, unlike A which needs the full map in advance.

Introduction

In mobile robotics, path planning is typically dominated by classic algorithms like A* or Dijkstra. While these graph-search methods guarantee optimal paths, they are computationally expensive because they must search a massive portion of the configuration space. This high "search space" translates directly to heavy memory utilization, which is a bottleneck for embedded devices. On the other hand, purely learning-based planners (like Value Iteration Networks or Motion Planning Networks) are faster and more memory-efficient, but they struggle to match the high success rates and reliability of classic algorithms, often failing in complex environments. Waypoint Planning Networks (WPN) addresses this gap by using machine learning to generate highly accurate waypoints that guide a classic algorithm, thereby shrinking the search space without sacrificing the success rate.

Methods

WPN introduces a hybrid architecture split into two main components: a Global Kernel (learned) and a Local Kernel (classic).

The WPN architecture combines a learned Global Kernel for waypoint generation with a classic Local Kernel for navigation.

The Global Kernel is responsible for looking at the environment and dropping a breadcrumb trail of waypoints toward the goal. It is built from several sub-modules:

  • View Module: An LSTM network that acts greedily based on local surroundings (distance to obstacles, direction to the goal).
  • Map Module: A Convolutional Auto-encoder (CAE) paired with an LSTM that processes a compressed global snapshot of the map (even if it's only partially known).
  • Bagging Module: An ensemble approach that runs the View and Map modules in parallel, dynamically picking the best solution based on progress and path length.
  • Waypoint Module: Uses the Bagging module to bound the iterations of the global search, outputting discrete waypoints.

The Local Kernel then takes over. WPN uses standard A to navigate the short, simple distances between the generated waypoints. Because A is only solving micro-routes rather than the entire global map, its search space is kept incredibly small.

Key Results

WPN was evaluated on synthetic datasets (PathBench), large-scale indoor layouts (HouseExpo), and real-world SLAM maps. The results demonstrate significant improvements over both classic and purely learned baselines:

  • High Success Rate: On 64×64 maps, WPN achieved a 98.13% success rate, matching A* and vastly outperforming purely learned models like VIN (26.2%) and MPNet (16.2%).
  • Search Space Reduction: WPN drastically reduces the computational burden. On 64×64 maps, WPN only needed to search 2.03% of the map cells, compared to A's 10.82%*.
Comparison of search space between WPN (left) and A* (right). WPN achieves a near-optimal path with a significantly smaller search space (2.30% vs 18.54%).
  • Zero-Shot Generalization: Despite being trained on synthetic 64×64 maps, WPN successfully generalized to much larger 512×512 maps and real-world SLAM maps without retraining.
  • Exploration Capability: Unlike standard A*, which requires a complete map in advance, WPN can operate on partial maps, generating waypoints as the robot explores unknown territory.

Conclusion

Waypoint Planning Networks provide a robust hybrid solution for 2D path planning. By combining the efficiency of LSTMs with the reliability of A, WPN achieves near-optimal results with a fraction of the search space required by traditional methods. While the neural network overhead currently results in slower raw computation times than pure A, the massive reduction in memory usage makes WPN a promising candidate for resource-constrained embedded systems. Future work will focus on optimizing computation time, extending the architecture to 3D environments, and incorporating kinematic constraints.

Summary updated

Abstract

With the recent advances in machine learning, path planning algorithms are also evolving; however, the learned path planning algorithms often have difficulty competing with success rates of classic algorithms. We propose waypoint planning networks (WPN), a hybrid algorithm based on LSTMs with a local kernel - a classic algorithm such as A*, and a global kernel using a learned algorithm. WPN produces a more computationally efficient and robust solution. We compare WPN against A*, as well as related works including motion planning networks (MPNet) and value iteration networks (VIN). In this paper, the design and experiments have been conducted for 2D environments. Experimental results outline the benefits of WPN, both in efficiency and generalization. It is shown that WPN's search space is considerably less than A*, while being able to generate near optimal results. Additionally, WPN works on partial maps, unlike A* which needs the full map in advance. The code is available online.
BibTeX
@inproceedings{toma2021waypoint,
  author = {Alexandru-Iosif Toma and Hussein Ali Jaafar and Hao-Ya Hsueh and Stephen James and Daniel Lenton and Ronald Clark and Sajad Saeedi},
  title = {{Waypoint Planning Networks}},
  booktitle = {CRV},
  year = {2021},
  url = {https://openreview.net/forum?id=mE9g9KOsXw_},
}
Figure