Artificial Intelligence - Unit 1 i5q40

Artificial Intelligence UNIT - 1 Prepared by, Mrs. Madhumathi Rajesh Artificial Intelligence, 2nd Ed.,Elaine Rich & Kevin Knight, Tata McGraw Hill, 1999

INTRODUCTION TO Al AND PRODUCTION SYSTEMS UNIT - 1

Syllabus • Introduction to Al — Chapter -1 • Problem formulation, Problem Definition — Production systems, Control strategies, Search strategies. Problem characteristics, Production system characteristics — Chapter -2

• Hill Climbing, Depth first and Breath first, Constraints satisfaction — Related algorithms, Measure of performance and analysis of search algorithms — Chapter -3

Chapter – 1 What is Artificial Intelligence? • • • • • •

The AI Problems The underlying Assumption What is an AI Technique? The level of the model Criteria for success Some general reference

What is AI? • Intelligence: “ability to learn, understand and think” (Oxford dictionary) • AI is the study of how to make computers make things which at the moment people do better.

• Examples: Speech recognition, Smell, Face, Object, Intuition, Inferencing, Learning new skills, Decision making, Abstract thinking

The AI Problems • Simple – Game playing , Theorem proving • Knowledge – Intelligence – common sense (GPS – General problem solving Task) – Perceptions (medical diagnosis & Chemical Analysis) – Natural Understanding

Task Domains of AI

ℑ Mundane Tasks: ℑ Perception ℑ Vision ℑ Speech ℑ Natural Languages ℑ Understanding ℑ Generation ℑ Translation ℑ Common sense reasoning ℑ Robot Control ℑ Formal Tasks ℑ Games : chess, checkers etc ℑ Mathematics: Geometry, logic, Proving properties of programs ℑ Expert Tasks: ℑ Engineering ( Design, Fault finding, Manufacturing planning) ℑ Scientific Analysis ℑ Medical Diagnosis ℑ Financial Analysis

The underlying Assumption • Evidence / Hypothesis • Physical Symbol System hypothesis: • Symbols , Expressions & Tokens (Relations) • Must be subjected to empirical validation

What is an AI Technique? • Intelligence requires Knowledge • Knowledge possesses less desirable properties such as: • • • •

Voluminous Hard to characterize accurately Constantly changing Differs from data that can be used

• AI technique is a method that exploits knowledge that should be represented in such a way that: • • • •

Knowledge captures generalization It can be understood by people who must provide it It can be easily modified to correct errors. It can be used in variety of situations

Tic Tac Toe • Three programs are presented : • Series increase • Their complexity • Use of generalization • Clarity of their knowledge • Extensability of their approach

10

Introductory Problem: Tic-Tac-Toe

X

o

X

11

Introductory Problem: Tic-Tac-Toe Program 1: Data Structures: • Board: 9 element vector representing the board, with 1-9 for each square. An element contains the value 0 if it is blank, 1 if it is filled by X, or 2 if it is filled with a O

•

Movetable: A large vector of 19,683 elements ( 3^9), each element is 9-element vector.

Algorithm: 1.

View the vector as a ternary number. Convert it to a decimal number.

2.

Use the computed number as an index into Move-Table and access the vector stored there.

3.

Set the new board to that vector. 12

Introductory Problem: Tic-Tac-Toe Comments: This program is very efficient in time. 1. A lot of space to store the Move-Table. 2. A lot of work to specify all the entries in the Move-Table. 3. Difficult to extend. 13

Introductory Problem: Tic-Tac-Toe

1 2 3 4 5 6 7 8 9 14

Introductory Problem: Tic-Tac-Toe Program 2: Data Structure: A nine element vector representing the board. But instead of using 0,1 and 2 in each element, we store 2 for blank, 3 for X and 5 for O Functions: Make2 Returns 5 if the center square of the board is blank, that is, if Board[5] = 2. Otherwise, this function returns any blank no corner square ( 2, 4, 6, or 8). Posswin(p) Returns 0 if player p cannot win on his next move; otherwise, it returns the number of the square that constitutes a winning move. This function will enable the program both to win and to block the opponent's win. Posswin operates by checking, one at a time, each of the rows, columns, and diagonals. Because of the way values are numbered, it can test an entire row (column or diagonal) to see if it is a possible win by multiplying the values of its squares together. If the product is 18 (3 x 3 x 2), then X can win. If the product is 50 (5 x 5 x 2), then 0 can win. If we find a winning row, we determine which element is blank, and return the number of that square. Go(n) Makes a move in square n. This procedure sets Board[n] to 3 if Turn is odd, or 5 if Turn is even. It also increments Turn by one 15

