Optimal Solving of Constrained Path-Planning Problems with Graph Convolutional Networks and Optimized Tree Search
arXiv:2108.01036 · doi:10.1109/IROS40897.2019.8968113
Abstract
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.
arXiv commentPublished as a conference paper at IROS 2019
References in corpus (18)
- Adam: A Method for Stochastic Optimization
- Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift
- Geometric deep learning: going beyond Euclidean data
- Spectral Networks and Locally Connected Networks on Graphs
- Deep Convolutional Networks on Graph-Structured Data
- MAGNN: Metapath Aggregated Graph Neural Network for Heterogeneous Graph Embedding
- Deep Graph Library: A Graph-Centric, Highly-Performant Package for Graph Neural Networks
- GNNExplainer: Generating Explanations for Graph Neural Networks
- Towards Deeper Graph Neural Networks
- Learning to schedule job-shop problems: Representation and policy learning using graph neural network and reinforcement learning
- Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search
- Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learning
- SIGN: Scalable Inception Graph Neural Networks
- Learning Combinatorial Optimization on Graphs: A Survey with Applications to Networking
- Message-Passing Neural Networks Learn Little's Law
- Joint Interaction and Trajectory Prediction for Autonomous Driving using Graph Neural Networks
- Path Planning using Neural A* Search
- Learning-based Preference Prediction for Constrained Multi-Criteria Path-Planning