From: Kevin Sikorski (kws_at_cs.washington.edu)
Date: Thu May 29 2003 - 22:41:54 PDT
Sapa: A Domain-Independent Heuristic Metric Temporal Planner
Minh B. Do & Subbarao Kambhampati
This paper introduces a planner called Sapa, a heuristic-guided temporal
planner which can also take into account temporal goals and metric
resources.
There are three main contribution of this paper, all of which are
interrelated: their time stamped state, the RTPG, and their usage of
heuristics in temporal planning. The time stamped state indicates not
only a state in the conventional manner, but also functions indicating the
metric resources, conditions to be maintained over a time interval, a
queue containing events that will transpire, and another set of predicates
that aren't entirely clear to me. The Relaxed Temporal Planing Graph
(RTPG) is an offshoot of the classic planning graph, but contains no
delete lists (and hence no mutexes), and ignores effects that reduce
resource levels. The RTPG is then used to produce one of a number of
admissible and non-admissible heuristics to estimate the distance from any
given time stamped state to the goal.
I'm somewhat confused about the performance of the planner using the
sum-act heuristic: it is unable to solve the zeno4 and log-p3 problems,
but solves the very next. The sum-dur heuristic performs similarly,
missing zeno3, 5 and 6, but solves 7-9, and some of these quite quickly.
I have a hard time believing that this is just an artifact or dumb luck.
Some exploration into what causes this would be nice.
I was a little disappointed that the admissible heuristics were not
feasible in even these tiny problems, but I think this is understandable.
Over all, I'd say the experiments were pretty well done.
One interesting direction in which to extend this planner would be to add
partial observablity. However, since this is a metric temporal planner,
it allows us to add uncertainty in several different ways that don't
appear in classical planning, namely in determining the current time, and
in resource management. In other words, how could this planner be
extended to handle actions that don't always take the same amount of time,
and we don't even know exactly how much time they take (say, perhaps
within +/- 5%)? Or, when we never know exactly how much resources each
action consumes (again, to within a percentage). Given how complicated
POMDPs are, and the complexity of temporal planners relative to classical
planners, this would be a very "interesting" type of planner to examine.
Another direction might be to incorporate unreliable agents - unreliable
in the sense that they may randomly fail, or that they may lie, and
attempt to act in a manner that benefits them. Such cases would likely
occur in real life, such as building a partially observable metric
temporal planner for an entire airport: employees might lie about their
location to gain minor personal advantages, planes might fail
unexpectedly. I'd consider borrowing multi-robot techniques for a system
like this, as just using contingency planning might make the state space
too large to be solvable.
This archive was generated by hypermail 2.1.6 : Thu May 29 2003 - 22:42:47 PDT