Introductory Problem: Tic-Tac-Toe Comments: 1. Not efficient in time, as it has to check several conditions before making each move. 2. Easier to understand the program’s strategy. 3. Hard to generalize. 17

Introductory Problem: Tic-Tac-Toe

8 3 4 1 5 9 6 7 2 15 − (8 + 5)

18

Introductory Problem: Tic-Tac-Toe Comments: 1. Checking for a possible win is quicker. 2. Human finds the row-scan approach easier, while computer finds the number-counting approach more efficient.

19

Introductory Problem: Tic-Tac-Toe Program 3: 1. If it is a win, give it the highest rating. 2. Otherwise, consider all the moves the opponent could make next. Assume the opponent will make the move that is worst for us. Assign the rating of that move to the current node. 3. The best node is then the one with the highest rating. 20

Introductory Problem: Tic-Tac-Toe Comments: 1. Require much more time to consider all possible moves. 2. Could be extended to handle more complicated games.

21

Introductory Problem: Question Answering “Mary went shopping for a new coat. She found a red one she really liked. When she got it home, she discovered that it went perfectly with her favourite dress”. Q1: What did Mary go shopping for? Q2: What did Mary find that she liked? Q3: Did Mary buy anything? 22

Introductory Problem: Question Answering Program 1: 1.

Match predefined templates to questions to generate text patterns.

2.

Match text patterns to input texts to get answers.

“What did X Y”

“What did Mary go shopping for?” “Mary go shopping for Z”

Z = a new coat 23

Introductory Problem: Question Answering Program 2:

24

Program 2:

26

The level of the model • Need for AI: • Work like man • Easier solution identifier • Work more the man

• Programs must concentrate on • • • •

Competing - Human performance Understanding - Human reasoning Computer Reasoning – Convince Human Learn Clues from Humans

Criteria for success

The Turing Test

(Can Machine think? A. M. Turing, 1950)

• Requires: • • • •

Natural language

Human

Knowledge representation Automated reasoning Machine learning

Human Interrogator

AI System

Some general reference • • • •

Survey books Conference proceedings Journal AI Conference

Chapter -2 Problems, Problem Spaces and Search • Problem: • Define the Problem • Analyze the problem • Isolate and represent the task knowledge • Choose the best problem-solving technique

Problem as a state space search •

A set of all possible states for a given problem is known as state space of the problem.

•

Representation of states is highly beneficial in AI because they provide all possible states, operations and the goals.

• If the entire sets of possible states are given, it is possible to trace the path from

the initial state to the goal state and identify the sequence of operators necessary for doing it.

Example: Problem statement "Play chess." To build a program that could Play chess: • Specify the initial position of the chessboard • Define every legal move • Define the board positions that represent a win for either of the sides.

Water Jug Problem Problem statement: Given two jugs, a 4-gallon and 3-gallon having no measuring markers on them. There is a pump that can be used to fill the jugs with water. How can you get exactly 2 gallons of water into 4-gallon jug. Solution: State space for this problem can be described as the set of ordered pairs of integers (X, Y) such that X represents the number of gallons of water in 4-gallon jug and Y for 3-gallon jug. 1.Start state is (0,0) 2.Goal state is (2, N) for any value of N.

Production Rules:

Points to be noted: State space • 1.Define a state space that contains all the possible configurations of the relevant objects. • 2.Specify one or more states within that space that describe possible situations from which the problem solving process may start. These states are called initial states.

• 3.Specify one or more states that would be acceptable as solutions to the problem called goal states.

• 4.Specify a set of rules that describe the actions. Order of application of the rules is called control strategy.

• 5.Control strategy should cause motion towards a solution.

Production Systems A production system consists of:

• A set of rules, each consisting of a left side and a right hand side. Left hand side or pattern determines the applicability of the rule and a right side describes the operation to be performed if the rule is applied.

• One or more knowledge/databases that contain whatever information is appropriate for the particular task. Some parts of the database may be permanent, while other parts of it may pertain only to the solution of the current problem. The information in these databases may be structured in any appropriate way.

• A control strategy that specifies the order in which the rules will be compared to the database and a way of resolving the conflicts that arise when several rules match at once.

• A rule applier.

