Chance-Constrained Probabilistic Simple Temporal Problems
Author(s)
Fang, Cheng; Yu, Peng; Williams, Brian Charles
DownloadWilliams_Chance-constrained probabilistic.pdf (735.1Kb)
OPEN_ACCESS_POLICY
Open Access Policy
Creative Commons Attribution-Noncommercial-Share Alike
Terms of use
Metadata
Show full item recordAbstract
Scheduling under uncertainty is essential to many autonomous systems and logistics tasks. Probabilistic methods for solving temporal problems exist which quantify and attempt to minimize the probability of schedule failure. These methods are overly conservative, resulting in a loss in schedule utility. Chance constrained formalism address over-conservatism by imposing bounds on risk, while maximizing utility subject to these risk bounds. In this paper we present the probabilistic Simple Temporal Network (pSTN), a probabilistic formalism for representing temporal problems with bounded risk and a utility over event timing. We introduce a constrained optimisation algorithm for pSTNs that achieves compactness and efficiency through a problem encoding in terms of a parameterised STNU and its reformulation as a parameterised STN. We demonstrate through a car sharing application that our chance-constrained approach runs in the same time as the previous probabilistic approach, yields solutions with utility improvements of at least 5% over previous arts, while guaranteeing operation within the specified risk bound.
Date issued
2014-07Department
Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory; Massachusetts Institute of Technology. Department of Aeronautics and AstronauticsJournal
Proceedings of the Conference on Innovative Applications of Artificial Intelligence (IAAI 2014)
Publisher
Association for the Advancement of Artificial Intelligence (AAAI)
Citation
Fang, Cheng, Peng Yu, and Brian C. Williams. "Chance-Constrained Probabilistic Simple Temporal Problems." in The Twenty-Sixth Annual Conference on Innovative Applications of Artificial Intelligence (IAAI-14), July 29–31, 2014, Québec City, Québec, Canada.
Version: Author's final manuscript
ISSN
2154-8080