TEACH NEWSOLVER Aaron Sloman Nov 1995 Revised version of TEACH SOLVER by Steven Hardy, June 1982 Introduction to classical STRIPS-like planning and problem-solving. Note: The old TEACH SOLVER was based on LIB SOLVER. This new version is based on LIB * NEWSOLVER CONTENTS - (Use g to access required sections) -- Introduction -- Using the library -- What is an operator? -- What the planner does -- The default blocksworld -- -- Default database -- -- Default operators -- Backward chaining from a goal -- Forward chaining from the database -- Search strategies -- Think about how you would solve some problems -- -- Example 1 [b2 on b5] -- -- Example 2 [b5 on b1] [b1 on b2] -- -- Example 3 [b5 on b1] [b1 on b5] -- -- Example 4 [b1 on b2] [b4 on b5] [b5 on b1] [b3 on b4] [b2 on b3] -- Using the problem solver to solve those problems -- -- Examples of the use of the program -- Changing the trace file -- -- Structure of the graphical trace -- -- achieve, reduce, and perform -- -- A simpler example -- -- A more complex example. -- Means-Ends Analysis -- Additional ways to invoke runstrips -- Improving the performance using the variable "clever" -- The ASTAR planner -- Use of the variable lookahead -- Making plans for other domains -- Possible exercises -- READING -- Introduction ------------------------------------------------------- This file describes a demonstration program to illustrate means-end analysis and the A* (A-STAR) heuristic search algorithm, in the framework employed by STRIPS, the Stanford Research Institute Problem Solver, described in many text books on AI as an example of a "classical" AI planner. The program is LIB * NEWSOLVER. In that library, several procedures and macros are made available to create plans in a hypothetical world. When the program runs, the intermediate states in construction of a plan are shown in the editor VED (unless The original design of the program was due to Steve Hardy, some time between about 1978 and 1982. It was reorganised and made consistent with current Pop-11 syntax in 1995. -- Using the library -------------------------------------------------- To compile the program, first do: uses newsolver This makes available a number of procedures for creating plans to solve problems. There will be a pause when you load the program, as it is quite a big program. The planner is set up to achieve a goal state, starting from a database describing the initial state of the world, and a set of operators for changing the world. It tries to achieve the new state by finding a sequence of operators that will transform the initial database to a state in which the goal state is true. There are two versions of the planner, one of which does a depth first search until it finds a plan. (See TEACH * TOWER, TEACH * SEARCHING). This often produces a wasteful plan which includes redundant actions. The other version uses the A* (ASTAR) algorithm to search for a more efficient plan. -- What is an operator? ----------------------------------------------- Plans a created by assembling operators into linear chains. Executing the plan involves applying the operators in sequence. (This is clearly inadequate as a GENERAL planning formalism. Why?) Each operator has four components: 1. The 'name' (or invoking pattern) of the action, e.g. [put ?X on ?Y] This is something that is not used internally in testing the operator, but is used to describe to the user which action is chosen. The variables X and Y will have their values bound as a result of the matching of some of the other patterns in the operator. A list of instances of these patterns will be used to formulate a plan. 2. A list of the preconditions of the action. These have to be made true if they are not already true, before the action can be performed. For example the above action might have a list of two preconditions: [[holding ?X] [cleartop ?Y]] If these are not already true when you wish to put X on Y, then they could define new sub-goals to be achieved in order to make the action possible. 3. A list the things made false by performing the action, This is the "delete list" for the operator. For example the action of putting X on Y could have the following delete list: [[holding ?X] [cleartop ?Y]] since both of those would become false when X is put on Y. 4. The things made true by the action. This is the "add list" for the operator). In the case of putting X on Y, the following might have to be added to the database after the action is performed. [[emptyhand] [?X on ?Y]] For more on such operators read about STRIPS in AI text books. -- What the planner does ---------------------------------------------- When you give the system a goal, a database, and a list of operators the planner looks to see if the goal description is already true in the database. If not, for each statement in the goal description which is not yet true, it looks to see if there is an operator whose add list includes something matching that statement. Then applying that operator could achieve the goal. However, if the operator has preconditions, it is necessary to check whether those preconditions are satisfied. If not, they determine new sub-goals. So the planner has to find a way of achieving the unsatisfied preconditions. In general there will be alternative ways of making a particular goal or subgoal true, and not all of them will be consistent with possible ways of solving other goals. So the problem solver will have to search for a sequence of operators which can be applied to solve the complete set of goals. This then becomes a standard state-space searching problem. From this description it should be clear that the general sorts of mechanisms described in TEACH * TOWER and TEACH * SEARCHING could be used to find plans to achieve a list of goals. LIB * NEWSOLVER provides mechanisms tailored specifically to problems posed in the format described here, i.e. using operators with precondition lists, delete lists, and add lists. -- The default blocksworld -------------------------------------------- The procedure blocksworld is defined to provide a default initial 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 within a DATABASE. There are also operators for manipulating the world. Each operator corresponds to a type of action, e.g. picking something up, putting something down, moving something, etc. The planning task consists of finding a sequence of applications of these operators to achieve some goal, given the initial state. Four operators are known initially to the problem solver, though you can define others, 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). You can set up an initial sample database, and a list of operators, by means of the command. blocksworld(); This assigns values to the two variables, database, and operators. -- -- Default database You can examine the initial state of the world thus: database ==> ** [[ontable b1] [b2 on b1] [cleartop b2] [holding b3] [cleartop b3] [ontable b4] [cleartop b4] [ontable b5] [cleartop b5]] This state is used as the default initial state for all the examples which follow. It can be depicted roughly as follows: || /[B3]\ [B2] [B1] [B4] [B5] =========================== You can change the state by assigning a different list in the appropriate format to database. -- -- Default operators The four default operators, their preconditions, delete lists, and add lists, can also be printed out: operators ==> ** [[[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]]]] For example the fourth operator has 1. Invoking pattern (or name) [[put ?X on ?Y] 2. Precondition list [[holding ?X] [cleartop ?Y]] 3. Delete list [[holding ?X] [cleartop ?Y]] 4. Add list [[emptyhand] [?X on ?Y]] -- Backward chaining from a goal -------------------------------------- Thus if one has a goal that is something like [b4 on b2] then that operator is potentially relevant because an item in its addlist matches that goal. Selecting that operator for that purpose would then create two new sub-goals by instantiating the precondition list: [holding b4] [cleartop b2] These two could then be used to find relevant operators with matching items in their add lists. Thus one could search backward from the goal to find a succession of operators until one finds operators whose preconditions are already true in the database. This is a backward chaining procedure and it can involve a lot of searching. -- Forward chaining from the database --------------------------------- A forward chaining search will start from the items that are already true (i.e. already in the database), and compare them with the preconditions of the operators. This will provide a set of applicable operators. E.g. by matching that last precondition list [[holding ?X] [cleartop ?Y]] with the database, we find that we could have X = b3 and Y = b5. (There are other options for Y). So if we applied the operator, the delete list would be instantiated to [[holding b3] [cleartop b5]] and the add list would be instantiated to [[emptyhand] [b3 on b5] ] Applying these would change the database to something like this [[emptyhand] ;;; new [b3 on b5] ;;; new [ontable b1] [b2 on b1] [cleartop b2] [cleartop b3] [ontable b4] [cleartop b4] [ontable b5]] So you could then find which operators now have their preconditions satisfied, and see what would happen if you applied them. This procedure involves chaining forward from the initial state until you find a sequence of operators that makes the complete list of goal lists true. -- Search strategies -------------------------------------------------- There are various ways you could do backward chaining or forward chaining to find a sequence of operators that solves a problem. If you consider all branches at each stage then that can amount to a breadth first search. It allows you to find the shortest route to a solution, but can be very costly in space required to store all the branches. If you select one branch at each stage and explore it as far as possible before returning to try other options (if the first branch fails to lead to the goal) then that constitutes depth first search. There are many different types of "heuristic" search in addition to breadth first and and depth first search. (See TEACH * TOWER, TEACH * SEARCHING). [Note computer scientists should be able to think about the space complexity and the time complexity of the different strategies.] One of the strategies that combines breadth first search with a heuristic for pruning the number of branches considered is called the A* or A-STAR heuristic. It is described in most AI text books (e.g. P.H. Winston 3rd Edition, Russell and Norvig). The newsolver library program includes both a depth first backward chaining procedure called runstrips, and a forward chaining procedure based on the A* algorithm, called runastar. A later section shows you how to try them out. -- Think about how you would solve some problems ---------------------- Before proceding look closely at the initial database and the list of operators and consider how you would achieve the following: -- -- Example 1 [b2 on b5] Write down the sequence of operators that would have to be applied, and in each case specify the values of the variables involved. The answer might be something like: Step 1 [place b3 on table] use operator 2, with X = "b3" preconditions: [holding b3] delete: [holding b3] add: [ontable b3][emptyhand] Step 2 [pick up b2 from b1] use operator 3 with X = "b2", Y = "b1" preconditions: [emptyhand] [b2 on b1] [cleartop b2] delete: [emptyhand][b2 on b1] add: [holding b2][cleartop b1] Step 3 [put b2 on b5] use operator 4 with X = "b2" Y = "b5" preconditions: [holding b2][cleartop b5] delete: [holding b2][cleartop b5] add: [emptyhand][b2 on b5] Check that in each step all the preconditions are true, either because they were true initially and have not been made false, or because they have been made true by an earlier step, and not made false subsequently. -- -- Example 2 [b5 on b1] [b1 on b2] Here the goal description includes TWO subgoals, both of which are to be made true after the execution of the complete plan. I.e. a state of the database must be achieved in which both are true. It will not suffice to make the first one true and then perform some actions that make the second one true, in the process undoing the first one. This example is much more complicated than the previous one. Try to devise a sequence of operators that will achieve this combination of goals, also starting from the initial database. Make sure in each case that the preconditions of the operator are true. Try to keep a note of how you search for a solution to this problem. If you find yourself going down blind alleys, or going round in circles, consider how you detect this situation and how you remedy it. Think about the benefits or disadvantages of forward chaining vs backward chaining for solving these problems. -- -- Example 3 [b5 on b1] [b1 on b5] What should a problem solver do about this? Compare the following: -- -- Example 4 [b1 on b2] [b4 on b5] [b5 on b1] [b3 on b4] [b2 on b3] -- Using the problem solver to solve those problems ------------------- Make sure the library is loaded: uses newsolver; There are two problem-solvers, one called runstrips, which performs a basic depth-first search, and one called runastar, which performs a more elaborate search based on the A* algorithm. Each can be invoked via a procedure called runsolver, which takes four arguments: 1. a problem-solver procedure (runstrips or runastar), 2. a list of of goals, each goal represented as a list 3. an initial database, 4. a list of operators. runsolver returns the plan, if it is able to find one, otherwise false. It runs the problem-solver procedure in such a way as to use the editor, VED to display the intermediate stages of construction of a plan. -- -- Examples of the use of the program For example, in order to see how the runstrips procedure achieves the goal of Example 1, i.e. [b2 on b5] do the following either by compiling the commands in this teach file, or preferably by first copying them to your output.p file ;;; set up the lists database and operators blocksworld(); runsolver(runstrips, [[b2 on b5]], database, operators) ==> This will display the process of creating a plan. At the end the plan is returned as a result, and is printed out, namely ** [[place b3 on table] [pick up b2 from b1] [put b2 on b5]] The trace of the planning process will go into a file called 'tree.p'. If the file has been obscured by the output file, you can used VED to make it visible, e.g. by doing ENTER ved tree.p or using one of the means of switching between VED buffers (e.g. ESC e). -- Changing the trace file -------------------------------------------- If you wish you can use a different trace file by assigning a different filename (which must be a string) to the variable picture_file. E.g. 'stripstree.p' -> picture_file; As the trace is produced the program repeatedly pauses waiting for you press the RETURN key. (If you wish it to continue without pausing any more, press "c" instead.) The trace file will be saved on disk, like any other VED file. If you wish to prevent that do the following before you run the program. false -> save_picture_file; To make it save the files, do the following before running the program. true -> save_picture_file; The picture file is an ordinary VED file, except that it contains special `graphic' characters which make it look nice in an Xterm window or Xved window. You can turn it into a printable file by doing ENTER printify You will need to do this before you try printing the file or incorporating it in a printable file, as the graphic characters cannot be printed. The next section of this file was produced using the printify command. -- -- Structure of the graphical trace The trace is a tree showing the structure of the current search for a plan. It grows and changes as the plan is being created and eventually looks something like this (except that VED's line graphics characters are used to make it look nicer). achieve [b2 on b5] \- reduce [b2 on b5] |- achieve [holding b2] [cleartop b5] | \- reduce [holding b2] | |- achieve [emptyhand] [b2 on b1] [cleartop b2] | | \- reduce [emptyhand] | | \- perform [place b3 on table] | \- perform [pick up b2 from b1] \- perform [put b2 on b5] Notice the use of the labels "achieve" "reduce" and "perform" in the planning tree. -- -- achieve, reduce, and perform In the depiction of a planning tree: "achieve" indicates one or more goals or subgoals that had to be achieved. "reduce" indicates a goal from an achieve list that could not be achieved directly, but had to be reduced to a list of sub-goals. These sub-goals are determined by the preconditions of an operator capable of making the goal true: the operator can be run only if its preconditions are made true, so that they become new sub-goals to be achieved. There may be different ways of reducing a particular goal. "perform" indicates that an action can be performed directly because its preconditions are already true when it is performed. This may be because previous actions have made them true. Thus perform actions have no subgoals shown in the diagram. Also performing an action always has the effect of making true a reduce sub-goal. When all the reduce subgoals of an achieve list have been made true, then the list of goals has been achieved. Summary: A goal is achieved by "reduce"ing it. This means linking it to other subgoals via an operator which achieves the goal, and whose preconditions are those other subgoals. "Perform" labels actions that are performed directly. While the program is running the graphical display uses upper case to show goals that have not yet been achieved. -- -- A simpler example Here is a simpler example to try. See if you can construct its planning tree before the program does, then check yours against the program's. runsolver(runstrips, [[holding b2]], database, operators) ==> ** [[place b3 on table] [pick up b2 from b1]] -- -- A more complex example. runsolver(runstrips, [[b1 on b2][b2 on b3]], database, operators) ==> ** [[place b3 on table] [pick up b2 from b1] [place b2 on table] [take b1 off table] [put b1 on b2] [pick up b1 from b2] [place b1 on table] [take b2 off table] [put b2 on b3] [take b1 off table] [put b1 on b2]] Remember, you can look back at the VED picture file using ESC e (fileselect). This one produces a plan that works, but is seriously redundant, because it includes steps that undo previous steps that were wasteful. How could you fix the planner to avoid producing such plans? The library provides another problem solving procedure that does better, using the A*, or ASTAR algorithm, described in many textbooks of AI, and described below. -- Using the program without the graphical tracing. ------------------- If you wish to run the procedure runstrips or runastar without the graphical interaction and without any pausing, do the following: false -> draw_solving; ;;; no picture to be drawn true -> no_show_plan; ;;; don't print out plan at end vars plan; runstrips([[b1 on b2][b2 on b3]], database, operators) -> plan; Then you can print out the plan (or make some other use of it): plan ==> Similarly with runastar: vars plan2; runastar([[b1 on b2][b2 on b3]], database, operators) -> plan2; plan2 ==> To make it interactive again, do this before running the command. true -> draw_solving; -- Means-Ends Analysis ------------------------------------------------ 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 by he problem solver. The parts of the tree actively being considered by the problem solver are shown in capital letters. -- Outline of the runstrips procedure --------------------------------- You can think of the algorithm used by the runstrips procedure as being approximately like this, though there are complications in the library version, to allow the nice graphical tracing in the editor, and other details, like building up a plan description. define runstrips(goals, database, operators); lvars goals, operators, plan; lvars current, plan_tree, treenumber, states_to_explore; dlocal database; ;;; Set up a list of possible states, the initial one being ;;; a state in which the given goals are to be achieved [[achieve ^goals]] -> states_to_explore; repeat if states_to_explore == [] then report('COULD NOT ACHIEVE GOALS'); return(); endif; ;;; Get the first possble plan tree to try to expand, ;;; saving the others in case this one fails destpair(states_to_explore) -> (plan_tree, states_to_explore); ;;; check if there are unachieved sub-goals that need to be ;;; achieved, by expanding the plan_tree expand_state(plan_tree, plan) -> plan_tree; if no_more_goals then report('GOALS ACHIEVED'); showplan(plan_tree); return(); endunless; ;;; Find alternative possible ways of expanding the plan tree ;;; and add them to the list of possible trees to expand [%strips_expand(plan_tree)%] <> states_to_explore -> states_to_explore; endrepeat; ;;; report failure enddefine; The runastar procedure uses a different structure because it basically chains forward from the database instead of chaining backward from the goals. -- Additional ways to invoke runstrips -------------------------------- Trying other examples: You can try additional examples. In VED, instead of runsolver(runstrips, [ ...], database, operators) ==> you can type on VED's command line. ENTER strips .... where the individual goals are enclosed in square brackets. E.g. ENTER strips [b1 on b2] [b2 on b1] Note: if you try those two goals, you will find that the program gets stuck in an endless loop. A possible part of a project would be to fix this. Compare ENTER strips [ontable b2] [b3 on b2] When you invoke strips in this mode, the final plan is printed in the picture file, but is not displayed separately or returned as a result. You can also run "strips" as a Pop-11 macro procedure in the VED buffer. E.g. copy this line to your output.p file, and the mark and load it (or use ESC d to load one line): strips [b2 on b5] ** [[place b3 on table] [pick up b2 from b1] [put b2 on b5]] This creates the planning window, and also prints out the successful plan. Try some more examples. 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 ENTER-TEACH command. Run the problem solver again, this time on a different problem, by giving the commnd: strips [b1 on b2] or ENTER 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] If you get bored with all the pausing, type "c" to continue. -- Improving the performance using the variable "clever" -------------- The problem solver can be made a bit cleverer by assigning TRUE to the variable CLEVER, ie: true -> clever_solve; Try the following problem again: strips [b1 on b2] [b2 on b3] It will take longer this time, but it will produce a better plan. What happens with clever_solve set true, 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 ASTAR planner -------------------------------------------------- The problem solver can perform a forward chaining heuristic search instead of the depth first search, if the procedure runastar is used instead of runstrips. Try the preceding examples again, with the runastar procedure, e.g.: false -> clever_solve; runsolver(runastar, [[b1 on b2][b2 on b3]], database, operators) ==> As before, the currently 'active' branch of the search tree is shown in capitals, except possibly for the final step. Even with clever_solve set false, this finds the sensible plan, and much faster than runstrips. Here are some more examples to try: runsolver(runastar, [[holding b2]], database, operators) ==> runsolver(runastar, [[b1 on b2]], database, operators) ==> runsolver(runastar, [[b1 on b2][b3 on b1]], database, operators) ==> The ENTER astar format can also be used ENTER astar [b3 on b1] Or the macro "astar" can used with vedloadline (ESC d): astar [b5 on b3] [ontable b3] astar [ontable b3] [b5 on b3] astar [ontable b2] [b5 on b2] But why does this one take so long (in the same initial state)? astar [b1 on b3] [ b2 on b1] And this: astar [ b2 on b3] [b3 on b1] If you get fed up with all the pauses, you can press "c" instead of RETURN, after which it will stop pausing, and continue to the end. -- Use of the variable lookahead -------------------------------------- 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. -- Making plans for other domains ------------------------------------- The package can be made to work on any problem domain by merely altering the values of DATABASE and OPERATORS. When providing your own OPERATORS the following rules must be obeyed: (1) Any variable in a schema must occur in the name (2) No two schema names must 'match' one another. The system checks the domain specification. -- Possible exercises ------------------------------------------------- 1. Explore ways of applying the library to solve some planning problems in some domains other than the blocks world, e.g. the river crossing problem (TEACH RIVER) or the tower building problem (TEACH TOWER) or a route-finding problem. Analyse any weaknesses of the program in solving your problem and see if you can come up with some ideas as to possible remedies (perhaps on the basis of some reading about planning systems.) HARDER: 2. Some of the plans produced by runstrips include redundant actions. Try to define a procedure which takes such a plan, analyses it, and produces an improved plan. 3. Try implementing your own version of either runstrips or runastar or some variant that does some other kind of heuristic search. You may find useful the techniques described in TEACH * SEARCHING 4. Try extending the operator format, either in your own version, or by modifying the code in LIB NEWSOLVER, so that in addition to the four components listed above (action pattern, preconditions, delete list, add list) each operator has a fifth (possibly empty) component a list of presuppositions. These are conditions which must be true for the operator to be applicable, but the system never tries to make them true if they are false. So they are treated differently from the precondition list. 5. Try to make the program more intelligent at dealing with blocks world problems, by tackling harder problems before easier ones. E.g. it's easier to achieve [emptyhand] goals than [?X on ?Y] goals. (Suggested by Manfred Kerber.) Why is it better to tackle harder problems first? One way to do the ordering is to associate weights with operators representing their difficulty and then have the planner use those weights in selecting goals to work on. Another way is for the database to have explicit information about which sorts of tasks are easier than which others, which may depend on the conditions. This would be more flexible, but harder to implement. 6. Can you make the program try to recognize towers and plan to build them from the bottom up, no matter in which order the goals are presented. E.g. this would prevent the redundant plan produced by this example: strips [b2 on b3] [b3 on b4] [b5 on b2] Is it possible to express in some general way what kind of knowledge we use in building things from the bottom up? Is it peculiar to stacking blocks, or is this an instance of some more general strategy that you could implement? (E.g. seeing which goals require actions which could interfere with other goals, and then doing them first. See G.J.Sussman's HACKER program, described in several AI text books and in his book.) 7. Can you make the system learn, so that having solved a problem it adds a new operator to the list of operators which can in future be used directly (by running the plan) without having to repeat the planning. You'd have to give the new operator an add list including the problem previously solved, and preconditions analogous to the initial situation in which it was solved. This requires finding an appropriate generalisation of the task. (Read about ABSTRIPS and NOAH ....) 8. Try to modify the system to cope with incomplete plans, where only partial information is available. E.g. the plan could solve part of the problem, leaving further details to be completed after the partial plan has been executed. (We often do that in real life.) VERY DIFFICULT: 9. What about planning in situations where actions don't have definitely predictable results, but only a probability of success (e.g. what are the probabilities of a train not reaching its destination on time, a car being held up on the motorway, a ship not sailing because of strikes, a bullet not hitting its target etc.) -- READING ------------------------------------------------------------ To be added See the sections on planning, searching, and the A* algorithm in standard text books on AI, including Winston, P.H. (1984 - 3rd edition 1992). Artificial Intelligence Reading, Mass: Addison-Wesley. Stuart Russell & Peter Norvig (1995) Artificial Intelligence, A Modern Approach. Prentice Hall. Charniak, E & McDermott D, (1985) Introduction to Artificial Intelligence Addison Wesley and others. Also: Sussman, G.J. (MIT Phd Thesis) A Computational Model of Skill Acquisition American Elsevier, 1975. For people familiar with Prolog: This is a complex, sophisticated program. To see how you might write your own problem solver in PROLOG, see TEACH * PSTRIPS --- $poplocal/local/teach/newsolver --- Copyright University of Birmingham 1995. All rights reserved. ------