This repository hosts a collection of programs written by team Improvisational-Teamwork (part of the Summer 2022 HEATlab group). This work resulted in a publication at the 33rd ICAPS conference on Automatic Planning and Scheduling titled "Sensitivity Analysis for Dynamic Control of PSTNs with Skewed Distributions". The paper is now available.
The results for SREA and DREA can be obtained from the DREAM algorithm source code. The results for Min-Loss and Max-Gain can be obtained from the DCforPSTN 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.
Two existing PSTN benchmarks are changed by replacing theirnormally-distributed uncertainty models with distributionsthat capture more natural sources of uncertainty. As a basis for our augmented benchmark, we use the DREAM bench-mark of 540 PSTNs (Abrahams et al. 2019) and the CAR-SHARING dataset of 169 PSTNs which was created by San-tana et al. (2016) and then edited by Akmal et al. (2019). Varied benchmarks can be found in the dataset folder.
We modify Min-Loss and Max-Gain from Gao, Popowski, and Boerkoel to build probability-aware dispatching algorithm under dynamic controllability. Details of modified algorithms can be found on branch minloss+ and maxgain+.
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 2022 HEATlab consisted of teams Improvisational-Teamwork and MAD-TN, which our team being the spiritual extention of 2021 team Controlled-Choices/ and 2019 team Ctrl-Alt-Repeat/ 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".
-
Improvisational-Teamwork ~ Team {Rosy Chen, Eryn Ma, Ingrid Wu}
- Evaluate how well existing scheduling approaches for PSTN with normal, symmetric distributions extend to skewed, non-ordinary distributions
- The paper can be accessed at https://ojs.aaai.org/index.php/ICAPS/article/view/27183.
This project is licensed under the terms of the MIT license.