NOTES FOR 2/25/03

Comments on class work

Ø	Turn in P2
Ø	For the next project - Write your own Domain
Ø	AltAlt - Top level goals exist and are not mutex is where the planner stops if you are not indicating to the planner to stop at level off
Ø	Examples
o	Biology
§	Find a plan to a disease
§	Make a medicine which breaks a part of the plan
§	This is the way medicine is starting to use planning for.
o	There will be a link to an article on "Biological Pathways as a Planning Problem"
Ø	Your Plan
o	You want your plan to succeed
o	Your enemy wants your plan to fail.
o	Use Classical Planning
o	Describe the domain
§	Abstract away thing which are not classical
§	This results in your domain
§	Write it in PDDL
o	Run your domain on AltAlt and at least one other planner
o	Second stage will be to exchange domains and analyze

Start of Lecture

EBL Example and Conversion to CSP:

Backward Search in Graphplan
Ø	There might be some variables which appear in the memo that doesn't have anything to do with the failure
Ø	Intelligent Backtracking
o	You need some explanation of the failure (DDB)
o	EBL (remembering these memos)
§	Remember memo and explanation
Ø	Conflict Set
o	For every variable, the set of variables that conflict with it.
o	Find the conflict and say this is the explanation of the failure
o	The conflict set becomes the memo
o	See example in the class slides
o	Use the conflict set to select options for later trials to reduce attempts
o	Do not use variables not in the conflict set as you backtrack because you know they don't have any relation to the failure.
o	How to back track with a conflict set
§	Skip other variables not in the set
§	Absorb the conflict set into the conflict set of the variable you are backtracking to.
§	When you come to the last variable, save that conflict set as the memo for the level under consideration.
§	Conflict set has predecessor and antecedent variables in the state set
§	As the conflict sets are absorbed the "absorbed sets" remain (memo) for later use on a new search.  i.e. "Take the complaint, add my name to it, and pass it along to my boss"
§	The conflict set for the last variable in the state is saved as the memo for the state
§	When the conflict set is saved, it just says that these values have conflicted and failed in the previous search branch.
§	Top level goals are the minimum explanation set if the lead to the conflict set in the next level.
§	Smaller explanations of failures help explain deeper and larger failures later on in the search. i.e. if G1 and G7 are mutex and another 5 goals, the set of the size {G1,G7,2^5 other suffixes} are excluded
§	If any stored memo is a subset of the current goal set, backtrack immediately and use the memo as the conflict set.

Ø	Conversion to CSP (constrain satisfaction problem)
o	Find an assignment of values to the variables for which no constraint is violated.
o	Variables should include all traces with nodes values and the number of levels.
o	You get a lot of variables and domains(action names)
o	See example in class slides
o	In standard CSP "everyone has a value"
o	Only certain variables need values (top level goals)
o	Use a "#" as a dummy value
o	Activation Constraint - Variables cannot have a null value.
o	Persist Actions - Supporting values cannot be null.  This is the same for values supporting preconditions.
o	Convert to CSP and give to a CSP solver.

Ø	GS-CSP - conversion runs faster than just GP.
Ø	How??  The technology of general computing has outpaced the technology of computing which could make Graphplan run faster.  (Seen many LISP computers lately?)
Ø	Normally, all computations are done at one level.  CSP doesn't do it that way.  Maybe level-by-level is not the best approach.
Ø	CSP is just the beginning - there is also SAT and ICP (ILP?)