Contingent planning via heuristic forward search with implicit belief states Academic Article uri icon


  • 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 (Brafman & Hoffmann 2004), 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 forwardsearch 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 …

publication date

  • June 5, 2005