Tutorials

Length: quarter-day (part of the COPLAS workshop)

Abstract: Planning problems can be solved by translating them to other formalisms such as constraint satisfaction. This tutorial explains mainstream constraint satisfaction techniques used in current constraint solvers, namely arc consistency, global constraints, and their integration to search algorithms. In the second part, the tutorial will survey existing constraint models for classical planning problems with the focus on modeling causal relations between the actions. Models for both sequential and parallel planning will be explained and compared.

Bio: Roman Barták is a professor at Charles University, Prague (Czech Republic). His work focuses on techniques of constraint satisfaction and their application to planning and scheduling. His research results are used in products of ILOG/IBM, Visopt, and ManOPT/Entellexi. He is author of the On-line Guide to Constraint Programming.

Length: half day

Abstract: The last ten years have seen impressive progress in the techniques used for solving combinatorial optimization in graphical models. Because these techniques apply to a variety of graphical models (probabilistic or not), these techniques have a wide scope of applicability in AI. The area is also mature enough to make it possible to give a clear, structured description on the most important contributions, in terms of inference, bounded inference, search and problem decomposition. Solvers implementing these techniques are available and have been applied on real problems. For the planning community, the notion of Planning as Inference became more mainstream in recent years and the ideas and principles presented should help develop planning scheme using the methodology of probabilistic inference.

This tutorial will present state-of-the-art algorithms for solving combinatorial optimization tasks in different graphical models (Bayesian networks, Markov networks, Constraint networks) and demonstrate their applicability to Planning under uncertainty, in particular for influence diagrams, POMDPS and to conformant planning.

Bio: Rina Dechter is a professor of Computer Science at the University of California, Irvine. She received her PhD in Computer Science at UCLA in 1985, an MS degree in Applied Mathematic from the Weizmann Institute and a BS in Mathematics and Statistics from the Hebrew University, Jerusalem. Her research centers on computational aspects of automated reasoning and knowledge representation including search, constraint processing and probabilistic reasoning.

Length: quarter-day (part of the IPC workshop)

Abstract: Hybrid systems are systems with both continuous control variables and discrete logical modes. Many interesting real problems are indeed hybrid systems, including oil refinery management, mission planning for autonomous vehicles, supply management and disaster recovery. Planning in these domains requires rich models to capture the interaction between discrete and continuous change, and methods for reasoning with temporal, spatial and continuous constraints. PDDL+ is the extension of PDDL for modelling hybrid systems, through continuous processes and events. The tutorial provides an overview of PDDL+, by showing some concrete examples on how to model hybrid domains using PDDL+. Then an overview of existing techniques for PDDL+ planning in these domains is provided. Finally, some recent challenging case studies are presented and open problems are discussed.

Bio: Dan Magazzeni is a Lecturer in Artificial Intelligence at King's College London. Dan received a PhD in Computer Science in 2009 at University of L'Aquila. His research explores the links between planning, controller synthesis and model-checking verification, with a particular focus on planning in mixed discrete-continuous domains, and hybrid systems control and verification. He gave tutorials on Planning in Hybrid Domains at ICAPS-13 and AAAI-14. He was chair of the workshop on Planning in Continuous Domains at ICAPS-13 and chair of the workshop on Model Checking and Planning (MOCHAP) at ICAPS-14. He is the coordinator of the 2014 Dagstuhl Seminar on Automated Planning and Model Checking.

Length: quarter-day

Abstract: RDDL is the Relational Dynamic Influence Diagram Language, the domain modeling language used in the ICAPS 2011 and 2014 International Probabilistic Planning Competitions. 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 and its extension in 2014 to RDDL2, 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.

Bio: Scott Sanner recently joined the faculty of Oregon State University after having spent nearly eight years at NICTA and the Australian National University. His research spans a broad range of topics from machine learning to optimization to planning.

Length: quarter-day

Abstract: Abstraction heuristics such as pattern databases (PDBs) and merge-and-shrink have been successfully used to solve classical planning tasks optimally for many years. More recently, new abstraction heuristics and heuristic combination methods have been developed that go beyond this previous state of the art. In this tutorial, we aim to cover both the established and the latest state-of-the-art methods of computing abstraction heuristics. The tutorial will be self-contained for everyone familiar with classical planning and heuristic search. However, our main focus will be on the most recent state-of-the-art techniques, which might be interesting especially for people with a research background in this area.

