T1. Approximation Based Reasoning and Conformant Planning --- Bridging Reasoning About Actions and Changes (RAC) and Planning

Open slides
Open handout

Presenter

Abstract

The thesis of this tutorial is that the study in reasoning about actions and changes can significant contributions to the development of conformant planning systems in particular and planning systems in general.

Over the years, several conformant planning systems employing different representation languages and different methods of reasoning have been developed. On the one hand, we can find many planning systems (e.g. CFF and POND) employ PDDL, a simple representation language with limited expressive power, and use sophisticated heuristics in the search for plans in the space of belief-states. On the other hand, we can find other systems which use a specialized representation language (e.g. the language used by the systems PKS and KACMBP) and employ sophisticated reasoning algorithms in the search for conformant plans. While the first approach relies on heuristic, the second one seems to gain performance through specialized algorithms. Yet, there is no documentation on the impact of reasoning method on the performance of planning systems.

It is also interesting to observe that theoretical results in reasoning about actions and changes do not often find their ways to be implemented in planning systems. As an example, several solutions to the ramification problem have been discussed and many languages allowing the representation and reasoning with arbitrary state constraints have been developed. Furthermore, reports on the usefulness of being able to deal directly with state constraints in planning have been published. Yet, the majority of top planning systems do not accept inputs containing arbitrary constraints. This raised the question of how theoretical studies in reasoning about actions and changes can be useful for the development of planning systems.

This tutorial addresses the above issue by presenting the development of several conformant planners. The key reasoning modules of these planners are based on the approximations obtained during our study on reasoning about actions and changes. As such, these planners are the "by-product" of our investigation of the problem in reasoning with incomplete information. We will discuss possible improvments for existing conformant planners.

The tutorial will include a discussion on the different problems in reasoning about actions and changes (frame problem, qualification problem, and ramification problem) and their well-known solutions.

The tutorial will be continued with the various reasoning methods in the presence of incomplete information and sensing actions. Possible world semantics and approximation based reasoning will be discussed.

The tutorial will also include a discussion of methods for complete reasoning based on approximation and its application to conformant planning. Experimental evaluation will be provided. Applications to classical planners will also be dicussed. In each of the above discussions, complexity results for the planning problems will be provided, whenever it is appropriate.