Tutorials

Decision diagrams have proved to be a useful data structure for model checking, temporal verification, graphical model inference, and factored planning (factored MDPs and POMDPs among may applications). This tutorial will cover the foundations of binary and algebraic decision diagrams (BDDs & ADDs) -- their properties, their algorithms, their use in various automated planning settings (including a discussion of when other techniques are preferable to decision diagrams), and tricks of the trade (variable orderings, approximation, and application-specific operations) that help one achieve maximal efficiency in practice. Beyond BDDs and ADDs, the tutorial will also cover a variety of less-used but important decision diagrams and their applications: Zero-suppressed DDs (ZDDs) for set representation, Affine ADDs (AADDs) for arithmetic function representation, recent extensions of decision diagrams to continuous variables, and many others (Factor Edge Value BDDs, Binary Moment Diagrams, etc.) as time permits. While focusing on the theory of decision diagrams, the tutorial will constantly relate the theory to practical applications in automated planning and scheduling

Length: 1.5 hours

This tutorial provides a survey of heuristic search algorithms, focusing on algorithms that find suboptimal solutions. We will cover algorithms that provide quality bounds, beam search algorithms, and anytime search algorithms. The commonality between these families of algorithms is that they all sacrifice finding optimal solutions in order to find solutions faster. The goal will be to develop an understanding of when the searches are likely to perform well and when they are likely to perform poorly.

Length: 1.5 hours

Handling g-value plateaus is an open and challenging problem for domain independent planning. One promising approach for dealing with these plateaus is to search on multiple objectives, hoping that the guidance of one cost metric will pull the search out of plateaus in another. For cost based planning, plan length is a natural candidate for this additional guidance. This tutorial examines how the field of heuristic search has been tackling the problem of using both solution cost and solution length within a single algorithm, with a special focus on how algorithms can incorporate solution length without abandoning guarantees on solution quality.

Length: 1.5 hours

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.

Length: 1.5 hours

Petri nets are a formalism for modelling discrete dynamical systems, widely used in automated verification (model checking). There is a wealth of results and algorithmic techniques for Petri nets, often based on principles quite different from those commonly employed in planning. This tutorial aims to present the basics of Petri nets, with focus on their relation to modelling formalisms used in planning and the exchange of algorithmic techniques between the two fields.

Length: 1.5 hours

Intended audience:

• Members of the Planning (and related) communities, who are working on solving problems via graph search and related algorithms and data structures.
• Researchers and Practitioners interested in the application of model checking techniques outside of the verification area.

Abstract:

The Model Checking Problem is the question whether a mathematical model (typically of a real-world system) fulfills its specification (often given as a set of logic formulas). Automatic solutions to solve such model checking problems have been researched and refined for close to 30 years now. Since reaching maturity, they have become a standard quality assurance method in, e.g., the semiconductor and aviation industries.

In this tutorial, we aim to connect research on model checking and the plethora of techniques it spawned (or incorporated successfully) to strongly related, and sometimes overlapping fields: graph searching, planning, scheduling, artificial intelligence.

Contents:

• Introduction to Model Checking: expressing properties, flavors of models, diagnostics
• Application areas and success stories: hardware, software, scheduling, puzzle solving, ...
• Conquering the search space: enumerative vs. symbolic methods
• Algorithmic techniques: sequential, directed, multi-core, distributed, and I/O-efficient algorithms (and combinations thereof)
• Symbolic methods: state space compression, binary decision diagrams, translations to SAT problems
• State-of-the-art techniques: CEGAR, bounded model checking, SMT solvers
• Engineering challenges: an explosion of modelling languages and exploration techniques

Slides: (pdf)

Length: 1.5 hours

This tutorial will focus on the application of motion planning for mobile manipulation in unstructured environments. Topics will include the following:

• integrating real time sensing with planning to deal with dynamic environments
• integrating planning and reactive control for mobile manipulation
• dealing with kinematic constraints
• plan monitoring and replanning in dynamic environments
• combining different planning techniques
• application of these techniques to real world problems in object manipulation, door opening, cart pushing

Length: 1.5 hours

RDDL is the Relational Dynamic Influence Diagram Language, the domain modeling language used in the ICAPS 2011 International Probabilistic Planning Competition. RDDL has been developed to compactly model real-world planning problems that use boolean, multi-valued, integer and continuous variables, unrestricted concurrency, non-fluents, probabilistic independence among complex effects (important for exogenous events), aggregation operators in addition to quantifiers, and partial observability. While RDDL addresses some of the probabilistic modeling limitations of PPDDL, it's deterministic subset also addresses some modeling limitations of PDDL (e.g., models needing nonlinear difference equations or unrestricted concurrency). This tutorial provides a general introduction to RDDL, it's semantics, and a number of detailed examples like elevator and traffic control to demonstrate it's expressive power. It also provides a brief introduction to the rddlsim software that permits the simulation, evaluation, and visualization of planners and planning domains.

Length: 1.5 hours