From: Alexander Yates (ayates_at_cs.washington.edu)
Date: Thu May 22 2003 - 20:13:49 PDT
Review of "Temporal Planning with Continuous Change," by Penberthy and Weld.
The authors describe a planner called Zeno that can handle metric
constraints on real-valued properties, including constraints about when
actions occur and for how long.
The main idea of the paper is to reduce the planning problem to a search
problem where at each step the planner must solve a linear program to check
for consistency in its partial plan. The planning problems that Zeno can
solve are written in a highly expressive language that can specify
continuous quantities and constraints over continuous variables, most
importantly time. The start time and the end time of an action (and thus
the duration) can be constrained, and the duration of a plan can be
constrained. Zeno is sound and complete if all the constraints are
(piecewise) linear or logical constraints, which means that the planner can
check the consistency of all the metric constraints using a linear program
solver.
The experimental evaluation was "terse." Also, it's hard to see why it's
important to have a sound and complete planner for these problems if the
planner is too slow to solve useful problems.
The authors built in a simplex solver (or at least part of one), but then
didn't use it to do optimization. That seems like an obvious direction for
research: extending the kinds of problems that Zeno can handle with
optimization problems. They seem particularly natural extensions in a
domain that already has metric quantities and a built-in notion of
time--instead of "Can you meet this deadline?" you could say, "Do this as
fast as possible" (or some linear combination of variables to optimize, like
resource consumption and time). Another obvious direction for research is
improving the speed of this planner (probably at odds with the first thing I
said) using heuristics, reachability analysis, mutexes...
This archive was generated by hypermail 2.1.6 : Thu May 22 2003 - 20:13:50 PDT