[ CogSci Summaries home | UP | email ]
http://www.jimdavies.org/summaries/

P. Hayes, The Frame Problem and Related Problems in AI. Artificial and Human Thinking, A. Elithorn and D. Jones (eds.), Jossey-Bass, 1973.

@InCollection{Hayes73,
  author =       "Pat Hayes",
  title =        "The frame problem and related problems in artificial
                 intelligence",
  booktitle =    "Artificial and Human Thinking",
  publisher =    "Jossey-Bass, Inc. and Elsevier Scientific Publishing
                 Company",
  year =         "1973",
  editor =       "A. Elithorn and D. Jones",
  pages =        "45--59",
}

Author of the summary: David Furcy, 1999, dfurcy@cc.gatech.edu

Cite this paper for:

System: MICRO-PLANNER, STRIPS (analyzed/reformulated)
Frame problem solved by frame rules instead of frame axioms.
Qualification problem.
Maintaining consistent belief states while making observations requires being able to retract previously drawn conclusions.

Summary

This paper deals with the representation of knowledge about a world that evolves over time, through actions. For an intelligent agent to interact with a dynamic world means to be able to maintain beliefs about time (e.g., causality) as well as beliefs about changing states of the world.

Traditionally, the representation of an evolving world has involved the representation (in first-order logic) of events (or actions) whose effects are explicitly stated. The frame problem refers to the difficulty of representing what is not changed by an event. For example, in the situation calculus framework (a first-order language), if block A is on B in situation (or timestamp) s and the action "move block C to block D" is executed in s, it is impossible to logically deduce that block A is still on B in the situation s' resulting from the action execution if the action description only specifies what parts of the world the action actually changes.

An obvious solution to the frame problem is to add special axioms to the domain representation, called frame axioms that explicitly list what is not changed by each action. Clearly, in complex domains, the list of frame axioms quickly becomes intractably large. In this paper, Hayes proposes to replace specific (and numerous) frame axioms by more general and more systematic frame rules which he claims can be implemented very efficiently. He then proceeds with the reformulation of some existing systems (namely STRIPS and MICRO-PLANNER) using frame rules.

The main difficulty with this approach is that adding new inference rules (to, e.g., modus ponens or resolution) may cause the logic to become inconsistent, which is hard to test for since consistency is not decidable (unless the expressive power of the language is reduced). In conclusion, Hayes claims that a solution to the frame problem will have to use frame rules plus some method(s) to enforce consistency.

Finally, this paper deals with the related problem of maintaining a consistent set of beliefs for the agent in the presence of incoming observations about the external world. Hayes is really talking about non-monotonic extensions to logic but he never uses the term. Instead, he talks about violating the "extension" (i.e. monotonicity) property. Taking observations into account implies not only having beliefs about time but also having the belief state of the agent evolve over time due to direct interaction with the world through observations. This means that new beliefs can be introduced from without (as opposed to from within through logical therefore consistent deductions) and lead to inconsistencies and the need to retract previous beliefs and inferences. And with the possibility of future observations contradicting the agent's current knowledge, the qualification problem arises, namely what preconditions must be stated in the description of an action so that its expected effects are guaranteed to result from its execution. The only way to ensure that all inferences remain consistent with the state of the world would be that the conditions for the applicability of all actions are stated exhaustively, leading to intractable descriptions. Alternatively, keeping preconditions reasonable requires being able to retract previously drawn conclusions upon receiving new information through observations.

Summary author's notes:

none

Back to the Cognitive Science Summaries homepage
Cognitive Science Summaries Webmaster:

JimDavies ( jim@jimdavies.org )

Last modified: Mon Aug 30 08:32:58 EDT 1999