Tutorials
We are pleased to present the ICAPS-13 Tutorial Program. This year the program included 8 tutorials given by leading scientists working in the area in automated Planning and Scheduling.
Tutorials took place on Tuesday June 10–11, 2013 at the Department of Computer, Control, and Management Engineering Antonio Ruberti at Sapienza University of Rome, Italy. See the program overview for the schedule.
We invite you to join us in Rome to take advantage of this rich program of tutorials!
The following tutorials will be presented at ICAPS 2013:
- Planning for Symbiotic-Autonomous Robots (Manuela Veloso)
- Planning in Hybrid Domains (Maria Fox and Daniele Magazzeni)
- Approximation Algorithms for Planning Under Uncertainty (Andrey Kolobov)
- Model Checking of Hybrid Systems via Satisfiability Modulo Theories (Alessandro Cimatti)
- MAXSAT for Planning Researchers (Fahiem Bacchus)
- Programming by Optimisation: A new Paradigm for Developing High-Performance Solvers for Computationally Challenging Problems (Holger H. Hoos)
- Engineering a Heuristic Search Planner (Gabriele Röger and Malte Helmert)
- Temporal planning and temporal networks (Andrew Coles and Luke Hunsberger)
Tutorial Program Chairs
* Gerard Verfaillie (ONERA, France), Gerard.Verfaillie@onera.fr
* Laura Barbulescu (Carnegie Mellon University, USA), laurabar@cs.cmu.edu
Call for Tutorial Proposals (Deadline expired) The call is available here.
Planning for Symbiotic-Autonomous Robots
By Manuela Veloso (Carnegie Mellon University, USA)
The creation of intelligent autonomous robots has been the research focus on many AI researchers. An autonomous robot perceives its environment, selects actions to achieve its goals based on the perceived state of the environment, and then executes the selected actions. This overall cycle is clearly of great relevance to the planning research community.
Symbiotic-autonomous robots are intelligent robots that are capable of complementing their perceptual, reasoning, and actuation capabilities by resourcing to external sources, such as humans, the web, and other artifacts. The robots further learn from their symbiotic interactions with the goal of improving their future tasks.
In this tutorial, I will introduce the core planning challenges for such symbiotic-autonomous robots, and present effective solutions for the underlying task-based planning, execution, and learning. The tutorial will be based on the concrete experience with our CoBot service mobile robots, which move in our multi-floor building performing a variety of pick and delivery tasks. The CoBot robots plan for their navigation and their interaction with humans and with the web. They have moved in our buildings for more than 200km.
Length: Half day
Date: June 11, 2013
Planning in Hybrid Domains
By Maria Fox and Daniele Magazzeni (King’s College London, UK )
Background and State of the Art. Hybrid systems are systems with both continuous control variables and discrete logical modes. Many interesting real problems are indeed hybrid, including logistics planning, mission planning for autonomous vehicles, oil refinery management, supply management and disaster recovery. In these domains there are temporal, spatial and continuous constraints, and planning techniques capable of reasoning with suitably rich models are required. This motivates both increases in the modelling power to capture these constraints and extensions to classical approaches to planning to enable efficient management of such complex problems. This tutorial provides an introduction to modelling and solving planning problems in hybrid domains.
Recent Advances and New Challenges. This tutorial presents new benchmark problems motivating the need for modelling more realistic domains, and presents recent advances in the interaction between planning and robot control systems, aiming to generate sensible plans for real world situations. The tutorial ends with a discussion on current challenges and open problems in planning with hybrid domains.
Length: Half day
Date: June 10, 2013
Approximation Algorithms for Planning Under Uncertainty
By Andrey Kolobov (University of Washington, USA)
Standard optimal algorithms for solving probabilistic planning scenarios modeled by Markov Decision Processes (MDPs) suffer from the curse of dimensionality. These techniques, e.g, value iteration, attempt to compute a policy separately for each state, the number of which is exponential in size of the problem specification. This tutorial surveys a class of much more scalable approaches that sacrifice MDP solution optimality in exchange for the ability to solve much bigger problems. The lecture will cover a wide range of approximation algorithms, from determinization-based techniques such as Robust FF to the hierarchical planning paradigm, paying special attention to the growing family of planners based on Monte Carlo Tree Search.
Slides: (pdf)
Length: Quarter day
Date: June 10, 2013
Model Checking of Hybrid Systems via Satisfiability Modulo Theories
By Alessandro Cimatti (Fondazione Bruno Kessler, Italy)
Complex embedded systems are increasingly present in our daily lives, whenever a computer-based system interacts with some physical plant or environment. Some application domains of interest are industrial production, automotive, railways,
and aerospace. The key feature of such complex system, often known as hybrid systems, is the combination of discrete dynamics (e.g. from the control logic) and the continuous dynamics (e.g. from the physical system). Discrete dynamics represent, for example, control states and operation modes, while continuous dynamics take into account the physical aspects such as duration of activities, speed and position of moving objects, and profiles for resource consumption.
The ability to reason about such systems is important in two complementary dimensions. In the design phases, there is a need to predict the behaviour of the control algorithms before they are put into operation. In the operation phases, the ability to reason about such dynamic systems is a backbone for plan generation, plan validation, plan execution and monitoring, fault detection/isolation/recovery (FDIR), and replanning.
The objective of the tutorial is to present a formal and comprehensive account for modeling hybrid systems, and a set of powerful techniques to reason about them.
The tutorial will be grounded in the well-studied formalism of hybrid automata, that encompasses instantaneous (mode) transitions and continuous (timed) transitions. We will introduce a symbolic representation in form of Satisfiability Modulo Theories formulae, which can be thought of as (fragments of) first-order logic where mathematical symbols are interpreted according to suitable theories (e.g. linear arithmetic). The (combinational) backends are SMT solvers, that can be seen as a tight integration of SAT (to deal with the boolean reasoning) with dedicated constraints solvers (to deal with theory reasoning).
The algorithms for reasoning about hybrid systems are able to carry out various forms of reachability analysis, and can be classified in two types. The basic ones, that lift to the case of SMT the SAT-base algorithms developed for the case of finite state model checking (including for example bounded model checking, induction, and interpolation based analysis). More advanced ones take into account the distinguishing features of networks of hybrid automata.
More details can be found here.
Slides: (pdf)
Length: Quarter day
Date: June 10, 2013
MAXSAT for Planning Researchers
By Fahiem Bacchus (University of Toronto, Canada)
MAXSAT is an optimization version of SAT that has many applications in Planning, particularly in cost optimal planning. Besides encoding optimal planning problems directly into MAXSAT, MAXSAT can be used in other less direct ways. For example, computing heuristics like h+ is an optimization problem that can be cast as a MAXSAT problem. In this tutorial we will examine some of the main techniques and algorithms for solving MAXSAT, and how these algorithms can be applied to problems that arise in planning. In addition to the algorithmic ideas the tutorial will also discuss some of the publicly available software that can be exploited in implementing these ideas.
Slides: (pdf)
Length: Quarter day
Date: June 10, 2013
Programming by Optimisation: A new Paradigm for Developing High-Performance Solvers for Computationally Challenging Problems
By Holger H. Hoos (University of British Columbia, Canada)
When creating software, particularly solvers for computationally challenging problems, developers fre- quently explore multiple ways of achieving certain tasks. Often, these alternatives are eliminated or abandoned early in the development process, based on the belief that the flexibility afforded by them would be difficult or impossible to exploit later. Programming by Optimisation (PbO) is a design paradigm that aims to avoid such premature design choices and to actively develop promising alternatives for parts of the design. Rather than build a single program for a given purpose, software developers specify a rich and potentially large design space of programs. From this specification, programs that perform well in a given use context are generated automatically through powerful optimisation techniques. PbO allows human experts to focus on the creative task of imagining possible mechanisms for solving given problems or subproblems, while the tedious job of determining what works best in a given use context is performed automatically, substituting human labor with computation. Furthermore, using PbO, per-instance algorithm selectors and parallel algorithm portfolios can be obtained from the same sequential source.
In this tutorial, I will share the vision of how PbO can fundamentally change the way challenging computational problems are solved in the future. I will present examples from work done in my own group and elsewhere that clearly illustrate the viability and promise of the approach. These examples will cover substantial advances in the state of the art (often by orders of magnitude) in SAT-based software verification, planning and timetabling, as well as mixed integer programming – perhaps the most widely used approach for solving optimisation problems in industry. I will briefly demonstrate the tools currently available to support PbO-based software development and outline additional support currently under development.
Slides: (pdf)
Length: Quarter day
Date: June 11, 2013
Engineering a Heuristic Search Planner
By Gabriele Röger and Malte Helmert (University of Basel, Switzerland)
A heuristic planning system mainly consists of a search algorithm and a heuristic function, maybe plus some enhancements such as preferred operators or pruning techniques. These ingredients of a system are usually well known and they are subject to scientific study. However, for a state-of-the-art performance of a system there are many other crucial aspects that are important from an engineering perspective. These include intelligent preprocessing techniques, the choice of suitable data structures and memory-saving strategies, as well as a clean and modular software architecture. This tutorial will address these engineering decisions and demonstrate possible solutions, using the Fast Downward planning system as an example.
Slides: (pdf)
Length: Quarter day
Date: June 11, 2013
Temporal planning and temporal networks
This is a two part tutorial, looking at two areas:
Temporal Planning: Ten Years of PDDL 2.1
(by Andrew Coles, King’s College London, UK)
2003 marked the publication of PDDL 2.1, the first published version of the language with an explicit model of time. In the decade since then, there has been a wealth of work in temporal planning, from understanding what makes temporal planning difficult, to managing the interaction between logical and temporal constraints.
In this tutorial, I’ll give an introduction to the area, looking at temporal PDDL, and what changes in planners are needed to support this. Specifically:
- The representation of time in PDDL 2.1: actions with start and end conditions and effects;
- Extending state-space search to build temporal plans;
- Using Simple Temporal Networks to manage the constraints in temporal plans;
- Heuristic guidance for temporal planning.
The Dynamic Controllability of Simple Temporal Networks with Uncertainty
(by Luke Hunsberger, Vassar College, USA)
Introduced in the late 1990s, Simple Temporal Networks with Uncertainty (STNUs) enable the representation and efficient management of temporal constraints among activities whose durations are uncertain, but guaranteed to lie within known bounds. The most important property of an STNU is whether it is dynamically controllable—that is, whether there exists a strategy for executing its time-points such that all constraints are guaranteed to be satisfied no matter how the durations of the contingent links turn out. Crucially, the execution strategy is only allowed to depend on past observations, not on advance knowledge of future events.
In this tutorial, I’ll give an introduction to STNUs and Dynamic Controllability, looking at both theoretical issues and a number of algorithmic approaches. Specifically:
- Definition of a Simple Temporal Network with Uncertainty;
- The Dynamic Controllability of STNUs;
- Algorithms for checking Dynamic Controllability, and for executing Dynamically Controllable STNUs;
- Recent advances in the graphical analysis of STNUs.
Slides: (pdf)
Length: Quarter day
Date: June 10, 2013
