Abstract

This tutorial introduces planning researchers to the basic and advanced features of the Planning.Domains APIs. It is a hands-on session and the attendees are encouraged to bring a laptop computer.

We will cover topics such as the existing (and new) API for the solver and api components, and the API features currently under development for the online editor. Emphasis will be on the latter, because it will enable planning researchers to provide new PDDL analysis and construction tools for the broader community using the editor’s upcoming plugin architecture.

No previous experience is required, aside from some basic programming skills to interface with the various APIs. While it is not expected that participants will implement software that uses the APIs fully, the tutorial serves as a foundation for them to begin experimenting. Researchers involved and familiar with the various APIs will also be available throughout the conference to address any questions.

Bios

Christian Muise is a postdoctoral associate with the MERS group at MIT CSAIL. He received his Ph.D. in 2014 from the University of Toronto, and was a research fellow from 2014 to 2015 at the University of Melbourne working on multi-agent planning. Other research interests include non-deterministic planning, deadend detection, execution monitoring, and knowledge compilation.

Abstract

With state-dependent action costs, it is possible to represent certain planning tasks exponentially more compactly than without. We discuss how action cost functions can be compactly encoded using edge-valued multi-valued decision diagrams (EVMDDs), how this encoding exhibits additive structure, and how this structure can be exploited, e.g., when computing relaxation or abstraction heuristics. In the theoretical part, we first give an introduction to planning with state-dependent action costs and to EVMDDs, and then show how state-dependent action costs can be compiled away using EVMDDs. Finally, we discuss how EVMDDs can be used to deal with state-dependent action costs directly during the computation of relaxation and abstraction heuristics without compilation. In the practical part, we will look into concrete implementations of EVMDDs and their properties, and we will see a tool that performs the compilation for PDDL inputs.

Bios

Robert Mattmüller is a postdoctoral researcher at the Foundations of AI group at the University of Freiburg, Germany. His research interests include algorithms and heuristics for classical and nondeterministic planning, and the intersection between planning and model checking. In 2013, he received the ICAPS Best Paper Award.

Florian Geißer is a PhD student at the Foundations of AI group at the University of Freiburg, Germany. He joined the group in February 2014 and has worked in the area of classical and probabilistic planning since then. His most recent work focuses on planning with state-dependent action costs.

Abstract

Many real-world planning tasks require making decisions that involve multiple possibly conflicting objectives. To succeed in such tasks, intelligent agents need planning algorithms that can efficiently find different ways of balancing the trade-offs that such objectives present. In this tutorial, we provide an introduction to decision-theoretic planning in the presence of multiple objectives.

In part 1, we present an overview of multi-objective decision-theoretic formalisms, with real-world examples. Then, we show that different assumptions about these problems lead to different solution concepts such as the convex hull and the Pareto front.

In part 2, we provide a examples of state-of-the-art planning algorithms. We start with multi-objective variants of dynamic programming for multi-objective Markov decision processes (MOMDPs). Then, we discuss recent work on MOPOMDPs, and discuss point-based planning for MOPOMDPs. We conclude with a brief overview of applications.

Bios

Shimon Whiteson is an Associate Professor in the Department of Computer Science at the University of Oxford. His research focuses on decision-theoretic planning and learning for single and multi-agent systems. He was awarded an ERC Starting Grant from the European Research Council in 2014.

