From: Nan Li (annli_at_cs.washington.edu)
Date: Tue May 20 2003 - 10:22:44 PDT
A Knowledge-Based Approach to Planning with Incomplete Information and
Sensing / Ronald P.A.Petrick, Fahiem Bacchus
This paper presents a novel perspective for planning with incomplete
information ans sensing. The domain actions are represented
as the planner's domain knowledge, then translated to a set of first-order
logic for queries.
The basic thought is, no matter how much the planner knows about the state
of the world, it will act only based on what it actually knows, and the
goals are achieved only when it is confident that they are true based on
its knowledge. (Of course, the assumption here is that the planner's
knowledge is correct though incomplete.) Natually, the planner's knowledge
about domain actions should also be defined on its own knowledge, instead
of the real world. The advantage of this abstraction is, in some domains,
the planner can avoid being buried by tons of detailed possibilities. For
example, if the planner wants to achieve G, and it knows that some action
has a certain effect G, under all circumstances(p and !p, e.g), then all
the planner needs to do is to achieve the precondition of this action: it
can safely ignore the truth value of p.
Following this direction, domain actions are modeled in terms of how they
modify the knowledge state of the planner rather than in terms of how they
modify the physical world, like most planning systems do. Then the authors
adopt a similar approach as SAT, using other techniques for planning. They
translate the knowledge base of the planner into a set of first-order
logic formula. The operations on the knowledge base now can be implemented
as queris in the formula set, which can be done by advanced techniques.
The first-order formula representation make it possible for function
reasoning. But to make the queries tractable, it also add restrictions on
domains that require complex case analysis.
The planner surely can use a more efficient search algorithm, but that's
not an important problem. I think the authors should do some work on the
analysis of domains that potentially work well using this planner. One
other aspect to improve, as the authors mention, is to define a richer
representation for other problems (e.g.continuous types).
--
This archive was generated by hypermail 2.1.6 : Tue May 20 2003 - 10:22:46 PDT