Added slides on quotienting and candidate set semantics for temporal planning

I added slides to last classe's lecture notes to reflect the
whiteboard discussion we had about
quotienting and lifted spaces and candidate set semantics for lifted
planning (this was done in
response to a question from Tuan).

FYI
Rao

Readings for Tomorrow..

Tomorrows agenda is

--> discuss any questions you might have on TCSPs (especially handling of STPs)

--> Discuss next topic: Scheduling

Reading:

Required: (required and in order)

Dana Nau text book 15.1--15.3

If possible, also read
http://rakaposhi.eas.asu.edu/cse574/smith-cheng-slack-aaai93.pdf (6
page paper on a scheduler)

============

Also, after the break, we will have a class to discuss the paper
http://rakaposhi.eas.asu.edu/cse574/KER00.pdf

(which talks about integrating planning and scheduling)

URL for unedited feedback comments...

is

http://rakaposhi.eas.asu.edu/cse574/s08-feedback.pdf

They should give you a more complete idea of what the class thinks and whether
it jives with your own view.

If you think the comments have a different meaning that I spun them for,
feel free to tell me that ( http://rakaposhi.eas.asu.edu/cgi-bin/mail?rao

)

regards
Rao

ZENO and Nondeterministic Choices

In the description of the ZENO algorithm, there is an interesting point (that didn't come up for discussion in class today), which we have covered earlier in the semester. While describing the nondeterministic decisions in the algorithm, the authors list 3 points: decomposing complex goals, choosing actions, and introducing constraints to prevent interference. They then go on to state that completeness requires backtracking on these decisions. That is, just finding a satisficing solution can only be guaranteed if the "nondeterministic" choices are determinised.

However (and this they point out subsequently), we have already seen earlier that for plan-space planners, the order in which the subgoals are selected for satisfaction has no effect on completeness. That is, unless we want to find the optimal solution, we need not determinise (introduce backtrack into) the order in which goals are selected.

This raises some interesting points:

1. Could this dichotomy be seen as a manifestation of the fact that while it is true that *all* subgoals need to be satisfied (at least in non-PSP scenarios) to have *a* solution, a given solution need not contain *all* the possible decompositions, or actions, or constraints?

2. The second part of 1. can perhaps be stated better as follows: any given combination of actions, simple goals and constraints is not necessarily a subset of any given solution, for all solutions in the spaces; however, any given subset of the subgoals is *necessarily* a subset of the subgoal set needed for top-level goal achievement.

These are just some of the things I could think of; I thought this was a very interesting point put forward by the authors. Please feel free to add your own.

kartik

One thought about completeness of ZENO and Decision Epoches planners

When reading these papers, I'm curious about why ZENO is complete but DEPs are not. One of the reasons I found is the difference between how they model the interaction/ordering between actions in the plans. ZENO post constraints between time points of actions, whereas DEPs uses advancing techniques. More interesting is that, in term of refinement planning, both of them can be considered as refinement operators, and advancing to decision epoches is not a complete refinement.
This difference does not exist in classical planning (i.e comparing POP v.s Progression/Regression) because decision epoches are not there and fattening and advancing work together...
A.Tuan

Final chance: Feedback opportunity to tell me how the class is going

Folks

Today is your last chance to send the midterm feedback. I will
summarize what I got tomorrow (and discuss in the
class if needed).

I got feedback from 5 students. The class has 12 registered
students--so this is not even a majority.
If it helps you galvanize to action, let me teasingly say that the
majority feedback received till now says
everything is upsy-daisy and requests if any thing for more homeworks and exams.

Rao

---------- Forwarded message ----------
From: Subbarao Kambhampati <rao@asu.edu>
Date: Tue, Feb 26, 2008 at 9:20 PM
Subject: Feedback opportunity to tell me how the class is going
To: Rao Kambhampati <rao@asu.edu>

Folks

Now that 6 weeks are over, I thought it would be good to poll y'all
on what is working and what is not working.
Please feel free to send your comments.

You can send comments either via anonymous web mail
http://rakaposhi.eas.asu.edu/cgi-bin/mail?rao

or by bringing a printed sheet to the class on Wednesday. Note that
the webmail records your ip address--so
you may want to send it from some ip address that is generic.

Here are some things I am interested in finding out. Other comments
welcome too:

1. Are the lectures too fast/too slow/too high level/too low level etc?

2. Are you actually able to connect your readings to lectures?

3. Are you reading before or after the topics are discussed?

4. Should there be more assessment (homeworks/projects etc)?

5. How is the progress towards semester project coming (qualitatively
speaking--
you will have an opportunity for detailed answers anyway)

6. Are the classes interacive enough or should they encourage more discussion?
If the latter, what can we do other than stopping for questions?

7. Overall, how does it compare to other graduate level courses you took/taking
(positively or negatively)

regards
Rao

Agenda an d readings for tomorrow...

Tomorrow I plan to answer any questions over SAPA and Zeno planning
algorithms (I am hoping you spent time reading them again after last
class), and then shift to temporal constraint networks (which
I mentioned as part of Zeno).

For the first part, I\in addition to the SAPA paper and IJCAI 2007
paper readings that you are already in charge of for last class, you
can also look at the Zeno paper
http://rakaposhi.eas.asu.edu/cse574/zeno.pdf

For the second part (temporal networks) you can look at

http://rakaposhi.eas.asu.edu/cse574/tcn-meiri-dechter-aij.pdf

rao