Diederik M. Roijers did his PhD on multi-objective decision-theoretic planning at the University of Amsterdam. Currently, he is working on a multi-objective approach to social robotics in the TERESA project (http://teresaproject.eu/), as a post-doctoral researcher in the Department of Computer Science at the University of Oxford.

Abstract

Decision diagrams have been used for decades as a compact representation of Boolean functions. More recently, they have emerged as a powerful tool for discrete optimization. They provide a discrete relaxation of the problem that does not require linearity or convexity. The relaxation yields useful bounds and a novel search strategy, leading to a general-purpose solver that is competitive with or superior to state-of-the-art integer and constraint programming on several classical benchmark problems. The solver accepts models in the form of a dynamic programming recursion and therefore affords an alternative approach to defeating the ìcurse of dimensionalityî in dynamic programming.

The specific application to sequencing and scheduling problems will be discussed in the following tutorial by Willem-Jan van Hoeve. Both tutorials are stand-alone presentations.

Bios

John Hooker is Professor of Operations Research and Holleran Professor of Business Ethics at Carnegie Mellon University. His research interests include integration of optimization and constraint programming, logic-based methods for optimization and data analytics, optimization with decision diagrams, and modeling systems, as well as ethics, cross-cultural management, and musical composition. He introduced logic-based Benders decomposition, and with T. Hadûi?, decision diagrams as an optimization method. His research website is web.tepper.cmu.edu/jnh.

Abstract

The problem of sequencing a set of activities over time is fundamental in planning and scheduling. We discuss how decision diagrams (DDs) can be used to compactly represent a wide range of sequencing problems with various side constraints and objective functions, and we demonstrate how these can be added to existing constraint-based scheduling systems. We show that the additional inference obtained by our DDs can speed up a state-of-the art solver by several orders of magnitude, over a diverse set of problem classes.

A more general description of the application of DDs to discrete optimization is given in the preceding tutorial by John Hooker. Both tutorials are stand-alone presentations.

Bios

Willem-Jan van Hoeve is Associate Professor of Operations Research at Carnegie Mellon University. His research focuses on developing new methodologies for solving discrete optimization problems, and the application of those methods in practice. He has made contributions to the area of constraint programming, hybrid optimization methods, and most recently to the development of a powerful framework for discrete optimization based on decision diagrams. More information can be found at http://www.andrew.cmu.edu/user/vanhoeve/

Abstract

Robots gain more capabilities every year, yet the use of planning methods to determine the overall behavior is still the exception rather than the norm. A robotics planning competition (in 2017) could foster mutual and closer cooperation between the planning and robotics communities. A first domain could be based on the RoboCup Logistics League in simulation.

This is a half-day tutorial to introduce the scenario, explain how to use the simulation, and characterize the planning domain for potential participants.

Bios

Tim Niemueller received the M.Sc. (diploma) degree in computer science from the Knowledge-based Systems Group of the RWTH Aachen University, Germany, in 2010, and is currently working towards the Ph.D. degree at the same university. He has worked at the Personal Robotics Lab of the Carnegie Mellon University with Siddhartha Srinivasa and as a freelancer for SRI International supervised by Robert C. Bolles. He is member of the RoboCup Executive Committee and team leader of the Carologistics and AllemaniACs RoboCup teams. His research interests are cognitive robotics in the areas of task planning, reasoning, and execution monitoring, world modeling and memory persistence, and robust system integration for personal and industrial autonomous mobile robots.

Erez Karpas is a senior lecturer (assistant professor) at the Faculty of Industrial Engineering and Management, Technion - Israel Institute of Technology. His main research interests are artificial intelligence and robotics. Erez was a postdoctoral associate at the Model-based Embedded and Robotics Systems Group at MIT. He completed his Ph.D at the Faculty of Industrial Engineering and Management at the Technion - Israel Institute of Technology, and received his M.Sc. in Computer Science and his B.Sc. in Math and Computer Science, both from Ben Gurion University.

Tiago Vaquero is a postdoctoral fellow at MIT CSAIL and Caltech. He is a former postdoctoral fellow at the University of Toronto working on automated planning and scheduling, and assistive robots. In 2011 he received his Ph.D. from the University of Sao Paulo. In 2007 he received his M.Sc. and in 2003 he received his B.Sc. both in mechatronics engineering from University of Sao Paulo. His research interests include autonomous systems, automated planning and scheduling, knowledge engineering, probabilistic planning, robotic space exploration, artificial intelligence and robotics in general.

Eric Timmons has graduated from MIT with Bachelors degrees in Aerospace Engineering and Physics (2010) and a Masters in Aerospace Engineering (2013). He is currently completing his Ph.D. degree in the EECS Department as part of the MIT/Woods Hole Oceanographic Institution (WHOI) Joint Program. Eric is researching the application of automated planning to autonomous underwater vehicles. Outside of research, Eric’s interests include robotics, UAVs, and teaching.