Jonsson, P. and Bäckström, C. (1996). On the Size of Reactive Plans. Technical Report LiTH-IDA-R-96-10, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
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 completeness becomes trivial.
CS Dept TR Overview