Plan Modification versus Plan Generation: A Complexity-Theoretic Perspective
Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence. Planning. Pages 1436-1443.
Abstract
The ability of a planner to modify a plan is considered as a valuable tool for improving efficiency of planning by avoiding the repetition of the same planning effort. From a computational complexity point of view, however, it is by no means obvious that modifying a plan is computationally as easy as planning from scratch if the modification has to follow the principle of "conservatism," i.e., to reuse as much of the old plan as possible. Indeed, considering propositional STRIPS planning, it turns out that conservative plan modification is as hard as planning and can sometimes be harder than plan generation. Furthermore, this holds even if we consider modification problems where the old and the new goal specification are similar. We put these results into perspective and discuss the relationship to existing plan modification systems.
@inproceedings{ijcai1993p199,
title = {Plan Modification versus Plan Generation: A Complexity-Theoretic Perspective},
author = {Nebel, Bernhard and Koehler, Jana},
booktitle = {Proceedings of the Thirteenth International Joint Conference on
Artificial Intelligence, {IJCAI-93}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Ruzena Bajcsy},
pages = {1436--1443},
year = {1993},
note = {Planning},
url = {https://ijcai.org/proceedings/1993/199},
}
TY - CPAPER TI - Plan Modification versus Plan Generation: A Complexity-Theoretic Perspective AU - Nebel, Bernhard AU - Koehler, Jana T2 - Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence, IJCAI-93 PB - International Joint Conferences on Artificial Intelligence PY - 1993 SP - 1436 EP - 1443 UR - https://ijcai.org/proceedings/1993/199 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
