Frame problem

The problem frame or frame problem referred to in the artificial intelligence is a problem in the logical representation of the effects of actions. In certain logic calculi (such as the situation calculus ) it is not sufficient merely to describe the effects of actions whose truth values ​​change. A complete, explicit description of all effects of actions at all applicable in a world of facts (ie, not only of "what changes " but also "what remains the same " ) would be too costly. The frame problem therefore deals with the question of how a logical calculus can be complete without describing non -trivial changes explicitly.

As a framework issues a series of similar problems are referred. In addition to the dissolved representational and inferential frame problems there is the qualification problem, which has not a complete solution.

The name of the context problem is related to the reference system ( English: Frame of reference) in physics. The frame problem is to capture not only the changing objects, but also the static frame of reference system.

Problems

Many logic calculi are used for the representation of knowledge that are based on predicate logic. So-called fluents are predicates that can have from one situation to a different truth value ( ie are not static ). In the following, it is assumed from the situation calculus. In this case, A is the number of different actions, F is the number of Fluent's and E is the maximum number of effects, which has an action.

Elles representation framework Problem

The representation elle frame problem refers to the difficulty of the representation of action effects with less effort than. The following example illustrates the problem.

The initial status "Agent a is the situation in the house and has no hat on ," [A 1] is represented as follows: , and. The following situations are and. The agent is thus made up his hat and leaves the house.

There are the following possible axioms: [A 2] place ( a, ImHaus, s) Poss ( home leave, s) and HutAuf ( a, s) Poss ( HutAufsetzen, s). There is also the effect axioms: Poss ( home leave, s) place ( a, ImHaus, Result ( home leave, s) ) and Poss ( HutAufsetzen, s) HutAuf (a, Result ( HutAufsetzen, s) ).

These can now show that the agent has in the hat on. The trivial published statement that this also applies to, can not be derived easily. Because it was not specified that leaving the house the Fluent HutAuf not change.

One possible solution would be the introduction of frame axioms. Frame axioms are rules that explicitly specify a non- change, in this case. However, as there are for each of the actions A F fluents and thus frame axioms, the Repräsentationssaufwand amounts to.

Much more efficient is a representation in, since the number of the maximum effects of an action usually is much smaller than the number of Fluent's.

Solution

For the representation elle frame problem there are many solutions, such as the Event Calculus or Fluentkalkül. In the following, the solution is described by the successor state axioms.

A successor state axiom is of the form:

Action is possible ( Fluent is true action - effect has made ​​true Fluent Fluent was true and action effect it has not modified).

The following successor state axiom describes the conditions for the truth and falsity of the fluents HutAuf. There is an action that makes true as HutAuf effect and two that make HutAuf wrong:

Poss ( action, s) ( HutAuf (a, Result ( action, s) ) action = HutAufsetzen ( HutAuf ( a, s) action HutAbsetzen action HutVerlieren ) ).

Thus, it can be shown that HutAuf (a, Result ( action, ) ) is true because the conjunction is satisfied in the last part of the formula.

Actions whose effects make a Fluent true, are in the corresponding axiom of fluents under action effect Fluent has listed made ​​true; Effects that make a Fluent wrong, under action effect it [ the Fluent ] not modified. For each fluent, there is a successor state axiom. In all the successor -state axioms together all the effects of all actions are called exactly once, so the promotional expenses is. Thus successor -state axioms are a solution to the problem in the framework of representation elle situation calculus.

Inferentielles frame problem

The inferential frame problem refers to the difficulty of calculating the situation efficiently, which results from a sequence of t actions. If the cost of the representation of a time step is, then, according to a naive approach of expenditure for t time steps would be at. In fact, it may be calculated in only. The number of all possible actions A has no influence on the effort, because only the actually performed in the sequence actions need to be taken into account.

The solution to the inferential frame problem is merely to save the changes to the fluents instead of copying the complete representation for each time step and then adapt. Using this index, it is possible in constant time access to successor state axioms and action effects. Since at each time step only a maximum of E effects (both in constant time ) need to be viewed in the axioms and up to E fluents ( also in constant time ) need to be adjusted, the cost of a time step that is located at, at, at t steps.

Qualification problem

The qualification problem refers to the not completely solved problem to specify all the conditions for an action. The completeness of opportunity axioms can not be shown.

For example, could be to the above opportunity Axiom HutAuf ( a, s) Poss ( HutAufsetzen, s) prove the additional conditions HutIstGreifbar, HutPasstAufKopf and more than necessary.

Frame problem in philosophy

The frame problem in the philosophical context is the epistemological question of how an agent determines the amount of knowledge that must be re-examined after an action on their veracity. Man is limited in the revaluation on relatively relevant to the plot findings. It is unclear, however, how the assessment of the relevance expires.

The philosophical framework problem developed from the artificial intelligence and was first formulated in 1978 by Daniel Dennett.

Sources and notes

• Peter Norvig, Stuart Russell: Artificial Intelligence: A modern approach. 2 edition. Prentice Hall, 2004 ( Original title: Artificial Intelligence: A Modern Approach ), ISBN 9,783,827,370,891th

Notes: