An Overview of the Frame Problem

In the confined world of a robot, surroundings are not static. Many varying forces or actions can cause changes or modifications to it. The problem of forcing a robot to adapt to these changes is the basis of the frame problem in artificial intelligence. Information in the knowledge base and the robot's conclusions combine to form the input for what the robot's subsequent action should be. A good selection from its facts can be made by discarding or ignoring irrelevant facts and ridding of results that could have negative side effects. (Dennett) (Fischler 304-5)

A robot must introduce facts that are relevant to a particular moment. That is, a robot will examine its current situation, and then look up the facts that will be beneficial to choosing its subsequent action. The robot should also search for any changeable facts. It then examines these facts to determine if any of them have been changed during a previous examination. There are two basic types of change:
  • Relevant Change: inspect the changes made by an action
  • Irrelevant Change: do not inspect facts that are not related to the task at hand

    Facts may be examined utilizing two levels:
    Semantic Level: This level interprets what kind of information is being examined. Solutions should become obvious by the assumptions of how an object should behave. There are believers in a purely semantic approach who believe that correct information can be reached via meaning. However, this hypothesis has yet to be proven.
    Syntactic Level: This level simply decides in which format the information should be inspected. That is, it forms solutions based on the structure and patterns of facts.
    (Boden)

    When inspecting the facts, various problems can occur:
  • Sometimes an implication can be missed.
  • Considering all facts and all their subsequent side effects is time-consuming.
  • Some facts are unnecessarily examined when they are unneeded.
    (Dennett)


    Problems Related to the Frame Problem

    The Qualification Problem

    The Qualification Problem was introduced by John McCarthy. It suggests that one is never completely positive if a specific rule will work. It also suggests that the robot does not necessarily know which rules to ignore in a given situation. Modifications in the environment can "confuse" the robot as certain rules will become obselete and new rules will be necessary before they exist.
    (Janlert) (Russell 207)

    The Representational Problem

    The Representational Problem is the difficulty of generating truths about the current environment. For example, how can one program the notions of up and down? These are relative to each other, and can not be simply described by direction. To partially rectify this problem, successor-state axioms are used. These axioms show all the true and false possibilities of a rule.
    (Russell 207)

    The Inferential Problem

    Difficulty with examining the methods by which the world is judged is the Inferential Problem. There are two kinds of purposes. The General Purpose is to inspect the entire world of things that are changeable. The Special Purpose is to only inspect actions that can modify over a small area of surroundings.
    (Russell 207)

    The Ramification Problem

    This problem describes how an action can cause deviations within its environment. For example, a robotic arm has been given the task of picking up a brick and placing it on its side in a different location. If the brick has been knocked over, what can the robot do to rectify the problem? Will it still know which side should be facing up without the ability of human sight? Should these deviations be examined individually each time an action has taken place?
    (Russell 207)

    The Predictive Problem

    The Predictive Problem deals with the benefits of predictions. That is, it is uncertain if a given prediction will cause a positive change in the environment. If the change will not be positive, "either the laws or description of the given situation must be imperfect (Janlert 9)."


    Approaches to a Frame Problem Solution

    The Non-Deductive Approach

    This approach deals with making decisions that imitate human thought processes. However, the task of programming human cognition has yet to be successful.
    (Janlert)

    The Deductive Approach

    This approach differs from the Non-Deductive Approach because it is free from psychological views. All Knowledge can be expressed as axioms and use predicate calculus to arrive at conclusions where:
  • S describes the task to be performed.
  • A describes all actions in an environment. This is the frame part of the problem.
  • Action A occurs and provides a conclusion for what A does in S.
    This will only work in simple instances.

    Problems:
  • There is an action that is not defined in A leading to an inaccurate conclusion.
  • There is an argument that humans do not think in this fashion (comparing A to S and if human behavior can be mimicked.
    (Janlert)

    Frames & Scripts Approch (Minsky & Schank)

    Minsky and Schank's Frames approach deals with separating the world into individual categories and aspects. Minsky suggests implementing the scenarios in frames, while Schank suggests implementing them in scripts. If a robot uses frames or scripts, then habits can be formed regarding specific situations where it deducts how it should react.

    Problems:
  • It is hard to recover from a mistake.
  • The robot could get stuck in a block that might not apply to all situations.
  • It is uncertain how large each category should be.

    Develop Experience Approach (Hume)

    This approach deals with the idea of "look before you leap." By planning the subsequent move based on assumption, the result produced could be used to increase the knowledge base. "Look before you leap" is used to form habits. This is a way for the robot to develop experience and in a sense learn from its mistakes.

    Problem:
    The one problem with this approach is how the habits can be represented in the knowledge base, since a rule could branch into many different paths or lead into the same ones.

    Ad Hoc

    The Ad Hoc certainty factor approach simply introduces probabilities in making a deciscion. Using Ad Hoc certainty factors, the probability of success can be predicted and may eliminate bad decisions.

    Problem:
    Certainty factors themselves are a problem because they are relative to each other and often derived from opinion. That is, one person's view of 60% may equal another person's view of 70%.

    Rethink the Semantic Level (Patrick Hayes)

    This approach simply suggests to draw conclusions about the kinds of information to look at based on "histories and processes (Dennett)."

    Android Epistemology (Clark Glymour)

    Introduced by Clark Glymour, based on an idea by Daneiel C. Dennett, android epistemology is the idea of combining philosophy and artificial intelligence.
    Problems:
  • Why should this be used for something that is obvious?
  • It is still a mystery if a robot can think like a human. If it can't, how can it think philosophically?
  • If a robot could think like a human, it could make wrong decisions as well.

    Circumscpription Approach (McCarthy)

    The Circumscription Approach involves "jumping" to appropriate conclusions. The system should not look for things which have previously been proven by another rule. Heuristics are used in this method.

    Problem:
    The problem with this approach is the question of exactly when this method should be executed in the inspections.

    Causal Connection Approach (Patrick Hayes)

    This approach suggests liking objects in the world by their similar properties. Then, if an object is changed and is causally connected to another, one is to check the other's properties too. This allows exceptions and new connections to be formulated.
    Problems:
  • What determines if something is causally connected?
  • If an object changes, and it is causally connected to another, all properties of the connected one may require verification.
    (Janlert)

    STRIPS (Fikes & Nilsson)

    The STRIPS approach utilizes both the deductive and non-deductive approaches. Essentially, a robot will inspect its environment viewing everything deductively, and then it will inspect between the changed environment non-deductively, which is necessary in planning. It utilizes the notion that "all that is not explicitly changed by an action remains unchanged (Janlert)." It is theorized that this approach, while not successful in solving the frame problem, is the best known solution available.
    (Janlert)


    This web page, entitled "The Frame Problem in Artificial Intelligence" was implemented and written by Jim Raredon and Melinda Blais. All sources have been given due credit via the References page and the numerous citations within this document.
    Created June 28th, 1998