mlsanityData to 7 Oct 2026

Optimal Solving of Constrained Path-Planning Problems with Graph Convolutional Networks and Optimized Tree Search

arXiv 2108.01036 ↗First posted 2 Aug 2021cs.AI cs.LG cs.ROcited by 3

Not on the map. Why?

Abstract (arXiv)

Deep learning-based methods are growing prominence for planning purposes. In this paper, we present a hybrid planner that combines a graph machine learning model and an optimal solver based on branch and bound tree search for path-planning tasks. More specifically, a graph neural network is used to assist the branch and bound algorithm in handling constraints associated with a desired solution path. There are multiple downstream practical applications, such as Autonomous Unmanned Ground Vehicles (AUGV), typically deployed in disaster relief or search and rescue operations. In off-road environments, AUGVs must dynamically optimize a source-destination path under various operational constraints, out of which several are difficult to predict in advance and need to be addressed online. We conduct experiments on realistic scenarios and show that graph neural network support enables substantial speedup and smoother scaling to harder path-planning problems. Additionally, information provided by the graph neural network enables the approach to outperform problem-specific handcrafted heuristics, highlighting the potential graph neural networks hold for path-planning tasks.

Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 48 of its 116 references that are in the map. First posted on arXiv 2 Aug 2021.

Builds on

48 of 116 references.

References · 48

  1. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  2. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  3. 2015Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shiftcited by 6,979
  4. 2018How Powerful are Graph Neural Networks?cited by 4,355
  5. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,906
  6. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,085
  7. 2013Spectral Networks and Locally Connected Networks on Graphscited by 1,097
  8. 2016Geometric deep learning: going beyond Euclidean datacited by 1,042
  9. 2015Gated Graph Sequence Neural Networkscited by 792
  10. 2019GNNExplainer: Generating Explanations for Graph Neural Networkscited by 735
  11. 2020MAGNN: Metapath Aggregated Graph Neural Network for Heterogeneous Graph Embeddingcited by 304
  12. 2020Towards Deeper Graph Neural Networkscited by 296
36 more
  1. 2020SIGN: Scalable Inception Graph Neural Networkscited by 283
  2. 2021Combinatorial optimization and reasoning with graph neural networkscited by 267
  3. 2015Deep Convolutional Networks on Graph-Structured Datacited by 246
  4. 2020Generalization and Representational Limits of Graph Neural Networkscited by 217
  5. 2019What graph neural networks cannot learn: depth vs widthcited by 195
  6. 2018Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Searchcited by 182
  7. 2021Training Graph Neural Networks with 1000 Layerscited by 169
  8. 2020Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learningcited by 139
  9. 2019Spatially-Aware Graph Neural Networks for Relational Behavior Forecasting from Sensor Datacited by 104
  10. 2019Graph Neural Networks for Decentralized Multi-Robot Path Planningcited by 84
  11. 2020Learning Combinatorial Optimization on Graphs: A Survey with Applications to Networkingcited by 70
  12. 2019Approximation Ratios of Graph Neural Networks for Combinatorial Problemscited by 68
  13. 2019Learning Decentralized Controllers for Robot Swarms with Graph Neural Networkscited by 62
  14. 2019Motion Planning Networks: Bridging the Gap Between Learning-based and Classical Motion Plannerscited by 62
  15. 2018Learning to Solve NP-Complete Problems - A Graph Neural Network for Decision TSPcited by 58
  16. 2020Collaborative Motion Prediction via Neural Motion Message Passingcited by 55
  17. 2021Learning to schedule job-shop problems: Representation and policy learning using graph neural network and reinforcement learningcited by 52
  18. 2020Path Planning using Neural A* Searchcited by 51
  19. 2019RouteNet: Leveraging Graph Neural Networks for network modeling and optimization in SDNcited by 47
  20. 2019Relational Graph Learning for Crowd Navigationcited by 42
  21. 2020Message-Aware Graph Attention Networks for Large-Scale Multi-Robot Path Planningcited by 41
  22. 2019Graph Colouring Meets Deep Learning: Effective Graph Neural Network Models for Combinatorial Problemscited by 40
  23. 2020Learning to Solve Combinatorial Optimization Problems on Real-World Graphs in Linear Timecited by 39
  24. 2020Planning with Learned Object Importance in Large Problem Instances using Graph Neural Networkscited by 38
  25. 2020Mobile Robot Path Planning in Dynamic Environments through Globally Guided Reinforcement Learningcited by 36
  26. 2021Spectral Temporal Graph Neural Network for Trajectory Predictioncited by 36
  27. 2020DAG-Net: Double Attentive Graph Neural Network for Trajectory Forecastingcited by 30
  28. 2020Distributed Scheduling using Graph Neural Networkscited by 27
  29. 2020Traffic Control Gesture Recognition for Autonomous Vehiclescited by 24
  30. 2019Neural Path Planning: Fixed Time, Near-Optimal Path Generation via Oracle Imitationcited by 23
  31. 2018Deeply Informed Neural Sampling for Robot Motion Planningcited by 19
  32. 2019Learned Critical Probabilistic Roadmaps for Robotic Motion Planningcited by 18
  33. 2019Joint Interaction and Trajectory Prediction for Autonomous Driving using Graph Neural Networkscited by 17
  34. 2020Graph Neural Networks for Decentralized Controllerscited by 14
  35. 2020PTP: Parallelized Tracking and Prediction with Graph Neural Networks and Diversity Samplingcited by 13
  36. 2019Message-Passing Neural Networks Learn Little's Lawcited by 7

Built on by

Cited by year

Citing papers per year: 2022: 3.

3 papers.

  1. 2022Space-Time Graph Neural Networks with Stochastic Graph Perturbationscited by 5
  2. 2022Solving Disjunctive Temporal Networks with Uncertainty under Restricted Time-Based Controllability using Tree Search and Graph Neural Networkscited by 1
  3. 2022Planning and Learning: Path-Planning for Autonomous Vehicles, a Review of the Literaturecited by 1