ECAI'14 Tutorial T12: Search Methods for Classical and Temporal Planning

Tutorial at the ECAI'14 conference

14:00-17:30 Tuesday August 19, 2014, Prague, Czech Republic

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 the most important forms of planning, including classical/deterministic planning and planning with timed system models. These include planning by symbolic methods such as SAT and its extensions, mixed integer linear programs, constraint programming, explicit 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 with timed systems
  7. Language extensions: durations, resources
  8. Connections to scheduling
  9. Search method: Explicit state-space search
  10. Search method: Planning my SAT, SMT, MILP, constraint programming
  11. State-space abstraction methods
  12. Planning with Continuous Change
  13. Language extensions for physical systems
  14. Extensions of search methods
  15. Planning systems
    1. preprocessing, algorithm portfolios
    2. evaluation of planners: benchmark problems, phase transition studies

Target Audience

The target audience consists of the following two groups of ECAI'14 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 ECAI 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