@article{Gao_Popowski_Boerkoel_2020, title={Dynamic Control of Probabilistic Simple Temporal Networks}, volume={34}, url={https://ojs.aaai.org/index.php/AAAI/article/view/6538}, DOI={10.1609/aaai.v34i06.6538}, abstractNote={<p>The controllability of a temporal network is defined as an agent’s ability to navigate around the uncertainty in its schedule and is well-studied for certain networks of temporal constraints. However, many interesting real-world problems can be better represented as Probabilistic Simple Temporal Networks (PSTNs) in which the uncertain durations are represented using potentially-unbounded probability density functions. This can make it inherently impossible to control for all eventualities. In this paper, we propose two new dynamic controllability algorithms that attempt to maximize the likelihood of successfully executing a schedule within a PSTN. The first approach, which we call M<span style="font-variant: small-caps;">in</span>-L<span style="font-variant: small-caps;">oss</span> DC, finds a dynamic scheduling strategy that minimizes loss of control by using a conflict-directed search to decide where to sacrifice the control in a way that optimizes overall success. The second approach, which we call M<span style="font-variant: small-caps;">ax</span>-G<span style="font-variant: small-caps;">ain</span> DC, works in the other direction: it finds a dynamically controllable schedule and then attempts to progressively strengthen it by capturing additional uncertainty. Our approaches are the first known that work by finding maximally <em>dynamically controllable</em> schedules. We empirically compare our approaches against two existing PSTN offline dispatch approaches and one online approach and show that our M<span style="font-variant: small-caps;">in</span>-L<span style="font-variant: small-caps;">oss</span> DC algorithm outperforms the others in terms of maximizing execution success while maintaining competitive runtimes.</p>}, number={06}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Gao, Michael and Popowski, Lindsay and Boerkoel, Jim}, year={2020}, month={Apr.}, pages={9851-9858} }