Please reply to this mail with your paper and (optionally) presentation as attachments

thanks
Rao

bring your presentations on a memory stick..

Folks

Bring your slides for today on a memory stick. We will load them on
the class computer in the beginning so the presentations can be
streamlined.

thanks
rao

Fwd: Real world blocksworld

Here is some information about real world block stacking application ;1/2)

rao

---------- Forwarded message ----------
From: William Cushing <william.cushing@gmail.com>
Date: Tue, Apr 29, 2008 at 8:34 AM
Subject: Fwd: Real world blocksworld
To: "Plan-Yochan@Parichaalak. Eas. Asu. Edu"
<plan-yochan@parichaalak.eas.asu.edu>

Indeed, Hector took the picture. "Optimizing the Steel Plate Storage
Yard Crane Selection Problem", ICAPS 2007 (DC Poster). I believe a
short paper version exists in the proceedings somewhere...

picture: http://picasaweb.google.es/hectorpal/Icaps2007/photo#5116899415236524914

that group's publication list:
http://www2.imm.dtu.dk/pubdb/public/publications.php?cmd=full_view&pubtype=&section=7

A related journal article on blockstacking (no joke, that's one of the
keywords):

http://www.springerlink.com/content/f60826852715v545/

(I attached the pdf if you don't have access to springer)

-Will

---------- Forwarded message ----------
From: William Cushing <william.cushing@gmail.com>
Date: Tue, Oct 2, 2007 at 7:07 PM
Subject: Real world blocksworld
To: plan-yochan <plan-yochan@parichaalak.eas.asu.edu>

http://picasaweb.google.es/hectorpal/Icaps2007/photo#5116899415236524914

This poster is on a domain which is very blocksworld-ish. Also has
towers-of-hanois-ish in that there is no table of infinite capacity;
only stacks. However, there appear to be no stacking restrictions
(objects don't have different weights or sizes that require sorted
stacks).

The steel plates *do* have individual names which distinguish them, a
highly important technical point (in the comparison with blocksworld).

The goal state is not a stacking configuration; the goal is to
minimize movement over time (as I understand it), each day one is to
deliver certain plates to a conveyer at the far right of the
coordinate system. One has a nominal schedule when plates will
arrive and when they will be requested, allowing one to subgoal on
intermediate stacking configurations (or rather a sequence of stacking
configurations) which minimizes movements while achieving those
schedules. (and then there is some online planning for each day as
requests and supplies deviate from nominal).

So many interesting components that bar applying FF directly to the
problem...but....a big core part of the technical problem *is*
blocksworld. On ~1000 "blocks", in case anyone likes to think of
planning + scaling.

-Will

Correction for a homework 2 problem..

In Question 1, where I say "Y can start at least 1 unit or at most 2
units after X" , please replace the "or" with an "and" (the "or"
constraint becomes a non-constraint since you will basically have two
constraints [-inf 2] [1 +inf] which is equivalent to [-inf +inf]

thanks
rao

Assistance or distraction?

The agent is quite intelligent and his behavior is close to the optimal, he is doing well. The assistant learns the agent’s goal and behavior, and starts to act. The agent notices that the world became friendlier, but different. It is time for active exploration (which is expensive) by the agent. The exploration changes goal distribution completely; the assistant distorts the world by trying to achieve wrong goals. After awhile the assistant stops to act, the agent finishes exploration (suspecting he had a glitch); and they are back to the old world.
It seems that assistance works, if an assistant much smarter than an agent; and an agent accepting the world as it appears, without trying to learn it.

*Important*: Format of the class of 4/29--you will do short presentations of your project findings

Folks:

For 4/29 (i.e., next Tuesday's class), I will take about 10 min to
do a "here is what we did" spiel. The rest of the class will be spent
with
each of you making a 5-min presentation about your project findings.
This will also serve as a quick summary of your report (that you will
also
bring to the class that day). Ideally, you make this presentation as
an advertisement to draw people to read your report (you will also
give me electronic--
pdf and ppt versions) of the report and talk.

I think there is a reasonable amount of diversity in the projects that
it is worth everyone hearing summaries of what others did).

thanks
Rao
-------------------
Subbarao Kambhampati
http://rakaposhi.eas.asu.edu/rao.html

(correct URL) Reading for tomorrow (as well as slides and audi...

Sorry,
the URL for Minh Do's paper is

http://www2.parc.com/isl/members/minhdo/publications/2008/do.pdf

rao

---------- Forwarded message ----------
From: Subbarao Kambhampati <subbarao2z2@gmail.com>
Date: Wed, Apr 23, 2008 at 2:26 PM
Subject: [CSE574 Planning & Learning] Reading for tomorrow (as well as
slides and audi...
To: subbarao2z2@gmail.com

Folks

For Minh Do's guest lecture tomorrow, you might want to read the
following paper

http://www.aaai.org/Conferences/AAAI/2008/aaai08nectar.php

(it is
only 5 pages!)

(Additional related papers are on his homepage at
http://www2.parc.com/isl/members/minhdo/ )

----------

Also, for those of you who missed Biplav Srivastava's talk on web
service composition today, his slides
and audio are up on the class notes page http://rakaposhi.eas.asu.edu/cse574

see you tomorrow.

Rao

--
Posted By Subbarao Kambhampati to CSE574 Planning & Learning at
4/23/2008 02:26:00 PM

Reading for tomorrow (as well as slides and audio from today's talk)

Folks

For Minh Do's guest lecture tomorrow, you might want to read the
following paper

http://www.aaai.org/Conferences/AAAI/2008/aaai08nectar.php

(it is
only 5 pages!)

(Additional related papers are on his homepage at
http://www2.parc.com/isl/members/minhdo/ )

----------

Also, for those of you who missed Biplav Srivastava's talk on web
service composition today, his slides
and audio are up on the class notes page http://rakaposhi.eas.asu.edu/cse574

see you tomorrow.

Rao

Fwd: teaching evaluations

You are so encouraged! As usual, in addition to the numbers, it will
be helpful to have
written comments on what worked and what didn't.

thanks
rao

---------- Forwarded message ----------
From: James Collofello <JAMES.COLLOFELLO@asu.edu>
Date: Wed, Apr 23, 2008 at 9:59 AM
Subject: teaching evaluations
To: "DL.WG.CEAS.Faculty" <DL.WG.CEAS.Faculty@mainex1.asu.edu>
Cc: Ann Zell <ann.zell@asu.edu>

Colleagues,

The Spring 2008 teaching evaluations became available to students on
Mon 4/21, around 10:30 a.m. and will close at Wed 4/30 (reading day)
at 12:00 midnight. Students will be able to access the evaluation
tool at: https://fultonapps.asu.edu/eval

Please encourage your students to complete the evaluations, especially
the students who enjoy your class, or they will face several nagging
email requests.

jim

James S. Collofello

Associate Dean for Academic and Student Affairs

Ira A. Fulton School of Engineering

Refreshed the plan recognition slides from the first plan recognition lecture..

Folks

FYI, I revised and expanded the plan recognition slides from the
first lecture based on the actual discussion in the class.

rao

Reminder: Talk Today 11AM on "The Myth and Reality of Web Services Composition" by Biplav Srivastava of IBM research 4/23 11AM BY 510

Title:
The Myth and Reality of Web Services Composition

Speaker:
Dr. Biplav Srivastava
IBM Research

Time: 11AM--12AM; Wednesday April 23rd; BY 510

Abstract:

Divide-and-conquer or working with complex systems from their
basic building blocks is one of the basic tenets of modern engineering.
While its applicability to Information Technology has always been
felt – example Object Oriented Methodology, its success has been
limited. There is a resurgence of interest in componentization of
IT systems and services through focus on Service Oriented Architecture,
and Web Services as its most popular form. Consequently, Web Services
has received wide attention in both academia and IT industry over
the past 5-7 years. The attractiveness of this technology lies in
the fact that the specifications of the building
blocks (i.e., services) are openly available in a registry and
so are the building blocks themselves. So, the promise is that a user
can build (or modify) an application by composing (or re-composing)
components whose specification it discovers from the registry
and whose capabilities it can access whenever needed. Depending on
what is defined as a service, web services composition can enable
many IT issues -- Mashups, Asset Reuse, Business-to-IT alignment,
Business-to-Business and Enterprise Application Integration, ...

In this talk, we will look at where the hardness of automatically
composing web services comes from in practice and how traditional
Computer Science techniques (notably planning) have fared. While
the original myth was that composition would be hard, in reality,
most composition scenarios did not demand scalability of the
top-of-the-line planning algorithms. However, what has turned
out to be harder than composition is how to set up the composition
problem as a traditional Computer Science (notably planning) problem.
Two trends are emerging to address this: the composition problem is
often cast as a plan reuse and modification problem in the context of
richer domain models (e.g., Industry Business Processes), and new
composition/ planning paradigms like model-lite planning which are
resilient to impoverished domain models.

-----------

About Biplav:

Dr. Biplav Srivastava is a Research Staff Member at IBM Research since
February 2001. Though based at IBM's India Research Laboratory, Biplav
is on assignment to IBM's T.J.Watson Research Center in Hawthorne, NY, USA.
Biplav's research interests are in planning, scheduling, policies,
learning and information management, and their practical applications
in services -- infrastructure and software (web services), semantic web,
autonomic computing and societal domains. Prior to IBM Research, he
was Core Technology Architect at an erstwhile Silicon Valley
start-up, Bodha, eventually acquired by SAP (2000-2001; process integration),
Staff Software Engineer at VLSI/ Philips Semiconductors (1996-2000;
electornic design automation) and Assistant System Analyst at TCS,
India (1993-1994).

Aiming to minimize the expected fallout from the unexpected hanging... ;-)

I will accept one page (printed) on your review/insight on the
decision theoretic assistance paper
at the *beginning* of thursday's class. Credit for saying things that
I didn't particularly bring out.

cheers
Rao

Talk on "The Myth and Reality of Web Services Composition" by Biplav Srivastava of IBM research 4/23 11AM BY 510

[CSE574 Folks:

This is the first of the two application talks planned for this week.
The second one will be in class on Thursday. Please make every effort
to attend. -Rao]

Title:
The Myth and Reality of Web Services Composition

Speaker:
Dr. Biplav Srivastava
IBM Research

Time: 11AM--12AM; Wednesday April 23rd; BY 510

Abstract:

Divide-and-conquer or working with complex systems from their
basic building blocks is one of the basic tenets of modern engineering.
While its applicability to Information Technology has always been
felt – example Object Oriented Methodology, its success has been
limited. There is a resurgence of interest in componentization of
IT systems and services through focus on Service Oriented Architecture,
and Web Services as its most popular form. Consequently, Web Services
has received wide attention in both academia and IT industry over
the past 5-7 years. The attractiveness of this technology lies in
the fact that the specifications of the building
blocks (i.e., services) are openly available in a registry and
so are the building blocks themselves. So, the promise is that a user
can build (or modify) an application by composing (or re-composing)
components whose specification it discovers from the registry
and whose capabilities it can access whenever needed. Depending on
what is defined as a service, web services composition can enable
many IT issues -- Mashups, Asset Reuse, Business-to-IT alignment,
Business-to-Business and Enterprise Application Integration, ...

In this talk, we will look at where the hardness of automatically
composing web services comes from in practice and how traditional
Computer Science techniques (notably planning) have fared. While
the original myth was that composition would be hard, in reality,
most composition scenarios did not demand scalability of the
top-of-the-line planning algorithms. However, what has turned
out to be harder than composition is how to set up the composition
problem as a traditional Computer Science (notably planning) problem.
Two trends are emerging to address this: the composition problem is
often cast as a plan reuse and modification problem in the context of
richer domain models (e.g., Industry Business Processes), and new
composition/ planning paradigms like model-lite planning which are
resilient to impoverished domain models.

-----------

About Biplav:

Dr. Biplav Srivastava is a Research Staff Member at IBM Research since
February 2001. Though based at IBM's India Research Laboratory, Biplav
is on assignment to IBM's T.J.Watson Research Center in Hawthorne, NY, USA.
Biplav's research interests are in planning, scheduling, policies,
learning and information management, and their practical applications
in services -- infrastructure and software (web services), semantic web,
autonomic computing and societal domains. Prior to IBM Research, he
was Core Technology Architect at an erstwhile Silicon Valley
start-up, Bodha, eventually acquired by SAP (2000-2001; process integration),
Staff Software Engineer at VLSI/ Philips Semiconductors (1996-2000;
electornic design automation) and Assistant System Analyst at TCS,
India (1993-1994).

talk on Online Continual Planning to Control Modular Production Printer (Minh Do; PARC Labs) 4/24 3:15pm BY 190

Title: Online Continual Planning to control Modular Production Printer

Speaker: Minh B. Do, (Xerox) PARC Labs, Palo Alto

Date/Time: Thursday 4/.24 3:15pm BY 190

Abstract: This talk summarizes the recent work at the Embedded
Reasoning System at PARC on applying automated planning techniques to
the control of modular production printing equipments. These
reconfigurable printers radically change the traditional design by
using simpler, interchangeable, but smarter components. Like many
other real-world applications, such as mobile robotics, this complex
domain requires real-time autonomous decision-making and robust
continual operation. To our knowledge, this work represents the first
successful industrial application of embedded domain-independent
temporal planning. Main challenges of applying automated planning
technology in this domain include compositional modeling, on-line
planning and exception handling, real-time planner control, and the
interaction with low-level controller. At the heart of our system is
an on-line algorithm that combines techniques from state-space
planning and partial-order scheduling. For example, our
planning-graph-based planning heuristic takes resource contention into
account when estimating makespan remaining. We suggest that this
general architecture may prove useful as more intelligent systems
operate in continual, online settings. Our system has been used to
drive several commercial prototypes and numerous hypothetical (but
realistic) printer configurations. When compared with
competition-winning state-of-the-art off-line planners in this domain,
our system is hundreds of times faster and often finds much better
quality plans. At the end of the talk, I will also discuss current
extensions of our current planning framework to other online planning
domains that share similar characteristics and also to objective
functions beyond the default maximization for machine productivity.

Bio: Minh Do is a Research Staff in the Embedded Reasoning Area at the
Palo Alto Research Center (formerly Xerox PARC). He graduated from the
Yochan planning group at Arizona State University in 2004 and has been
working on transferring his knowledge in offline domain-independent
metric temporal planning into fast online continual planning
applications. Besides temporal and online planning, Minh Do has
worked on other planning topics such as over-subscription planning,
planning as CSP/ILP/SAT, and integrating planning and diagnosis. He
has published a few dozens papers, filed several patents on automated
planning and co-authored the ICAPS best application paper award on
planning for high-speed modular printer control. This year, he is
co-chairing the deterministic track of the 6th International Planning
Competition.

Re: [CSE574 Planning & Learning] readings for next class

should work now

rao

On Mon, Apr 21, 2008 at 1:50 PM, Aishwarya Sivaraman <asivaram@asu.edu> wrote:
> Dr. Rao,
>
> I am unable to open the longer versions' link. I get a 404 error.
>
> http://rakaposhi.eas.asu.edu/cse574/notes/asst.pdf
>
>
> Regards,
> Aishwarya
>
>
> On Mon, Apr 21, 2008 at 1:23 PM, Subbarao Kambhampati
> <SUBBARAO.KAMBHAMPATI@asu.edu> wrote:
>
> > For the decision theoretic assistant paper, if you find the short one
> > too succinct, you might
> > consider the longer version here
> >
> > http://rakaposhi.eas.asu.edu/cse574/notes/asst.pdf
> >
> > rao
> >
> >
> > On Sun, Apr 20, 2008 at 9:32 PM, Subbarao Kambhampati
> > <subbarao2z2@gmail.com> wrote:
> > > Folks
> > > Here are two readings for next class:
> > >
> > > Primary: http://www.cs.orst.edu/%7Eafern/papers/ijcai07-assistant.pdf
> > >
> > >
> > > Secondary:
> > >
> > > http://www.cs.rochester.edu/~kautz/papers/gps-tracking.pdf
> > >
> > >
> > > Rao
> > >
> > > --
> > > Posted By Subbarao Kambhampati to CSE574 Planning & Learning at
> 4/20/2008
> > > 09:32:00 PM
> > >
> > >
> > >
> > >
> > >
> > >
> >
>
>

Re: [CSE574 Planning & Learning] readings for next class

For the decision theoretic assistant paper, if you find the short one
too succinct, you might
consider the longer version here

http://rakaposhi.eas.asu.edu/cse574/notes/asst.pdf

rao

On Sun, Apr 20, 2008 at 9:32 PM, Subbarao Kambhampati
<subbarao2z2@gmail.com> wrote:
> Folks
> Here are two readings for next class:
>
> Primary: http://www.cs.orst.edu/%7Eafern/papers/ijcai07-assistant.pdf
>
>
> Secondary:
>
> http://www.cs.rochester.edu/~kautz/papers/gps-tracking.pdf
>
>
> Rao
>
> --
> Posted By Subbarao Kambhampati to CSE574 Planning & Learning at 4/20/2008
> 09:32:00 PM
>
>
>
>
>
>

readings for next class

Folks
Here are two readings for next class:

Primary: http://www.cs.orst.edu/%7Eafern/papers/ijcai07-assistant.pdf

Secondary:

http://www.cs.rochester.edu/~kautz/papers/gps-tracking.pdf

Rao

Link to the goal graph based plan recognition discussed in today's class..

is here
http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume15/hong01a.pdf

Rao

ps: Here is a paper talking about minimizing a possibly non-minimal plan. It shows the NP-completeness of
      minimization and talks about polynomial sound-but-incomplete minimization algorithms

http://citeseer.ist.psu.edu/fink92spectrum.html 

an efficient temporal planner for handling required concurrency..

Here is a planner to appear in AAAI that realizes Tempo (described in the temporal planning paper you read) and
shows that it is efficient (recall that VHPOP like planners could already solve RC problems--while
DEP planners couldn't. Tempo was supposed to be a way of combining reachability heuristics with non-DEP
search space. this planner--Crikey3--realizes Tempo by making several interesting improvements to
SAPA's relaxed plan graph heuristics).

FYI
rao


http://www.cis.strath.ac.uk/cis/research/publications/papers/strath_cis_publication_2248.pdf

Reference on McLug

I discussed McLug at great speed towards the end of the class. Here are ways you can get more information on it:

You can look at the relevant section in the planning graph heuristics survey paper (that you had already printed):

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

or you can read an entire paper describing it.
 
http://rakaposhi.eas.asu.edu/dan-aij.pdf (journal version)

http://rakaposhi.eas.asu.edu/ICAPS0602BryceD.pdf (older conference version)


Rao

ps: Check out the CFP for a 2008 ICAPS workshop on planning under uncertainty, to get an overview of some of the
       hot/provocative issues in the area:

          http://www.ai.sri.com/~bryce/ICAPS08-workshop.html

Reading for next class

I am trying to find an easy survey for plan recognition--but as of now the best I could manage is the background chapter of Nate Blaylock's thesis.
It is 16 pages double spaced, and is available at

http://rakaposhi.eas.asu.edu/cse574/blaylock-pr.pdf

So unless I find something better, this is your reading for the next class.

Rao

(IMPORTANT) Schedule for the rest of the semester etc.

Folks:

 

 Here is a heads up on the rest of the semester.

 

===========

Class:

 

We will complete the treatment of FOMDPs on Tuesday (make sure you do the readings).

For the next topic--which will be discussed on Thursday and Tuesday 4/22,  I am trying to decide between POMDPs (partially observable MDPs) and plan recognition.

(If you have any preference let me know).

 

In the week of 4/22,  we will likely have 2 external speakers who will talk on applications of planning.

On 4/23 (Wednesday), Biplav Srivastava from IBM will speak on planning for web service composition

On 4/24 (Thursday)--during the class time--Minh Do will speak about applications of planning technology at Xerox PARC

(where they use it to plan paper paths through copiers!).

 

4/29 will be recap and summary. You will be doing an interactive review.

 

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

Assessment:

 

1. The class project report/paper will be due on the last day of classes (4/29).You should give yourself  at least 10 days to write the report.  Incoherent and badly organized reports will not be good for your grade.

 

2. The second homework also will be due on 4/29

 

3. The final exam for the class will be on the normal final exam day--which is May 6th (2:40--4:30pm)

 

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

 

 

cheers

Rao

 

Readings for Tuesday's class

A paper on the probabilistic planning competition (the first one). Describes PPDDL standard as well as
thumbnail sketches of competitors

http://www.jair.org/media/1880/live-1880-2554-jair.pdf



A paper on solving stochastic planning problems using determinizations
(it describes the algorithm that seems to work best on the current benchmarks)

http://rakaposhi.eas.asu.edu/tmp/hh.pdf

(note that this is a paper to appear in AAAI 2008. The proceedings version will be available on Tuesday (which is the deadline
for sending it :-)


You may also, optiionally, read the following critique of probabilistic planning competition:

http://www2.parc.com/isl/members/minhdo/icaps07_ws/papers/ICAPS06LittleI.pdf

Rao

Homework 2

Folks

 

 I put up some questions for homework 2. I expect to put more questions--on temporal planning, MDPs etc soon.

This homework will be due by the end of the semester. So you may want to work on it when you have time rather than

all at once...

 

 

I will send mails when I add more questions

 

rao

 

Cooperative planning using multiple agents

I haven't seen many comments on the blog for awhile, so here's something for discussion.

The topic of cooperative planning between multiple agents came up in another class I attend. No one in that class had heard of much research on this front. The questions are, what could be done, what has been done, and what interesting problems are there in this field?

I suggested at the time that if each agent was an executioner of the plan then these agents could be viewed as resources, and one among them could act as a scheduler assigning parts of the plan to each agent. The plan would be divied up and each agent given a sub plan that when all executed together would complete the larger plan. This is sort of cheating though because all of the planning is then being done by one agent, its just the doing that is cooperated. This was really all that I knew of that had been done in planning that could contribute to this topic.

The next bit was applying game theory. Do the agents assume the other agents are cooporative? How is a goal established? How does each agent plan around the possibility that other agents do not complete their part? How much communication and sensing do each of these agents have during planning and execution? In the case of non perfect communication could these agents adapt to unexpected problems during execution and adjust the plan?

If you know of successful research along this topic post a link to it. Otherwise feel free to post thoughts on any part of this.

Plan (and readings) for next Tuesday's class (4/8)

Folks:

 As I mentioned, I will be away on travel next Tuesday (4/8).  Sungwook Yoon will
lecture on Reinforcement Learning--which will be a natural continuation of (FO)MDPs that we are discussing
this week. RL involves interleaving learning, planning and execution.

The reading for 4/8  is the chapter 21 in Russell and Norvig.

regards
Rao

ps: Regarding the idea of having an assessment exam on 4/8--the feedback I got was in favor of exam at the end of the semester.
     

Readings for Tomorrow--LAO* and LRTDP

Part of what we will do tomorrow is to consider optimal policy
construction algorithms for
FOMDPs that make it look more like heuristic search that we have seen
for the rest of the semester.

In particular, we saw that classical planning can be seen as A*
search, and belief-space planning can be seen as
AO* search. Typical AO* search algorithms work on acyclic graphs (note
that AO* can be seen as a
problem decomposition framework, and cycles imply that you are
reducing a problem indirectly to itself).
The LAO* paper below shows that FOMDP policy construction can be seen
as AO* search on cyclic
graphs.

LAO*
http://www.cse.msstate.edu/~hansen/papers/laostar.pdf

Another idea for viewing value function computation is in terms of
fixed-depth expansion under a node
(as in game trees--in fact, in 471, I motivated game trees in terms of
RTDPs). The LRTDP algorithm
improves a bit on RTDP

LRTDP
http://ftp.cs.ucla.edu/pub/stat_ser/R319.pdf

rao