From: Tal Shaked (tshaked_at_cs.washington.edu)
Date: Tue Jun 03 2003 - 10:42:04 PDT
Local Search Techniques for Temporal Planning in LPG - Gerevini, Serina,
Saetti, Spinoni
This paper discusses how to extend LPG to include temporal information for
actions and propositions, and new heuristics to guide the local search.
One of the important ideas of this paper was modifying the original notion
of actions graphs into temporal action graphs that are linear action graphs
with real values assigned to facts and actions (denoting times when actions
complete and propositions appear) and have a set of ordering constraints.
Linear actions graphs are an improvement over previous actions graphs
because they have a simpler structure resulting in faster and more accurate
heuristic computation.
Another important part of the algorithm is defining the heuristics to guide
the search and describing how they can be computed efficiently. TA-graphs
are modified by adding and removing actions to remove inconsistences (such
as unsatisfied preconditions). Considering all such actions and
modifications is considered a neighborhood for a given inconsistency and
TA-graph. Three heuristics - Execution cost (estimates the increase in
plan execution cost for the added action), Temporal cost (estimates the end
time of the added action), and Search cost (estimates the increase in number
of search steps to reach a solution) are used with weights that can vary to
guide the selection of actions and graph modifications.
The paper starts out at a high level, but then gets detailed very quickly
and often the reader is referred to previous papers and work. I didn't have
time to look at the details much or read previous work to try to understand
how the heuristics are computed (and done efficiently), but I'm not sure if
there is a better way to present them.
Apart from the high level description, I don't have much of an intuition of
the problems with the search. I suppose just like any such search, getting a
better idea of the structure of the domain and finding ways to automatically
tune the choice of inconsistencies to select the best ones first will help,
but specifically I have not thought of how this can be done.
This archive was generated by hypermail 2.1.6 : Tue Jun 03 2003 - 10:42:06 PDT