Conformant planning is the problem of finding a sequence of actions for achieving a goal in the presence of uncertainty in the initial state or in action effects. On the other hand, Contingent planning is concerned with the problem of achieving goals in the presence of incomplete information and sensing actions. Both problems have been approached as a path-finding problem in belief space where good belief representations and heuristics are critical for scaling up. In this tutorial, we present algorithms for both conformant and contingent planning that rely on translations to classical planning problems, solved by an off-the-shelf classical planner.

The first half of this 1.5 hours tutorial will be devoted to present translations from conformant planning (i.e. planning with incomplete information and no sensing) into classical planning. Compiled classical problems are solved by a classical planner, taking advantage of heuristics developed for classical planning: as long as heuristics for searching in belief space have not be as successful so far. On top such a translation was built the T0 conformant planner, best performer of conformant track at IPC 2006. These general translation schemes are sound and we establish the conditions under which such translations are also complete. Thus, we present the notion of conformant width, that characterize the size of classical translations that are guarantee to be complete.

In the second half of the tutorial, we will focus on how to build efficient action selection mechanisms for planning with sensing (contingent planning) on top of conformant planning translations. In fact, the ability to find conformant plans is needed in contingent settings where conformant situations constitute a special case. Planning with incomplete information and partial observability is the most complex setting for planning. We will show how to obtain a closed-loop algorithm for achieving the goal in planning with sensing, using a conformant translation. Also, we will introduce the notion of contingent width, similar to the former conformant width, to characterize contingent planning problems.

Finally, building on the same translations, we will show how to obtain robust fine-state controllers. Finite-state and memoryless controllers are simple action selection mechanisms widely used in domains such as videogames and mobile robotics. We show how to develop model-based method for deriving finite-state controllers automatically. In particular, the models represent a class of contingent problems where actions are deterministic and some fluents are observable. The problem of deriving a controller from such models is converted into a conformant planning problem that is solved using classical planners, taking advantage of a complete translation introduced before. All algorithms will be illustrated with examples.

We expect the tutorial to be interesting for general AI researchers, as we build on simple ideas that has been successful, and that we introduce step by step. We will discuss other similar approaches and their limits, e.g. how a representation affects heuristic search, to put the translations introduced into context.