Estimating Reaction Plan Size

Abstract

The Shannon/Ginsberg circuit size estimate, by assuming independence of Boolean inputs, is not usable as a plan size estimate. By re-estimating circuit size as a function of the number of combinations w of Boolean inputs, I show that a reaction plan over w world states should grow as O(w/log w), on average. However, in a Blocks World containing N blocks and w ≈ NN world states, actual Universal Plans grow only as O(N3). This difference is shown to be attributable to the Universal Plans' use of dynamically bound object variables. Finally I obtain the general domain-independent result that for a domain containing w world states, the expected size of a reaction plan with variables is O((w/log w)1/log p(p+(b-1)v)) where p is the number of preconditions per operator, v is the number of those preconditions that introduce an unbound variable, and b is the number of possible bindings per variable. The exponent is ≤ 1 and allows this formula to predict plan size reductions of many orders of magnitude.