Generating Optimal Plans in Highly-Dynamic Domains

Christian Fritz, Sheila McIlraith
Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, PMLR R7:177-184, 2009.

Abstract

Generating optimal plans in highly dynamic environments is challenging. Plans are predicated on an assumed initial state, but this state can change unexpectedly during plan generation, potentially invalidating the planning effort. In this paper we make three contributions: (1) We propose a novel algorithm for generating optimal plans in settings where frequent, unexpected events interfere with planning. It is able to quickly distinguish relevant from irrelevant state changes, and to update the existing planning search tree if necessary. (2) We argue for a new criterion for evaluating plan adaptation techniques: the relative running time compared to the "size" of changes. This is significant since during recovery more changes may occur that need to be recovered from subsequently, and in order for this process of repeated recovery to terminate, recovery time has to converge. (3) We show empirically that our approach can converge and find optimal plans in environments that would ordinarily defy planning due to their high dynamics.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR7-fritz09a, title = {Generating Optimal Plans in Highly-Dynamic Domains}, author = {Fritz, Christian and McIlraith, Sheila}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {177--184}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/fritz09a/fritz09a.pdf}, url = {https://proceedings.mlr.press/r7/fritz09a.html}, abstract = {Generating optimal plans in highly dynamic environments is challenging. Plans are predicated on an assumed initial state, but this state can change unexpectedly during plan generation, potentially invalidating the planning effort. In this paper we make three contributions: (1) We propose a novel algorithm for generating optimal plans in settings where frequent, unexpected events interfere with planning. It is able to quickly distinguish relevant from irrelevant state changes, and to update the existing planning search tree if necessary. (2) We argue for a new criterion for evaluating plan adaptation techniques: the relative running time compared to the "size" of changes. This is significant since during recovery more changes may occur that need to be recovered from subsequently, and in order for this process of repeated recovery to terminate, recovery time has to converge. (3) We show empirically that our approach can converge and find optimal plans in environments that would ordinarily defy planning due to their high dynamics.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Generating Optimal Plans in Highly-Dynamic Domains %A Christian Fritz %A Sheila McIlraith %B Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2009 %E Jeff Bilmes %E Andrew Y. Ng %F pmlr-vR7-fritz09a %I PMLR %P 177--184 %U https://proceedings.mlr.press/r7/fritz09a.html %V R7 %X Generating optimal plans in highly dynamic environments is challenging. Plans are predicated on an assumed initial state, but this state can change unexpectedly during plan generation, potentially invalidating the planning effort. In this paper we make three contributions: (1) We propose a novel algorithm for generating optimal plans in settings where frequent, unexpected events interfere with planning. It is able to quickly distinguish relevant from irrelevant state changes, and to update the existing planning search tree if necessary. (2) We argue for a new criterion for evaluating plan adaptation techniques: the relative running time compared to the "size" of changes. This is significant since during recovery more changes may occur that need to be recovered from subsequently, and in order for this process of repeated recovery to terminate, recovery time has to converge. (3) We show empirically that our approach can converge and find optimal plans in environments that would ordinarily defy planning due to their high dynamics. %Z Reissued by PMLR on 04 October 2026.
APA
Fritz, C. & McIlraith, S.. (2009). Generating Optimal Plans in Highly-Dynamic Domains. Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R7:177-184 Available from https://proceedings.mlr.press/r7/fritz09a.html. Reissued by PMLR on 04 October 2026.

Related Material