From: Kevin Sikorski (kws_at_cs.washington.edu)
Date: Mon Apr 28 2003 - 23:51:44 PDT
This paper augments graphplan to support probabilistic MDPs, resulting in
two planners: PGraphplan, which is slower than vanilla Graphplan but finds
optimal policies, and TGraphplan, which is faster, but has no optimality
guarantees.
The authors use a few nice little tricks to prune the search space in
PGraphplan. First, they perform a backward sweep over the graph, removing
nodes that do not lie on any paths to the goals. This prunes the
searchspace, and is a major step toward making forward-chaining feasible.
They also annotate each node with a vector indicating which goal literals
are reachible from that node. This allows PGraphplan to determine, at any
particular state, if it is impossible to accomplish the goal.
The planners were tested on only four domains: Castle-Moat, 8-puzzle,
Flat-tire, and blocksworld. I would have liked to see a few more domains.
Also, how do PGraphplan and TGraphplan perform on deterministic MDPs
compared to classic Graphplan? Another interesting measurement would be
to see how these planners perform in probabilistic non-Markovian domain.
Clearly, the answer is "poorly", but perhaps one will work better than the
others?
The authors admit that TGraphplan still relies on Graphplan's concept of
exclusive operators. They also mention the idea of exclusive outcomes,
but do not develop it. Such a refinement to the planner's mutexes may
help prune searchspace, and improve execution speed.
This archive was generated by hypermail 2.1.6 : Mon Apr 28 2003 - 23:51:45 PDT