25 A Logic of Actions P. Hayes

THE FRAME PROBLEM One of the central principles upon which intelligent devices seem to operate is that of maintaining internal models of their external environments. In artificial systems which have been constructed to date various representations for this internal model have been used; but in every nontrivial case the need arises to consider the effect, upon the structure of the model, of the performance by the system of actions in the external world, so that their potential consequences may be reckoned. How difficult this is, depends upon both the complexity of the model and its method of representation. In particular, it is usually easy when the problem is posed in the classical heuristic search paradigm, and the data structures used to represent static configurations of the puzzle are relatively unproblematic (arrays, lists, and so on). For in this case [see, for instance, Manna (1970) and Pikes (1970) for examples] one can use the ordinary device of assignment to model the changes in the world.which The lack of side-effects reflects the simplicity of the physics which such models embody. This limitation to elementary forms of interaction is not, of course, intrinsic to the heuristic search method; but when more complex models are constructed it becomes less trivial to pursue the consequences of performing an action. The use of assignment to portray the doing of actions does seem to presuppose a trivial physics. Another method of constructing microcosms is to use a logical language to describe the real world (McCarthy 1959, McCarthy and Hayes 1969). This approach is more general than the heuristic search method (but the latter -- when it has sufficient expressive power -- wins at present by its computational advantage). The key idea is to use expressions denoting situations to separate out assertions according to which (static) state of the world they purport to describe. Assertions mentioning several different situations can then be used to describe dynamical laws which move us from one situation to another. But in some ways the resulting sharp separations between states of affairs are an embarrassment. For if we distinguish two situations s1 and s2, then from the fact, if such it be, that a predicate p is true of Si, nothing whatever follows concerning s2. And this is true even when s2 is directly associated with sl. Say s2 results from s1 by the performance of some action: s2 do (a, si) then no matter how remote -- speaking intuitively -- the connection between the property p and the action a, it still does not follow that p is true of s2. If we want it to so follow we must state this explicitly. Now, unfortunately, there are innumerable facts which might remain unchanged when actions are performed. So instead of writing a law of motion' in the form A(s) B(do(a, s)) where A and B are fairly short expressions, we are apparently obliged to list systematically all conceivable facts which are not changed.