A Caltech Library Service

PARIS: a Polynomial-time, Risk-Sensitive Scheduling Algorithm for Probabilistic Simple Temporal Networks with Uncertainty

Santana, Pedro and Vaquero, Tiago and Toledo, Cláudio and Wang, Andrew and Fang, Cheng and Williams, Brian (2016) PARIS: a Polynomial-time, Risk-Sensitive Scheduling Algorithm for Probabilistic Simple Temporal Networks with Uncertainty. In: 26th International Conference on Automated Planning and Scheduling, June 12-17, 2016, London, UK.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


Inspired by risk-sensitive, robust scheduling for planetary rovers under temporal uncertainty, this work introduces the Probabilistic Simple Temporal Network with Uncertainty (PSTNU), a temporal planning formalism that unifies the set-bounded and probabilistic temporal uncertainty models from the STNU and PSTN literature. By allowing any combination of these two types of uncertainty models, PSTNU's can more appropriately reflect the varying levels of knowledge that a mission operator might have regarding the stochastic duration models of different activities. We also introduce PARIS, a novel sound and provably polynomial-time algorithm for risk-sensitive strong scheduling of PSTNU's. Due to its fully linear problem encoding for typical temporal uncertainty models, PARIS is shown to outperform the current fastest algorithm for risk-sensitive strong PSTN scheduling by nearly four orders of magnitude in some instances of a popular probabilistic scheduling benchmark, effectively bringing runtimes of hours to the realm of seconds or fractions of a second.

Item Type:Conference or Workshop Item (Paper)
Related URLs:
URLURL TypeDescription Website
Additional Information:© 2016 Association for the Advancement of Artificial Intelligence. This research was partially funded by the AFOSR grant FA95501210348. The second author is funded by the Keck Institute for Space Studies (KISS). We would like to thank Peng Yu for making the CAR-SHARING dataset available, and Christian Muise and our anonymous reviewers for their constructive and helpful comments.
Group:Keck Institute for Space Studies
Funding AgencyGrant Number
Air Force Office of Scientific Research (AFOSR)FA95501210348
Keck Institute for Space Studies (KISS)UNSPECIFIED
Subject Keywords:Scheduling under uncertainty
Record Number:CaltechAUTHORS:20160404-084538286
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:65880
Deposited By: Colette Connor
Deposited On:04 Apr 2016 18:43
Last Modified:03 Oct 2019 09:51

Repository Staff Only: item control page