On the Size of Reactive Plans

Abstract

One of the most widespread approaches to reactive planning is Schoppers' universal plans. We propose a stricter definition of universal plans which guarantees a weak notion of soundness not present in the original definition. Furthermore, we isolate three different types of completeness which capture different behaviours exhibited by universal plans. We show that universal plans which run in polynomial time and are of polynomial size cannot satisfy even the weakest type of completeness unless the polynomial hierarchy collapses. However, by relaxing either the polynomial time or the polynomial space requirement, the construction of universal plans satisfying the strongest type of completeness becomes trivial. Introduction In recent years reactive planning has been proposed as an alternative to classical planning, especially in rapidly changing, dynamic domains. Although this term has been used for a number of more or less related approaches, these have one thing in common: There is usu...