From: Sumit Sanghai (sanghai_at_cs.washington.edu)
Date: Tue May 27 2003 - 10:42:59 PDT
Temporal Planning with Mutual Exclusion Reasoning
-- D. Smith and D. Weld
Summary : The paper extends graphplan to do temporal planning.
An important contribution of the paper is the fact that
propositions are monotonically increasing and mutexes are monotonically
decreasing in a graphplan. This can be exploited to give a much compact
representation of the graphPlan (which uses only 2 sets of nodes :
propositions and actions along with numbers which indicate when they
can become true). This can be extended to the temporal domain quite
easily.
Another important idea is the concept of conditional and eternal mutex.
Eternal mutex are mutexes that are true between pairs at any point in time
whereas conditional mutexes are true only for a given time period. The
paper also introduces action proposition mutexes which are required in the
temporal domain for a better analysis. These mtexes can be efficiently
built using an incremental update.
The paper then presents a solution extraction technique which is similar
to grpahplan except for a time domain.
One of the problems is the fact that conditional mutexes can get
arbitrarily complex. Thus, they have to be approximated which is done
using the concept of asymmetry. This though can lead to a loss of
information.
Some of the future work can be to explore metric constraints and
continuous change problems and extending TGP to handle them. SOme others
are already present in the paper such as extending to handle "trigger"
preconditions/temporary effects etc. A further future work could be to
compare time taken to build the exact cmutex vs tme taken to extract. If
one builds the exact cmutexes it will take a large time, but it will
reduce the time for solution extraction because of better information.
This archive was generated by hypermail 2.1.6 : Tue May 27 2003 - 10:43:02 PDT