We have seen that it is possible to solve a problem by considering the appropriate form of knowledge representation and using algorithms to solve parts of the problem and also to use searching methods. The first major method considered the solution as a search from the initial state to a goal state through a state space. There are many ways of moving through this space by using operators and the A* algorithm described the best first search through a graph. This method is fine for simpler problems but for more realistic problems it is advisable to use problem decomposition. Here the problem is split into smaller sub problems and the partial solutions are then synthesised. The danger in this method occurs when certain paths become abortive and have to be discarded. How much of the partial solution can be saved and how much needs to be recomputed. The frame problem gave some guidance on enabling us to decide on what stays the same and on what changes as we go from state to state. If the problem concerned designing a robot to build a car then mounting the engine on the chassis would not affect the rear of the car nowadays.
The AO* algorithm enabled us to handle the solution of problems where the problem could be split into distinct parts and then the partial solutions reassembled. We saw that difficulties arose if parts interacted with one another. Most problems have some interaction and this implies some thought into the ordering of the steps; for example if the robot has to move a desk with objects on it from one room to another; or to move a sofa from one room to another and the piano is near the doorway. The thought process involved in recombining partial solutions of such problems is known as planning. At this point we run into a discussion about the role of the computer in the design of a plan as to how we can solve a problem. It is extremely unlikely at this stage that a computer will actually solve the problem unless it is a game and here some intersaction with a person is needed. Generally the computer is used to decide upon or to offer words of wisdom on the best method of approaching the solution of a problem. In one sense this can be interpreted as a simulation; if we are considering the handling of queues at an airport or a post office there are no actual people and so we can try a range of possibilities; likewise in a traffic control problem there are no cars or aircraft piling up at a junction or two miles over an airport. Once the computer based investigation has come up with the best solution we can then implement it at the real site.
This approach assumes that there is contnuity in the way of life. It cannot budget for rapid change or revolution. How can this approach cater for unexpected events such as a faulty component or a spurious happening such as two items stuck together or a breakdown in the path somewhere vital such as in a camera reel. When a fault or some unrecognisable state is encountered it is not necessary to restart for much of what has been successfully solved is still useful. Consider a child removing the needles from a partially completed knitted sweater. The problem lies in restarting from a dead end and this will need some backtracking. This method of solution is pursued to reduce the level of complexity and so to ensure successful handling we must introduce reasoning to help in the backtracking required to cater for faults. To assist in controlling backtracking many methods go backward from the goal to an initial state.
PLANNING TECHNIQUES
BLOCKS WORLD
The blocks world is chosen to illustrate these techniques as it is sufficiently simple and well behaved to be easily understood yet it provides the environment to illustrate the way problems are broken into nearly distinct subproblems; thus showing how thepartial solutions need to be combined to form a realistic complete solution to the set problem. The world consists of a flat surface such as a tabletop and an adequate set of identical blocks which are identified by letters. The blocks can be stacked one on one to form towers of apparently unlimited height. The stacking is achieved using a robot arm which has fundamental operations and states which can be assessed using logic and combined using logical operations. The robot can hold one block at a time and only one block can be moved at a time.
We shall use the four actions:
UNSTACK(A,B) pick up clear block A from block B;
STACK(A,B) place block A using the arm onto clear block B;
PICKUP(A) lift clear block A with the empty arm;
PUTDOWN(A) place the hled block A onto a free space on the table.
and the five predicates:
ON(A,B) block A is on block B
ONTABLE(A) block A is on the table
CLEAR(A) block A has nothing on it
HOLDING(A) the arm holds block A
ARMEMPTY the arm holds nothing
Using logic but not logical notation we can say that
If the arm is holding a block it is not empty
If block A is on the table it is not on any other block
If block A is on block B,block B is not clear.
COMPONENTS
1 choose the best rule based upon heuristics
2 apply this rule to create a new state
3 detect when a solution is found
4 detect dead ends so that they can be avoided
5 detect when a nearly solved state occurs & use special methods to make it a solved state.
The special methods used involve finding the differences between the current states and the goal states and then choosing the rules that reduce these differences most effectively which is means end analysis. If we wish to travel by car to visit a friend the first thing to do is to fill up the car with fuel. If we do not have a car then we need to acquire one. The largest difference must be tackled first. To travel by car requires fuel minimise the distance, but if the vehicle is not there acquire the vehicle. To create a happy home find a housekeeper food heating and home comforts but if you do not have a house you need to find one first.
RULE APPLICATION
Previously rules could be applied without any difficulty as complete systems were specified and rules enabled the sysstem to progress from one state to the next. Now we must be able to handle rules which only cover parts of systems. A number of approaches to this task have been used and the first such is due to Green. Here considering fig 13.1 we note the changes to a state produced by the application of a rule.
In informal notation unstacking block A from block B means that block A is clear and is on block B and as a result in the new state the arm is holding block A and that block B is now clear.
We do not explicitly know that block Bis on the table and that it is unaffected by this transition. Thus additional rules or frame axioms need to be produced. This approach using resolution is powerful & only requires a single mechanism but it does need a large number of frame axioms.
Another approach is needed and this was used by STRIPS. Basically each operator has three lists of predicates associated with it, the first is a list of things that become TRUE called ADD and the second are things that become FALSE called DELETE. The third list is a set of prerequisites that must be true before the operator can be applied. Anything not in these lists is assumed to be unaffected by the operation.
Consider the following example in the Blocks World where the four fundamental operations of
STACK UNSTACK PICKUP AND PUTDOWN are discussed.
Stack requires the arm to be holding a block A and the other block B to be clear.
Afterwards the block A is on block B and the arm is empty and these are true--- add;
The arm is not holding a block and block B is not clear; predicates that are false delete;
Unstack requires that the block A is on block B; that the arm is empty and that block A is clear.
Afterwards block B is clear and the arm is holding block A true---add;
The arm is not empty and the block A is not on block B; predicates that are false delete;
Pickup needs a block to be clear and on the table and the arm to be empty.
Afterwards the arm is holding the block which is true--add;
The block is not on the table and the arm is not empty; predicates that are false delete;
Putdown means that the arm is holding a block.
Afterwards the block is on the table and the arm is empty which is true--add;
The arm is not holding the block; predicates that are false delete;
Although quite frequently preconditions are deleted it is not always so, see pickup and this is why three lists must be maintained.
We have now greatly reduced the information that needs to be held. If a new attribute is introduced we do not need to add new axioms for existing operators. Unlike in Green's method we remove the state indicator and use a database of predicates indicating the current state as in fig 13.3. Going back to fig 13.1
The current state is
ONTABLE(B) H ON(A,B) H CLEAR(A)
after the unstack operation
ONTABLE(B) H CLEAR(B) H HOLDING(A) H CLEAR(A)---UNAFFECTED
Note the use of the ADD and DELETE lists.
In fig 13.3 progress is made by moving down the tree but if an incorrect path is chosen then it is possible to correct it by choosing the appropriate elements in the add and delete lists of the operator in question at the relevant arc linking together the nodes on the incorrect path. In this way the backtracking repairs the damage.
Instead of reaching node 3 as shown in fig 13.3 from fig13.1 we backtrack by adding the DELETE predicates and delete each of the ADD predicates giving the same reult as we derived above through unstacking viz
ONTABLE(B) H CLEAR(B) H HOLDING(A) H CLEAR(A)
Proceeding one stage further back gives us the original position.
DETECTING PROGRESS
The final solution can be detected if we can devise a predicate that is true when the solution is found and is false otherwise. This can require a great deal of thought and requires a proof.
Detecting false trails is also necessary and we have seen in A* that if insufficient progress is made then this trail is aborted in favour of a more hopeful one. Sometimes it is clear that solving a problem one way has reduced the problem to parts that are harder than the original state. By moving back from the goal state to the initial state it is possible to detect conflicts and any trail or path that involves a conflict can be pruned out. Reducing the number of possible paths means that there are more resources available for those left. Supposing that the computer teacher is ill at a school there are two possible alternatives transfer a teacher from mathematics who knows computing or bring another one in. If the maths teacher is the only teacher of maths the problem is not solved. If on the other hand there is no money left the second solution could be impossible.
If the problems are nearly decomposable we can treat them as decomposable and then patch them, how? Consider the final state reached by treating the problem as decomposable as the current state and noting the differences between the goal state and the current state and the goal state and the initial state and use appropriate Means End analysis techniques to move in the best direction. Better is to work back in the path leading to the current state and see if there are options. It may be that one optional path could lead to a solution whereas the existing route led to a conflict. Generally this means that some conditions are changed prior to taking an optional path through the problem. Another approach involves putting off decisions until one has to leaving decision making until more information is available and other routes have been explored. Often some decisions need not be taken as these nodes are never reached.GOAL STACK PLANNING
The earliest technique used to handle interactive compound goals uses goal stacks. The problem solver uses a stack containing goals operators and a database maintaining for each operator used the ADD DELETE and PREREQUISITE lists. Referring to fig 13.4 the goal stack is
ON(C,A) H ON(B,D) H ONTABLE(A) H ONTABLE(D)
It would appear that this splits into four problems of which two are solved as they already are true in the initial state viz ONTABLE(A) ONTABLE(D) . We proceed with the other two.
There are two ways to proceed
1 ON(C,A)
ON(B,D)
ON(C,A) H ON(B,D) H ONTABLE(A) H ONTABLE(D) and
2 ON(B,D)
ON(C,A)
ON(C,A) H ON(B,D) H ONTABLE(A) H ONTABLE(D)
The method is to investigate the first node on the stack ie the top goal. If a sequence of operators is found that satisfies this goal it is removed and the next goal is attempted. This continues until the goal state is empty. Alternative 2 finds a solution quickly so for information we shall consider the other alternative 1.
The first goal ON(C,A) is not true and the only operator that would make it true is
STACK (C,A) which replaces ON(C,A) giving
STACK (C,A)
ON(B,D)
ON(C,A) H ON(B,D) H ONTABLE(A) H ONTABLE(D)
To be able to apply this operator the prerequisites must be met which means that block A is clear and the arm is holding block C. Because all changes to the structure of the blocks involve the arm it is best to leave the state of the arm to the end as it is the easiest state to change a heuristic.
The goal stack becomes
CLEAR(A)
HOLDING(C)
CLEAR(A) H HOLDING(C)
STACK (C,A)
ON(B,D)
ON(C,A) H ON(B,D) H ONTABLE(A) H ONTABLE(D)
The top goal is false and can only be made true by unstacking B. This leads to
ON(B,A)
CLEAR(B)
ARMEMPTY
ON(B,A) H CLEAR(B) H ARMEMPTY
UNSTACK(B,A)
HOLDING(C)
CLEAR(A) H HOLDING(C)
STACK (C,A)
ON(B,D)
ON(C,A) H ON(B,D) H ONTABLE(A) H ONTABLE(D)
We see that the first goal is true, that the second is universally true, that the arm is empty and that all three goals are true means that we can apply the operator UNSTACK(B,A) as all prerequisites are met. This gives us the first node in database
ONTABLE(A) H ONTABLE(C) H ONTABLE(D) H HOLDING(C) H CLEAR(A)
Note as a future reference of the use of UNSTACK(B,A) that
HOLDING(B) is true as well as CLEAR(A)
The goal stack becomes
HOLDING(C)
CLEAR(A) H HOLDING(C)
STACK (C,A)
ON(B,D)
ON(C,A) H ON(B,D) H ONTABLE(A) H ONTABLE(D)
There are two ways we can achieve HOLDING(C) by using the operators PICKUP(C) or
UNSTACK(C,someblock) where someblock is an unspecified block.
This leads to two alternative paths
ON(C someblock)
CLEAR(C)
ARMEMPTY
ON(C, someblock) H CLEAR(C) H ARMEMPTY
UNSTACK(C, someblock)
CLEAR(A) H HOLDING(C)
STACK (C,A)
ON(B,D)
ON(C,A) H ON(B,D) H ONTABLE(A) H ONTABLE(D)
In this first route we can see three references to someblock and these must refer to the same block, although in the search it is conceivable several blocks will become temporarily attached. Hence the binding of variables to blocks must be recorded. Investigating further we need to satisfy the first goal and this requires stacking C on some block which is clear.
CLEAR(someblock)
HOLDING(C)
CLEAR(someblock) H HOLDING(C)
STACK (C,someblock)
CLEAR(C)
ARMEMPTY
ON(C someblock) H CLEAR(C) H ARMEMPTY
UNSTACK(C, someblock)
CLEAR(A) H HOLDING(C)
STACK (C,A)
ON(B,D)
ON(C,A) H ON(B,D) H ONTABLE(A) H ONTABLE(D)
We now notice that one of the goals created is HOLDING(C) which was the goal we were trying to achieve by applying UNSTACK(C someblock) in this case and PICKUP(C) in the following approach. So it would appear that we have added new goals and not made progress and in terms of the A* algorithm it seems best to try the other approach.
ONTABLE(C)
CLEAR(C)
ARMEMPTY
ONTABLE(C) H CLEAR(C) H ARMEMPTY
PICKUP(C)
CLEAR(A) H HOLDING(C)
STACK (C,A)
ON(B,D)
ON(C,A) H ON(B,D) H ONTABLE(A) H ONTABLE(D)
Looking at fig 13.4 again we can see that the first goal is achieved block C is on the table. The second goal is also achieved block C is clear. Remember that HOLDING(B) is still true which means that the arm is not empty. This can be achieved by placing B on the table or planting it on block D if it is clear. Lookahead could be used here to compare the ADD lists of the competing operators with the goals in the goal stack and there is a match with ON(B,D) which is satisfied by STACK (B,D). This also binds someblock to block D. Applying STACK (B,D) generates extra goals
CLEAR(D) and HOLDING(B)
The new goal stack becomes
CLEAR(D)
HOLDING(B)
CLEAR(D) H HOLDING(B)
STACK (B,D)
ONTABLE(C) H CLEAR(C) H ARMEMPTY
PICKUP(C)
CLEAR(A) H HOLDING(C)
STACK (C,A)
ON(B,D)
ON(C,A) H ON(B,D) H ONTABLE(A) H ONTABLE(D)
At this point the top goal is true and the next and thus the combined goal leading to the application of STACK (B,D), which means that the world model becomes
ONTABLE(A) H ONTABLE(C) H ONTABLE(D) H ON(B,D) H ARMEMPTY
This means that we can perform PICKUP(C) and then STACK (C,A)
Now coming to the goal ON(B,D) we realise that this has already been achieved and checking the final goal we derive the following plan
1 UNSTACK(B,A)
2 STACK (B,D)
3 PICKUP(C)
4 STACK (C,A)
This method produces a plan using good Artificial Intelligence techniques such as heuristics to find matching goals and the A* algorithm to detect unpromising paths which can be discarded.
SUSSMAN ANOMALY
Consider the problem shown in fig 13.5 which is harder and is known as the Sussman anomaly because it was studied by Sussman in 1975.
This immediately leads to two approaches as given below
ON(A,B) ON(B,C)
ON(B,C) ON(A,B)
ON(A,B) H ON(B,C) ON(A,B) H ON(B,C)
choosing path 1 and trying to get block A on block B leads to the goal stack given in fig13.6
This achieves block A on block B which was produced by puttting block C on the table giving the diagram of fig 13.6a and the goal stack shown. The sequence of operators is
1 UNSTACK(C,A)
2 PUTDOWN(C)
3 PICKUP(A)
4 STACK (A,B)
Working on the next goal of ON(B,C) requires block B to be cleared so that it can be stacked on block C. Unfortunately we need to unstack block A which we just did. Thus the list of operators become
1 UNSTACK(C,A)
2 PUTDOWN(C)
3 PICKUP(A)
4 STACK (A,B)
5 UNSTACK(A,B)
6 PUTDOWN(A)
7 PICKUP(B)
8 STACK (B,C)
Arriving at fig13.6b we can see that block A is not on block B so that two extra operations are needed giving the final scheme
1 UNSTACK(C,A)
2 PUTDOWN(C)
3 PICKUP(A)
4 STACK (A,B)
5 UNSTACK(A,B)
6 PUTDOWN(A)
7 PICKUP(B)
8 STACK (B,C)
9 PICKUP(A)
10 STACK(A,B)
Analysing this sequence we observe that steps 4 and 5 are opposites and therefore cancel each other out, also steps 3 and 6 are opposites and therefore cancel each other out as well leaving the more efficient scheme
1 UNSTACK(C,A)
2 PUTDOWN(C)
7 PICKUP(B)
8 STACK (B,C)
9 PICKUP(A)
10 STACK(A,B)
To produce in all such cases this efficient scheme where this interaction between the goals requires more sophisticated techniques which will be considered next time.