@TECHREPORT{R-96-10, PSURL = {/publications/cgi-bin/tr-
fetch.pl?r-96-10+ps}, NUMBER = {R-96-10}, INSTITUTION = ida,
ADDRESS = idaaddr, YEAR = {1996}, AUTHOR = {Jonsson, Peter and
B{\"a}ckstr{\"o}m, Christer}, TITLE = {On the Size of Reactive
Plans}, ABSTRACTURL = {/publications/cgi-bin/tr-
fetch.pl?r-96-10+abstr}, ABSTRACT = {One of the most wide-spread
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 complete