From: Kevin Sikorski (kws_at_cs.washington.edu)
Date: Thu May 22 2003 - 23:05:44 PDT
Temporal Planning with Continuous Change
J. Scott Penberthy and Daniel S. Weld
This paper describes a partial-order temperal planner called ZENO. It
uses an expressive typed, first-order language to represent the available
actions, and it operates by regression search. At each step, the planner
either decomposes a complex goal into two or more simpler ones and
possibly splitting the time interval it's working in, selecting an action
to satisfy a goal, or working with constraints. No proofs are given, but
it is said that the algorithm is sound and complete.
The plan found for the example problem is not optimal: you could mix the
fast-fly and slow-fly actions while flying the first leg to get better
time. I'm not really sure why it's not found. Is it because during goal
reduction, if a time interval is split, the split (ie 50-50%, 25-75%, etc)
is determined by the length of time that actions might take, and for some
reason, the fact that you might want to fly between two cities at two
different speeds is never checked for? Not much time was spent on this
interval splitting, so I really can't tell. But if this is the case, it's
a fundamental flaw that prevents ZENO from finding "more optimal" plans.
In the Constraint Management section, it mentions that it handles linear
equations via Gaussian Elimination, and linear inequalities via Simplex.
But ZENO just waits and hopes that something eventually simplifies
nonlinear equations into one or more linear equations - it doesn't solve
them directly. Is it guaranteed that this will always happen? Or is it
possible that in sufficiently convoluted example could create a system of
nonlinear equations that can't be broken down in this manner?
I thought for a bit about how I'd solve the given plane problem as a
human. Basically, I'd solve the problem first ignoring the fuel issue.
This would probably also create simple time constraints like "I have to
fly-fast on at least one of the legs of the trip or I won't make it in
time." Then, I'd fix-up my plan to handle fuel concerns. In terms of
applying this approach to ZENO, one can look at it in two ways: 1) this is
similar to HSPr, in that we use a solve a simpler problem to generate a
heuristic, but then we just fix-up the resulting plan rather that start
planning anew. Or 2) we can plan through the problem, but disregard
constraints such as "we must always have a non-negative amount of fuel on
board", and go through a second phase where we just fix-up the fuel issue.
There's the huge problem of deciding what issues in a given problem to
avoid too... Adding something like this to ZENO would be a good way to
extend it, and likely speed it up dramatically.
This archive was generated by hypermail 2.1.6 : Thu May 22 2003 - 23:05:46 PDT