Solving Disjunctive Temporal Networks with Uncertainty under Restricted Time-Based Controllability using Tree Search and Graph Neural Networks
Not on the map. Why?
Abstract (arXiv)
Planning under uncertainty is an area of interest in artificial intelligence. We present a novel approach based on tree search and graph machine learning for the scheduling problem known as Disjunctive Temporal Networks with Uncertainty (DTNU). Dynamic Controllability (DC) of DTNUs seeks a reactive scheduling strategy to satisfy temporal constraints in response to uncontrollable action durations. We introduce new semantics for reactive scheduling: Time-based Dynamic Controllability (TDC) and a restricted subset of TDC, R-TDC. We design a tree search algorithm to determine whether or not a DTNU is R-TDC. Moreover, we leverage a graph neural network as a heuristic for tree search guidance. Finally, we conduct experiments on a known benchmark on which we show R-TDC to retain significant completeness with regard to DC, while being faster to prove. This results in the tree search processing fifty percent more DTNU problems in R-TDC than the state-of-the-art DC solver does in DC with the same time budget. We also observe that graph neural network search guidance leads to substantial performance gains on benchmarks of more complex DTNUs, with up to eleven times more problems solved than the baseline tree search.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 39 of its 81 references that are in the map. First posted on arXiv 28 Mar 2022.
Builds on
39 of 81 references.
References · 39
- 2015Deep Residual Learning for Image Recognitioncited by 51,809
- 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
- 2018How Powerful are Graph Neural Networks?cited by 4,355
- 2017Neural Message Passing for Quantum Chemistrycited by 3,460
- 2019A Comprehensive Survey on Graph Neural Networkscited by 2,906
- 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,085
- 2019GNNExplainer: Generating Explanations for Graph Neural Networkscited by 735
- 2016Interaction Networks for Learning about Objects, Relations and Physicscited by 503
- 2018Neural Relational Inference for Interacting Systemscited by 339
- 2019Exact Combinatorial Optimization with Graph Convolutional Neural Networkscited by 313
- 2020Towards Deeper Graph Neural Networkscited by 296
- 2020SIGN: Scalable Inception Graph Neural Networkscited by 283
27 more
- 2021Combinatorial optimization and reasoning with graph neural networkscited by 267
- 2020Generalization and Representational Limits of Graph Neural Networkscited by 217
- 2019What graph neural networks cannot learn: depth vs widthcited by 195
- 2018Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Searchcited by 182
- 2021Training Graph Neural Networks with 1000 Layerscited by 169
- 2020Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learningcited by 139
- 2019Graph Neural Networks for Decentralized Multi-Robot Path Planningcited by 84
- 2020Learning Combinatorial Optimization on Graphs: A Survey with Applications to Networkingcited by 70
- 2019Approximation Ratios of Graph Neural Networks for Combinatorial Problemscited by 68
- 2018Learning to Solve NP-Complete Problems - A Graph Neural Network for Decision TSPcited by 58
- 2020Collaborative Motion Prediction via Neural Motion Message Passingcited by 55
- 2021Learning to schedule job-shop problems: Representation and policy learning using graph neural network and reinforcement learningcited by 52
- 2018Experience-driven Networking: A Deep Reinforcement Learning based Approachcited by 41
- 2019Graph Colouring Meets Deep Learning: Effective Graph Neural Network Models for Combinatorial Problemscited by 40
- 2020Learning to Solve Combinatorial Optimization Problems on Real-World Graphs in Linear Timecited by 39
- 2020Planning with Learned Object Importance in Large Problem Instances using Graph Neural Networkscited by 38
- 2019Unveiling the potential of Graph Neural Networks for network modeling and optimization in SDNcited by 27
- 2020Distributed Scheduling using Graph Neural Networkscited by 27
- 2020Graph Neural Networks for Decentralized Controllerscited by 14
- 2018Online Planner Selection with Graph Neural Networks and Adaptive Schedulingcited by 13
- 2020PTP: Parallelized Tracking and Prediction with Graph Neural Networks and Diversity Samplingcited by 13
- 2019Size Independent Neural Transfer for RDDL Planningcited by 12
- 2019Message-Passing Neural Networks Learn Little's Lawcited by 7
- 2019Complexity Bounds for the Controllability of Temporal Networks with Conditions, Disjunctions, and Uncertaintycited by 3
- 2021Optimal Solving of Constrained Path-Planning Problems with Graph Convolutional Networks and Optimized Tree Searchcited by 3
- 2021Constrained Shortest Path Search with Graph Convolutional Neural Networkscited by 2
- 2021Learning-based Preference Prediction for Constrained Multi-Criteria Path-Planningcited by 2
Built on by
Citing papers per year: 2022: 1.
1 paper.