The method relies on rules that change the initial state to a current state and enable goal states to be achieved. The rules that are used consist of two parts left hand sides that are prerequisites and right hand sides that indicate the changes to be introduced. The data structure used consists of a difference table. We shall observe how a household robot moves a desk holding two objects upon it from one room to another. The desk can only be moved if clear and the two objects must be placed upon the desk when it is in the other room. Each rule has a prerequisite and this indicates that the desk cannot be moved until it is clear. Various aspects of position must be considered before the goal state can be achieved. This topic was fully explored by Newell & Simon in their GPS general problem solver in the nineteen sixties.

In means end analysis we consider a household robot whose task is to move a desk with two objects upon it from one room to the next. The task is achieved using differences between the current state and the goal state and applying the required pre requisites shown in fig 3.15 etc.

The main difference between the start and final states is the position of the desk.See fig 3.17

This can be reduced by using PUSH or CARRY and in each case the prerequisites must be met.

PUSH is chosen as the other choices lead to dead ends; PUSH has 4 prerequisites;

the robot must be at the desk, the desk must be clear , we can ignore desk is heavy and robot's arm is clear.

WALK brings the robot to the correct spot. PICKUP and PUTDOWN are used to clear the desk.

Now the two states the current state and goal state are close together in terms of differences and the only thing left is to place the objects back on to the desk.

The robot must be brought to hold the objects before they can be placed upon the table.

The progress is mapped out in fig 3.18 and the whole algorithm is expressed.

GENERAL PROBLEM SOLVER GPS

The GPS program was written by Newell Simon and Shaw in 1960 and improved versions were created in 1967 and 1969. It is a truly unified multipurpose program and is not an amalgam of specialised programs. Examples of the problems it could solve are:

Missionaries and Cannibals

Towers of Hanoi

Father and Sons

Three Coins

Seven Bridges of Konisberg

Water Jug

Farmer Goose Fox and Grain

Monkey and Bananas

Mathematical Integrals.

FEATURES OF GPS

1 GPS applies itself to subproblems. It is therefore recursive hierarchical and displays action centred control.

2 GPS achieves goals by finding differences and it uses procedures to find the differences and so it may be thought of as constituting an object centred control.

3 GPS is itself a procedure that finds procedures for doing things such as reducing differences. There is no way of stating or showing that things cannot be done.

4 GPS involves no statement about resource allocation among procedures, there is no parallelism nor is a procedure stopped before it succeeds or gives up.

5 GPS has the goal of reducing the difference betwen a current state and a goal state. GPS therefore uses means end analysis.

6 GPS moves forward iteratively searching for a goal. GPS therefore involves search the particular kind being depth first search with backup.

7 GPS creates subgoals and therefore involves problem reduction.

8 GPS uses planning by deferring action on details until after the overall solution path is established.

9 GPS cannot answer this question

' how is it possible to maintain coherence and consensus among parallel procedures?'

and so is not involved in parallelism.

10 GPS cannot say anything about the following as its list of procedures is fixed. ' how is it possible for a problem solver to spawn new procedures as problem solving proceeds?'

MEANS END ANALYSIS

GPS works by considering the present position as the current state and the objective as the goal state. It considers the differences between these two states and finds ways of reducing the difference between them. The current state embraces all the facts known about the present state inclusding a specification of the current problem. Consider the following examples.

1 In a travel problem the current state and the goal state are defined by physical locations.

2 In a robot assembly problem the current state and the goal state are defined by the raw materials and the finished product respectively.

3 In a geometry problem the current state is all that is known both general and specific. The goal state is also all that is known together with the problem set.

AUNT AGATHA AND ROBBIE THE ROBOT

Let us consider another problem in greater detail

Aunt Agatha lives in Los Angeles. Robbie a robot lives in Boston and Aunt Agatha invites Robbie to stay with her in Los Angeles. How can Robbie make the journey from Boston to Los Angeles as there are many ways of travelling. He has to make decisions as to which is the best means of travellling at each stage in the journey. To make it easier for Robbie there is a difference procedure table available and this is shown on the attached sheet. Following Robbie's path

a To go from Boston to Los Angeles involves travelling over 1000 miles and this means using an aeroplane. But to use an aeroplane you must be at an airport and Robbie is at home. To travel from home to an airport is a new adjacent goal.

b How can Robbie do this, since the distance is less than 100 but more than 1 mile Robbie drives in a car. Being at the airport is not being at the plane but the distance between the carpark and the plane is less than 1 mile so Robbie walks.

c Now at Los Angeles Robbie has to leave the airport and reach his aunt's house. The distance is greater than 1 mile so he chooses to use a car. However this creates a problem as the car is in Boston. Going back to Boston to get the car will make the difference larger rather than smaller so his option is ignored for the time being. There is an alternative and that involves a taxi. Robbie chooses this but must first walk to the taxirank.

d Robbie is now at the kerb of Aunt Agatha's house and walks in.

GPS does Forward Chaining not Backward chaining

Since GPS works from the current state towards the goal state, GPS is said to be doing forward chaining. Ordinary forward chaining GPS involves a commitment to one kind of search depthfirst search. This is illustrated by the following procedure decription:

To reach a goal state from a current state using GPS

1 Form a one-state queue consisting of the current state.

2 Until the queue is empty or the goal state has been reached, call the first state in the queue the current state:

2a If there is no untried procedure for reducing the difference between the current state and the goal state remove the first state from the queue

2b Otherwise select a procedure for reducing the difference:

(i) If the procedure's preconditions are not satisfied attempt to satisfy them using GPS with the preconditions defining a new goal state.

(ii) If the preconditions are satisfied use the procedure and put the new state at the front of the queue.

3 If the goal state has been found announce success otherwise announce failure.