Control Strategies Requirement for a good Control Strategy • It should cause motion: In water jug problem, if we apply a simple control strategy of starting each time from the top of rule list and choose the first applicable one, then we will never move towards solution.

• It should explore the solution space in a systematic manner: If we choose another

control strategy, let us say, choose a rule randomly from the applicable rules then definitely it causes motion and eventually will lead to a solution. But one may arrive to same state several times. This is because control strategy is not systematic.

Breadth First Search Let us discuss these strategies using water jug problem. These may be applied to any search problem.

• Construct a tree with the initial state as its root. • Generate all the offspring of the root by applying each of the applicable rules to the initial state.

Algorithm for Breadth-First Search 1. Put the initial node on the list of START. 2. If (START is empty) or (START = GOAL) terminate search. 3. Remove the first node from the list of START. Call this node d. 4. If (d = GOAL) terminate search with success. 5. Else if node d has successors, generate all of them and add them at the tail of START. 6. Go to step 2.

The major problems of this search procedure are: 1. Amount of time needed to generate all the nodes is considerable because of the time complexity. 2. Memory constraint is also a major hurdle because of space complexity. 3. The Searching process re all unwanted nodes, which is of no practical use for the search.

Depth First Search • pursue a single branch of the tree until it yields a solution or until some prespecified depth has reached and then go back to immediate previous node and explore other branches in DF fashion. •Blind searches are exhaustive in nature •These are uninformed searches •If the problem is simple then any control strategy that causes motion and is systematic will lead to an answer. But in order to solve some real world problems, we must also demand a control strategy that is efficient.

Algorithm for Depth-First Search 1. Put the initial node on the list of START. 2. If (START is empty) or (START = GOAL) terminate search. 3. Remove the first node from the list of START. Call this node d. 4. If (d = GOAL) terminate search with success. 5. Else if node d has successors, generate all of them and add them at the beginning of START. 6. Go to step 2. The major drawback of Depth-First Search is the determination of the depth (cut-off depth) until which the search has to proceed. The value of cut-off depth is essential because otherwise the search will go on and on.

CHAPTER -3 Heuristic Search Techniques - Guess • The idea of a "heuristic" is a technique, which sometimes will work, but not always. It is sort of like a rule of thumb. Most of what we do in our daily lives involves heuristic solutions to problems. Heuristics are the approximations used to minimize the searching process. Heuristics are criteria for deciding which among several alternatives be the most effective in order to achieve some goal.

• Heuristic is a technique that improves the efficiency of a search process possibly by sacrificing claims of systematicity and completeness. It no longer guarantees to find the best answer but almost always finds a very good answer.

• Using good heuristics, we can hope to get good solution to hard problems (such as travelling salesman) in less than exponential time.

• There are general-purpose heuristics that are useful in a wide variety of problem domains. • We can also construct special purpose heuristics, which are domain specific.

Heuristic Function This is a function that maps from problem state descriptions to measures of desirability, usually represented as numbers. • Which aspects of the problem state are considered, • how those aspects are evaluated, and • the weights given to individual aspects are chosen in such a way that • the value of the heuristic function at a given node in the search process gives as good an estimate as possible of whether that node is on the desired path to a solution.

• Well designed heuristic functions can play an important part in efficiently guiding a search process toward a solution.

Example Simple Heuristic functions • Chess : The material advantage of our side over opponent. • TSP: the sum of distances so far • Tic-Tac-Toe: 1 for each row in which we could win and in we already have one piece plus 2 for each such row in we have two pieces

General-purpose heuristics Vs Special purpose heuristics • A general-purpose heuristics for combinatorial problem is nearest neighbour algorithms which

works by selecting the locally superior alternative. • For such algorithms, it is often possible to prove an upper bound on the error which provide reassurance that one is not paying too high a price in accuracy for speed.

• Eg TSP

• •In many AI problems, it is often hard to measure precisely the goodness of a particular solution. • For real world problems, it is often useful to introduce heuristics based on relatively unstructured knowledge. It is impossible to define this knowledge in such a way that mathematical analysis can be performed.

• Eg: Parking lot

Problem Characteristics Analysing the problem: 1. Is the problem decomposable into a set of independent smaller sub problems? 2. Can solution steps be ignored or at least undone if they prove to be unwise? 3. Is the universe Predictable? 4. Is a good solution Absolute or Relative ? 5. Is the solution state or a path? 6. What is the Role of knowledge? 7. Does the task require Interaction with a person? 8. Is the knowledge base consistant?

