ACAI Summer School on Automated Planning and Scheduling

Scheduling has been the "little brother" of planning since scheduling started being studied within AI in roughly the early 1980s. Modern scheduling, even within AI, increasingly reflects the integration of theory and high-performance algorithmic techniques from Operations Research where scheduling has studied since at least the 1950s. This tutorial is designed to provide an introduction to the core algorithmic technologies in scheduling research, a glimpse of the state-of-the-art, and some wild speculations about the place of scheduling within AI research.

The tutorial is organized into three sections:

1) Core scheduling technologies - After defining that scheduling actually is, we will look at the three primary technologies used to solve scheduling problems today: constraint programming (CP), mixed-integer programming (MIP), and metaheuristics.

2) Hybrid scheduling approaches - The three core technologies are increasingly being combined and many of the state-of-the-art algorithms are loosely or tightly coupled hybrids of these core techniques. We will look at two styles of hybrid in the context of scheduling: CP with metaheuristics and CP with MIP.

3) Polemics and perspectives - With the technical foundation of the first two parts, we will revisit the title to try and understand where (if anywhere) scheduling sits within AI, the relationship between scheduling and AI planning, and some ideas for the future directions of AI scheduling research.

Slides: (pdf)

Length: 3 hours

In two talks about non-deterministic planning, I plan to cover the most relevant aspects (for planning) of the underlying mathematical models used for casting probabilistic planning problems, the standard and novel algorithms to solve these models, and the current limitations and challenges that lay ahead for developing successful planners capable of tackling large and complex problems.

As we will see, the underlying mathematical models are complex and well understood, there are many algorithms for computing solutions, but very few heuristics. Thus, the field offers many opportunities to young and enthusiastic people looking to do groundbreaking research not only in planning but also in areas such as stochastic control theory and operations research.

Slides: (pdf)

Length: 3 hours

Two men are sitting in the basket of a balloon. For hours, they have been drifting through a thick layer of clouds, and they have lost orientation completely. Suddenly, the clouds part, and the two men see the top of a mountain with a man standing on it. "Hey! Can you tell us where we are?!" The man doesn't reply. The minutes pass as the balloon drifts past the mountain. When the balloon is about to be swallowed again by the clouds, the man on the mountain shouts: "You're in a balloon!"
"That must have been a mathematician."
"Why?"
"He thought long and thoroughly about what to say. What he eventually said was irrefutably correct. And it was of no use whatsoever..."

Having heard this famous joke, you are starting your Ph.D. in the area of AI planning and scheduling, and you surely wonder what type of research you'll better be doing. On the one hand, "There is nothing better for practice but a good theory!" (Bolzano). On the other hand, "So far, nobody has won IPC by proving theorems on the complexity of fragment A of problem class B in formalism C!" (Anonymous). So confusing ...

The sole purpose of this talk is to reduce your confusion, if not to eliminate it altogether. The talk will have two interleaving motives.

I'll try to overview the evolution of the complexity analysis research within the ICAPS community for the last two decades, with a particular focus on results related to deterministic planning. Importantly, this overview will aim at providing you not with a handbook, but with a "cooking book", helping you (and myself) to make sense of:

• What are the different questions of interest in this research area?
• When a seemingly boring question becomes interesting and the other way around?
• What are the advantages and disadvantages of doing purely theoretical work?

etc.

While Anonymous claims above that theory is possibly good in Latex, but surely useless in C++, I'll try to convince you that ICAPS experience over the last two decades (and beyond that) suggests exactly the opposite.

You may ask now: So what will be your suggestion at the end with respect to the "theorem proving vs. code bulletproofing" dilemma?
Well, with answer to this one you'll have to wait until June.

Disclaimer: The idea of starting this abstract with a joke was unashamedly stolen from the abstract of Jörg Hoffmann.

Slides: (pdf)

Length: 3 hours

It was only in 2005 that F.E.A.R. was the first popular modern computer game to use a planner to drive its non player characters, and it used a STRIPS planner without variables and backtracking. In this session, I will discuss the challenges the game industry faces in adopting modern Artificial Intelligence techniques such as planning from a design, technical and funding point of view. I will cover F.E.A.R.'s use of a planner and detail some of the techniques that have been introduced since to adopt other planners into shipped games, such as HTN planners in Killzone 2 and other games. Many challenges remain in bridging the gap between industry and academia in this field, but there are also many unexplored opportunities. I will conclude by summarizing these and providing a research overview of game-related work in reinforcement learning, decision making under uncertainty and plan recognition that has not made it into shipping games yet.

Length: 1.5 hours

An astronomer, a physicist and a mathematician are on a train in Scotland. The astronomer looks out of the window, sees a black sheep standing in a field, and remarks, "How odd. Scottish sheep are black." "No, no, no!" says the physicist. "Only some Scottish sheep are black." The mathematician rolls his eyes at his companions' muddled thinking and says, "In Scotland, there is at least one sheep, at least one side of which is black."

