AAAI Publications, Thirty-First AAAI Conference on Artificial Intelligence

Font Size: 
Robust Execution of Probabilistic Temporal Plans
Kyle Lund, Sam Dietrich, Scott Chow, James C. Boerkoel

Last modified: 2017-02-12


A critical challenge in temporal planning is robustly dealing with non-determinism, e.g., the durational uncertainty of a robot's activity due to slippage or other unexpected influences. Recent advances show that robustness is a better measure of solution quality than traditional metrics such as flexibility. This paper introduces the Robust Execution Problem for finding maximally robust dispatch strategies for general probabilistic temporal planning problems. While generally intractable, we introduce approximate solution techniques — one that can be computed statically prior to the start of execution with robustness guarantees and one that dynamically adjusts to opportunities and setbacks during execution. We show empirically that our dynamic approach outperforms all known approaches in terms of execution success rate.


Probabilistic Temporal Planning; Simple Temporal Problem; Robustness; Scheduling Under Uncertainty

Full Text: PDF