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 ************************************************/