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.
Introduction
state-space search, and its application in planning and other areas of AI
domain-dependent vs. domain-independent planning
example applications
relation to model-checking in CAV, DES diagnosis, intelligent control
Action languages
transition systems
state variables, actions (operators)
STRIPS, PDDL, Petri nets, and other formalisms
Planning by explicit state-space search
state-space search with A* and other heuristic search algorithms
pruning techniques: symmetry reduction, partial order reduction
Logical (symbolic) data structures for reachability
representation of actions and transition relations is logic
manipulation of transition relations (composition, image/preimage operations)
symbolic state-space traversal algorithms
normal forms: BDD, DNNF, and others
Planning as satisfiability
reduction of planning to SAT
parallel plans
plan search, optimal vs. non-optimal plans
algorithms for SAT
Planning systems
preprocessing, algorithm portfolios
evaluation of planners: benchmark problems, phase transition studies
extensions: temporal, conditional
Target Audience
The target audience consists of the following two groups of
IJCAI'13 participants.
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.
Introduce novices to major topics of Artificial Intelligence.
Introduce expert non specialists to an AI subarea.
Survey a mature area of AI research and/or practice.
Provide instruction in established but specialized AI methodologies.
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.