TEACH SOLVER Steven Hardy, June 1982 This file describes a demonstration program to illustrate means-end analysis and the A* (A-STAR) heuristic search algorithm. To use the program, first do: lib solver The problem solver is set up to work on a blocks world. In this world there are five blocks on a table top. The blocks are named B1, B2, B3, B4 and B5. Blocks B1, B4 and B5 are on the table. Block B2 is on B1 and block B3 is being held in a robot hand. This world is described with in a DATABASE, thus: database ==> ** [[ontable b1] [b2 on b1] [cleartop b2] [holding b3] [cleartop b3] [ontable b4] [cleartop b4] [ontable b5] [cleartop b5]] Four actions are known to the problem solver, they are: take ?X off table place ?X on table pick up ?X from ?Y put ?X on ?Y Each of these actions has various preconditions and effects. For example, the action TAKE ?X OFF TABLE can only be done if the robot has an empty hand, if the block X has a clear top (ie nothing is on it) and if the block X is on the table. After the action is performed, certain things will no longer be true (X will no longer be on the table and the robot will no longer have an empty hand) and certain things will have become true (the robot will be holding X). The four actions are described by in a list in the variable SCHEMALIST, thus: schemalist ==> ** [[[take ?x off table] [[emptyhand] [cleartop ?x] [ontable ?x]] [[emptyhand] [ontable ?x]] [[holding ?x]]] [[place ?x on table] [[holding ?x]] [[holding ?x]] [[ontable ?x] [emptyhand]]] [[pick up ?x from ?y] [[emptyhand] [?x on ?y] [cleartop ?x]] [[emptyhand] [?x on ?y]] [[holding ?x] [cleartop ?y]]] [[put ?x on ?y] [[holding ?x] [cleartop ?y]] [[holding ?x] [cleartop ?y]] [[emptyhand] [?x on ?y]]]] It is not important that you precisely understand the format of this list. Briefly, each action is described by one element on the list. Each action is described by a four element sub-list whose components are: the 'name' of the action, the preconditions of the action, the things made false false by the action, and the things made true by the action. If you wish to know what the problem solver would do to be holding block B1, then give the command: strips [holding b1] The problem solver uses VED to display a 'picture' of its 'state of mind' as it solves the problem. It can be also be invoked whilst you are in VED. Press and then type: strips [holding b1] This is especially convenient when using the problem solver and simultaneously reading this TEACH file! There will be a VERY long pause (a minute or two) the first time you use STRIPS because the POP system has to load in a big program from the library. Don't worry that you don't understand everything that happens - just watch and when the problem solver has finished, return to this file by giving an TEACH command. The STRIPS problem solver uses means-end analysis. This means that when it is given a number of goals to ACHIEVE it first determines which of the goals that is not already true is (in its opinion) the hardest and then decides to REDUCE the task by achieving that one goal. When that has been done it reconsiders the goals and if they are not yet all achieved it selects a new one to REDUCE. To REDUCE a goal it decides which action would achieve that one goal and decides to PERFORM it. Before it can PERFORM that action, it must, however, ACHIEVES its preconditions. This recursive call of ACHIEVE might involve its own calls of REDUCE and PERFORM. The picture that is shown shows 'goal hierarchy' being considered byt he problem solver. The parts of the tree actively being considered byt he problem solver are shown in capital letters. Run the problem solver again, this time on a different problem, by pressing and typing strips [b1 on b2] This asks the problem solver how it would get block B1 onto block B2. The problem solver doesn't actually do anything (it merely makes plans) so the plan produced will be from the intial state as described earlier. Try the problem solver on all the following problems: strips [b1 on b4] strips [emptyhand] strips [cleartop b1] strips [ontable b2] strips [b1 on b2] [b3 on b4] [holding b5] strips [b1 on b4] [holding b2] strips [cleartop b1] strips [ontable b2] strips [b1 on b2] [b2 on b3] You will notice that the problem solver is not very smart about the last problem. Try the problem solver on a really hard problem: strips [b1 on b2] [b2 on b3] [b3 on b4] [b4 on b5] The problem solver can be made a bit cleverer by assigning true to the variable clever, ie: : true -> clever; This can be done in VED if you first press the button. Try the following problem again: strips [b1 on b2] [b2 on b3] It will take much longer this time. What is happening is that when STRIPS realises that is it doing something stupid (like producing a plan with a loop in it) then it backtracks to its most recent decision. This will have been either to select a particular action to PERFORM to REDUCE a goal or else it will have been to select a particular goal to REDUCE first out of a list of goals it is trying to ACHIEVE. The problem solver will also illustrate a forwward chaining search if the command ASTAR is used instead of STRIPS. Try the preceding examples again. The currently 'active' branch of the search tree is shown in capitals. The performance of ASTAR (and STRIPS to a lesser extent) is partially determined by the value of the variable LOOKAHEAD. This is initially 2; if set higher then ASTAR performs better; if set lower (but not less than zero) then ASTAR becomes more breadth-first. The package can be made to work on any problem domain by merely altering the values of DATABASE and SCHEMALIST. When providing your own SCHEMALIST the following rules must be obeyed: # Any variable in a schema must occur in the name # No two schema names must 'match' one another. The system checks the domain specification. ****** SOLVER is a complex, sophisticated program. To see how you might ****** write your own problem solver in PROLOG, see TEACH * PSTRIPS --- C.all/teach/solver --- Copyright University of Sussex 1995. All rights reserved.