From: Nan Li (annli_at_cs.washington.edu)
Date: Tue May 27 2003 - 10:51:47 PDT
Temporal Planning with Mutual Exclusion Reasoning / David E. Smith, Daniel
S. Weld
This paper extends GraphPlan to temporal planning. The planner, TGP,
allows different duration, concurrency, and limited temporally quantified
constraints.
When actions have differing durations, an important change must be done to
the original Graphplan: the symmetric alternate levels of actions and
propositions no longer makes sense, unless a bunch of "advance-time"
actions filled in. The authors represent a compact graph structure to
replace the levels. Recall actions/propositions at previous level are
copied to a newly generated level in the original graph structure, now
there are only two levles, each for actions and propositions. Each action
and proposition will be only one node in the graph, with labels marking
the first time it appears. This tight structure saves space and time
costs, and more importantly, makes it possible that actions/propositions
can be labeled by arbitrary numbers.
Next, the authors introduce new action/proposition mutex, which is defined
based on their conservative model of action: preconditions must hold
throughout execution, and the effects are undefined until the end of
execution. They also divide mutexes into two groups: eternal and
conditional mutexes. The conditional mutexes only hold in certain
intervals. These enhancements maintain concurrency information
between actions/propositions. Empirical results show noticeable speedup
with these techniques.
It's also interesting to compare the solution extraction procedure in TGP
and in the original Graphplan algorithm. To deal with concurrent actions,
a partially completed plan is kept during exploration. Here, since the
algorithm slides each action to the rightmost end, it might be
unnecessary to record of every executed action for search: only those
scheduled yet uncompleted action at the search time is needed.
Although TGP is fast enough for practical domains, it can handle only a
limit scope of continuous time constraints. So, as the authors mention, an
obvious open topic is to extend it to a richer temporal planning domain.
Speeding up exact reasoning for cmutex may be also wanted.
This archive was generated by hypermail 2.1.6 : Tue May 27 2003 - 10:51:50 PDT