Now replace the sheep with data on benchmarks, the astronomer with an enthusiastic author, the physicist with a well-meaning reviewer, and the mathematician with a not quite as well-meaning one. Then you get what is frequently called "evaluation" in planning. The talk points out many of the pitfalls of this jolly tradition. In lack of a universally valid answer how to do it better, we give a number of good (and bad!) examples.

A tad more concretely: the talk does NOT attempt to give a comprehensive introduction to statistics and empirical methodology; we point to existing tutorials and books for that purpose. Instead, I review what evaluation in planning is, and what it should be (according to my humble opinion). I give examples of typical mistakes, and solutions to some typical situations, and I discuss at some length the interpretation of data.

Disclaimer: the talk is mostly aimed at evaluation of classical planners, and may be less applicable outside of that scope, and less understandable to people not familiar with classical planning and the IPC.

Slides: (pdf)

Length: 1.5 hours

In its early days, the planning community routinely and gleefully let its reach exceed its grasp in terms of the class and scope of problems under consideration. Even when our planners were really classical but quite glacial, and could at best handle three blocks problems under mere minutes on a good day, we still blithely directed myriad efforts at lifted planning, temporal planning, stochastic planning, open world planning, mixed-initiative planning, and multi-agent planning.

The principled scale-up in classical planning in the last decade should have opened a more expansive vent for all that pent-up ambition. Alas, it hasn't quite turned out that way; our successes in scale-up seem to have turned us more circumspect. A Martian looking at any of the recent ICAPS proceedings can be forgiven for thinking that we are all mostly in quest of ever-more speed-up for classical planning.

In these lectures, I will make a case for turning our (and especially your) energies back to the future of planning, and explain how we can co-opt the scale-up in classical planning to aid in this quest. We shall look, in particular, towards advances in partial satisfaction planning, temporal planning, stochastic planning, as well as planning with incomplete models and open worlds.

Slides: (pdf)

Length: 3 hours

Heuristic search using heuristics extracted from the problem description has been one of the most successful approaches in domain-independent planning. Here we review the main approaches in deriving informative heuristics, including those obtained from the delete relaxation, critical paths, landmarks, and abstractions. We focus on heuristics as solutions to well-defined problem relaxations and the conceptual links between different types of heuristics.

Slides: (pdf)

Length: 3 hours

Interactive Storytelling systems form part of the next generation of interactive media and as such represent a major new application area for AI planning. Here, planning is used for the generation of narratives that are presented interactively in 3D entertainment systems using animations (and video). Since planning was first proposed in 2000 it has been enthusiastically adopted in this area and now represents the core technology for Interactive Storytelling systems. The roots of this lie in the application of planning for the control of virtual agents and its popularity stems from the apparent natural fit between narratives and plans which enables narratives to be naturally modelled as sequences of actions allowing the embedding of key features such as causality among story events which has been shown to be an important factor in user experience.

In the talk I will motivate this application area with examples to give a feel for the current state of the art in planning for Interactive Storytelling. Then I'll consider a number of questions about the role of planning in IS such as (1) whether we should be using planning at all? (2) where do the real challenges lie in IS -- with representation or with reasoning? (3) will the development of better planners result in better narratives? (4) what is a ``good'' solution when planner ouput is a narrative rather than a plan?

Slides: (pdf)

Length: 1.5 hours

For decades, space systems have explored most planets within our solar system. More recently, autonomous underwater vehicles have penetrated the deepest points of our oceans, such as the Marina Trench. Recently autonomous air vehicles, ground vehicles and humanoid robots have accomplished similar feats. While these systems are autonomous, they lack even a rudimentary capability to reason. Instead they are programmed through simple linear sequences, which are often brittle to unforeseen circumstances. In this tutorial we present a series of increasingly capable plan executives that reason from models on the fly, in order to both elevate the level of commanding and to achieve robustness to disturbances and failure.

This tutorial presents three complementary paradigms for model-based execution. First, we present executives that perform coordinated tasks under time pressure. They adapt to temporal disturbances by scheduling on the fly, while using models of uncertainty to ensure future success. These executives have been applied to a range of systems, from autonomous space probes to teams of robots.

Second, we present executives that control dynamical systems robustly. These systems are commanded simply through plans whose activities are specified through goal states, while actions are generated by solving online optimization problems within a model-predictive control framework. These executives have been applied to a range of systems, from autonomous deep sea vehicles to personal air vehicles.

Finally, we present executives that control complex engineered systems. These systems execute plans in the face of failure by constantly monitoring and diagnosing, repairing and reconfiguring the engineered system as the plan is being executed. These executives have been applied to a range of systems, from NASA’s deep space one probe to automobiles.

Slides: (pdf)

Length: 3 hours