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


  • Marc-Emmanuel Coupvent des Graviers Safran Electronics & Defense
  • Kevin Osanlou Lamsade Paris-Dauphine University
  • Christophe Guettier Safran Electronics & Defense
  • Tristan Cazenave Lamsade Paris-Dauphine University




Machine And Deep Learning In Search, Constraint Search, Real-life Applications


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.