Estimating the Probability of Meeting a Deadline in Hierarchical Plans
Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 1551-1556.
Abstract
Given a hierarchical plan (or schedule) with uncertain task times, we may need to determine the probability that a given plan will satisfy a given deadline. This problem is shown to be NP-hard for series-parallel hierarchies. We provide a polynomial-time approximation algorithm for it. Computing the expected makespan of an hierarchical plan is also shown to be NP-hard. We examine the approximation bounds empirically and demonstrate where our scheme is superior to sampling and to exact computation.
Liat Cohen, Solomon Eyal Shimony, and Gera Weiss. 2015. Estimating the Probability of Meeting a Deadline in Hierarchical Plans. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15. IJCAI, 1551–1556. https://ijcai.org/proceedings/2015/222
Cohen, L., Shimony, S. E., & Weiss, G. (2015). Estimating the Probability of Meeting a Deadline in Hierarchical Plans. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15 (pp. 1551–1556). IJCAI. https://ijcai.org/proceedings/2015/222
@inproceedings{ijcai2015p222,
title = {Estimating the Probability of Meeting a Deadline in Hierarchical Plans},
author = {Cohen, Liat and Shimony, Solomon Eyal and Weiss, Gera},
booktitle = {Proceedings of the Twenty-Fourth International Joint Conference on
Artificial Intelligence, {IJCAI-15}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Qiang Yang and Michael Wooldridge},
pages = {1551--1556},
year = {2015},
month = {7},
note = {Main Track},
url = {https://ijcai.org/proceedings/2015/222},
}
TY - CPAPER TI - Estimating the Probability of Meeting a Deadline in Hierarchical Plans AU - Cohen, Liat AU - Shimony, Solomon Eyal AU - Weiss, Gera T2 - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15 PB - International Joint Conferences on Artificial Intelligence PY - 2015 SP - 1551 EP - 1556 UR - https://ijcai.org/proceedings/2015/222 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
