From: Tal Shaked (tshaked_at_u.washington.edu)
Date: Fri May 23 2003 - 11:00:20 PDT
Temporal Planning with Continuous Change – Penberthy, Weld
This paper describes how to extend partial-order-planning to implement a
sound and complete planner that can deal with deadline goals, metric
preconditions, metric effects, and continuous change, through additional
constraints and links, and a modified algorithm to select and reduce goals.
An important aspect of this paper is Zeno’s action schema and language that
allows these temporal and metric definitions. This has to be descriptive
enough to model interesting problems, but also reasonable enough to fit
within the POP framework. In particular, this includes adding start and end
times to actions, and equality and inequality constraints that can model
metric values and continuous change through some time interval.
A plan consists of a set of instantiated actions, a set of causal links
(protection ranges), and a set of constraints (equality, inequality,
non-codesignation, metric). The planning algorithm tries all ways to
decompose a complex goal, choose actions to satisfy goals, and deal with
constraints, in search of a consistent plan. The additional constraints
that include linear equations, inequalities, and non-linear equations can be
solved using Gaussian elimination and linear programming algorithms
(Simplex), while non-linear equations will eventually be simplified to
linear equations.
The experiments section was sparse. I was also surprised that little was
said about the optimization problem, which is very natural for these kind of
domains (instead sound and complete was mentioned in several places). There
was little discussion of heuristics, which could at least have been brought
up briefly since most likely something was done about this.
Future work can focus on the optimization version and heuristics (relaxed
planning graph to get an idea of temporal limits, overlap not counting
precondition constraints). These kind of planning problems have a lot in
common with scheduling problems so perhaps this structure can be taken
advantage of in some better way.
This archive was generated by hypermail 2.1.6 : Fri May 23 2003 - 11:00:18 PDT