mlsanityData to 7 Oct 2026

Time-based Dynamic Controllability of Disjunctive Temporal Networks with Uncertainty: A Tree Search Approach with Graph Neural Network Guidance

arXiv 2108.01068 ↗First posted 2 Aug 2021cs.AI cs.LG cs.ROcited by 1

Not on the map. Why?

Abstract (arXiv)

Scheduling in the presence of uncertainty is an area of interest in artificial intelligence due to the large number of applications. We study the problem of dynamic controllability (DC) of disjunctive temporal networks with uncertainty (DTNU), which seeks a strategy to satisfy all constraints in response to uncontrollable action durations. We introduce a more restricted, stronger form of controllability than DC for DTNUs, time-based dynamic controllability (TDC), and present a tree search approach to determine whether or not a DTNU is TDC. Moreover, we leverage the learning capability of a message passing neural network (MPNN) as a heuristic for tree search guidance. Finally, we conduct experiments for which the tree search shows superior results to state-of-the-art timed-game automata (TGA) based approaches. We observe that using an MPNN for tree search guidance leads to a significant increase in solving performance and scalability to harder DTNU problems.

Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 13 of its 29 references that are in the map. First posted on arXiv 2 Aug 2021.

Builds on

13 of 29 references.

References · 13

  1. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  2. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  3. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  4. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,906
  5. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,085
  6. 2015Gated Graph Sequence Neural Networkscited by 792
  7. 2016Interaction Networks for Learning about Objects, Relations and Physicscited by 503
  8. 2018Neural Relational Inference for Interacting Systemscited by 339
  9. 2019Exact Combinatorial Optimization with Graph Convolutional Neural Networkscited by 313
  10. 2018Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Searchcited by 182
  11. 2018Experience-driven Networking: A Deep Reinforcement Learning based Approachcited by 41
  12. 2019Unveiling the potential of Graph Neural Networks for network modeling and optimization in SDNcited by 27
1 more
  1. 2019Complexity Bounds for the Controllability of Temporal Networks with Conditions, Disjunctions, and Uncertaintycited by 3

Built on by

Cited by year

Citing papers per year: 2022: 1.

1 paper.

  1. 2022Planning and Learning: Path-Planning for Autonomous Vehicles, a Review of the Literaturecited by 1