Response to first thinking topic

If the state space is not a tree, there is a cycle, and so running around in the cycle as much as desired before achieving the goal generates plans of any desired length.

That being said, there tends to be very little interesting in generating plans with cycles, so one can always prune any plan with 2^k actions (which visits 2^k+1 states -- 1 more than the total number of states, ergo, the plan is cyclic, removing the cycle shows that it is non-minimal).

More practically, one keeps a closed list, i.e., a hash table of visited states. There is never a reason to pass through a real state or a regressed "state" in more than the shortest distance, so one tracks that number and prunes any search branches failing this condition.  In some formalisms this is expensive to do, so instead one simply examines the states visited by the current branch, and prune the branch if there are any cycles. 

Removing such restrictions does allow progression and regression planners to find any walk through state space, i.e., all plans minimal or otherwise.  Such planners could enumerate all such walks, if desired, by printing plans whenever the goal check succeeds (but refusing to terminate, and generating the children of the state even though the goal is already true), but the search control does have to be breadth or best first [i.e., there must exist some measure of a plans with the guarantee that solutions are printed in sorted order with respect to the measure, and that only finitely many plans ever map to a value of the measure].  These considerations are important to partial satisfaction planning, actually.

Regression can, of course, generate cycles as easily as progression.  One can almost invert any STRIPS domain; the inverted domain requires disjunctive and negative preconditions (and the original domain has to insist on conjunctive and positive preconditions).  The idea here is that progression in the  inverted domain is exactly regression in the original domain [so general properties of progression are also general properties of regression, and vice versa, unless the properties depend upon purely conjunctive or purely positive preconditions].

Minimizing a plan, by this definition, is going to be exponential -- every subset of actions would have to be checked in worst-case scenarios.  In many domains, however, a simple search considering removing one action at a time could terminate early in every branch, leaving polynomial time.  (if, for example, each action contributes the truth of a proposition that is needed by another action known to be necessary, and that no other action in the plan gives that condition, then this action is also necessary (counting the initial state and goal states as actions, with the goal state being the only action initially marked necessary).  A simple backwards sweep is sufficient.  Slight optimizations would be sufficient to minimize Blocksworld plans, and i think the approach as stated works for Rovers plans without cycles in move operators [which are easy to separately detect])


Different notions of planning define minimality in different ways; progression and regression normally imagine minimality to mean acyclic.  Under that notion of minimality, with normal sorts of pruning based on cycle checking or duplicate detection, progression and regression generate minimal plans.

Under the suggested definition of minimality, progression and regression can generate non-minimal plans under any search control that doesn't guarantee optimality [even if employing duplicate detection or cycle elimination].  First note than an optimal plan must be minimal, since removing any set of actions reduces cost.  Consider the following sketch of a state space:

sI -A-> s1 -B-> s2 -A'-> s3 -Z-> sG
  -A'-> s3 -Z-> sG

An optimal planner will visit s3 by the shortest path first (optimal planners typically guarantee optimality in this recursive manner).  A suboptimal planner, however, might choose to do ABA'Z, which is acyclic and non-minimal (A and B can be removed).  Note that if B depends upon A, and A' depends upon B (or the initial state, and A deletes the condition that both the initial state and B assert), then removing either A or B alone leaves an unsound plan [thus showing the need to consider all subsets of a plan].

A planner that only prunes cyclic search branches (instead of keeping a closed list) will generate such acyclic, non-minimal, sub-optimal solutions with the greatest of ease.

For a much more thorough analysis of a very similar problem, one could look at Backstrom's analysis of reordering and deordering of plans; reordering being the hard problem of determining whether or not a plan has many alternative causal-link proofs [this is related to minimality as defined here].

While optimality implies minimality, and non-minimality implies sub-optimality, minimality does not imply optimality.  (Under either definition of minimality: acyclic or every subset kills the plan).

-Will

A screed and discussion on the optimality track of planning competition...

You might want to check out

http://raos-ruminations.blogspot.com/2006/07/on-suboptimality-of-optimal-planning.html

for a recent (as in 1.5 years back controversy) about optimality track
of the IPC

Rao

Email addresses of initial advisors

In case you don't know how to get in touch with initial advisors

wcushing@asu.edu
j.benton@asu.edu
sungwook.yoon@asu.edu
menkes@asu.edu
rao@asu.edu

rao

Readings for next class + additional material for todays'

Folks

