Quantifying Degrees of Controllability in Temporal Networks with Uncertainty

  • Shyan Akmal Harvey Mudd College
  • Savana Ammons Harvey Mudd College
  • Hemeng Li Harvey Mudd College
  • James C. Boerkoel Jr. Harvey Mudd College


Controllability for Simple Temporal Networks with Uncertainty (STNUs) has thus far been limited to three levels: strong, dynamic, and weak. Because of this, there is currently no systematic way for an agent to assess just how far from being controllable an uncontrollable STNU is. We use a new geometric interpretation of STNUs to introduce the degrees of strong and dynamic controllability – continuous metrics that measure how far a network is from being controllable. We utilize these metrics to approximate the probabilities that an STNU can be dispatched successfully offline and online respectively. We introduce new methods for predicting the degrees of strong and dynamic controllability for uncontrollable networks. In addition, we show empirically that both metrics are good predictors of the actual dispatch success rate.