From: Alexander Yates (ayates_at_cs.washington.edu)
Date: Tue May 20 2003 - 01:25:30 PDT
Review of "A Knowledge-Based Approach to Planning with Incomplete
Information and Sensing," by Ronald Petrick and Fahiem Bacchus.
By writing operators that act directly on an agent's knowledge rather than
on sets of possible worlds, PKS is able to find contingent plans very fast.
The main idea in this paper is the representation used for planning domains.
The authors describe a representation system that allows only a very
simplified set of knowledge-producing and -erasing actions, namely those
that give the agent knowledge of ground atomic formulas or the value of an
unnested function term. They also include a way to encode XOR knowledge
(the K_x database), which they claim is an important kind of knowledge found
in many planning problems. They do not allow encoding of arbitrary SAT
terms; in particular, ordinary disjunctive clauses can't be encoded.
Operators then act directly on the knowledge in the various databases,
rather than on objects in the real world.
I had a little trouble understanding what was really so different about
their approach. The K_x DB may be new, but in looking at some of the
operator descriptors from the Puccini paper we read, it seems like the
operators are similarly working on the "knowledge level", as the authors
would put it. What's the difference, really, between K(p) in PKS and
satisfy(p) in a Puccini effect? And both languages have conditional
effects, "observe" effects, run-time variables, etc. It seems like the
speed of their planner has more to do with their (incomplete) IA algorithm
and the depth-first search than anything else.
The paper describes the need for further implementation. In addition, it
would be nice to see a comparison between this approach and other contingent
planners, both in terms of planning performance and in terms of the kinds of
problems they can understand (the complexity of the planning language).
Alex
This archive was generated by hypermail 2.1.6 : Tue May 20 2003 - 01:25:30 PDT