From: Russell Power (rjpower_at_u.washington.edu)
Date: Tue Nov 18 2003 - 23:59:00 PST
The authors present a planning method that builds on earlier work in the
area of Markov decision processes, creating an algorithm that avoids some
unnecessary computation performed in previous work.
The paper describes a modified LAO* algorithm that uses the notion of
'symbolic' searching - searching through sets of states, rather than
individually - that allows the authors to prune the area searched by the
algorithm. The authors conclude from their experimental results that in the
case of larger problem sets, this pruning is effective, and dramatically
reduces the amount of work needed to search.
The use of artificial examples to exhibit the efficiency of the new
algorithm is questionable. Had the authors chosen some other, widely used
example problem, the results would be much stronger. As it is, it is hard
to tell what to think (e.g. - bubble sort is really fast on unsorted
inputs).
The authors have demonstrated that there is significant potential in
exploring this area further. Certainly other methods of pruning the search
tree may exist that do not have the same level of overhead as that found in
the presented method. The use of heuristics in addition to dynamic
programming is an interesting and novel idea, and it would be interesting to
see what deeper investigation might lead to.
Also, someone might show P=NP and blow the whole field out of the water.
_That_ would be an interesting development.
This archive was generated by hypermail 2.1.6 : Tue Nov 18 2003 - 23:59:31 PST