AAAI 2015 Tutorial
A Beginner's Introduction to Heuristic Search Planning

Malte Helmert, Gabriele Röger
AAAI 2015, Austin, Texas
Sunday, January 25, 2015, 9:00-13:00
Room Zilker 2, First Level

Description

Classical planning is a traditional area of AI interested in general problem solving: developing a single algorithm to find the best actions for an agent to execute in all possible environments that fit within the scope of the planning algorithm's modeling language. The tutorial is aimed at starting AI researchers with little or no previous familiarity with the research area of automated planning.

We introduce the problem of classical planning, explain its place within the wider AI research area, and discuss the foundational techniques underlying most state-of-the-art planning algorithms. The emphasis is on planning as heuristic search, where the challenge is to derive accurate search heuristics for a problem domain without human intervention, given only a declarative problem description. We explain the major ideas underlying today's search heuristics and present some concrete examples in depth.

The tutorial includes hands-on demonstrations and shows how to implement new search heuristics in the state-of-the-art Fast Downward planning system.

Outline

1.	What is Planning? (PDF)
2.	Planning Formalisms (and Heuristic Search) (PDF)
3.	A Simple Heuristic (PDF)
4.	Five Families of Heuristics (PDF)
5.	Abstraction Heuristics and Pattern Databases (PDF)
6.	Delete Relaxation and Landmarks (PDF)
7.	Going Further (PDF)

Hands-on Material

Attendees who want to participate in the hands-on demonstrations need to set up their laptop in advance of the tutorial.

Option 1: Install the required software on your Linux laptop

You need a C++11 compiler (we use GCC 4.8) and the usual build tools such as GNU make. For the plan validator, VAL, you will need flex and bison. To run the planner, you also need Python 2.7 or Python >= 3.2.

On a recent Ubuntu version, you can install the required infrastructure with
$ sudo apt-get install g++ make python flex bison

If you are using an x64 system, you will probably also need to run
$ sudo apt-get install g++-multilib

Download the archive hands-on.tar.bz2 (9.1M) and unpack it.

Compile the planner for the hands-on demonstrations:
$ cd hands-on
$ ./build.sh (does not change anything outside the hands-on directory)

To test your installation so far, you can run
$ cd hands-on
$ ./fd tile/puzzle.pddl tile/puzzle01.pddl --search "eager_greedy(ff())"

For the part on the implementation of a heuristic you need to compile the relevant code as follows:
$ cd hands-on/heuristic-implementation
$ ./build_all (does not change anything outside the heuristic-implementation directory)

To test this part of your installation, you can run
$ cd hands-on/heuristic-implementation
$ ./fast-downward.py ../tile/puzzle.pddl ../tile/puzzle01.pddl --search "eager_greedy(ff())"

Option 2: Use VirtualBox

As an alternative, we prepared a virtual machine running Ubuntu Linux where everything is already set up. You can use it with (almost) any desktop operating system (including Linux, Windows and OS X), but it requires a large download and 7 GB of free disk capacity.

Install VirtualBox on your machine if it is not yet installed (instructions).

Download the virtual machine image AAAI_Tutorial.ova (1.9G). Start VirtualBox and import the image using the "Import Appliance" menu option.

To test the virtual machine, start it in VirtualBox, open a terminal window and issue the same test commands as with Option 1 above. You can omit all installation and compilation steps; only test the "fd" and "fast-downward.py" commands. (Everything is already installed and compiled.)

In case you want to perform any operations requiring admin privileges in the virtual machine, the password is aaai2015.