filename: Pweak_info (version alpha-16) -- Created 20/Apr/94 -- Updated 12/Feb/98

This is an information file for the (simple) planning system "Pweak".  This 
file contains french accents and other special characters which may not be 
displayed nor printed correctly on non-apple Macintosh machines.  These 
characters are here below placed between " and ":

      Macintosh         LaTeX             HTML
        "¥"             \bullet           
  • "±" \pm "" \c{c} "ç" "ƒ" \'{E} "É" "Ž" \'{e} "é" "" \`{e} "è" "”" \^{\i} "î" "š" \"{o} "ö" "¯" \emptyset "Ø" "³" \geq "Ã" \sqrt{~} "Â" \neg "ª" author's name : ƒric Jacopin current e-mail : ejacopin@acm.org current fax number: +33 01 44 27 70 00 Acknowledgements :---------------------------------------------------------- Thanks to Mike Brady (Trinity College, Dublin, Ireland) for his great help on Open Prolog. Thanks to Claude Le Pape (Bouygues, Saint-Quentin en Yvelines, France) and Jean-Franois Puget (ILOG, Gentilly, France) for their help on Pweak and planning. Thanks to Mark Drummond (NASA Ames, USA), Bertram Fronhšfer (Technical University, Munich, Germany) and Subbarao Kambhampati (Arizona State University, Tempe, USA) for helpful discussions about planning. Special thanks to Philippe Morignot (Ilog, France), Pierre Regnier (IRIT, Toulouse, France) and Sylvie ThiŽbaux (IRISA, Rennes, France) for planning interactions. Thanks to FredŽric Bidaud and Brigitte Lamare (IRIT, Toulouse, France), first (forced) Pweak testers. Thanks to Jacqueline Zizi for her help on Mathematicaª. And thanks to Ramana Rao (Xerox PARC, USA) for making me aware that "there is so much need for development" and interacting with me about visualization. File contents :============================================================ ("¥" denotes a section while "¥¥" denotes a subsection) ¥ Introduction ¥ What is Pweak? ¥ Requirements ¥ Installation ¥¥ Contents of the Pweak folder ¥¥ Upgrading from an older version ¥ World language ¥ Action language ¥ Planning problem ¥ Plan language ¥ Plan existence problem ¥¥ Complexity of the plan existence problem ¥ Solution to the plan existence problem ¥ Plan modification operators (plan construction) ¥¥ Definition (what the plan modification operators are) ¥¥ Semantics (applicability of plan modification operators) ¥¥ Movements (how Pweak chooses to apply plan modification operators) ¥¥ Precondition achievement ¥ Running Pweak on examples ¥¥ Plan existence tuples ¥¥ Adding your examples ¥¥ What options for which planners? ¥ Tracing Pweak ¥ Pweak's user files ¥¥ The 'configurations' file ¥¥ The 'constraints' file ¥¥ The 'examples_list' file ¥¥ The 'preferences' file ¥ Known bugs References (books, published articles, internal technical reports, manuals, etc) can be found at the end of some sections. References begin with the three characters [*] (thus, searching for [*] in this document is searching for the references). ¥ What is Pweak? :========================================================= Pweak is a planning system written in Prolog which is designed to help testing classical non linear planning procedures (positive atomic formulas, Strips action description, a plan is a partial order, plan modification planning is in the partial plan space). Not only can you simulate the usual planning procedures of the literature (such as Tweak, SNLP, UA and others) but also you can degrade those procedures in selecting some parts of them, or else combine options in order to get new procedures. To simulate a non linear planning procedure, menus and dialog boxes are provided. Search can be selected for one, all or a certain number of solutions. Solutions can be automatically saved in a file together with some tracing informations. Options can be pre-selected from a preferences file. User-constraints are possible. A Mathematicaª package is provided to analyze and visualize the search space visited by the planning procedures that have been simulated. More than 30 examples (from the literature and others) are provided. Pweak is copyright ©1994Ñ1998, ƒric Jacopin. The Pweak planning system should be considered as a free research domain software. This 'free research domain software' here has the following meanings: 1. Pweak's code can contain programming and conceptual bugs, mistakes, errors, and is not to be considered as reliable. 2. Successive versions of code, examples and file formats are assumed to be incompatible. 3. Inclusion of a reference to Pweak is a must to any publication (e.g. paper, report, manual) of any work related to Pweak (e.g. research, course, programming project). 4 The Pweak software or any part of it cannot be used for commercial purposes (by the way, who would want of such a buggy code ;-). As long as you accept and respect the four previous points, you can do anything you like with the Pweak software. ¥ Introduction :=========================================================== This (simple) planning procedure simulator is written in Prolog. The dialect is Open Prolog, a nice freeware (Edinburgh-like) prolog for the Apple Macintosh, which provides menu and window predicates for this machine. I henceforth refer to the planning system as "Pweak". Pweak was originally designed in 1990 on an Acorn A310 machine running under Prolog_X with 4Mb, and fitted with a 35MHz ARM 3. Pweak ran during weeks (non-stop) on this machine. My A310 still is a fantastic machine; but Open Prolog is a great freeware prolog for the Mac. In this information document, I have tried to do my best so that no knowledge of prolog is needed; if you ever think this is not the case, please tell me. Anyway, you can refer to informations provided with Open Prolog. Some knowledge of artificial intelligence classical planning is needed. You will find some basics in this file, but don't hope too much. [References] Collection of articles about planning? [*] "Readings in Planning", Edited by James ALLEN, Jim HENDLER & Austin TATE, Morgan Kaufmann (1990), 754 pages. ISBN 1-55860-130-9 Beginning with Prolog for Artificial Intelligence? [*] Ivan BRATKO, "Prolog Programming for Artificial Intelligence", Addison-Wesley (1986). I use the french edition (1988), 445 pages, ISBN 2-7296-02321 and I like it. A second edition exists, apparently only in english. Gentle introduction to Artificial Intelligence through Prolog? Contains a description of Strips and means-ends analysis. [*] Peter SCOTT & Rod NICOLSON, "Cognitive Science Projects in Prolog", Lawrence Erlbaum Associates (1991), 277 pages. ISBN 0-86377-182-3 Nth steps in Prolog? [*] Richard O'KEEFE, "The Craft of Prolog", MIT Press (1990), 387 pages. ISBN 0-262-15039-5 ¥ Requirements :=========================================================== In order to use Pweak, you must have: An Apple Macintosh with system 7 or later and at least 4Mb of memory. Of course, the more powerful the processor, the better. Although really slow, a Macintosh LC is enough to begin. Since Open Prolog runs under system 6, this system should be enough to run Pweak; accordingly, since Open Prolog runs on PowerPC Macs in emulated mode, so does Pweak on these machines. However, I still have to test this. A copy of Open Prolog. Open Prolog is available from http://www.cs.tcd.ie/open-prolog/ in ".hqx" format. Now that Pweak uses the dialog features of Open Prolog, the needed version is 1.0.3d38 (and later, I hope); I myself use Open Prolog 1.0.3d38 to develop Pweak. The Pweak server (address below) provides a version of Open-Prolog always compatible with Pweak. A copy of Pweak. Pweak is available from http://www-poleia.lip6.fr/~jacopin. Actual Pweak version is 0.91d2 (i.e. it still is under development; however, it runs on all of the examples that can be loaded within Pweak). There, you can find Pweak's Releases_Notes file in HTML format, Pweak's Pweak_info file in ascii format and where to reach me; note you can get both Pweak and a compatible version of Open-Prolog from there. Note that the Pweak pages also contain numerous pointers related to artificial intelligence planning. ¥ Installation :=========================================================== Please, completely read this section before installing Pweak. Once ftp-retrieved, files must be transformed into usual Macintosh folders. Both Open Prolog and Pweak are compacted to a self-extractable archive and then converted to hexadecimal to facilitate network transfer. You must therefore convert back to binary and then decompact these files in order to use Open Prolog and Pweak. Freeware "Stuffit Expanderª" will do these conversion and decompaction automatically; just drag and drop the ".hqx" file on the "Stuffit Expander" icon. Freeware "BinHex 4.0" will convert the ".hqx" file into a binary self-extractable archive: to decompact it, just double-click on the file. "Stuffit Expanderª" and "BinHex 4.0" can be found on any classical anonymous ftp site (sumex-aim.stanford.edu and its mirrors). Pweak and Open Prolog do not fit together on the same 1.44Mb floppy. IF you wish to do so, you'll have to delete some files; for instance, you may wish to delete the Mathematica files of Pweak contained in the :Pweak:Tools folder. You can also delete the documentations files of both Pweak and Open-Prolog. To install Pweak on your hard disk, with at least 5Mb of free space, copy, where you wish it, both the Open Prolog folder and the Pweak folder. Reserve 2048 Kb of memory in the Apple-I info box of Open Prolog (to get this box, select the finder, click once on the Open Prolog icon and select 'Information' in the 'File' menu). Pweak shall not load into 1024Kb (i.e. 1Mb) of memory. Moreover, 2Mb is necessary to run Pweak on most examples. If you look for information about Open Prolog, open the Open Prolog folder. The "Beginners - look in here" folder contains a "Getting Started" file in Microsoft's Word format; and the "Documents" folder contains extra information. To load Pweak (and automatically load Open Prolog), open the Pweak folder and then double-click on the file named "Open Prolog Worksheet". This first loads Open Prolog and then Pweak. Once loaded, the righmost menu item in the menu bar should be "Pweak"; also, the version of Pweak and the date I packaged it should be written in the Open Prolog Worksheet. IF doucle-clicking on the file named "Open Prolog Worksheet" in the Pweak folder does not load Pweak but prompts a dialog box saying that the application that created this document is impossible to find (and then proposing to open it with TeachText) THEN you must rebuild your desktop so that Open Prolog documents are taken into account. To rebuild your desktop, press both the apple and option keys and restart your Macintosh; press apple-option until a dialog box asks you if you really want to rebuild your desktop; either click 'Ok' or hit the enter key. Once the desktop is rebuilt, doucle-clicking on the file named "Open Prolog Worksheet" in the Pweak folder should load Pweak correctly. When, in the window titled "Open Prolog Worksheet" one can read the following (or about): Pweak 0.90d12 (released on Monday, November 21st, 1997) is ready to go. You are then ready to use the planning system. IF you experience ANY problem THEN do not hesitate to contact me (email is ejacopin@acm.org). ¥¥ Contents of the Pweak folder :------------------------------------------ The Pweak folder contains the following folders: "Configurations" contains files that configure Pweak so that it can simulate a particular planning procedure. "Documents" contains informations files about Pweak (this file and another about what I'd like to add to Pweak). "Problems" contains planning problem files as well as an example file template. "Solutions" shall contain auto-saved files. DO NOT remove this folder. "Sources" contains all the source files of Pweak. "Tools" contains Mathematicaª files to visualize the partial plan space of a problem. "User" contains user definitions; for instance, constraints, the examples_list file and the preferences file. The Pweak folder contains the following files: "Open Prolog Worksheet" where to double-click to load Pweak. "Open Prolog Startup" tells Open Prolog to load source file ":Sources:Pweak_mac_loader" at startup. "Read_Me" says where to double-click to load Pweak and Open Prolog. "Releases_Notes" tells you everything you should know about previous released versions of Pweak. ¥¥ Upgrading from an older version :--------------------------------------- If you did not customized Pweak's prolog code, THINK of the solutions files you may have saved in the :Solutions folder and would like to keep. Once you have placed your solutions files in a safe place, just trash the Pweak folder and copy the new version. THINK also of the Mathematicaª files you may wish to keep. Gee. If you customized Pweak's code, what can I tell you? Check the Releases_Notes file and see what has changed and try to update the files accordingly. Good luck! Anyway, if you have any problem or want to see your code incorporated, do not hesitate to contact me. ¥ World language :========================================================= For Pweak, the world is made of (a potentially infinite number of) states. Sets of formulas describe a state of the world. Formulas are positive first order logic atomic formulas: predicates whose parameters are terms; a term is either a constant symbol, a variable or a function term. A constant symbol is a string of characters (the first character cannot be a number and letters must be lower case). A variable is any string of characters (the first character must be a capital letter or else the underscore "_"); a variable can be attributed from a set of constants called its universe. We shall note U(X) the universe of the variable X. A symbol is any constant symbol. The number of parameters of a function symbol is its arity; a n-ary symbol is a symbol with n parameters. A function term is made of a n-ary function symbol and n terms (i.e. n arguments that can be terms again). Symbols with arity n are noted symbol/n. For instance, table is a constant whereas Table and _table both are variables. If succ/1 is a function symbol with arity 1 then succ(2), succ(X) and succ(succ(1)) are function terms. A predicate is made of a n-ary predicate symbol and n terms. For instance, if clear/1 is a predicate symbol of arity 1 then clear(table), clear(Block) both are predicates (note that in the first case, the argument is a constant whereas in the second case it is a variable). They also are non negated (i.e. positive) atomic formulas. The semantic attached with formulas is that of membership: if a formula is a member of a set describing a state of the world, then it is true; it is false otherwise. Assume that "a", "b" and "c" are three 0-ary predicate symbols. Then the set {a,b} makes both "a" and "b" true and "c" false in the state that this set desribes. The world is a set of sets of formulas. It also is a subset of the power set of the set of all possible sets of formulas. As before, consider the only three possible formulas "a", "b" and "c". Then there are eight different sets from the set {a,b,c}: {¯, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}} where ¯ reads as the empty set. The world is a subset of this set in the sense that maybe the sets {a,b,c} and {a} describe an impossible state of the world; then, {¯, {b}, {c}, {a,b}, {a,c}, {b,c}} describe the world. Note that in the situation described by ¯, all the possible formulas are false. Later, I shall refer to lists. These are basic syntactic sugar: list ::= "[" element_enum "]" element_enum ::= element {"," element}* For instance, "[clear(X),next_to(robot,door),wired]" is a list. [References] A brilliant and pedagogical book on logic? [*] Dirk VAN DALEN, "Logic and Structure", Universitext Series, Springer Verlag (1983), 207 pages (ISBN 3-540-12831-X). Why "atomic formulas only" for classical planning? [*] Vladimir LIFSCHITZ, "On the Semantics of Strips", in: "Reasoning about Actions & Plans", Proceedings of the 1986 Workshop, Timberline, Oregon, Michael Georgeff and Amy Lansky (Eds), Morgan Kaufman (1987), pages 1--9. Can also be found in: "Readings in Planning", James Allen, James Hendler and Austin Tate (Eds), Morgan Kaufman (1990), pages 523--530. Atomic formulas? You mean that one can use functions symbols? [*] Eric JACOPIN, "A Look at Functions Symbols and Planning", AAAI Technical Report SS-93-01, AAAI Press (Palo Alto, 1993), pages 62--66. ftp://ftp.lip6.fr/lip6/softs/poleia/pweak/.html/papers.html ¥ Action language :======================================================== An action allows to move from one state to another. Note that it is an assumption that this move is instantaneous. Since sets of formulas describe the states of the world, an action allows to move from a set of formulas to another; thus possibly making some formulas false (the deleted formulas, the ones which are not member of the set which is reached) and some true (the added formulas, the ones which are member of the set which is reached). Consequently, an action can be seen as the couple of sets where the first set is where an action is applied and the second is the result of the application of the action. The first set is called the preconditions set and the second set, the postconditions set. Assume that ({a,b},{b,c}) is a couple describing an action. Then to move from the set {a,b} to the set {b,c}, one must delete the element a from the set {a,b}, resulting in the set {b}, and then add the element c to the set {b}, resulting in the set {b,c}. Note that adding c first and only then deleting a does not change the resulting set. In order to be practical, an action description is a triple where the postconditions set is split into a deleted set and an added set. Thus the resulting situation {b,c} = ({a,b} \ {a}) U {c}. Where \ is the set difference and U is the set union and the action description triple is ({a,b},{a},{c}). So that either the set-union or the set-difference can be computed in any order, the intersection of the deleted set with the added set must be empty. Practically, this says that an action cannot make a formula both true and false at the same time. Although it indeed takes some time to compute set-union and set-difference, theoretically, these are timeless: in theory, it takes no time to compute those set operations. And a formula cannot be added and deleted at the same time. It is then considered that a formula cannot belong to both sets. Note that this corroborates the assumption of the instantaneous move from one world state to another. A last point about the preconditions set. Consider the triple ({a,b,c},{a},{c}) which allows to move from the set {a,b,c} to the set {b,c}: {b,c} = ({a,b,c} \ {a}) U {c}. Note that classical notion of set does not allow mutliple occurences of elements: {b,c} U {c} = {b,c} (and not {b,c,c}). This triple reaches the same set than ({a,b},{a},{c}). But they differ only from the preconditions set; both the deleted and added sets are the same. In fact, one considers that an action triple is applicable to any situation to which its preconditions set is included. Consequently, if the preconditions set of an action is empty then it is applicable to any situation of the world. If an action triple contains variables then one must assign a value before computing the union and difference. Thus, there exists an instantiation function attributing a constant of its universe to a variable: i : {X| X is a variable of the World language} --> U(X) X --> i(X) = c One can now begin to define a result function. Let s be a state description and ad = (P,D,A) be an action description (or, an operator) whose variables have been instantiated. The result function takes an operator and a situation as arguments and returns a situation: result : O x S --> S (ad,s) --> r = result((ad,s)) with the following rules to compute the resulting state r: result(ad,s) = (s \ D) U A if P is a subset of s. result(ad,s) = s if P is not a subset of s. An operator is always applicable in a situation description s. If its preconditions set is included in s then the result function above gives the application of the operator to the situation description s. If an operator is not applicable to a situation, it acts as an identity on s (i.e. s remains unchanged under the application of an unapplicable operator). Note this prevents from seeing the set of operators as a group acting on the set of states: indeed several actions could act as identity whereas a group structure requires the identity action to be unique... First, here is an example of an action description understandable for Pweak (/* and */ denote beginning and end of comments -- action description taken from example file 'Sussman anomaly'): define(action(chapman::newtower),domain(blocks_world), comment('Take a block off a tower atop the table'), body(parameters::(X,Z:box), constraints::[neq(X,Z)], precondition::[on(X,Z),clear(X)], positive_effect::[on(X,table),clear(Z)], negative_effect::[on(X,Z)])). All fields use :: to separate the field identifier from content. An action description thus is a structure with 3 fields in which action description data is stored. In particular, the third field contains the Strips action description usual fields: precondition, add and delete lists. The parameters field contains the list of the variables used in the action description and the universes in which they take their values. The Header field has the following syntactic form (recall that characters or strings between " and " below must be exactly typed in; expressions between [ and ] are optional; expressions between { and }* can be repeated as many times as desired, in the order specified in the parenthesis): identifier = constant_symbol variable_list = variable_symbol {"," variable_symbol}* variable_declaration = variable_list ":" identifier formal_variable_declaration = variable_declaration {";" variable_declaration}* Header_field = identifier ["::" "(" formal_variable_declaration ")"] Note that the form "::" formal_variable_list is optional: it may be the case that the action description contains no variable. In this case, this syntactic form is omitted (action description taken from example file 'Looping Pweak') and the Var_constraints field is empty: define(action(example::one),domain(this_info_file), comment('As an example, add q to the current state'), body(parameters::[], constraints::[], precondition::[p], positive_effect::[q], negative_effect::[])). As previously mentioned, variables possess a universe where they take their values. The variable declaration part of the header (e.g. (X,Z:box)) is here to say to what universe a variable refer to. This is the same as a procedure heading in a classical programming language such as PASCAL. The second field is a list of constraint predicates whose arguments are variables (and/or constants) of the formal_variable_declaration of the Header field of the action description (thus in the action description newtower above, the constraint predicate neq/2 means that its arguments should Not be EQual): parameter = variable_symbol | constant_symbol parameter_list = parameter {"," parameter}* constraint = predicate_symbol "(" parameter_list ")" constraint_enumeration = constraint {"," constraint}* Var_constraints_field = "[" constraint_enumeration "]" The user can define constraints. See the file 'Constraints' in the 'User' folder. The third, fourth and fifth fields are lists of positive atomic formulas. Note however, that function terms are not fully handled in Pweak. See example file 'Simulating a counter' for additional information on using a simplistic function term in Pweak. [References] On action execution (about the result function): [*] Vladimir LIFSCHITZ, "On the Semantics of Strips", in: "Reasoning about Actions & Plans", Proceedings of the 1986 Workshop, Timberline, Oregon, Michael Georgeff and Amy Lansky (Eds), Morgan Kaufman (1987), pages 1--9. Can also be found in: "Readings in Planning", James Allen, James Hendler and Austin Tate (Eds), Morgan Kaufman (1990), pages 523--530. ¥ Planning problem :======================================================= A planning problem is a 4-tuple (T,I,G,Ops) where T is declaration of the universes, I and G are state descriptions of the world and Ops is a set of action descriptions. I is the initial state of the problem and G is the Goal state. For Pweak, (T,I,G,Ops) is encoded into four syntactic forms: "define(constant_symbol_0;types(list_0))." "define(constant_symbol_1,initial_state(list_1))." "define(constant_symbol_2,final_state(list_2))." "define(action(operator_set_name::operator_name), domain(what_is_the_operator_usable_for), comment('this is an example'), body(parameters::list_31, constraints::list_32, precondition::list_33, positive_effect::list_34, negative_effect::list_35))." where constant_symbol_0, constant_symbol_1, constant_symbol_2 and constant_symbol_3 are any constant symbol of your choice. list_0 is a list of couple (constant_symbol,list_of_constant) which describes, in extension, the universes of the planning problem. list_1, list_2, list_31, list_32, list_33, list_34 and list_35 are lists of formulas (see section ¥ World language above and section ¥ Action language above). Here is an example. First let us begin with a type declaration: "define(jazz,types([(pianist,[bill_evans,oscar_peterson]), (guitarist,[wes_montgomery,pat_metheny])])). Then, an initial state: "define(rock,initial_state([roll])." A final state: "define(be,final_state([bop]))." Finally, at least one operator: "define(action(example::one),domain(this_info_file), comment('As an example, add q to the current state'), body(parameters::[], constraints::[], precondition::[p], positive_effect::[q], negative_effect::[]))." ¥ Plan language :========================================================== Let N be the infinite set of natural integers and x denotes the cartesian product of sets. Let L be a labelling function assigning an integer to a unique operator: L : N --> Ops n --> ad = L(n) L is a priori not surjective (some operators may not be related to any integer). L is certainly not injective (two distinct integers can relate to the same operator). For instance, it might be possible that: L(16) = L(15) = define(action(chapman::puton),domain(blocks_world), comment('Move a block from one stand to another'), body(parameters::(X,Y:box;Z:stand), constraints::[neq(X,Y),neq(Y,Z),neq(X,Z)], precondition::[on(X,Z),clear(X),clear(Y)], positive_effect::[on(X,Y),clear(Z)], negative_effect::[on(X,Z),clear(Y)])). Finally, some integers may not be related to any operators at all. Let F_L the family of all possible L as previously defined. Let Li be a element of F_L and O = {o such that o = (n,Li(n))} be a set of labelled operators. A plan is a couple (O,<) where < is a strict partial order on O (i.e. < is a binary relation over O which is not reflexive, antisymmetric and transitive; it is a subset of O x O). The length of a plan (O,<) refers to the cardinal of O, noted |O|. For Pweak, O is encoded into a list of action descriptions (see ¥ Action language above) where the identifier of the Header field of each action description is concatenated to the label of the action description; for instance, newtower_15 is such a labelled identifier. The partial order < is encoded as a list of t/2 predicates whose parameters are both headers of operators; for instance, t(newtower_15::(X,c),puton_22::(a,b,Z)) reads newtower_15::(X,c) < puton_22::(a,b,Z). One can now extend the definition of the previous result function to handle the result of a plan whose set of action descriptions contains two operators: {O1,O2}. The function result returns a situation according to the order relations between O1 and O2: (0) result({0},s) = result(O,s) (1) IF O1 < 02 THEN result({O1,O2},s) = result({02}, result(01, s)) (2) IF Â(O1 < O2) and Â(O2 < O1) THEN (2.1) result({O1,O2},s) = result({02}, result({01}, s)) (2.2) result({O1,O2},s) = result({01}, result({02}, s)) (0) is syntactic sugar. (1) says how to execute a sequence of ordered operators (i.e. apply the first one and then apply the second one). Whereas (2) says how to execute a sequence of unordered operators (i.e. arbitrarily first execute either one or else the other). This trivially is extended to the case of a plan containing more than two operators. A planning problem is encoded into an initial plan noted p_init; thus the planning system only manipulates plans from the beginning of its search. This initial plan possess two fake operators; an initial operator, noted begin, with the initial state as its add list; and a final operator, noted end, with the final state as its preconditions list (begin and end are not labelled): ({begin = (¯,¯,I), end = (G,¯,¯)},{(begin,end)}) which, for Pweak is (first comes the operators list and then the partial order) encoded as: [ad(begin, /* Header */ [], /* Var_constraints */ [], /* Preconditions */ list_1, /* Added set */ []), /* Deleted set */ ad(end, /* Header */ [], /* Var_constraints */ list_2, /* Preconditions */ [], /* Added set */ []) /* Deleted set */ ] [t(begin,end)] ¥ Plan existence problem :================================================= The plan existence problem is the following: "Let (T,I,G,Ops) be a planning problem. Is there a plan P = (O,<) such that its application to the initial state yields at least the goal state (G is included into result(O, I))?" Note that since unapplicable operators act as the identity, the length of a solution can be arbitrarily long. Also note that the answer to the plan existence problem is either "yes" or "no"; indeed the plan existence problem is a decision problem. Finally recall that an operator must be instantiated to be executable. Pweak attempts to build a plan in order to answer yes. ¥¥ Complexity of the plan existence problem :------------------------------ It is probably necessary to know a few about Turing machines and complexity classes to read this subsection. Let (T,I,G,Ops) be a plan existence problem. Looking at the format of the action descriptions, one can give the (worst case) size of the search space or the (worst case) time needed to solve the problem: the number of formulas, and the language used to compose them, in the preconditions set, added list and deleted list entail a complexity. Both TIME and SPACE complexity results have been found for planning problem; and both give upper bound results (i.e. worst case). TIME complexity gives an upper bound to the number of step unit needed to reach a solution; and SPACE complexity gives an upper bound to the number of storage unit needed to reach a solution. Encoded on a Turing machine, one step unit corresponds to the execution of one transition of the machine; one storage unit corresponds to one tape square; and reaching a solution corresponds to reaching a halt state of the machine. To obtain complexity results for a planning problem, the idea is to encode a Turing Machine as a planning problem: - First show that a the computation of a Turing machine can be encoded as a planning problem (and back). Therefore a storage unit corresponds to a formula used in the planning problem encoding the Turing machine. - Second, showing that the action description format can encode (up to a polynomial transformation) a given Turing machine (with its given complexity). Therefore, a step unit corresponds to the application of an action description of the planning problem encoding the Turing Machine. The consequence is that the solving of the planning problem is as complex as the halting problem of the Turing Machine (up to a polynomial transformation of an halting problem into a planning problem). Some complexity results are given in the table below. The first column refers to the language used in the description of the planning problem. The second refers to the format (number of preconditions, added and deleted formulae) of action descriptions. The third column gives the complexity of the problem of finding a plan. And the last (fourth) column gives the complexity of the problem of finding a plan of at most a certain length. For instance, assume the problem is described with a language which is propositional (formulae are only made of 0-ary predicates) and action descriptions of the problem are limited to one positive precondition, as many added formula as desired and no deleted formula; if x storing unit is used to encode the problem, the space needed to solve the problem is bounded by log(x+1). As you can see, log(x+1) is an upper bound: in the worst case, log(x+1) storage unit shall be used to solve the problem. ±, + and - respectively mean either positive or negative formulae, positive only and negative only; * means as many as desired. =========================================================================== | Language | AD format | Finding a plan...|...of length ² L | |-------------|----------------------|------------------|-----------------| | 0-ary | (1+,*,0) | NLOGSPACE | NP | | predicates |----------------------|------------------|-----------------| | only. | (1±,*,*) and g goals | Polynomial | Polynomial | | |----------------------|------------------|-----------------| | | (³2+,*,0) | Polynomial | NP | | |----------------------|------------------|-----------------| | | (0,i,j) and i+j=1 | Polynomial | Polynomial | | |----------------------|------------------|-----------------| | | (0,2,0) | Polynomial | Polynomial | | |----------------------|------------------|-----------------| | | (0,*,*) | Polynomial | NP | | |----------------------|------------------|-----------------| | | (*+,i,j) and i+j=1 | Polynomial | NP | | |----------------------|------------------|-----------------| | | (*+,0,*) or (*-,*,0) | Polynomial | NP | | | and g goals | | | | |----------------------|------------------|-----------------| | | (*+,0,*) or (*-,*,0) | NP | NP | | |----------------------|------------------|-----------------| | | (1±,*,0) | NP | NP | | |----------------------|------------------|-----------------| | | (*±,*,0) | NP | NP | | |----------------------|------------------|-----------------| | | (1±,*,*) | NP | PSPACE | | |----------------------|------------------|-----------------| | | (2+,i,j) and i+j³2 | PSPACE | PSPACE | | |----------------------|------------------|-----------------| | | (*±,i,j) and i+j=1 | PSPACE | PSPACE | | |----------------------|------------------|-----------------| | | (*±,*,*) | PSPACE | PSPACE | |-------------|----------------------|------------------|-----------------| | Predicates | (1+,*,0) | PSPACE | PSPACE | | and |----------------------|------------------|-----------------| | constants | (*+,*,0) | EXP-TIME | N-EXP-TIME | | |----------------------|------------------|-----------------| | | (*±,*,0) | N-EXPTIME | N-EXP-TIME | | |----------------------|------------------|-----------------| | | (*,*,*) | EXPSPACE | N-EXPTIME | |-------------|----------------------|------------------|-----------------| | Atomic | (*,*,*) | 1/2 D | 1/2 D | | formulas | | | | =========================================================================== Polynomial is a TIME complexity NP(-complete) is a TIME complexity PSPACE means Polynomial SPACE complexity EXP- means exponential N- means Non deterministic and corresponds to a problem complexity for a non-deterministic Turing machine. Recall these machines possess a "Choose" operator which creates as many copies of a deterministic Turing machine as there are possible choices. For instance, NP means that any of the created deterministic Turing machines solve or fail in Polynomial TIME -- but the number of the machines that have been created is exponential in the number of possible choices of the "Choose" function. 1/2 D means semi-decidable (i.e. the procedure shall only stop to say yes) [References] What is a Turing Machine? Mac Software to experiment with Turing Machines? [*] Jon BARWISE & John ETCHEMENDY, "Turing's World 3.0 (An Introduction to Computability Theory)", Center for the Study of Language and Information, Lecture Notes No. 35 (1993), 123 pages. ISBN 1-881526-10-0 What is a Turing machine? About problem complexity? [*] Michael GAREY & David JOHNSON, "Computers and Intractability (A guide to the Theory of NP-Completeness)", Freeman (1979), 340 pages. ISBN 0-7167-1045-5 Where can some of the results (and the proofs) in the above table be found? [*] Tom BYLANDER, "The Computational Complexity of Propositional STRIPS Planning, Artificial Intelligence 69 (1994)", pages 165--204. Where can some of the results (and the proofs) in the above table be found? [*] Kutluhan EROL, Dana NAU, V.S. SUBRAHMANIAN, "Complexity, Decidability and Undecidability Results for Domain-Independent Planning", Technical Report, Computer Science Department, University of Maryland (1992), 46 pages. Contact nau@cs.umd.edu ¥ Solution to the plan existence problem :================================= Let (T,I,G,Ops) be a planning problem and P = (O,<) be a plan such that the initial oprator begin and the final operator end belong to O and all operators of O but begin are after begin, all operators of O but end are before end. P is a solution to (T,I,G,Ops) if and only if result(O, s = ¯) is a superset of G. "result(O, s = ¯) is a superset of G" is translated by the following: For all operators A of O and for all their preconditions p, there exists an operator T of O before A which adds p, such that all operators C of O deleting p are not in between T and A (i.e. all operators C are either before T or else after A). ¥ Plan modification operators (plan construction) :======================== Pweak starts with the initial plan ({begin = (¯,¯,I), end = (G,¯,¯)}, {(begin,end)}) and tries to modify this plan so that it becomes a solution to the planning problem it encodes. Modifications to the initial plan are made by the application of plan modification operators. ¥¥ Definition (what the plan modification operators are) :----------------- Let PP be the set of partial plans for a planning problem, i.e. the set of all possible couples (O,<) over N x Ops. Note that PP is infinite. A plan modification operator (PMO) is a mapping from PP into itself minus the initial plan p_init (\ stands for set-difference): PMO : PP --> PP \ {p_init} px --> py = PMO(px) PMO is an order preserving function: for all operators O1 and O2 of O_x such that O1 <_x O2 then PMO(O1) <_x PMO(O2). PMO is not supposed to act as identity (i.e. px = py = PMO(px)); it increases the number of operators or else the relation order. PMO never reduces the number of relations between the operators of a plan. The idea of a plan modification operator thus is to "add" a partial plan to another one so as the resulting plan is closer to a solution. This addition is made on the two set components of a plan using set-union. Recall that set-union is idempotent (in what follows, U stands for set-union): {a} U {a} = {a} (or, {a} cannot be distinguished from {a,...,a}; note that the concept of multiset allows to distinguish mutliple occurences of the same element of a set). When Pweak modifies the operators set, at most one new operator is added to this set, and always with an order related to this operator (O_x is the operators set of plan px, O1 and O2 are two operators; O1 is newly inserted and O2 already belong to px): "Operator insertion" : py = (O_x U {O1},<_x U {(Oi,O1),(O1,O2),(O1,Of)}) Note that because set union is idempotent, adding Oi, O2 and Of to px is a fake addition. Thus, for simplicity, Oi, O2 and Of are henceforth omitted in the addition to O_x. Pweak can also only modify the partial order by inserting at most one precendence constraint at a time (O_x is the operators set of plan px and O1 and O2 are operators already belonging to O_x such that (O2,O1) does not already belong to <_x): "Precedence insertion" : py = (O_x,<_x U {(O1,O2)}) "Operator insertion" and "Precedence insertion" are the only two plan modification operators used in Pweak. Surjectivity of PMO is desired: for all py of PP there exists a px such that py = PMO(px), which means in using PMO, Pweak is able to construct all plans of PP. This is clearly necessary for completeness reasons. To be injective, PMO(px) = PM0(py) implies that px = py, which means there is only one "way" to build a plan using PMO. Injectivity maps the partial plan space into a tree whereas non-injectivity maps it into a graph. "Operator insertion" and "Precedence insertion" do not to act as identity: when an operator is added to O_x, it does not already belong to it; it is a new operator. When an order is added to <_x this is a new precendence constraint which did not previously belong to <_x. ¥¥ Semantics (applicability of plan modification operators) :-------------- Let (T,I,G,Ops) be a planning problem. Let (O,<) be a partially ordered plan and let A, E and C be three elements of O. Let p be a precondition of A, added by E and deleted by C. "Operator insertion" is applied when there exists no establisher for the current precondition to be established: assume p of A has no establisher yet and, and moreover, no operator of O_x adds p. But E_new of Ops adds p. Then, E_new is added to O following "Operator insertion": "Operator insertion" : py = (O_x U {E_new},<_x U {(E_new,A)}) This is called establishment by a new operator. E_new is the establisher for p. E is new because it has been newly inserted to establish p. If an operator of O_x adds p (let E_old be this operator) then only "Precedence insertion" is applied, if and only if E_old is not already after A: "Precedence insertion" : py = (O_x,<_x U {(E_old,A)}) This is called establishment by an old operator. E_old is the establisher for p; E is written E_old because it was already in the plan. Assume now that p of A is established by E; then (E,A) is an element of <_x. For all C which are clobberers of p, "Precedence insertion" will be applied: "Precedence insertion" : py = (O_x,<_x U {(A,C)}) This is called promotion of C after A and is possible only if (C,A) does not already belong to <. And "Precedence insertion" : py = (O_x,<_x U {(C,E)}) This is called demotion of C before E and is possible only if (E,C) does not already belong to <_x. If C is not comparable neither to E nor A (i.e. the intersection of {(C,E),(E,C),(A,C),(C,A)} and <_x is empty), then both promotion and demotion of C are applicable. Pweak always tries demotion first (because demotion appears first in the source file "declobbering"). If there ever exists one C such that (E,C) and (C,A) belong to <_x then p is said to be incorrectly achieved. Let p_c the formula of the deleted set of C which unifies with p precondition of A. If p_c contains variables, it is possible to force future unifications of these variables so that p_c does not unify with p anymore. For instance, let us assume clear(a) is a precondition of A established by E. And C is an operator in-between E and A which possess clear(Z) in its deleted set. Then, by enforcing variable Z to unify to a value different from a, the plan can still be correct. Note that this can be applied even if C is not in-between E and C, thus protecting precondition p while avoiding to modify the partial order. This is called variable (Tweak) separation. As it is presented, separation acts as identity: neither an operator is inserted nor a precedence constraint is added. This has lead some researcher to include a third component to a plan: a list of unification constraints (usually called a binding set in the literature). Thus separation never acts as identity. However, one can decide to apply separation as a precedence insertion, enforcing the clobberer to always be in-between E and A: not only p_c shall not unify with p but C is both after E and before A. This is called SNLP separation and does not act as identity anymore. Note that if none of promotion, demotion or else separation (Tweak or SNLP) can be applied, then Pweak shall backtrack on previous choices --- either establishers or "Precedence insertion" for clobberers; if all previous choices have been tried, Pweak returns failure. An optional plan modification operator is provided. For instance, when there exists one C such that (E,C) and (C,A) belong to < then it is possible to look for an operator Old_WK already in the plan such that on can constraint Old_WK in-between C and A : "Precedence insertion" : py = (O_x,<_x U {(C,Old_WK)}) "Precedence insertion" : py = (O_x,<_x U {(Old_WK,A)}) This is called the demotion by an old white knight and is possible only if neither (Old_WK,C) nor (A,Old_WK) belong to <_x. ¥¥ Movements (how Pweak chooses to apply plan modification operators) :---- Constructing a plan amounts to move in the space of partial plans (PP). PP is a graph where vertices are partial plans and arcs are plan modification operators (PMO). In theory, PP is infinite and so is its graph. In practice, we shall now consider PP(n) = I x Ops with I a subset of N, containing consecutive integers, of cardinality n. PP(n) just represents (the space of partial) plans containing at most n operators, whatever these (labelled) operators are and whatever the partial order is, providing, hozever, it is always a lattice with begin and end as its minimum and maximum, respectively. All vertices of PP(n) are connected to each other. However, since Pweak only uses two PMOs ("Operator insertion" and "Precedence insertion"), it cannot leave a vertex by any of the arcs. Only those related to the two PMOs can be followed. There are certainly plenty of arcs consistent with the PMOs which leave any vertex; and possibly so many that there exists more than one path from the initial plan to a plan-solution (there might be many solutions to a problem). Some paths may be shorter, some may be longer. Pweak plunges depth-first into PP(n); but this depth-first plungeon does not mean Pweak increases the number of operators of its current partial plans at each vertex. Arc selection (to leave a vertex) depends on which precondition must be satisfied and how it is satisfied. To satisfy a precondition, Pweak always tries to find an establisher in the plan first; and always tries demotion first. Among all the possible unachieved precondition that can be chosen (in order to try to establish it), Pweak chooses the first one of a list (the list of not yet achieved preconditions). This list is modified when PMO "Operator insertion" is applied: the preconditions set of the newly inserted operator is added to this list, either at the end (in case the list is maintained as a queue) or else at the beginning (the list is thus maintained as a stack). These two goal list managements are proposed via the menu 'Goal list management...'. Initially, the goal list is managed as a queue. The queue or stack strategy must be chosen prior to running Pweak and is valid until the runtime is complete. A third management scheme of the goal list is also possible. It can be used in conjunction with the stack or else the queue schemes. It is that of cyclic update. Once a goal has been achieved, it is possible to see if any other unachieved goals can be achieved while leaving the plan unchanged (i.e. this step does not involve inserting operators and/or modifying the order relation). Note also that when PMO Tweak separation is applied, the vertex is not left since neither operator insertion nor precedence constraint is applied. ¥¥ Precondition achievement :---------------------------------------------- Pweak applies PMOs so as to get closer and closer to a solution. A first step closer is made when looking for an establisher (i.e. applying old_establishment of new_establishment) and other steps are made for declobbering (i.e. demotion, promotion, etc, of clobberers). The combination of establishment and declobbering ensures that the concerned precondition is safe: it is now correctly achieved. Each partial plan thus possess a set of preconditions that are already achieved (henceforth noted Paa) and a set of preconditions that are not yet achieved (henceforth noted Pnya) in which a unachieved precondition is chosen (this set can be managed as a stack, as a queue, etc, see subsection ¥¥ Movements above) so as to get closer to a solution. A solution vertice is a vertice whose Pnya is empty. Let us now consider the following Achieve function: Achieve : (PP x Pnya(PP) x Paa(PP)) --> (PP\{p_init} x Pnya(PP\{p_init}) x Paa(PP\{p_init})) (px,Pnya(px),Paa(px)) --> py = Achieve(px) where Pnya(PP) is the set of all not yet achieved preconditions sets of all partial of PP while Pnya(px) is the set of Preconditions of partial plan px that are not yet achieved. Accordingly for Paa(PP) and Paa(px). Obviously, function Achieve must be surjective. Surjectivity says that for all py, there exists a px such that Achieve(px) = py. Assume this is not the case; i.e. there exists a py such that there is no px such that Achieve(px) = py. Then py is unreachable through Achieve. If py is a solution then Achieve cannot reach it and the planner using Achieve is not complete. Surjectivity of Achieve is the key to completeness of the planning procedure. Let us first consider the case where Achieve is not injective: there exists two distinct partial plans pa and pb which have the same image through Achieve: Achieve(pa) = Achieve(pb). This means that vertex related to pa and vertex related to pb are connected to a third vertex (note this third vertex may be pa or pb) with Achieve (because Achieve(pa) = Achieve(pb)). PP thus is visited as a graph: it can be the case that one partial plan is visited more than once (once coming from pa and once coming from pb). If Achieve is injective, any two distinct vertices have different images through Achieve. PP thus is visited as a tree: there is a unique path from a partial plan to its image through Achieve. For instance, there is no way to leave a partial plan unchanged: Achieve should not be able to act as identity to be injective. Note that if Achieve is injective then its inverse exists. Since Achieve is made of applications of plan modification operators, injectivity or surjectivity is reached by controlling the applications of those plan modification operators. Never using promotion places surjectivity out of reach. And using Tweak separation places injectivity out of reach; so does any combination which leaves a partial plan unchanged. This can always be the case when old establishment is applied; note that if you use cyclic update (as in planners TO and UA) in conjunction with old establishment, then injectivity is enforced. Moreover if declobbering does not change the partial order, then the partial plan is left unchanged and then Achieve is not injective (since the partial was first reach from a distinct partial plan and then it is reached again from itself, though a new precondition has been achieved); again, cyclic update corrects this. Effects of these properties on efficiency are currently unknown, but research does its best. [References] About UA (brilliant, must read, papers)? [*] Steven MINTON, John BRESINA and Mark DRUMMOND, "Commitment Strategies in Planning: A Comparative Analysis", Proceedings of IJCAI'91, pages 259--265. Also technical report FIA-91-08 (December 1991), NASA Ames Research Center, AI Research Branch, 29 pages. Also Journal of Artificial Intelligence Research 2 (1994), pages 227-262. Research does its best? [*] Subbarao KAMBHAMPATI, Craig KNOBLOCK & Qiang YANG, "Planning as refinement Search: A Unified Framework for Evaluating Design Tradeoffs in Partial-Order Planning", Special issue of Artificial Intelligence on Planning and Scheduling, Volume 76:1-2, pages 167--238. ¥ Running Pweak on examples :============================================== To run pweak on examples, you must first load an example. ¥¥ Loading and example :--------------------------------------------------- To load an example, click on the "Pweak" item of the menu bar and then select 'Load an example'. An hierarchical menu appears. Each item corresponds to an example file to be loaded. If you select one, say "Empty problem", the corresponding example file is loaded and the menu item "Empty problem" is both disabled and marked (the latter, i.e. Ã, for better visibility of loaded examples). While loading the file, Open Prolog displays a progress bar. The corresponding filename is returned in the Open Prolog Worksheet window. For instance, Example file <:Examples:Empty problem> is now loaded. is written in the Open Prolog Worksheet window after selecting the 'Empty problem' menu item. You can load as many examples as the available memory of your Mac shall let you do it. Selecting 'Discard all examples' purges all loaded examples. Be careful, this will purge all the loaded example from memory. A message is returned in the Open Prolog Worksheet. For instance, ...All example clauses retracted! tells you that 3 examples were removed (becaused of the three dots before the sentence). Once all examples are retracted, the 'Discard all examples' menu and all example-related menus are disabled. Once an example has been loaded, you can run the planner. ¥¥ Plan existence tuples :------------------------------------------------- To run pweak, select "Pweak(Types,Is, Fs, Ops)..." in the "Planner" menu. A planning problem selection dialog appears. You are asked to enter 4 strings and a number. This means that not only you are asked to give a 4-tuple (made of a type descriptor, an initial state, a final state and a set of operators) but also to give a number bounding the number of operators in a possible solution. In the case the 'Sussman anomaly' example is loaded, enter the 5 following answers (press the tab key to move from one field to another or click in the field with the mouse): sussman_anomaly sussman_anomaly sussman_anomaly chapman 3 How can you know you have to type these 5 answers to get Pweak running on the Sussman anomaly example? To know the first four, once an example has been loaded and before selecting 'Pweak(Types, Is, Fs, Ops)...', select "Current descriptors..." in the "Pweak" menu. Current descriptors of all loaded examples are then written in the Open Prolog Worksheet. For instance if the sussman anomaly is loaded, the following is written: Descriptors of actually loaded examples: Type(s): [sussman_anomaly] Initial state(s): [sussman_anomaly,sa_robot] Final state(s): [sussman_anomaly,sussman_anomaly_1,sa_robot_1] Operators set(s): [chapman,robot] IPP operators set(s): [] IPP order(s): [] IPP Pnyaa: [] IPP Paa: [] The user has to know the number (how many operators are needed to reach the final state, starting from the initial state?). Assume you type 3 for the sussman anomaly example; this means the procedure shall look for solutions possessing at most 3 operators. Please note that some numbers are given below. There is actually no other way than looking in the example file in order to know what these descriptors refer to. A future version of Pweak could fix this. Click "Go" (or hit the enter key) when you have finished entering the three strings and the number. The problem data, the current date and time are printed first in the Open Prolog Worksheet: Types : [(box,[a,b,c]),(stand,[a,b,c,table])] Initial State : [clear(table),clear(c),on(c,a),on(a,table),clear(b),on(b,table)] Final State : [on(a,b),on(b,c)] Operators : chapman Maximum depth : 3 Search begins at 14:19:57, Jeudi 16 Mars 1995 Pweak is then ran on this problem and shall print each solution it finds in the Open Prolog Worksheet. Here is what it prints for the first solution it finds, when separation is on: # solutions/# visited = 1/47 @ depth 3 (Jeudi 16 Mars 1995, 14:20:05) ----------> Pweak proposes a plan! -----> Operators set: [ad(newtower_3(c,a), [neq(c,a)], [on(c,a),clear(c)], [on(c,table),clear(a)], [on(c,a)]), ad(puton_2(b,c,table), [neq(b,c),neq(c,table),neq(b,table)], [on(b,table),clear(b),clear(c)], [on(b,c),clear(table)], [on(b,table),clear(c)]), ad(puton_1(a,b,table), [neq(a,b),neq(b,table),neq(a,table)], [on(a,table),clear(a),clear(b)], [on(a,b),clear(table)], [on(a,table),clear(b)]), ad(begin, [], [], [clear(table),clear(c),on(c,a),on(a,table),clear(b),on(b,table)], []), ad(end, [], [on(a,b),on(b,c)], [], [])]. -----> Relations set: [t(newtower_3(c,a),puton_2(b,c,table)), t(begin,newtower_3(c,a)), t(puton_2(b,c,table),puton_1(a,b,table)), t(begin,puton_2(b,c,table)), t(newtower_3(c,a),puton_1(a,b,table)), t(begin,puton_1(a,b,table)), t(puton_2(b,c,table),end), t(puton_1(a,b,table),end), t(begin,end)]. -----> Bindings set: env([neq(table,c),neq(table,b)],[]) For instance "t(newtower_3(c,a),puton_2(b,c,table))", in the relations set, means that the operator whose header is newtower_3(c,a) is before the one whose header is puton_2(b,c,table). Pweak now displays a confirm box which asks whether the user wants to continue the search. If so, just click 'Yes' (or hit the enter key); click 'No' otherwise. While searching, the current solution number, the number of partial plans that have been visited so far and the current depth (i.e. the cardinal of the operators set of the current plan) are displayed in the message box at the top of the Open Prolog Worksheet. For instance, when the previous plan-solution is printed, the message box displays "0-47-3": 0 solution has been visited, 47 plans has been visited so far and the current depth is 3. A menu 'Solutions' with 4 submenus is provided which allows to change this 'find first solution and then ask to go on' behavior. The 4 submenus and their respective behavior are: 1. 'First and ask' which stops the search when a solution is found and asks the user whether to keep on searching. 2. 'First and stop' which ends up the search as soon as the first solution is found. 3. 'All' means the search only ends up when all solutions have been found. 4. 'Other...' asks the user the number of solutions to be found before ending up the search. A mark indicates which submenu is currently active. 4 extra submenus are also available for auto-saving purpose. For instance, you may choose to automatically save in a file what is written in the Open Prolog Worksheet. The 4 extra submenus and their respective behavior are: 5. 'Auto-saving' which saves in a file what is written in the Open Prolog Worksheet. The filename is NOT chosen by the user: it is made of the current date and is placed in the "Solutions" folder. Only the last runtime of consecutive runtimes on the same day will be kept. 6. 'Auto-saving as...' which saves in a file what is written in the Open Prolog Worksheet. But the filename is now chosen by the user. A dialog box is presented to the user. A filename MUST be given in a Mac format. No checking is made. A relative filename (e.g. :Solutions:Blah) or else an absolute filename (HD:Pweak:Solutions:Blah) can be given. To deactivate 'Auto-saving as...' once it is selected, select this option again and just click 'Ok' (i.e. no filename must be given: the corresponding field must be empty). 7. 'Auto-saving only' which is initially disabled and is enabled only when option 5. or else 6. above have been selected. It prevents from writing in the Open Prolog Worksheet. This is particularly useful to save runtime traces in a file only (remember Open Prolog windows can only contain 32kb). 8. 'PPS Statistics' which is initially disabled and is enabled only when option 5. or else 6. above have been selected. This writes informations about the Partial Plan Space. For instance, it writes the current number of the plan, its depth, its number of unachieved and achieved preconditions. Select this option to produce files compatible with the Mathematicaª files provided in the :Pweak:Tools folder. Selecting 5. while 6. is already selected leaves 7. and 8. as previously selected (e.g. if 'Auto-saving' is on together with 'Auto-saving only', then toggling to 'Auto-saving as...' will leave 'Auto-saving only' switched on). There are about 70 tuples (made of the 4 strings and the number). Some are given below (* means any number will do; when a number is given it is the length of the shortest solution; when '_' is given, try by yourself...): - (empty,empty,empty,empty,*) - (sussman_anomaly,sussman_anomaly,sussman_anomaly,chapman,3) - (sussman_anomaly,sussman_anomaly,sussman_anomaly1,chapman,3) - (sussman_anomaly,sa_robot,sa_robot_1,robot,6) - (doubledas,doubledas,doubledas,chapman,6) - (doubledas,doubledas_rh,doubled_as,robot,12) - (fiveblocks,fiveblocks,fiveblocks,chapman,5) - (fiveblocks,fiveblocks,fiveblocks_rh,robot,10) - (disprover,disprover,disprover,disprover,4) - (th,th_3d_3p,th_3d_3p,th_3d,7) - (llregistres,llregistres,llregistres1,llregistres,3) - (llregistres,llregistres,llregistres2,llregistres,3) - (llregistres,llregistres,llregistres3,llregistres,3) - (empty,offex1,offex1,offex1,3) - (empty,np_offex1,np_offex1,np_offex1,3) - (empty,loop_tweak,loop_tweak,loop_tweak,*) - (empty,loop_pweak,loop_pweak,loop_pweak,*) - (mtex7_1,mtex7_1,mtex7_1,mtex7_1,_) - (mtex7_1,mtex2,mtex2,mtex2,_) - (mtex7_1,mtex2biscorrect,mtex2bis,mtex2bis,_) - (mtex7_1,mtex2bisincorrect,mtex2,mtex2bis,_) - (mtex7_1,mtex2tercorrect,mtex2ter,mtex2ter,_) - (mtex7_1,mtex2terincorrect,mtex2ter,mtex2ter,_) - (m2c,m2cex1,m2cex1,m2c,_) - (m2c,m2cex2,m2cex2,m2c,6) - (be_1st,be_1st,be_1st,chapman,2) - (be_2nd,be_2nd,be_2nd,chapman,4) - (be_3rd,be_3rd,be_3rd,chapman,6) - (be_4th,be_4th,be_4th,chapman,8) - (be_1st,be_1st_robot,be_1st_robot,robot,4) - (be_2nd,be_2nd_robot,be_2nd_robot,robot,8) - (be_3rd,be_3rd_robot,be_3rd_robot,robot,12) - (be_4th,be_4th_robot,be_4th_robot,robot,16) - (empty,old_wk_useful,old_wk_useful,old_wk_useful,4) - (lba,lba,lba,lba,13) - (mtsimulelba,mtsimulelba,mtsimulelba,mtsimulelba,_) - (deuxsat,deuxsat,deuxsat,deuxsat,8) - (ch_4_blocks,ch_4_blocks,ch_4_blocks,jacopin,4) - (counters,start_from_zero,reach_two,sim_counter,2) - (counters,start_from_two,reach_six,sim_counter,3) - (counters,start_from_three,reach_zero,sim_counter,6) If you don't like these names, feel free to edit the example files and change them to what you wish. ¥¥ Adding your examples :-------------------------------------------------- The addition of an example is towfold. First, you have to write a file problem. Give a look at the example files to get some hints. Moreover, a "* problem file template" in the "Examples" folder provides the general format of what you should fill in. Second, you may wish to have your example file appear in the "Load an example" menu. If so, open the file "examples_list" in the "Examples" folder and add your filename (between ' and ': it is a prolog-string of characters!) with the other filenames. Your filename can be put anywhere in the list, because this list is alphabetically sorted before the menu is constructed. Then, when Pweak is loaded, your example appears in the example menu. ¥¥ What options for which planners? :-------------------------------------- Playing with Pweak menus, you may think there are too much or too little to play with. Here are a few planning procedures of the literature that can be simulated with Pweak, using different options, listed in the table below (where ± means optional, i.e. it can be selected but is not in the original procedure; + means it is necessary; Ñ means unnecessary or useless; and ? means unknown; NYI means Not Yet Implemented). Note that all the options can be switched on or off as you like. For instance, you may wish to switch on some (but not all) of the necessary options of the contributor protection to simulate UA. Then, you partially simulate UA, but you got a planner anyway. You may also switch on the SNLP Separation (Establishement Refine.) for Pweak or MacNonLin instead of the Tweak Separation, just for fun or for serious tests (the only difference between those two is the contraining of the clobberer in-between the establisher and the established in the case of the SNLP Separation); note that in this case, you are simulating a yet unknown planning procedure... ================================================================================= | | TWEAK | PWEAK | McNonLin | UA | SNLP | SNLP_UA | visit | |----------------------|-------|-------|----------|----|------|---------|-------| | Does the procedure |-------|-------|----------|----|------|---------|-------| | accept variables? | YES | NO | YES | NO | YES | YES | YES | 'NO' means propositional |----------------------|-------|-------|----------|----|------|---------|-------| language |*Goal List Management |-------|-------|----------|----|------|---------|-------| | FIFO | - | ± | ± | ± | ± | ± | ± | should be switched on. | LIFO | - | ± | ± | ± | ± | ± | ± | Only 1 of those 2 | Pick-up (MTC) |-------|-------|----------|----|------|---------|-------| | Establishment | + | - | - | - | - | - | - | | Promotion | + | - | - | - | - | - | - | | Demotion | + | - | - | - | - | - | - | | Separation | + | - | - | - | - | - | - | | Old White Knight | + | - | - | - | - | - | - | | Cyclic Update | ± | - | - | + | - | + | - | |----------------------|-------|-------|----------|----|------|---------|-------| |*Establishment Refine.|-------|-------|----------|----|------|---------|-------| | Promotion | + | + | + | - | + | + | + | | Demotion | + | + | + | + | + | + | + | | Separation (Tweak) | + | - | + | - | - | - | + | | Separation (SNLP) | - | - | - | - | + | + | - | | Old White Knight | + | ± | ± | - | - | - | + | |----------------------|-------|-------|----------|----|------|---------|-------| |*Establisher Protect. |-------|-------|----------|----|------|---------|-------| | Promotion | - | + | + | - | + | + | - | | Demotion | - | + | + | - | + | + | - | | Separation (Tweak) | - | - | + | - | - | - | - | Only 1 of those 2 | Separation (SNLP) | - | - | - | - | + | + | - | should be switched on. | Old White Knight | - | ± | ± | - | - | - | - | |----------------------|-------|-------|----------|----|------|---------|-------| |*Decontributing: |-------|-------|----------|----|------|---------|-------| | Promotion | - | - | - | - | + | + | - | | Demotion | - | - | - | - | + | + | - | | Separation (Tweak) | - | - | - | - | - | - | - | Only 1 of those 2 | Separation (SNLP) | - | - | - | - | + | + | - | should be switched on. |----------------------|-------|-------|----------|----|------|---------|-------| |*Deinteracting: |-------|-------|----------|----|------|---------|-------| |**Demotion |-------|-------|----------|----|------|---------|-------| | Add(E) \ Pre(I) ­ ¯| - | - | - | + | - | + | - | | Del(E) \ Pre(I) ­ ¯| - | - | - | + | - | + | - | | Del(E) \ Add(I) ­ ¯| - | - | - | + | - | + | - | | Add(I) \ Pre(E) ­ ¯| - | - | - | + | - | + | - | | Del(I) \ Pre(E) ­ ¯| - | - | - | + | - | + | - | | Del(I) \ Add(E) ­ ¯| - | - | - | + | - | + | - | |**Promotion |-------|-------|----------|----|------|---------|-------| | Add(E) \ Pre(I) ­ ¯| - | - | - | + | - | + | - | | Del(E) \ Pre(I) ­ ¯| - | - | - | + | - | + | - | | Del(E) \ Add(I) ­ ¯| - | - | - | + | - | + | - | | Add(I) \ Pre(E) ­ ¯| - | - | - | + | - | + | - | | Del(I) \ Pre(E) ­ ¯| - | - | - | + | - | + | - | | Del(I) \ Add(E) ­ ¯| - | - | - | + | - | + | - | ================================================================================= About Cyclic update. This option acts as MTC-goal-pick-up does, in removing, from the goal list, all possible preconditions that can be achieved in one cycle of the chosen planning procedure. Therefore, when this option is on, it is as if you selected MTC-goal-pick-up, although the first-goal-pick-up runs ok with it. But when the MTC-goal-pick-up is first selected, the cyclic update of the goal list is an option. In Subbarao Kambhampati's papers (see the references below), Establisher protection is called Interval protection; Contributor protection is not cited. However, his contributor protection is both my establisher and contributor protections. Finally, Interaction protection is called Unambiguous ordering. Note that back in (december) 1990, Pweak was able to simulate a planning procedure called Pweak (hence its name) and Tweak. UA came as a procedure designed from Pweak from the original procedure by the end of 1992 (with a simpler "interacts?" metrics than that of UA). This has been designed and ported on the Macintosh since March 1994 on top of the original 1990 Pweak procedure. The other options have been added since the Macinstosh version and with the help of Subbarao Kambhampati's papers. [References] About the very first PWEAK planning procedure? [*] ƒric JACOPIN & Jean-Franois PUGET, "From TWEAK to PWEAK: Reducing the Non-Linear Planning Framework", Laforia Technical Report 27/90, 12 pages. ftp://ftp.lip6.fr/lip6/softs/poleia/pweak/.html/papers.html About Tweak (difficult paper)? [*] David CHAPMAN, "Planning for Conjunctive Goals", Artificial Intelligence 32, pages 333--377. About UA (brilliant, must read, papers)? [*] Steven MINTON, John BRESINA & Mark DRUMMOND, "Commitment Strategies in Planning: A Comparative Analysis", Proceedings of IJCAI'91, pages 259--265. Also technical report FIA-91-08 (December 1991), NASA Ames Research Center, AI Research Branch, 29 pages. Also Journal of Artificial Intelligence Research 2 (1994), pages 227-262. About SNLP (don't hope too much)? [*] David McALLESTER & David ROSENBLITT, "Systematic Nonlinear Planning", Proceedings of the 9th AAAI (July 1991), pages 633--639. A (very bad and very inefficient) Prolog Implementation of SNLP? First read the SNLP paper and then duplicate this code. And then look at the code in Pweak which simulates SNLP: much much faster! [*] Yoav SHOHAM, "Artificial Intelligence Techniques in Prolog", Morgan Kaufmann (1994), pages 225-233. About comparing planners (brilliant, must read, paper)? (McNonLin) [*] Subbarao KAMBHAMPATI, "Design Tradeoffs in Partial Order (Plan Space) Planning", Proceedings of the 2nd International Conference on Artificial Intelligence Planning Techniques (Chicago, June 1994), pages 92--97.. Much longer version than the previous paper; try to implement the procedure of the previous paper first; when you're stuck, switch to this paper. When you're stuck again, ask rao; but don't tell him I told you so. Better description of McNonLin. [*] Subbarao KAMBHAMPATI, Craig KNOBLOCK & Qiang YANG, "Planning as refinement Search: A Unified Framework for Evaluating Design Tradeoffs in Partial-Order Planning", Special issue of Artificial Intelligence on Planning and Scheduling, Volume 76:1-2, pages 167--238. Comparison of efficiency between McNONLIN, TWEAK and SNLP? [*] Craig KNOBLOCK & Qiang YANG, "Relating Performance of Partial Order Planning Algorithms to Domains Features", ACM SIGART Bulletin Volume 6, Number 1, ACM Press (1995), pages 8--15. ¥ Tracing Pweak :========================================================== Before running Pweak, either hit Apple-T or select "Trace planning". The trace is then printed in the Open Prolog Worksheet window, as soons as Pweak's run has begun. However, any Open Prolog window can only contain 32Kb of text. This is very few regarding all the tracing information that is printed: the 32Kb limit is reached very quickly. You can save this trace in a file and prevent from writing it in the Open Prolog Worksheet by selecting submenu 'Auto-saving only' of the 'Solutions' menu. Once tracing has been switched on and Pweak is running, tracing cannot be switched off. One must wait for Pweak to terminate or Open Prolog to be aborted in order to switch off tracing. ¥ Pweak's user files :===================================================== In the :Pweak:User folder, there are four files which give the user some control over Pweak. ¥¥ The 'configurations' file :--------------------------------------------- This file contains a expression of the form: define(configurations_list, c_l(['From menus', '-', 'McNonLin', 'Pweak', 'SNLP', 'Tweak', 'UA', '-', 'McNonLin_MTC', 'SNLP_UA', 'SNLP_MTC', 'Tweak_visit' ])). All the strings are names of files contained in the 'Pweak:Configurations' folder. When Pweak is loaded, this list is read and the planning configurations menu of Pweak is constructed from it. ¥¥ The 'constraints' file :------------------------------------------------ There, you can define your own constraints to be used in the corresponding var. constraints field of an action description. To use them during the planning process, the 'Variable constraints' menu must be selected prior to any run. This selection can be automatic if you add pps(var_constraints) in the user preferences files (see below). ¥¥ The 'examples_list' file :---------------------------------------------- This file contains a expression of the form: define(examples_list, e_l(['2-counter machine', 'Chapman''s 4 blocks', 'Disprover 3rd IJCAI', '2-register swapping', '2-SAT',hierarchical, 'Block Exchange', 'Looping Tweak', 'Sussman Anomaly', 'Pengi planning', 'TM simulates LBA', 'Towers of Hanoi', 'Doubled Sussman Anomaly', 'Non-Polynomial Sussman Anomaly', 'Old WK Useful', 'Polynomial Sussman Anomaly', 'Simulating a counter', 'Empty problem', 'Five blocks', 'LBA (G0011D -> GXXYYD)', 'Looping Pweak', 'Turing (B0011B -> BXXYYB) (C)', 'Turing (BXBYB -> BXXYB) (J)', 'Turing (BXYB -> BYXB) (C)', 'Turing (BXYB -> BYXB) (J)' ])). All the strings are names of files contained in the 'Pweak:Examples' folder. When Pweak is loaded, this list is read and the examples menu of Pweak is constructed from it. Before contruction, it is first sorted in alphabetical order. If you want to add an example in the Pweak's menu of examples, you must: (i) place your file in the 'Pweak:Examples' folder and (ii) add the name of your file anywhere in the above list of the 'examples_list' file. Or you can (i) place your file in the 'Pweak:Examples' folder and (ii) select the 'Add example...' menu within Pweak and follow the intructions; Pweak shall automatically adds your example filename to the list above and update the menus accordingly. At the top of the submenu constructed from the list above, there are two menus: one to add (resp. to delete) an example to (resp. from) both the list in the file and the examples menu. No checking is made at addition time. The existence of a menu is checked before deletion; the user is warned when the menu does not exist. For both menus, a dialog box is opened after selection, asking the user to give a menu name to be either added or else deleted. For instance, if you want to delete 'Looping Pweak' from the menus (and the examples file), type Looping Pweak (with no quotes) in the editable field of the dialog box. ¥¥ The 'preferences' file :------------------------------------------------ This file contains an expression of the form (this is an example): pweak_gestalt([solutions(first_and_stop,1), partial_plan_space(establisher_protection,promotion), partial_plan_space(establisher_protection,demotion), search(depth_first), interactor_protection(add_tn_pre_in,demotion), interactor_protection(del_tn_pre_in,promotion), e_r(promotion), e_r(demotion), goal_list_management(queue), precondition_pick_up(first) ]). Mots of the predicates contained in the pweak_gestalt list correspond to an option that can be selected from either a menu or else a dialog box. Switching on or off an option design a planning procedure (see ¥¥ What options for which planners? above). These options are written in a solution file when solutions are written in a solution file. They are also written in a special option window when the 'Pweak's current gestalt...' menu is selected. When this menu is selected, use the Window menu of Open Prolog to toggle between windows. Once some options have been selected they can be written in the file ':Pweak:User:preferences' using the 'Save preferences' menu. At boot time for Pweak, they are used to pre-select the menus, when Pweak is loaded (after double clicking on (i) the Open Prolog Worksheet of the Pweak Folder or (ii) any alias of the Open Prolog Worksheet of the Pweak Folder). For instance, the predicate solutions(first_and_stop,1) shall select the corresponding option in the "Solution Management..." dialog box. Consequenlty, if you wish to pre-select some options, then you just need to add the options to the list contained in the ':Pweak:User:preferences' file. Please note that option search(depth_first) SHOULD ALWAYS appear in the preference list. ¥ Known bugs :============================================================= This section contains informations about present bugs contained in the version you are running. These bugs may or may not be corrected in future versions. ***** Interval [Establisher,Needer] Management do note DeInteract correctly ***** (fixed with 0.91d1) /** end of file Pweak_info ************************************************/