29
Frame Problem in Artificial Intelligence PATRICK J. HAYES By, Vinodkumar Gangal Roll No-130913020

AI frame prob

Embed Size (px)

Citation preview

Page 1: AI frame prob

Frame Problem in Artificial Intelligence

PATRICK J. HAYES

By, Vinodkumar GangalRoll No-130913020

Page 2: AI frame prob

Overview Introduction Time & Change Frame Axioms Effects of actions Frame Problem

Qualification problem Ramification problem.

Some Partial Solutions Using Frame Rules. Frames Casual Connection StripsConclusionReferences05/03/23 2/29

Page 3: AI frame prob

Introduction A robot is an intelligent system equipped with sensory

capabilities, operating in an environment similar to the everyday world inhabited by human robots.

Belief is meant any piece of information which is explicitly stored in the robot's memory.

New beliefs are formed by (at least) two distinct processes: thinking and observation.

Thinking: involves operations which are purely internal to the belief system.

Observation: involves interacting with the world, that is, the external environment and, possibly, other aspects of the robot's own structure.

05/03/23 3/29

Page 4: AI frame prob

Time and Change For him to think about the real world, the robot's beliefs

must handle time. This has two distinct but related aspects.

(a) There must be beliefs about time. For example, beliefs about causality.

(b) The robot lives in time: the world changes about him.

The first is solely concerned with thinking: the second involves observation

R(e,s)

05/03/23 4/29

Page 5: AI frame prob

Effects of actions An action performed in a given situation results in a new

situation. The function Result(action, situation) is used to denote the

situation which results from performing the action action in the situation situation.

actions are specified in terms of their preconditions and postconditions(effects)

for example, the action of picking up or dropping a block in the blocks V x V s(clear(x) → holding(x, Result(pickup, s)))V x V s( ~holding(x, Result(drop, s)))

05/03/23 5/29

Page 6: AI frame prob

Frame Axioms Effect axioms are not sufficient to keep track of whether

the agent is holding a block

V a V x V s( holding(x, s) & (a ≠ drop) → holding(x, Result(a, s)))

V a V x V s( ~holding(x, s) & (a ≠ pickup) → ~holding(x, Result(a, s)))

axioms which describe which parts of the world are not changed by an action are called frame axioms.

05/03/23 6/29

Page 7: AI frame prob

The Frame problem Representational frame problem. The inferential frame problem refers to the need to

reason explicitly about things that don’t change.

when reasoning about sequences of actions, each property must be (re)derived for each new situation, even if the property hasn’t changed.

since each action usually changes only a few facts about a situation, this is very inefficient.

05/03/23 7/29

Page 8: AI frame prob

The qualification problem in general, it is difficult to specify precisely the situations

in which an action will have the specified (intended) effect.

For example, it may not be possible to perform a pickup action if the block is slippery or glued to the table.

if these “side conditions” are left out of the effect and frame axioms, we may derive false beliefs about the consequences of executing an action.

how to qualify the “normal” effects of an action in “abnormal” circumstances is the qualification problem.

05/03/23 8/29

Page 9: AI frame prob

The ramification problem In addition to the explicit consequences specified in their

definition, actions also have implicit consequences For example, picking up a box also picks up all the objects in

the box (if any), and if I take the box somewhere, I also take its contents etc.

the ramification problem can be seen as the derivation of the ultimate effects of an action.

may involve additional simple inferences (if the box is in the living room, then all the objects in the box are in the living room), reasoning about cause and effect (naive physics) and other kinds of consequences.

hard to know when to stop …05/03/23 9/29

Page 10: AI frame prob

The Frame Problem How to identify effectively which data are relevant in solving a

problem (without first solving the problem)?

Is relevant in the solution? find a solution with

No time to try all data!

• Make educated guesses (e.g. heuristics)• Abstract data (how?)

05/03/23 10/29

Page 11: AI frame prob

The Frame Problem Frame problem

Can we let relevance emerge through interplay between problem concepts and specific data?• relevant concepts shapes the abstraction of data • specific data adapts relevance of concepts

French flagblue, white, red

circle, trapezoid

