## Thursday, January 31, 2008

### 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...

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

## Tuesday, January 29, 2008

### Email addresses of 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'

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..

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

## Thursday, January 24, 2008

### Reading for next class--reachability heuristics for planning

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

## Tuesday, January 22, 2008

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

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)

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..

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

## Monday, January 21, 2008

### [Thinking topic]: Completeness and minimality..

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..

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