Is the problem decomposable? • We can solve this problem by breaking it down into three smaller sub problems, each of which we can then be solved using a small collection of specific rules. • Decomposable problems can be solved by the divideand-conquer technique.

• Use of decomposing problems: -Each sub-problem is simpler to solve -Each sub-problem can be handed over to a different processor. - Can be solved in parallel processing environment. • There are non decomposable problems. For example, Block world problem is non decomposable.

Can solution steps be ignored or at least undone? Three types of problems: Ignorable, Recoverable and Irrecoverable.

• Example1:(Ignorable):In theorem proving-(solution steps can be ignored) • Example2: (Recoverable):8 puzzle-(solution steps can be undone) • Example3: (Irrecoverable): Chess(solution steps cannot be undone)

Is the Universe Predictable? • Certain Outcome ( ex: 8-puzzle) • Uncertain Outcome ( ex: Bridge, controlling a robot arm) • For solving certain outcome problems, open loop approach ( without ) will work fine.

• For uncertain-outcome problems, planning can at best generate a sequence

of operators that has a good probability of leading to a solution. We need to allow for a process of plan revision to take place.

Is a good solution Absolute or Relative ? • In water jug problem there are two ways to solve a problem. If we follow one path successfully to the solution, there is no reason to go back and see if some other path might also lead to a solution. Here a solution is absolute.

• In travelling salesman problem, our goal is to find the shortest route. Unless all routes are known, the shortest is difficult to know. This is a best-path problem whereas water jug is any-path problem.

• Any path problem can often be solved in reasonable amount of time using heuristics that suggest good paths to explore.

• Best path problems are in general computationally harder than any-path.

Is the Solution state or a path? • Examples:–Finding a consistent interpretation for the sentence “The bank president ate a dish of pasta salad with the fork”. We need to find the interpretation but not the record of the processing.

• Water jug : Here it is not sufficient to report that we have solved , but the

path that we found to the state (2,0). Thus the a statement of a solution to this problem must be a sequence of operations ( Plan) that produces the final state.

What is the Role of knowledge? • In Chess game, knowledge is important to constrain the search for a solution otherwise just the rule for determining legal moves and some simple control mechanism that implements an appropriate search procedure is required.

• Newspapers scanning to decide some facts, a lot of knowledge is required even to be able to recognize a solution.

Does the task require Interaction with a person? • The programs require intermediate interaction with people for additional inputs and to provided reassurance to the .

• There are two types of programs: –Solitary –Conversational

• Decision on using one of these approaches will be important in the choice of problem solving method.

Is the knowledge Base consistent? Example: Inconsistent knowledge:

• Target problem: A man is standing 150 ft from a target. He plans to hit the target by shooting a gun that fires bullets with velocity of 1500 ft/sec. How high above the target should he aim?

• Solution: Velocity of bullet is 1500 ft./sec i.e., bullet takes 0.1 sec to reach the target. Assume bullet travels in a straight line. Due to gravity, the bullet falls at a distance (1/2)gt2= (1/2)(32)(0.1)2 = 0.16ft. So if man aims up 0.16 feet high from the target, then bullet will hit the target.

• Now there is a contradiction to the fact that bullet travel in a straight line because the bullet in actual will travel in an arc. Therefore there is inconsistency in the knowledge used.

Production system Characteristics • Relationships are there between problem types and the types of production systems best suited to solving the problems

• Classes of Production systems: • Monotonic Production System: the application of a rule never prevents the later application of another rule that could also have been applied at the time the first rule was selected. (rules are independent)

• Non-Monotonic Production system • Partially commutative Production system: property that if application of a particular sequence of rules

transforms state x to state y, then permutation of those rules allowable, also transforms state x into state y (Theorem Proving)

• Commutative Production system.

Four Categories of Production System Monotonic

Non Monotonic

Partially Commutative

Theorem proving

Robot Navigation

Not Partially Commutative

Chemical Synthesis

Bridge

Issues in the design of search programs • The direction in which to conduct the search ( forward versus backward reasoning).

