From: MAUSAM (mausam_at_cs.washington.edu)
Date: Fri May 23 2003 - 11:06:03 PDT
Temporal Planning with Continuous Change
Penberthy and Weld
This paper describes a regression search planner called ZENO which solves
temporal planning problems involving metric constraints, deadline goals
and continuous change.
The key idea of the paper is the expressive first order language that it
uses and handling of this language to do the search. In particular, it
searches the space of <partially specified plans, goals to achieve>. Goal
reduction is done by interval splitting i.e. splitting an interval subgoal
into two subinterval subgoals. This splitting is done upto a preset depth
to avoid infinite branching. Zeno also protects the fluents from threats
by promotion,demotion, confrontation.
For constraint management linear constraints are solved by Gaussian
elimination and simplex method. The algorithm is made complete by using
Iterative Deepening Search.
In the paper, the search technique used was DFS. I would suspect the
possibility of a heuristic based search here to speed it up.
Moreover, the paper itself mentions that the performance is not all that
great. In fact, the performance would deteriorate with more objects. I
wonder if modern techniques which exploit the inherent relational
structure of the domain could be used to speed things up.
The other important key issue is how to involve actions with uncertain
effects in the system. As one can see, output of this program is a plan,
whereas output of problems with uncertainty is usually a policy. And hence
those are the relevant search spaces as well. Could we reach a joint
search space for the two problems, we might also be able to handle them
together.
This archive was generated by hypermail 2.1.6 : Fri May 23 2003 - 11:06:06 PDT