As I said, we will discuss any outstanding questions on heuristics
(including probably a quick discussion on use of reachability
heuristics for
Plan-space planning), and then discuss bounded-length planning as a
combinatorial problem. What we did with Graphplan today will become
a simple subcase--with other cases being pushing planning as SAT/CSP/IP etc.

The additional reading for tomorrow's class is:

Chapters 6 and 7 in Nau et. al.'s text book

or if you want a shorter version, Chapter 11 (sections 4 and 5) in
Russell and Norvig (if you don't have the text, here is that chapter
from AIMA site:
http://aima.cs.berkeley.edu/newchap11.pdf )

-----------------

Also, if any of you felt a little lost today and wanted a more
structured lecture on the heuristics, check out

http://rakaposhi.eas.asu.edu/ICAPS06-tutorial/ICAPS06-1.mp3

which is the first part of the tutorial based closely on the paper you
read and slides you saw.

Rao

Initial advisors for cse574 projects... You will have to meet with your advisor by end of this week..

Folks

Thanks for writing down your initial ideas for class projects. We
(myself and the Teaching czars) went through them and
put in our bids.

Please look at https://wiki.asu.edu/planning/index.php/Project_ideas

and see who your primary advisor bid is from.

You will have to contact the advisor and make an appointment (about an
hour or less in most cases) so you can talk to them
and flesh out what is potentially feasible.

You will be required to maintain a wiki page with the summary of the meeting.

Rao

Reading for next class--reachability heuristics for planning

For the next class, read the following paper

http://rakaposhi.eas.asu.edu/pgSurvey.pdf

(definitely upto page 61,
and preferably upto page 66. Before you die of shock,
note that the paper starts at page 47 ;-)

No summaries are needed--but you should read the paper before coming.
Since part of this material has been covered once in
471 (if you took it from me), I intend to go at a brisk pace (brisk
pace for rao is not unlike realtime for redwoods).

Rao

Fwd: A little more on white-knight clause..

After class, Tuan and Kartik had a ton of questions on the infamous
white-knight clause. Here is a gist of that discussion for general
edification. (Tuan--you can copy this over to your scribe notes as
necessary).

The term white-knight comes from the "White knights in shining armor
rescuing damsels in distress".. The white-knight step intervenes
between the threatening step and the step needing the condition and
re-establishes the condition.

*NOTE* that while white-knight clause is needed to prove correctness
of arbitrary partial order plans, it is *NOT* needed to ensure
completeness of plan-space planning (which, like progression and
regression, only needs to generate all action sequences that can solve
the problem). While the plan-space planner I discussed in the class
will never be able to terminate with the white-knight example plan
(because there is no way to come up with an un-threatened causal link
for that plan), it is able to terminate with two different
specializations (refinements) of that plan--such that every action
sequence that is a top-sort of the white-knight plan is also a
top-sort of one of these refinements.

*IF* for some strange reason, you do want your plan-space (partial
order) planner to terminate with the white-knight plan, then you need
to generalize the semantics of causal links such that you have three
ways of resolving a threat. Specifically, if a causal link s1--p--s2
is threatened by a step s3 (which has effect ~p), then, we have three
resolution possibilities:

1. Promotion: put s3<s1
2. Demotion: put s2<s3
3. White-knight "de-clobbering"
Find a step s4 (either existing in the plan, or from the library)
such that s4 has effect p.
Introduce ordering s3<s4<s2
(so s4 comes between s3 and s2)

As mentioned above, the white-knight declobbering is unnecessary for
completeness in the space of action sequences.

It is also worth noting that when you allow white-knight declobbering,
you are essentially changing the semantics of the causal-link
constraint. Without declobbering, we in essence say that once
established, the causal link condition *CANNOT BE VIOLATED EVEN
TEMPORARILY*. Allowing declobbering means you can allow it to be
temporarily violated.

[Maintenance goals] Sometimes, plan-space planners use causal links to
model *Maintenance* goals. (The normal goals we saw until now are
goals of attainment--i.e., the conditions must be true at the end.
Sometimes, you also have goals of maintenance--all through the
execution of the plan, a certain condition must hold true. For
example, if you want to walk through a dark basement garage to the
fuse box to reset the fuse, then you need light to help you navigate
the garage. This light must be on pretty much all through the
execution of the plan. This kind of semantics will not be respected by
white-knight declobbering.

[White-knight and Chapmans Modal Truth Criterion;] White-knights
entered planning vocabulary through an (unfortunately) influential
paper from 1987 by David Chapman.

I stored a copy at http://rakaposhi.eas.asu.edu/cse574/notes/chapman-mtc.pdf

for your edification

This paper was unfortunate in that it (1) confused plan-space planning
with the need for being complete in the space of partial plans (which
as I pointed out is *NOT needed*) and (2) consequently assumed that
per-node complexity in plan-space planning will be influenced by the
cost of checking correctness of a partially ordered plan. Another
wrong assumption that Chapman made was that plan-space planners *MUST*
deal with partially instantiated partial order plans (this is the
*lifted planning* I started talking about).

Since a PO Plan can have an exponential topoligical sorts, and many
more ground topological sorts, it is not surprising that checking the
correctness of all those topological sorts can potentially be
exponential.

Chapman's +ve result was that *if* actions have no conditional
effects, and all variables are considered to have *infinite* domains
(which is a bogus assumption), then correctness can be checked in poly
time (note that this requires the white-knight clause). His negative
result was that once you have conditional effects, the correctness
check will be NP-complete. He somehow made this sound as if it was
the end of the world (and the planning community, for its part, went
along with it). On scholar.google.com, you see that Chapman's paper
has had 845 citations--most before 1991..

http://scholar.google.com/scholar?q=chapman+modal+truth+criterion&hl=en&lr=

The third paper in that page--written some 7 years after Chapman's
paper--brings up some of these critiques.

Rao

ps: What is wierd about Chapman's paper is that Chapman should have
known better. 10 years before his work, the planner "Nonlin" was
developed by Austin Tate and it saw farther (the plan-space planner we
discussed today is closer to 1977 paper by Tate than anything in
Chapman's 1987 paper). Apparently Chapman did talk to Tate but somehow
Tate's work is not cited prominently. Checkout

http://rakaposhi.eas.asu.edu/nonlin-review.txt

for an opinionated review of this whole episode..

Refinement Planning Mandatory reading for next class (summary required before class--post as a comment on the blog)

Here is the paper you have to read for next class. You will be
required to write and post a summary of the paper as a comment to this
posting on the blog

http://rakaposhi.eas.asu.edu/kambhampati.pdf

Rao

Policies on scribing..

Folks:
Unless otherwise stated, the deadlines for the scibe notes to be put
on the wiki are:

Tuesday class: Ideally by Thursday---but definitely by Saturday

Thursday class: Ideally by Saturday--but definitely by Sunday

This will give us czars a chance to make changes to the notes if needed.

If you see yourself falling behind this schedule, it is your
responsibility to let us know.

regards
rao

[Thinking topic]: Completeness and minimality..

[Part of the required participation in the class involves taking part
in the blog discussions--and giving answers to thinking topics. Here
is one]

An interesting issue about planner completeness is whether or not the
planner is capable of finding *every plan* for the problem.

Let us get some terminology straight.

A sequence of actions a1...an is considered a solution to a problem
[I,G] if we can
execute the sequence starting in state I and G will hold in the final
state after executing an.

A solution plan P: a1...an is said to be minimal if it is not
possible to remove any subset of actions from P
without violating its solution-ness.

An example of a non-minimal plan for achieving On(A,B) when A, B and C
are all on table is:

put A on C, take A of C, put A on B.

Cleraly, we can cut the first two actions out and it will still be a
solution (so it is a non-minimal solution).

Consider the following questions:

0. Given a planning problem that is solvable, how many solutions
(minimal as well as non-minimal) are there?

1. Is progression planner complete for all plans (including minimal
and non-minimal plans)?

2. Is regression planner complete for all plans (including non-minimal)?

3. Will regression planner ever find any non-minimal plans?

4. Will progression planner ever find any non-minimal plans?

5. If a planner is capable of producing non-minimal plans, then will
sussman anomaly be non-serializable for such a planner?

6. Given a possibly non-minimal plan, how costly would it be to
"minimize" it (i.e., remove redundant actions from it)?
(Complexity-wise... is it polynomial?
exponential? etc)

Mailing list and class blog set up..

Folks:

If you are receiving this mail, you are still registered for CSE574
(i.e., forgot to drop the class before add/drop end ;-).

I created a mailing list as well as a blog for the class. Most of you
know the drill:

The intended usage of the mailing list is for me to send you
announcements as well as things to think about.
All mails sent to the mailing list are sent to your email address,
posted to the class mail archive as well as to the class blog.

All of you have posting privileges to the class blog. You can post to
the blog as well as write comments on other posts.
You can keep track of changes to the blog through RSS feed etc.

cheers
Rao