Frame problem

In artificial intelligence, the framework problem or frame problem refers to a problem in the logical representation of the effects of actions. In certain logic calculi (such as the situation calculus ) it is not sufficient to merely describe the effects of actions whose truth values change. A complete, explicit description of all the effects of actions on all facts valid in a world (ie not just “what changes” but also “what remains the same”) would be too time-consuming. The framework problem thus deals with the question of how a logic calculus can be complete without explicitly describing trivial non-changes.

A number of similar problems are referred to as frame problems. In addition to the solved representative and inferential framework problems, there is the qualification problem that does not have a complete solution.

The name frame problem relates 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 the reference system.

Problems

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

Representative framework problem

The representative framework problem describes the difficulty of representing action effects with less effort than . The following example illustrates the problem. ${\ displaystyle {\ mathcal {O}} (A * F)}$

The initial status “Agent a is in the house for the situation and has no hat on” is represented as follows:, as well as . The following situations are and . So the agent puts on his hat and leaves the house. ${\ displaystyle s_ {0}}$ ${\ displaystyle location (a, ImHaus, s_ {0})}$ ${\ displaystyle \ lnot HutAuf (a, s_ {0})}$ ${\ displaystyle s_ {1} = Result (Put on your hat, s_ {0})}$ ${\ displaystyle s_ {2} = Result (HausVer Lassen, s_ {1})}$

There are the following axioms of ${\ displaystyle \ Rightarrow}$ possible possibilities: Place (a, ImHaus, s) Poss (HausVerbaren, s) and HutAuf (a, s) Poss (HutTo place, s) . There are also the effect axioms: Poss (HausVerbaren, s) Ort (a, ImHaus, Result (HausVer Lassen, s)) as well as Poss (Hut Auf Auf, s) HutAuf (a, Result (Hut Aufützen, s)) . ${\ displaystyle \ lnot}$ ${\ displaystyle \ Rightarrow}$ ${\ displaystyle \ Rightarrow \ lnot}$ ${\ displaystyle \ Rightarrow}$

These can now be used to show that the agent is in the hat. The seemingly trivial statement that this also applies to cannot be derived without further ado. Because it was not specified that leaving the house does not change the Fluent Hut Auf . ${\ displaystyle s_ {1}}$ ${\ displaystyle s_ {2}}$

One possible solution would be to introduce frame axioms. Frame axioms are rules that a non-change explicitly specify in this case . However, since there are F fluents and thus frame axioms for each of the A actions, the representation effort adds up . ${\ displaystyle HatOn (a, s) \ Rightarrow HatOn (a, (Result (HouseLeave, s))}$ ${\ displaystyle {\ mathcal {O}} (A * F)}$

A representation in is much more efficient , since the number of maximum effects of an action is usually much less than the number of fluents. ${\ displaystyle {\ mathcal {O}} (A * E)}$

solution

There are numerous solutions to the representative framework problem, for example through the event calculus or the fluent calculus . In the following, the solution is described by successor state axioms.

A succession state axiom is of the form:

Action is possible ( Fluent is true Action Effect made Fluent true Fluent was true and Action Effect did not modify it ). ${\ displaystyle \ Rightarrow}$ ${\ displaystyle \ Leftrightarrow}$ ${\ displaystyle \ vee}$

The following succession state axiom describes the conditions for the truth and falsehood of the fluent hats . There is one action that makes Hat Auf true and two that make Hat Auf false:

Poss (action, s) (hat on (a, Result (action, s)) action = hat on (hat on (a, s) action hat set off action hat lose)) ${\ displaystyle \ Rightarrow}$ ${\ displaystyle \ Leftrightarrow}$ ${\ displaystyle \ vee}$ ${\ displaystyle \ wedge}$ ${\ displaystyle \ neq}$ ${\ displaystyle \ wedge}$ ${\ displaystyle \ neq}$ .

This shows that HutAuf (a, Result (action, )) ${\ displaystyle s_ {2}}$ holds, since the conjunction in the last part of the formula is fulfilled.

Actions whose effects make a fluent true are listed in the corresponding axiom of the fluent under Action-Effect made fluent true ; Effects that do a fluent wrong, under Action Effect it has not modified [the fluent] . For every fluent there is a succession state axiom. In all succession-state axioms together, all effects of all actions are named exactly once, so the representation effort is in . Thus, succession state axioms in the situation calculus are a solution for the representative framework problem. ${\ displaystyle E}$ ${\ displaystyle A}$ ${\ displaystyle {\ mathcal {O}} (A * E)}$

Inferential framework problem

The inferential framework problem describes the difficulty of efficiently calculating the situation that results from a sequence of t actions. If the effort for the representation of a time step is, then according to a naive approach the effort for t time steps would be . In fact, it can only be calculated. The number of actions A possible at all has no influence on the effort, since only the actions actually carried out in the sequence have to be taken into account. ${\ displaystyle s_ {t}}$ ${\ displaystyle {\ mathcal {O}} (A * E)}$ ${\ displaystyle {\ mathcal {O}} (A * E * t)}$ ${\ displaystyle s_ {t}}$ ${\ displaystyle {\ mathcal {O}} (E * t)}$

The solution to the inferential framework problem is to just save the changes to the fluents, instead of copying and then adapting the complete representation for each time step. With the help of indices it is possible to access successor state axioms and action effects in constant time. Since at each time step, only a maximum of E effects must be (both in constant time) looked up in the axioms and up to E must be adjusted (also in constant time) Fluents, the effort is for a time step in , in t steps so at . ${\ displaystyle {\ mathcal {O}} (E)}$ ${\ displaystyle {\ mathcal {O}} (E * t)}$

Qualification problem

The qualification problem describes the not completely solved problem of specifying all requirements for an action. The completeness of axioms of possibility cannot be shown.

For example, in addition to the axiom of possibility hat on (a, s) Poss (hat on, s), the additional conditions hat is palpable , hat fits on head and others could prove to be necessary. ${\ displaystyle \ lnot}$ ${\ displaystyle \ Rightarrow}$

Framework problem in philosophy

The framework problem in the philosophical context is the epistemological question of how an agent determines the amount of knowledge that has to be checked again for truth after an action. When reassessing, humans limit themselves to findings that are relevant to the action . However, it is unclear how the assessment of relevance works.

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

Sources and Notes

Peter Norvig , Stuart Russell : Artificial Intelligence: A Modern Approach . 2nd Edition. Prentice Hall, 2004, ISBN 978-3-8273-7089-1 (English: Artificial Intelligence: A Modern Approach .).

Remarks:

↑ An agent is what acts or acts, i.e. a person, animal or a computer agent .

↑ Poss stands for Possible , i.e. the possibility of an action in a situation s .

Web links

Murray Shanahan: Frame problem. In: Edward N. Zalta (Ed.): Stanford Encyclopedia of Philosophy .

[1] An agent is what acts or acts, i.e. a person, animal or a computer agent .

[2] Poss stands for Possible , i.e. the possibility of an action in a situation s .