From: Kevin Sikorski (kws_at_cs.washington.edu)
Date: Tue May 27 2003 - 12:02:06 PDT
Temporal Planning with Mutual Exclusion Reasoning
David E. Smith, Daniel S. Weld
This paper presented a modification to the standard Graphplan plan graph,
changing the classical "leveled" graph into a cyclic graph. This Temporal
Planning Graph is significantly smaller than the classical plan graph
because information is not duplicated on subsequent levels. It also
allows the plan graph to be updated incrementally, somewhat speeding the
graph construction phase. Most significantly, because the graph is no
longer leveled, it allows us to accomodate actions of varying durations in
parallel. The other main contribution is the mutex reasoning machinary
for propagating mutexes from properties to actions and vice-versa, as well
as the asymmetric forms used to speed this reasoning.
The Experiments were pretty well done - we have a comparison of TGP and
SGP, as well as TGP without its cmutex reasoning. This gives us both a
baseline to compare TGP with, and also the ability to see how much the
mutex reasoning aids performance.
I would think Figure 5 plots times for each of the tested problems: The
X-axis is the times using CMutex reasoning, and the Y-axis is the times
without. I am just guessing, of course, and the numbers don't really work
out properly, so I'm probably wrong. Labels for the axes would help here
a lot. Maybe it's a log-log plot?
I also had some difficulty with section 7. The key idea here is that this
new assymmetric form makes reasoning with mutexes faster. However, I
don't see how converting them to a more complicated, and sometimes only
approximate, form is a good thing. Perhaps if experiments could be run to
show execution times with just the naive reasoning, we could compare them?
I also don't see how these forms are used to determine satisifiability.
So far all mutex work we've seen in class is related to "binary" mutexes,
that is, mutexes on exactly two objects. It would be interesting to see
the mutex reasoning extended to mutexes on n objects, and to see how this
would improve performance. I would expect to see fewer mutexes with
increasing n, so doing it for 3 or 4 should be enough, though I don't have
a good feel for how many of these we would see in common problems.
This archive was generated by hypermail 2.1.6 : Tue May 27 2003 - 12:02:08 PDT