非表示:
キーワード:
-
要旨:
Contingent planning is the task of generating a conditional plan
given uncertainty about the initial state and action effects, but
with the ability to observe some aspects of the current world state.
Contingent planning can be transformed into an And-Or search problem
in belief space, the space whose elements are sets of possible
worlds. In \cite{CFF}, we introduced a method for implicitly
representing a belief state using a propositional formula that
describes the sequence of actions leading to that state. This
representation trades off space for time and was shown to be quite
effective for conformant planning within a heuristic forward-search
planner based on the \ff\ system. In this paper we apply the same
architecture to contingent planning. The changes required to adapt
the search space representation are small. More effort is required
to adapt the relaxed planning problems whose solution informs the
forward search algorithm. We propose the targeted use of an
additional relaxation, mapping the relaxed {\em contingent} problem
into a relaxed {\em conformant} problem. Experimental results show
that the resulting planning system, \contff, is highly competitive
with the state-of-the-art contingent planners \pond\ and \mbp.