Proceedings of the AAAI Conference on Artificial Intelligence, 12
Formal Models of Reactive Control
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. 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.