From: Christophe Bisciglia (chrisrb_at_cs.washington.edu)
Date: Tue May 27 2003 - 10:58:35 PDT
D. Smith and D. Weld, Temporal Planning with Mutual Exclusion Reasoning
This paper present TGP, an extension of GraphPlan than allows actions to
take arbitrary lengths of time to complete.
One of the key contributions of this paper was noticing that since the
number of propositions is monotonically increasing, while the number of
actions and mutexes is monotonically decreasing. This allows a much more
compact representation of the planning graph requiring one proposition
layer and one action layer with a time value on each node where it
first/last appears. This is valuable because it applies not only to TGP,
but to regular GraphPlan as well.
Another idea that makes TGP work well was the distinction between eternal
and conditional mutexes. This allows for more powerful reasoning, and
helps manage the arbitrary duration of actions.
My only complaints with the paper are the examples were to small to grasp
some of the concepts, and like everyone else, I couldn.t tell what the
graph in figure 5 is trying to say.
I did not get the impression that the plans produced by TGP were optimal
(mainly because they are .shifted. to the right). I wonder if one could
apply any ideas from dynamic programming to build up an optimal plan once
a solution could be extracted. It seems like one all the goal propositions
exist at some time, that would be close to optimal (only off by shifting)
. could one optimally arrange the steps in that plan?
This archive was generated by hypermail 2.1.6 : Tue May 27 2003 - 10:58:36 PDT