Hybrid Search with Graph Neural Networks for Constraint-Based Navigation Planning [Extended Abstract]

Marc-Emmanuel Coupvent des Graviers, Kevin Osanlou, Christophe Guettier, Tristan Cazenave

Introduction

Route planning for autonomous vehicles involves navigating complex, sparse road networks while adhering to strict operational constraints such as delivery windows, fuel limits, and cargo capacity. Traditional optimization methods, like Constraint Programming (CP), provide mathematical guarantees of optimality but often suffer from exponential search times as problem sizes grow. Conversely, pure Machine Learning (ML) approaches offer rapid inference but frequently struggle with feasibility guarantees and generalization to larger, unseen maps.

This research introduces a hybrid navigation planning framework that combines the pattern-recognition strengths of Graph Neural Networks (GNNs) with the rigorous optimality of CP. By using a GNN to "score" edges on real-world road networks, the system provides a high-quality search strategy that allows CP solvers to find optimal routes significantly faster.

The Hybrid Architecture

The proposed framework utilizes a two-stage process to bridge the gap between neural intuition and mathematical rigor:

1. The GNN Probe

Unlike auto-regressive models that build paths step-by-step—a process that is computationally expensive—the authors designed a message-passing GNN that performs a single inference pass. This GNN analyzes the graph topology and assigns a probability score to each edge, representing the likelihood that the edge belongs in an optimal path. To ensure the model is robust and "translation invariant," the researchers used shortest-path costs between nodes as input features rather than absolute GPS coordinates. This allows the model to focus on connectivity and distance rather than specific geographic locations.

2. Constraint Programming (CP) Guidance

These GNN-generated edge scores are integrated directly into a CP solver. Instead of exploring the search tree blindly, the solver uses the scores to prioritize which variables to branch on first. This guided search focuses the solver's efforts on the most promising areas of the solution space. Crucially, because CP remains the underlying engine, the system maintains its ability to prove optimality or determine if no feasible solution exists, even if the GNN's predictions are imperfect.

Experimental Setup and Datasets

Moving beyond synthetic benchmarks, the study utilized real-world data from OpenStreetMap. The researchers generated training and validation sets by selecting mandatory delivery points on these real maps and solving them exactly to provide "ground truth" labels. This approach ensures the model learns the nuances of actual road topologies rather than the simplified geometry of random point clouds.

Key Insights and Performance

  • Scalability and Generalization: A pivotal finding was that a GNN trained on small routing problems (e.g., 20 nodes) can effectively guide a solver through much larger problems (e.g., 50+ nodes). This suggests the GNN learns fundamental rules of navigation that scale beyond its training distribution.
  • Topological Awareness: By training on non-complete graphs (actual road networks), the GNN captures richer structural information than standard Traveling Salesperson Problem (TSP) solvers, which often assume every point is directly connected to every other point.
  • Computational Efficiency: Because the GNN only runs once per problem instance, the computational overhead is minimal. This makes the framework feasible for deployment on the limited hardware typically found in autonomous vehicle systems.
  • Search Quality: The hybrid method demonstrated a significant increase in performance, particularly in its ability to find high-quality intermediate solutions quickly for large-scale instances.

Limitations and Future Directions

While the model excels at single-vehicle routing, expanding the framework to multi-vehicle fleets with intersecting constraints remains a primary challenge. Additionally, while the model is invariant to rotation and translation, transfer learning between drastically different graph structures (e.g., moving from a grid-like city to a rural network) requires further investigation. Future work will also focus on incremental solving to handle real-time re-planning in response to dynamic obstacles or updated delivery requirements.

Summary updated

Abstract

Route planning for autonomous vehicles is a challenging task, especially in dense road networks with multiple delivery points. Additional external constraints can quickly add overhead to this already-difficult problem that often requires prompt, on-the-fly decisions. This work introduces a hybrid method combining machine learning and Constraint Programming (CP) to improve search performance. A new message passing-based graph neural network tailored to constraint solving and global search is defined. Once trained, a single neural network inference is enough to guide CP search while ensuring solution optimality. Large-scale experiments using real road networks from cities worldwide are presented. The hybrid method is effective in solving complex routing problems, addressing larger problems than those used for model training.
BibTeX
@inproceedings{graviers2023hybrid,
  author = {Marc-Emmanuel Coupvent des Graviers and Kevin Osanlou and Christophe Guettier and Tristan Cazenave},
  title = {{Hybrid Search with Graph Neural Networks for Constraint-Based Navigation Planning [Extended Abstract]}},
  booktitle = {SOCS},
  year = {2023},
  doi = {10.1609/socs.v16i1.27299},
}
Figure