|CSE Home||AI Home||About CSE||Search||Contact Info|
The ZENO Temporal Planner
We have built a least commitment planner, ZENO, that handles actions occuring over extended intervals of time and whose preconditions and effects can be temporally quantified. These capabilities enable ZENO to reason about deadline goals, piecewise-linear continuous change, external events and, to a limited extent, simultaneous actions. In particular, actions are allowed to overlap in time only when their effects do not interfere. While other planners exist with some of these features, ZENO is different because it is both sound and complete.
Since ZENO relies on constraint satisfaction for all temporal and metric aspects reasoning, sound and efficient algorithms are essential. Specialized routines cooperate to handle the different types of constraints: codesignations, linear equalities, linear inequalities, and nonlinear equations.
Codesignations are handled as they were in the UCPOP planner. A simple algorithm maintains equivalence classes of all logical variables, then determines whether the noncodesignations are inconsistent with the classification.
Mathematical formulae posted by ZENO are parsed dynamically into a set of linear equations, inequalities, and pairwise nonlinear equations. These canonical forms are identical to the matrix representation of equations used in linear algebra and operations research.
Linear equations are solved by Gaussian elimination, linear inequalities by the Simplex algorithm, and nonlinear equations are delayed until they become linear via the solution of other equations and inequalities. To ensure sound constraint handling, each equality that is derived by one algorithm is passed to all other algorithms.
Determining an inconsistency using Gaussian elimination is straightforward; if a constraint c=0 is detected during elimination, where c is non-zero constant, then the equations are inconsistent. Finding inconsistencies in linear inequalities is a bit trickier. ZENO uses the incremental version of the phase one Simplex algorithm, devised for the CLP(R) programming language. To expedite temporal queries, ZENO caches temporal relations with Warshall's transitive closure algorithm.
For further information, see
J.S. Penberthy, Planning with Continuous Change. PhD thesis, University of Washington, 1993(available as technical report UW-CSE-93-12-01).
Computer Science & Engineering|
University of Washington
Seattle, WA 98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX
[comments to Corin Anderson]