rectangle

05/03/23 11/29

Page 12: AI frame prob

The Frame Problem The “frame problem”: assumes – that perception was

always accurate.

The problem of deciding what parts of the internal model to update when a change is made to the model or the external world.

05/03/23 12/29

Page 13: AI frame prob

The Frame Problem A problem of determining which elements of a description

are consequentially altered after an event occurs. Named after cartoon animation in which a frame of

elements - chairs, walls, etc. - is kept static while the subjects of attention move around it. Which graphic elements can remain in the frame and which must be redrawn per cel?

Child brick ex: Child knows that other bricks will stay put.

05/03/23 13/29

Page 14: AI frame prob

Some Partial Solutions Using Frame Rules Frames

- a finite number of monadic second-order predicates P,. If Pi(h) for a non-logical symbol h then we say that h is in the ith block of the frame.

The frame rule iswhere h1…hn, are all the non logical symbols which occur crucially in

05/03/23 14/29

Page 15: AI frame prob

Some Partial Solutions Using Frame Rules Casual Connection:

- that there is a 3-place predicate ->(x,y,S) which has the intuitive meaning that if x is not connected to y, then any change to y does not affect x. - It seems reasonable that -> should be a partial ordering on its first two arguments (reflexive and transitive).

Strips

05/03/23 15/29

Page 16: AI frame prob

STRIPS

•Stanford Research Institute Problem Solver (1970s)•Planning system for a robotics project.

•Knowledge Representation : First Order Logic.

•Algorithm : Forward chaining on rules.

•Any search procedure : Finds a path from start to goal.•Forward Chaining : Data-driven inferencing.•Backward Chaining : Goal-driven

05/03/23 16/29

Page 17: AI frame prob

Forward & Backward Chaining•Rule : man(x) mortal(x)•Data : man(Shakespeare)

To prove : mortal(Shakespeare)

•Forward Chaining:man(Shakespeare) matches LHS of Rule.X = Shakespeare mortal( Shakespeare) added

-Forward Chaining used by design expert systems

•Backward Chaining: uses RHS matching- Used by diagnostic expert systems

05/03/23 17/29

Page 18: AI frame prob

Example : Blocks World•STRIPS : A planning system – Has rules with precondition deletion list and addition list

AC

A

CBB

START GOAL

Robot hand

Robot hand

Sequence of actions : 1. Grab C2. Pickup C3. Place on table C4. Grab B5. Pickup B

6. Stack B on C7. Grab A8. Pickup A9. Stack A on B

05/03/23 18/29

Page 19: AI frame prob

Example : Blocks World•Fundamental Problem :The frame problem in AI is concerned with the question of what piece of knowledge is relevant to the situation.

•Fundamental Assumption : Closed world assumptionIf something is not asserted in the knowledge base, it is assumed to be false.

(Also called “Negation by failure”)

05/03/23 19/29

Page 20: AI frame prob

Example : Blocks World•STRIPS : A planning system – Has rules with precondition deletion list and addition list

on(B, table)on(A, table) on(C, A)hand emptyclear(C)clear(B)

on(C, table)on(B, C) on(A, B)hand emptyclear(A)

AC

A

CBB

START GOAL

Robot hand

Robot hand

05/03/23 20/29

Page 21: AI frame prob

Rules•R1 : pickup(x)

Precondition & Deletion List : hand empty, on(x,table), clear(x)

Add List : holding(x)

•R2 : putdown(x)Precondition & Deletion List : holding(x)Add List : hand empty, on(x,table), clear(x)

05/03/23 21/29

Page 22: AI frame prob

Rules•R3 : stack(x,y)

Precondition & Deletion List :holding(x), clear(y) Add List : on(x,y), clear(x)

•R4 : unstack(x,y)Precondition & Deletion List : on(x,y), clear(x)Add List : holding(x), clear(y)

05/03/23 22/29

Page 23: AI frame prob

Plan for the block world problem

• For the given problem, Start Goal can be achieved by the following sequence :1. Unstack(C,A)2. Putdown(C)3. Pickup(B)4. Stack(B,C)5. Pickup(A)6. Stack(A,B)

