From: Tal Shaked (tshaked_at_u.washington.edu)
Date: Tue May 27 2003 - 00:07:14 PDT
Temporal Planning with Mutual Exclusion Reasoning – Smith, Weld
This paper discusses a technique for extending a planning graph to handle
certain types of temporal planning through the addition of some types of
mutexes and the related algorithms for reasoning about them and extracting a
solution.
One of the most important ideas mentioned is developing a compact
representation of the planning graph that saves space, execution cost, and
allows a more flexible representation that can handle time by marking when
actions can start and when literals can be reached.
Perhaps more important is the further distinction and addition of different
types of mutexes. Apart from the standard planning graph mutexes, the
notion of mutexes between actions and propositions is introduced, as well as
the distinction between eternal mutexes and conditional mutexes (that may go
away at some later time). The conditional mutexes are used primarily to
model conflicts between actions and propositions at certain times, and when
they involve actions, they may not be symmetric. Generally over time the
conditional mutexes may go away.
Once the graph has been constructed, the solution extraction phase involves
repeatedly trying all ways to satisfy goals on an agenda, and for each
action (or persistence action) that handles some goal at a given time, a new
goal is added with an earlier time to meet those preconditions. Eventually
either all goals are satisfied, or the time reaches 0 and no solution is
found.
Perhaps a different or longer example could have been used to illustrate
some of the other ideas, although this might be quite lengthy. For example,
the conditional mutexes are a little confusing so perhaps a longer example
illustrating asymmetry and other issues might be useful.
Figure 5 has no axes labeled and is not self-explanatory.
Can TGP find optimal plans, or minimize the time needed to reach some goal?
Instead of sliding things to the right, can perhaps the graph be built
backwards and then tilted to the left? Can metric constraints and
continuous change be added to this graph, perhaps as further annotations and
mutexes between the propositions and actions (although it might be hard to
reason about actions that increase some resource – what if in the middle of
a plan time could be added by a time-travel action?)
This archive was generated by hypermail 2.1.6 : Tue May 27 2003 - 07:28:24 PDT