From: Kevin Sikorski (kws_at_cs.washington.edu)
Date: Mon Jun 02 2003 - 23:26:58 PDT
Local Search Techniques for Temporal Planning in LPG
by Algonso Gerevini, Ivan Serina, Alessandro Saetti, Sergio Spinoni
This paper combines heuristic-guided search, stochastic local search, and
action graphs in a temporal planner. The primary contributions of this
paper was the use of local search via WALKPLAN. At each step, they select
the next TA-graph through a variant on WALKSAT, estimating the "value" of
each possible graph in the local search neighborhood through heuristics.
The huge spike on the Rovers-Time/Speed graph is interesting. Is there
some artifact in the problem that makes this much harder to solve than the
others? Or is this an artifact of the WALKPLAN module (ie, unlucky random
numbers)? If it's the former, it would be interesting to see what about
the problem made it so much harder to solve. The authors also only
presented graphs for 3 of the 5 problem domains - I would like to know if
LPG performed better or worse in the missing two domains.
This paper was pretty dense. They did admit that there was a longer more
in-depth paper. Adding something to improve the organization, and offer
an early, high-level algorithm for the planner would have helped.
It may be useful to incorporate some degree of learning in the
WALKPLAN/heuristic search. For example, the evaluation function of
similar sections of the TA graph would likely be similar. This could
produce a heuristic of the heuristic function, allowing the planner to
focus compute time on more accurately examining more promising areas of
the evaluation function.
This archive was generated by hypermail 2.1.6 : Mon Jun 02 2003 - 23:27:00 PDT