CogSci Summaries home |
P. Hayes, The Frame Problem and Related Problems in AI.
Artificial and Human Thinking, A. Elithorn and D. Jones (eds.),
author = "Pat Hayes",
title = "The frame problem and related problems in artificial
booktitle = "Artificial and Human Thinking",
publisher = "Jossey-Bass, Inc. and Elsevier Scientific Publishing
year = "1973",
editor = "A. Elithorn and D. Jones",
pages = "45--59",
Author of the summary: David Furcy, 1999, email@example.com
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.
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
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
Summary author's notes:
Back to the Cognitive Science Summaries homepage
Cognitive Science Summaries Webmaster:
Last modified: Mon Aug 30 08:32:58 EDT 1999