Bios: Malte Helmert is an assistant professor for artificial intelligence at the University of Basel, Switzerland. He has been a long-standing member of the automated planning research community, participating in every ECP/AIPS/ICAPS conference since 1999. He has received more than 20 scientific awards including the IJCAI 2011 Computers and Thoughts Award and, most recently, the ICAPS 2013 Best Paper Award, ICAPS 2013 Best Student Paper Award, ICAPS 2014 Best Paper Award, a AAAI 2014 Outstanding Paper Award Honorable Mention and the AAAI 2015 Outstanding Paper Award. He was conference cochair for ICAPS 2011 and SoCS 2013 and coorganizer of the ACAI 2011 Summer School on Automated Planning and Scheduling. He is a member of the ICAPS Executive Council and an associate editor of JAIR. His complete list of publications can be found at http://ai.cs.unibas.ch/people/helmert/publications.html.

Jendrik Seipp is a PhD student in the Artificial Intelligence group at the University of Basel, Switzerland. He is working on the project Abstraction Heuristics for Planning and Combinatorial Search (AHPACS) funded by the Swiss National Science Foundation (SNSF). Since he joined the group in March 2013 he has published multiple papers on classical planning, including a paper that won the AAAI 2015 Outstanding Paper Award. The work most closely related to this tutorial are the papers from ICAPS 2013 and ICAPS 2014 (see below). His complete list of papers is available at http://ai.cs.unibas.ch/people/seipp/.

Silvan Sievers is a PhD student in the Artificial Intelligence group at the University of Basel, Switzerland. He joined the group in November 2012 and has worked in the area of classical planning since then. His most recent work related to abstraction heuristics focuses on merge-and-shrink heuristics. Both relevant papers are published at AAAI (2014 and 2015) and listed below. The 2014 paper received an honorable mention for the AAAI Outstanding Paper Award. A full list of Silvan's publications can be found at http://ai.cs.unibas.ch/people/sievers/

Length: quarter-day

Abstract: Linear programs (LPs) provide a powerful optimization framework and can be efficiently solved in polynomial time. Therefore, they appear to be well-suited to form the basis for highly informed heuristics for classical planning. Since solving a typical planning instance optimally requires to evaluate a heuristic for millions of individual states, it nevertheless was for a long time expected to be too time-intensive to solve a LP for every single state. However, several recent heuristics show that this can not only be practically feasible but also be very beneficial. This tutorial will cover most of these recent LP-based heuristics: optimal cost partitioning for abstractions, post-hoc optimization of heuristic estimates, optimal estimates from disjunctive action landmarks, the state-equation heuristic, potential heuristics, and an LP-based heuristic for relaxed planning. We also will introduce a unifying framework that allows to beneficially combine these heuristics. Participants need no background on linear programming but basic knowledge about heuristic search is desirable.

Bios:Florian Pommerening is a PhD student at the Artificial Intelligence group at the University of Basel, Switzerland. He has published papers on the tutorial topic at IJCAI 2013 and ICAPS 2014 and has received the ICAPS 2014 Best Paper Award for this work.

Gabriele Roger is a postdoctoral research assistant at the Artificial Intelligence group at the University of Basel, Switzerland. Since 2006, she regularly has published on planning-related topics at ICAPS, AAAI, IJCAI, and ECAI. She has received the AAAI 2008 Outstanding Paper Award and the ICAPS 2014 Best Paper Award and was conference cochair of SoCS 2013 and coorganizer of the ACAI 2011 Summer School on Automated Planning and Scheduling.

Malte Helmert is an assistant professor for artificial intelligence at the University of Basel, Switzerland. He has been a long-standing member of the automated planning research community, participating in every ECP/AIPS/ICAPS conference since 1999. He has received more than 20 scientific awards including the IJCAI 2011 Computers and Thoughts Award and, most recently, the ICAPS 2013 Best Paper Award, ICAPS 2013 Best Student Paper Award, ICAPS 2014 Best Paper Award, and a AAAI 2014 Outstanding Paper Award Honorable Mention. He was conference cochair for ICAPS 2011 and SoCS 2013 and coorganizer of the ACAI 2011 Summer School on Automated Planning and Scheduling. He is a member of the ICAPS Executive Council and an associate editor of JAIR.

Length: half-day

Abstract: Plan executives must often map simple discrete activities specified in the plan to continuous control trajectories or motions. These executives must ensure correctness despite uncertainty in the environment, for example, due to temporal delays, actuator disturbances and sensor noise. To adapt, plan executives should dynamically adjust the timing of activities and control trajectories that implement these activities, and activity plan descriptions should offer flexibility in temporal and state constraints, needed to perform these adaptations. When uncertainty is specified probabilistically, successful plan execution cannot be guaranteed as there is always some risk of failure. In this case, activity plans should include specifications of what level of risk of failure is acceptable, and plan executives should ensure that they operate within this risk bound. We will present two tutorials: one deals with scheduling activities with probabilistic durations, and the other deals with path planning with stochastic dynamics. Both tutorials will present the risk allocation methodology, and techniques for performing reisk allocation - each in the context of its respective problem. Each tutorial is independent: you are welcome to attend either of these tutorials, or both.