PARIS: A Polynomial-Time, Risk-Sensitive Scheduling Algorithm for Probabilistic Simple Temporal Networks with Uncertainty. Santana, P., Vaquero, T., Toledo, C., Wang, A., Fang, C., & Williams, B. In ![PARIS: A Polynomial-Time, Risk-Sensitive Scheduling Algorithm for Probabilistic Simple Temporal Networks with Uncertainty [link]](https://bibbase.org/img/filetypes/link.svg "link")
Paper abstract bibtex 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.
@inproceedings {icaps16-180,
track = {Main Track},
title = {PARIS: A Polynomial-Time, Risk-Sensitive Scheduling Algorithm for Probabilistic Simple Temporal Networks with Uncertainty},
url = {http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13138},
author = {Pedro Santana and Tiago Vaquero and Cláudio Toledo and Andrew Wang and Cheng Fang and Brian Williams},
abstract = {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.},
keywords = {Scheduling under uncertainty}
}
Downloads: 0
{"_id":"c7LHDm3c8GqAJTZhy","bibbaseid":"santana-vaquero-toledo-wang-fang-williams-parisapolynomialtimerisksensitiveschedulingalgorithmforprobabilisticsimpletemporalnetworkswithuncertainty","downloads":0,"creationDate":"2016-03-09T03:08:50.051Z","title":"PARIS: A Polynomial-Time, Risk-Sensitive Scheduling Algorithm for Probabilistic Simple Temporal Networks with Uncertainty","author_short":["Santana, P.","Vaquero, T.","Toledo, C.","Wang, A.","Fang, C.","Williams, B."],"year":null,"bibtype":"inproceedings","biburl":"icaps16.icaps-conference.org/papers.bib","bibdata":{"bibtype":"inproceedings","type":"inproceedings","track":"Main Track","title":"PARIS: A Polynomial-Time, Risk-Sensitive Scheduling Algorithm for Probabilistic Simple Temporal Networks with Uncertainty","url":"http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13138","author":[{"firstnames":["Pedro"],"propositions":[],"lastnames":["Santana"],"suffixes":[]},{"firstnames":["Tiago"],"propositions":[],"lastnames":["Vaquero"],"suffixes":[]},{"firstnames":["Cláudio"],"propositions":[],"lastnames":["Toledo"],"suffixes":[]},{"firstnames":["Andrew"],"propositions":[],"lastnames":["Wang"],"suffixes":[]},{"firstnames":["Cheng"],"propositions":[],"lastnames":["Fang"],"suffixes":[]},{"firstnames":["Brian"],"propositions":[],"lastnames":["Williams"],"suffixes":[]}],"abstract":"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.","keywords":"Scheduling under uncertainty","bibtex":"@inproceedings {icaps16-180,\r\n track = {Main Track},\r\n title = {PARIS: A Polynomial-Time, Risk-Sensitive Scheduling Algorithm for Probabilistic Simple Temporal Networks with Uncertainty},\r\n url = {http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13138},\r\n author = {Pedro Santana and Tiago Vaquero and Cláudio Toledo and Andrew Wang and Cheng Fang and Brian Williams},\r\n abstract = {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.},\r\n keywords = {Scheduling under uncertainty}\r\n}\r\n\r\n","author_short":["Santana, P.","Vaquero, T.","Toledo, C.","Wang, A.","Fang, C.","Williams, B."],"key":"icaps16-180","id":"icaps16-180","bibbaseid":"santana-vaquero-toledo-wang-fang-williams-parisapolynomialtimerisksensitiveschedulingalgorithmforprobabilisticsimpletemporalnetworkswithuncertainty","role":"author","urls":{"Paper":"http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13138"},"keyword":["Scheduling under uncertainty"],"metadata":{"authorlinks":{}},"downloads":0,"html":""},"search_terms":["paris","polynomial","time","risk","sensitive","scheduling","algorithm","probabilistic","simple","temporal","networks","uncertainty","santana","vaquero","toledo","wang","fang","williams"],"keywords":["scheduling under uncertainty"],"authorIDs":[],"dataSources":["iMkx859KiXcegwsin","EZtZjCTnxcdTTyeij"]}