• Execution of a plan: achieved through a data structure called Triangular Table.

05/03/23 23/29

Page 24: AI frame prob

Triangular Table

holding(C)

unstack(C,A)

putdown(C)

hand emptyon(B,table) pickup(B)

clear(C) holding(B) stack(B,C)

on(A,table) clear(A) hand empty pickup(A)

clear(B) holding(A) stack(A,B)

on(C,table) on(B,C) on(A,B)clear(A)

clear(C)on(C,A)

hand empty

0 1 2 3 4 5 6

1

2

3

4

5

6

7

05/03/23 24/29

Page 25: AI frame prob

Triangular Table

• For n operations in the plan, there are :• (n+1) rows : 1 n+1• (n+1) columns : 0 n

• At the end of the ith row, place the ith component of the plan. • The row entries for the ith step contain the pre-conditions for the

ith operation.• The column entries for the jth column contain the add list for the

rule on the top.• The <i,j> th cell (where 1 ≤ i ≤ n+1 and 0≤ j ≤ n) contain the pre-

conditions for the ith operation that are added by the jth operation.• The first column indicates the starting state and the last row

indicates the goal state.

05/03/23 25/29

Page 26: AI frame prob

Search in case of planning

Ex: Blocks world

Triangular table leads to some amount of fault-tolerance in the robot

Start

S1 S2

Pickup(B) Unstack(C,A)

AC

BSTART

A CBAC B

WRONG

MOVE

NOT ALLOWED

05/03/23 26/29

Page 27: AI frame prob

Conclusion In the long run, frame rules will be required

for non-trivial problems, corresponding respectively to the "strategic" and "tactical" aspects of computing descriptions of new situations.

One outstanding defect of present approaches is the lack of a clear model theory.

Even to begin such a project would seem to require deep insight into our pre-systematic intuitions about the physical world.

05/03/23 27/29

Page 28: AI frame prob

References[1] F. Bacchus, J. Halpern, H.J. Levesque, Reasoning about noisy sensors and effectors in the situation calculus,Artificial Intelligence 111 (1999) 171–208.[2] C. Baral, T. Son, Formalizing sensing actions—A transition function based approach, Artificial Intelligence125 (2001) 19–91.[3] R. Bull, K. Segerberg, Basic modal logic, in: D. Gabbay, F. Guenther (Eds.), Handbook of PhilosophicalLogic, Vol. II, Chapter 1, D. Reidel, Dordrecht, 1984, pp. 1–88.[4] B.F. Chellas, Modal Logic: An Introduction, Cambridge University Press, Cambridge, 1980.[5] O. Etzioni, S. Hanks, D.Weld, D. Draper, N. Lesh,M.Williamson, An approach to planning with incompleteinformation, in: B. Nebel, C. Rich, W. Swartout (Eds.), Principles of Knowledge Representation andReasoning: Proceedings of the Third International Conference, Cambridge, MA, 1992, pp. 115–125.[6] R. Fagin, J.Y. Halpern, Y.O. Moses, M.Y. Vardi, Reasoning about Knowledge, MIT Press, Cambridge, MA,1995.[7] A. Frisch, R. Scherl, A general framework for modal deduction, in: J.A. Allen, R. Fikes, E. Sandewall(Eds.), Principles of Knowledge Representation and Reasoning: Proceedings of the Second InternationalConference, Morgan Kaufmann, San Mateo, CA, 1991, pp. 196–207.[8] J. Funge, Representing knowledge within the situation calculus using interval-valued epistemic fluents,J. Reliable Comput. 5 (1) (1999).[9] G. De Giacomo, H.J. Levesque, Projecting using regression and sensors, in: Proc. IJCAI-99, Stockholm,Sweden, 1999, pp. 160–165.[10] G. De Giacomo, H.J. Levesque, An incremental interpreter for high-level programs with sensing, in: LogicalFoundations for Cognitive Agents: Contributions in honor of Ray Reiter, Springer, Berlin, 1999, pp. 86–102.

05/03/23 28/29

Page 29: AI frame prob

Thank you

05/03/23 29/29