Book review: Reasoning agents in a dynamic world: The frame problem. Kenneth M. Ford and Patrick J. Hayes, eds.,
Jozsef A. Toth · 1995
ion is typically realized in a representation either for the purposes of modeling in AI, or to explain a particular behavioral phenomenon in cognitive science. The frame problem is “the tip of the iceberg”, as it were, of certain scientific and methodological approaches in AI and cognitive science. The germinal issue, then, does not appear to entail whether the frame problem is solvable or not. Rather, it seems to pertain to whether a particular representational approach in AI or cognitive science will lead to the intractability which has been identified as the frame problem. The contributions of Nutter, Perlis and Stein, in particular, provide important insights to an argument of this kind, suggesting that the frame problem is really an unsolvable obstacle-much like the mathematical impossibility of dividing any number by zero or infinity. For the past two decades, the frame problem appears to have served as an ontological and epistemological “litmus test” for those who have cared to notice its significance, such as Chapman (1987, 1991), Agre & Chapman ( 1987) or Pollack & Ringuette (1990) have demonstrated in the domain of planning. I maintain that the narrow/broad distinction introduced by the editors, which is also discussed by some of the contributors, does not effectively capture the essence of the frame problem. Therefore, in the discussion (Section 3), I will assume a more expansive posture and examine in greater detail the methodological issues pertaining to the relationship between the reasoning agent and its environment. For the remainder of this Section however, I will introduce some of the fundamental intractabilities associated with certain modes of abstraction and representation that lead to the frame problem, in an attempt to set the stage for the survey of the book in Section 2 and the ensuing discussion in Section 3. 1.2. Machine cognitiorz and omniscience Certain assumptions of omniscience underlie most approaches to abstraction and representation in AI and cognitive science. Omniscience means that in order for a particular representation to work, the reasoning agent endowed with that representation must have complete knowledge of all objects and events in the world and complete knowledge of itself. This general assumption was inherent in McCarthy’s situation calculus, where describing the external world was accomplished by saying that a state &+I in the world results from an action A, in state S,,. 2 Characterized by McCarthy & Hayes, “A situation S is the complete state of the universe at one time” (1969, p. 33). The terms state and situation are more or less synonymous. Frame axioms were the first, albeit defunct, attempt at providing a solution to, or way around, the original frame problem discovered in the situation calculus. Frame axioms are logic expressions that maintain information about what properties do not change in the transition from one state to the ’ As a historical note, McCarthy’s earlier thinking which eventually led to the situation calculus had involved the requirement for “a kind of means-ends analysis used in ordinary life” ( 1963, p, 410). Likewise, relating to what would later come to be identified as the frame problem, “Causality logic should be extended to allow inference that certain propositional Ruents will always hold” ( 1963, p. 417). A juenf can be thought of as an attribute or property whose value can change or remain the same over time. J.A. Toth/Arti$cial Intelligence 73 (1995) 323-369 327 next as the result of an action. The following expression is an example of a frame axiom in a simple world involving blocks: If block x has a color c in situation S, and situation S,+r results from moving block x in S,, then block x will have the same color c in ,$,+I. (Morgenstern, p. 135) Simply put, a block in this pedagogical world does not change color as the result of being moved. In order for this frame axiom to work however, one kind of omniscient assumption that must be made is that nothing else can occur between states other than what is described by this frame axiom regarding the block’s color c. This omniscient assumption holds that, “all intervening events are known” (Haugh, p. 110). For example, if a five year old child, holding a full, quality-assured can of spray paint of a different color c’ were to come along between the states S,, and &+I, and paint the block x to the new color c’, the frame axiom described a moment ago would be rendered invalid. In turn, if other frame axioms were to depend on the validity of this frame axiom, the constancy of a particular color c, those would also become invalid. One can see how the reasoning agent could rapidly become confused if events in the world did not occur exactly as prescribed. A reasoning agent equipped with the situation calculus and frame axioms, or even with a more recent representation in AI or cognitive science, can only truly function with the assumption of omniscience. Other varieties of omniscience will be covered later in the survey of Haugh’s chapter in Section 2.3. In a sense omniscience is a fallacy since a biological or electromechanical reasoning agent cannot possibly be aware of everything that transpires around it. Nevertheless, omniscience mandates that the agent be aware of everything and that this awareness must be represented and maintained internally by the reasoning agent. Hence, in general, if any representation-related change in the world occurs, it must be acknowledged by the electromechanical agent; and, in turn, the corresponding internal representation that is maintained to describe the agent’s model of the world must also be updated to reflect this change. The agent cannot be made aware on a “need to know” basis. In the case of the simple scenario presented above, whenever block x in S,, is moved in the world, either by the reasoning agent or as the result of some other external cause, information about the block’s new state in S,+i must be propagated to the corresponding internal representation in the reasoning system, from #S, to #S,+r (the ‘#’ symbol denotes “in the mind of the agent”). The formalism of situation theory (Devlin, 1991; Barwise & Perry, 1983) effectively represents this principle of external-internal correspondence, as depicted in Fig. 1. Moreover, this new internal information must be exhaustively propagated, and verified, among all the other objects in the internal representation in order to curtail any potential conflicts and contradictions. For instance, two different blocks cannot occupy the same x, y, z location at the same time. This intricate practice of bookkeeping, in particular, has been one of the main thrusts of the nonmonotonic reasoning research community. In the review of Perlis’ and Goodwin & Trudel’s chapters, potential uses for the maintenance of co-existing, conflicting values of properties will be explicated. Even if the world of the electromechanical reasoning agent involves thousands or millions of objects, because of omniscience, each relevant external object, {~a,. . J,},