Student Co-author

HMC Undergraduate

Document Type

Conference Proceeding

Department

Harvey Mudd College, Computer Science (HMC)

Publication Date

4-3-2020

Abstract

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 MIN-LOSS 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 MAX-GAIN 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 dynamically controllable schedules. We empirically compare our approaches against two existing PSTN offline dispatch approaches and one online approach and show that our MIN-LOSS DC algorithm outperforms the others in terms of maximizing execution success while maintaining competitive runtimes.

Rights Information

© 2020 Association for the Advancement of Artificial Intelligence

Terms of Use & License Information

Creative Commons Attribution 4.0 License
This work is licensed under a Creative Commons Attribution 4.0 License.

Download

Share

COinS