From: Nan Li (annli_at_cs.washington.edu)
Date: Fri May 23 2003 - 10:45:14 PDT
Temporal Planning with Continuous Change / J. Scott Penberthy, Daniel Weld
This paper represents a POCL planner, ZENO, for domains with metric
quantified constraints and continuous time. It's sound and complete.
The representation in ZENO is expressive enough for metric quantities and
continuous change. It uses LP techniques to manage these constraints. More
specifically, ZENO uses a combination of Gaussian elimination for linear
equalities and an incremental Simplex algorithm for linear inequalities.
Non-linear constraints are dealt with by waiting until enough variables
are determined that they become linear. Another approach is to reduce the
goals to linear form. ZENO continuously checks metric constraints and
whenever inconsistency is detected, the procedure fails; if no violation
occurs, then newly generated linear constraints are post as subgoals.
For continuous change, ZENO restricts concurrent actions affecting the
same metric quantity, and limit constraints to linear inequalities.
Under these assumption, ZENO use two linear constraints for both
endpoints to represent the constraint on the whole interval.
ZENO is sound and complete. Intuitively, the soundness is ensured by the
soundness of linear programming techniques ZENO uses, and the completeness
is achieved as most POCL systems in a nondeterministic framework.
The algorithm is quite slow though. The bottleneck is to deal with those
temporal queries: whether there exists an interval that is covered by all
time windows? Although speed is not ZENO's first concern, it would be nice
to see how well optimization techniques can speedup the algorithm.
This archive was generated by hypermail 2.1.6 : Fri May 23 2003 - 10:45:16 PDT