This repository hosts a collection of programs written by team Ctrl Alt Repeat (part of the Summer 2019 HEATlab group). This work resulted in a publication at the Thirty-Fourth AAAI conference on Artificial Intelligence titled "Dynamic Control of Probabilistic Simple Temporal Networks". A pre-print is available here.
Note that the files included in this repository need to be executed within the code environment created by team Prob-In-Ctrl of HEATlab, which can be accessed here. Additionally, the results for SREA and DREA can be obtained from the DREAM algorithm source code.
The stn folder contains files describing an STN class (which is really a class for STNUs, and more generally could be easily extended to represetn PSTNs) and converting between the class and JSON representations of networks.
The remaining programs are not organized in any particular way. Because of this, in the comments that follow we often describe as a function taking in an "STN" when it really also works with STNUs as input.
Implements conflict generating algorithms for checking if a STNU is dynamically controllable (DC). If the network is not DC, there are functions for reporting the "conflicts" that prevent the network from achieving controllability.
Implements the DCDijkstra algorithm described in (Williams 2017).
Implements a dispatch strategy and associated simulation for STNUs, based off Algorithm 2 from (Nilsson 2014).
This strategy should always succeed for dynamically controllable STNUs.
It works by first leveraging a conversion to the DC_STN class to infer wait constraints, and then following early execution.
Defines STN, Edge, and Vertex classes.
A Vertex represents an event in an STN. It is encoded as a single node with a unique integer ID.
An Edge represents a constraint in an STN.
It is encoded as a pair of vertex IDs labeled with an interval and type.
The type designates an edge as a requirement (stc) or contingent (stcu) edge.
An STN consists of events with constraints in between events. An STN object is encoded as set of Vertices with Edges between some pairs of vertices.
In general, a Vertex with ID zero is treated as the zero-timepoint.
Provides functions to create STN objects from input JSON files.
Computes and plots empirical results, mainly related to strong controllability.
Leverages functions from LP.py, dispatch.py, and relax.py to measure approximate and exact degrees of strong controllability, approximate degrees of dynamic controllability, and true success rates with different dispatch strategies.
Comtains some methods for plotting these results as well.
The Summer 2019 HEATlab consisted of teams Ctrl-Alt-Repeat and MAD-TN, which our team being the spiritual extention of 2018 team Prob-In-Ctrl/ All teams worked at Harvey Mudd College under the supervision of Professor Jim Boerkoel as part of the HMC CS department's "summer of CS".
-
Ctrl-Alt-Repeat ~ Team {Lindsay Popowski, Michael Gao}
- Explored dynnamic controllability schedulers for PSTNs
- A pre-print of our work, published in ICAPS-19, can be accessed here.
This project is licensed under the terms of the MIT license.