文档介绍：... ... ....
Artificial Intelligence 170 (2006) 507–541
ate/artint
Conformant planning via heuristic forward search: A new approach ✩
Jörg Hoffmann a,∗,
a Max Planck Institute puter Science, Stuhlsatzenhausweg 85, 66123 Saarbrücken, Germany
b Department puter Science, Ben-Gurion University, PO Box 653, Beer-Sheva 84105, Israel
Received 16 July 2004; received in revised form 2 December 2005; accepted 4 January 2006
Available online 9 February 2006
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 essful 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 F 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.
2006 Elsevier . All rights reserved.
Keywords: Planning under uncertainty; Heuristic search planning; Relaxed plan heuristic
1. Introduction
Conformant plan