From: Kevin Sikorski (kws_at_cs.washington.edu)
Date: Mon May 19 2003 - 23:04:08 PDT
A Knowledge-Based Approach to Planning with Incomplete Information and
Sensing
by Ronald P.A. Petrick and Fahiem Bacchus
This paper presents a framework for representing a planning problem as
four knowledge bases, and evaluates a planner based on this approach.
Probably the biggest contribution of this paper is the idea of
representing planning problems as a series of knowledge bases. By
applying actions, it can then manipulating the formulas in the bases, thus
moving through the problem's knowledge space and eventually to the goal.
The next interesting idea is the concept of using worlds - basically
combinations of ways that propositions of unknown truth values can be
instantiated - to handle incomplete information. Before applying actions,
we must ensure that the preconditions to that action are true in all
worlds. Similarly, we know that a proposition is true if it is true in
all worlds.
With reguard to maintaining different worlds in order to model incomplete
information: the potential for exponential blow-up here frightens me. The
authors admit to using some type of "finite sets of formulas of a
first-order modal logic of knowledge". They do provide a reference, but
no real explanation of how it gets around the curse of dimensionality.
I don't see how this could nicely generalize to a continuous domain. As
always, you can discretize your space, but given that I don't see how they
handle exponential blow-up, this scares me.
How about worst-case performance? We aren't given a concrete problem that
this representation does very poorly on, or cannot solve that more
traditional planning techniques work on. They do mention a domain where
It is not clear to me what the knowledge base K_x represents, or why it
was included. Ironically, it is the only knowledge base that is new to
this paper, but of the 4 bases described, they spent the least amount of
time on this one.
The authors state in several places in the paper that their representation
restricts the types of knowledge that can be modeled. This would likely
make it impossible for this planner to solve certain types of problems.
Unfortunately, I don't have a strong grasp of what an example would be.
I don't understand the specifics of how this works well enough to give any
non-trivial possible future work like "see if there is a way to make this
representation handle the types of information it currently can't".
This archive was generated by hypermail 2.1.6 : Mon May 19 2003 - 23:04:10 PDT