Temporal Planning with Constraints (Preliminary Report)

We present ZENO, an implemented, partial-order planner that handles simultaneous actions occurring over extended time intervals. The action language supports a large subset of KRSL, including metric constraints, deadline goals, and synergistic (additive) effects. We believe the algorithm is both sound and complete. The chief technical contributions are (1) token reduction breaks complex goals into pieces that can be systematically supported, (2) incremental algorithms from operations research determine the consistency of temporal and other metric constraints, and (3) lazy evaluation and the Mean Value Theorem are exploited to cope with actions involving continuous change.