Review of Problems Undertaken

Missionaries and Cannibals

There are 3 missionaries and 3 Cannibals and a boat on one side of a river. How can the 6 people get across the river in the boat subject to the following constraints

1 There must be at least one person in the boat

2 There cannot be more than two people in the boat at any time

3 There cannot be more cannibals than missionaries on either bank otherwise the cannibals will eat the missionaries. Note there is a misere version in which we cannot have more missionaries than cannibals on any bank otherwise the missionaries will convert the cannibals.

GPS generated 57 goals and took 969 seconds.

Father and sons

Basically similar except father weighs 200 and each son 100 boat can take 200 units only how can all three get across. GPS generated 33 goals.

Three coins

Three coins lie on a table in the order tails, heads ,tails. In precisely three moves make them face either all heads or all tails, GPS generated 10 goals.

Seven Bridges of Konigsberg

The problem is set in Konigsberg and asks can someone walk a complete circuit arriving back at the starting point and yet only crossing each bridge once.

After generating 71 goals GPS gave up because its memory was full GPS should have crecognised that it was impossible. In 1736 Euler invented graph theory to prove that it was impossible .

In proving that the problem could not be solved Euler focussed on the degree of the nodes of the graph observing that a node could be even or odd. An even degree node has an even number of arcs joining it to neighbouring nodes. Likewise an odd degree node.With the exception of its beginning and end nodes the desired walk would have to leave each node exactly as often as it entered it. Nodes of odd degree could be used only as the beginning or ending of the walk since such nodes could be crossed only a certain number of times before they proved a dead end. The traveller could not exit the node without using a previously travelled arc.Euler noted that unless a graph contained either exactly zero or two nodes of odd degree the walk was impossible. If there were two odd degree nodes the walk could begin at one and end at the other. If there were zero the walk could begin and end at the same node.

Monkey Puzzle

Problem

The monkey is in a closed room in which there is a small table. There is a bunch of bananas hanging from the ceiling but the monkey cannot reach them. Assuming that the monkey can move the table and if the monkey stands on the table the monkey can reach the bananas establish a method to instruct the monkey on how to capture the bananas.

1 Task Environment

A Information

set of places { on the floor, place1, place2, under the bananas}

B Operators

CLIMB

pretest the monkey is in the table's place

move the monkey becomes on the table

WALK

variable x is the set of places

move the monkey's place becomes x.

MOVE TABLE

variable x is the set of places

pretest the monkey's place is in the set of places

the monkey's place is in the table's place

moves the monkey's place becomes x.

the table's place becomes x

GET BANANAS

pretest the table's place is under the bananas

the monkey's place is on the table

move the contents of the monkey's hand is the bananas

C Differences

d1 is the monkey's place

d2 is the table's place

d3 is the contents of the monkey's hand

D Differences ordering

d3 is harder to reduce than d2 which is harder to reduce than d1.

Specific Task

Goal transform intial object to desired object

Objects

Initial the monkey's place is place1 the table's place is place2

the contents of the monkey's hand is empty

Desired the contents of the monkey's hand is the bananas

Constraint Satisfaction

The general problem is to find a solution that satisfies a set of constraints. Examples of this technique involve design problems and robot technology. Problems involve the movement of robot arms and the design of suitable joints and include the study of the movements of the robot's components in a variety of situations. The idea of this approach is that the range of solutions can be dramatically reduced by the constraints and so the search for the solution path is accelerated. An example of this approach occurs in Cryptarithmetic puzzles an example of which is given on the next page.

Cryptarithmetic leads into constraint analysis. Here the problem is to allocate unique digits to each of the letters in the problem so that the summation appears to be correct. Looking at the problem we can see that the letters are

S E N D M O R Y

and the digits 0-9 must be allocated on a one to one mapping to each of the above letters.

The leading digits must not be zero thus S and M are not zero.

We can assert that M is either one or zero as two digits can at most add up to 19, allowing for a previous carry. But no two letters can be the same so the maximum is actually eighteen.

However M is not zero from the first statement and so M=1.

Assuming that the carries from the least significant digits to the most significant are called

C1, C2, C3, C4 then S + M + C3 must be greater than 9 to generate a carry and M=1,

thus S + C3 is greater than 8 and as C3 is 0 or 1 then S is 8 or 9. Since S + M + C3 is 10 or 11 and M is 1 then O is 0 or 1 but as M knocks out the digit 1, then O is 0.

N cannot have the same value as E and since O is 0 then N=E+C2. Thus C2 = 1 and N = E + 1.

The addition now becomes

S E N D later S E N D

+ 1 0 R E 1 0 R E

1 0 N E Y 1 0 N E Y

C4 C3 C2 C1 1 C3 1 C1

In the thousands colum S + 1 + C3 gives ten thus S= 8 or 9.

In the tens colum C1 + E + 1 + R = 10 + E, so R + C1 = 9 thus R is 8 or 9, hence E<8

Therefore C3 = 0, S= 9 R =8

later 9 E N D finally 9 5 6 7

+ 1 0 8 E 1 0 8 5

1 0 N E Y 1 0 6 5 2

1 0 1 C1 1 0 1 1

In the tens colum E+1+8+C1 = 10 +E thus C1 = 1. Both E and N are <8.

E= 6, N =7 leads to D=5 Y=1 a conflict. E= 5 N =6 leads to D = 7 and Y =2

The best constraints are set up by finding the term that affects most relations that is the letter that occurs in most equations.E appears three times and N twice and E and N are related by a simple equation. By choosing sensible guesses for E and N we can proceed to produce values for the other letters. Sometimes conflicts arise because a letter may be assigned a value that has already been given to another letter. This produces additional constraints and leads to a solution.Proceeding in this way we generate the tree and the solution follows.