• How to select applicable rules ( Matching) • How to represent each node of the search process ( knowledge representation problem

Chapter – 3 Heuristic Search • Generate-and-test • Hill climbing • Best-first search • Problem reduction • Constraint satisfaction • Means-ends analysis

Generate-and-Test Algorithm 1. Generate a possible solution.

2. Test to see if this is actually a solution. 3. Quit if a solution has been found. Otherwise, return to step 1. Pros and Cons:

• Acceptable for simple problems. • Inefficient for problems with large space.

Generate-and-Test • Exhaustive generate-and-test. • Heuristic generate-and-test: do not consider paths that seem unlikely to lead to a solution.

• Plan generate-test: − Create a list of candidates. − Apply generate-and-test to that list.

Hill Climbing • Searching for a goal state = Climbing to the top of a hill

• Generate-and-test + direction to move. • Heuristic function to estimate how close a given state is to a goal state. Algorithm for simple hill climbing: 1. Evaluate the initial state.

2.

Loop until a solution is found or there are no new operators left to be applied: − Select and apply a new operator − Evaluate the new state: goal → quit better than current state → new current state Note: Evaluation function needs task-specific knowledge

Steepest-Ascent Hill Climbing (Gradient Search) • Considers all the moves from the current state. • Selects the best one as the next state. Algorithm 1. Evaluate the initial state.

2.

Loop until a solution is found or a complete iteration produces no change to current state: − SUCC = a state such that any possible successor of the current state will be better than SUCC (the worst state). − For each operator that applies to the current state, evaluate the new state: goal → quit better than SUCC → set SUCC to this state − SUCC is better than the current state → set the current state to SUCC.

Hill Climbing: Disadvantages Local maximum A state that is better than all of its neighbours, but not better than some other states far away. Plateau A flat area of the search space in which all neighbouring states have the same value.

Overcome Disadvantage Ways Out

• Backtrack to some earlier node and try going in a different direction. • Make a big jump to try to get in a new section. • Moving in several directions at once.

Hill Climbing: Example Start

A

Goal

D

D

C

C

B

B

A Blocks World

71

Start

0

A D

Goal

4

D C

C

B

B

A Blocks World

Local heuristic: +1 for each block that is resting on the thing it is supposed to be resting on. −1 for each block that is resting on a wrong thing.

72

0

A

2

D

D

C

C

B

B

A

73

This will halt Hill climbing, because Local maximum will be reached

2

D C B A

0

A 0

D C

C

D

C

0

B

B

A

B

A

D 74

Start

−6

A D C

Goal

6

D C B

B Blocks World A

Global heuristic: For each block that has the correct structure: +1 to every block in the structure. For each block that has a wrong structure: −1 to every block in the structure. 75

−3

D C B A

A

−6 −2

D C

C

D

C

−1

B

B

A

B

A

D 76

Hill Climbing: Conclusion • Can be very inefficient in a large, rough problem space. • Global heuristic may have to pay for computational complexity. • Often useful when combined with other methods, getting it started right in the right general neighbourhood.

77

Simulated Annealing • A variation of hill climbing in which, at the beginning of the process, some downhill moves may be made.

• To do enough exploration of the whole space early on, so that the final solution is relatively insensitive to the starting state.

• Lowering the chances of getting caught at a local maximum, or plateau, or a ridge.

78

Simulated Annealing Physical Annealing

• Physical substances are melted and then gradually cooled until some solid state is reached.

• The goal is to produce a minimal-energy state. • Annealing schedule: if the temperature is lowered sufficiently slowly, then the goal will be attained.

• Nevertheless, there is some probability for a transition to a higher energy state: e− ∆E/kT.

79

Simulated Annealing

Algorithm 1. Evaluate the initial state.

2. Loop until a solution is found or there are no new operators left to be applied:

− Set T according to an annealing schedule − Selects and applies a new operator − Evaluate the new state: goal → quit ∆E = Val(current state) − Val(new state)

∆E < 0 → new current state else → new current state with probability e−∆E/kT. 80

Best-First Search • Depth-first search: not all competing branches having to be expanded. • Breadth-first search: not getting trapped on dead-end paths. ⇒ Combining the two is to follow a single path at a time, but switch paths whenever some competing path look more promising than the current one.

Best-First Search –OR problem A

A B 3

A

C 5

D 1

B 3

C 5

Most Promising Node

A B G 6

H 5

C 5

D E 4

F 6

A D E 4

B F 6

G 6

H 5

C 5 I 2

D E J 1

F 6 82

Best-First Search - Graph • OPEN LIST: nodes that have been generated, but have not examined. This is organized as a priority queue.

• CLOSED LIST: nodes that have already been examined. Whenever a new node is generated, check whether it has been generated before.

Best-First Search Algorithm 1. OPEN = {initial state}.

2. Loop until a goal is found or there are no nodes left in OPEN: − Pick the best node in OPEN − Generate its successors − For each successor: new → evaluate it, add it to OPEN, record its parent generated before → change parent, update successors 84

Best-First Search • Greedy search: h(n) = estimated cost of the cheapest path from node

n to a goal state.

• Uniform-cost search: g(n) = cost of the cheapest path from the initial state to node n.

85

Best-First Search • Greedy search: h(n) = estimated cost of the cheapest path from node

n to a goal state.

Neither optimal nor complete

86

Best-First Search • Algorithm A* (Hart et al., 1968): f(n) = g(n) + h(n) h(n) = cost of the cheapest path from node n to a

goal state.

g(n) = cost of the cheapest path from the initial state

to node n.

87

A* Algorithm

Problem Reduction Goal: Acquire TV set

Goal: Steal TV set

Goal: Earn some money

Goal: Buy TV set

AND-OR Graphs

Algorithm AO* (Martelli & Montanari 1973, Nilsson 1980) 89

Problem Reduction: AO* A 5

A 6 9

B 3

A 9 B 3

9

C 4

C 4

D 5

A 11 D 10 E 4

F 4

B 6 G 5

12 H 7

C 4

D 10 E 4

F 4 90

Problem Reduction: AO* A 11 B 13 D 5

A 14

C 10

E 6

B 13 F 3

D 5

G 5 Necessary backward propagation

C 15

E 6

F 3

G 10 H 9 91

Constraint Satisfaction • Many AI problems can be viewed as problems of constraint satisfaction. Cryptarithmetic puzzle:

+

SEND MORE MONEY 92

Constraint Satisfaction • As compared with a straightforward search procedure, viewing a problem as one of constraint satisfaction •

can reduce substantially the amount of search. Operates in a space of constraint sets.

• Initial state contains the original constraints given in the problem. • A goal state is any state that has been constrained “enough”. Two-step process: 1.

Constraints are discovered and propagated as far as possible.

2.

If there is still not a solution, then search begins, adding new constraints.

send+more.docx

93

Initial state: • No two letters have the same value. • The sum of the digits must be as shown.

SEND

M=1 S = 8 or 9 O=0 N=E+1 C2 = 1 N+R>8 E≠9

+

MORE MONEY

E=2 N=3 R = 8 or 9 2 + D = Y or 2 + D = 10 + Y C1 = 0

C1 = 1

2+D=Y N + R = 10 + E R=9 S =8

2 + D = 10 + Y D=8+Y D = 8 or 9 D=8 Y=0

D=9 Y=1

94

Means-ends analysis • Involves detection of difference between current state and goal state • Once difference identified, an operator to reduce the difference must be • • • •

found But perhaps operator cannot be applied to current state Subproblem of getting to state where operator can be applied Operator may not result in goal state Second subproblem of getting from new state to goal state

MEA • MEA process applied recursively • Each rule (operator) has • LHS preconditions and RHS aspects of problem state changed. • Difference table of rules and differences they can reduce.

• Example: Problem for household robot: moving desk with 2 things on it from one room to another. Main difference between start and goal state is location. Choose PUSH and CARRY

Move object

Move robot

Clear object

Push

Carry

*

*

Walk

Pickup

Putdown

Operator

Preconditions

Results

PUSH (obj, loc)

at(robot,obj) &large (obj) &clear (obj) & arm empty

at(obj, loc) & at (robot, loc)

CARRY (obj, loc)

at(robot, obj) &Small (obj)

at(obj, loc) &at(robot, loc)

WALK(loc)

none

At(robot, loc)

PICKUP(obj)

At(robot, obj)

Holding(obj)

PUTDOWN(obj)

Holding(obj)

Not holding (obj)

PLACE(obj1, obj2)

At(robot,obj2) & holding (obj1)

on(obj1, obj2)

*

*

*

Get object on object Get arm empty

Be holding object

Place

*

*

*

Means-Ends Analysis 1. Compare CURRENT to GOAL. If no differences, return. 2. Otherwise select most important difference and reduce it by doing the following until success or failure is indicated. (a) Select an as yet untried operator O that is applicable to the current difference. If there are no such operators then signal failure. (b) Attempt to apply O to the current state. Generate descriptions of two states O-START a state in which O’s preconditions are satisfied and O-RESULT, the state that would result if O were applied in O-START. (c) If (FIRST-PART MEA (CURRENT,O-START) AND (LAST-PART MEA (O-RESULT, GOAL) are successful then signal success.