IJCAI'13 Tutorial TF3: AI Planning: Reasoning with Transition Systems

Tutorial at the IJCAI'13 conference

Monday August 5, 2013, Beijing, China

Presenter: Jussi Rintanen

Tutorial presentation (PDF)

Planning is a fundamental problem in the behavior of intelligent beings, and is therefore of importance in solving many types of computational problems arising when constructing intelligent agents.

During the last ten years a number of algorithmic breakthroughs have lifted the efficiency of domain-independent planning to the level required in many real-world applications. The tutorial presents the most important approaches to state space traversal as applied in algorithms for classical/deterministic planning and in implementations of algorithms for more general forms of planning. These include planning as satisfiability, planning by heuristic state-space search, and logic-based symbolic techniques for state space traversal.

We will explain how the main approaches work, what are their strengths and weaknesses, and where the research area is heading next.

  1. Introduction
    1. state-space search, and its application in planning and other areas of AI
    2. domain-dependent vs. domain-independent planning
    3. example applications
    4. relation to model-checking in CAV, DES diagnosis, intelligent control
  2. Action languages
    1. transition systems
    2. state variables, actions (operators)
    3. STRIPS, PDDL, Petri nets, and other formalisms
  3. Planning by explicit state-space search
    1. state-space search with A* and other heuristic search algorithms
    2. pruning techniques: symmetry reduction, partial order reduction
    3. heuristics: relaxations, pattern databases, aggregation
  4. Logical (symbolic) data structures for reachability
    1. representation of actions and transition relations is logic
    2. manipulation of transition relations (composition, image/preimage operations)
    3. symbolic state-space traversal algorithms
    4. normal forms: BDD, DNNF, and others
  5. Planning as satisfiability
    1. reduction of planning to SAT
    2. parallel plans
    3. plan search, optimal vs. non-optimal plans
    4. algorithms for SAT
  6. Planning systems
    1. preprocessing, algorithm portfolios
    2. evaluation of planners: benchmark problems, phase transition studies
    3. extensions: temporal, conditional

Target Audience

The target audience consists of the following two groups of IJCAI'13 participants.
  1. AI researchers interested in the state-of-the-art in planning techniques. The tutorial is intended for the general AI community audience and only assumes basic knowledge in AI and the propositional logic. Because of the wide applicability of basic planning techniques, applications potentially benefiting from planning technology span a wide range of subfields of AI. The tutorial gives an overview of the basic approaches to planning and provides a basis for assessing the suitability of different planning techniques for specific applications. The objectives best served by the proposed tutorial are the following.
  2. Graduate students and researchers working in AI planning. The approach in presenting the material is new and therefore also of interest to people already working in AI planning. We present the material in a unifying way that makes it easy to see connections between different strands of earlier work and to place earlier results in the big picture.
The tutorial assumes minimal prerequisite knowledge. Knowledge of the classical propositional logic and of the basic search algorithms in AI are sufficient.

Interest to IJCAI Audience

Planning is a fundamental problem in the behavior of intelligent beings, and is therefore of importance in solving many types of computational problems arising when constructing intelligent agents. The focus of the tutorial is in the algorithmic basis of different forms of state-space traversal which are needed in efficiently solving a wide range of AI planning problems stretching from the simplest forms of deterministic/classical planning to conditional planning and more general forms of multi-agent planning and game-theoretic planning.

Supplementary material