hide
Free keywords:
-
Abstract:
Conformant planning is the task of generating plans given uncertainty about the
initial state and action effects, and without any sensing capabilities during
plan execution. The plan should be successful regardless of which particular
initial world we start from. It is well known that conformant planning can be
transformed into a search problem in belief space, the space whose elements are
sets of possible worlds. We introduce a new representation of that search
space, replacing the need to store sets of possible worlds with a need to
reason about the effects of action sequences. The reasoning is done by
implication tests on propositional formulas in conjunctive normal form (CNF)
that capture the action sequence semantics. Based on this approach, we extend
the classical heuristic forward-search planning system FF to the conformant
setting. The key to this extension is an appropriate extension of the
relaxation that underlies FF's heuristic function, and of FF's machinery for
solving relaxed planning problems: the extended machinery includes a stronger
form of the CNF implication tests that we use to reason about the effects of
action sequences. Our experimental evaluation shows the resulting planning
system to be superior to the state-of-the-art conformant planners MBP, KACMBP,
and GPT in a variety of benchmark domains.
