Classical Planning Introduction

The aim of this post is not to cover classical planning or any of it’s extensions in great detail, but instead point to the spread of existing resources that have already been put together. As the available resources change and improve, this post will be updated accordingly.

If you have any questions, feel free to reach out to me.

Summary

Automated planning has many definitions, and most fail to capture the generality of the framework. According to a random author on Wikipedia,

Automated planning and scheduling, sometimes denoted as simply AI Planning, is a branch of artificial intelligence that concerns the realization of strategies or action sequences, typically for execution by intelligent agents, autonomous robots and unmanned vehicles.

The issue here is that while enabling robots to drive around the room is useful to describe some planning concepts, it is by no means the full picture of what planning is capable of tackling (and, in fact, you probably shouldn’t even use domain independent planning for driving robots around rooms, but that’s another story…)

When might my problem be a planning problem?

If you need to decide on a sequence of actions or events or steps or …, and you aren’t sure in advance which ones you should use (in addition to not knowing their order). If you already know everything that “needs to be done”, and just not the order to do those “things”, then chances are you have a scheduling problem and not a planning problem.

Part of the art of applying planning techniques to solve problems is recognizing if the problem is amenable to planning to begin with, and then deciding on what planning formalism is sufficient to capture enough of the problem. “Planning” is a general term that encompasses everything from finite and discrete to continuous and numeric; fully to partially observable; deterministic to continuous; etc.

As a general rule of thumb, you should always use the most restrictive formalism that you can get away with using to solve your problem.

This means that you may need to be clever in how you encode things as a planning problem so that you forgo model clarity for efficiency. This is why becoming familiar with modeling tricks and techniques is vital to successfully using planning solutions. This also means that it is best to start at the ground-level, and learn what planning is and how to model things in the most basic (and subsequently most computationally efficient) formalism – classical planning.

Resources to Learn Classical Planning and Modeling

Artificial Intelligence Planning with STRIPS, A Gentle Introduction

Written by someone from outside of the automated planning field, this is perhaps one of the best intros of classical planning to those who have never seen it before. It covers both the standard language we use to model planning problems (PDDL), and the search techniques that form the basis for research in the field.

Three States and a Plan: The A.I. of F.E.A.R.

Describes the AI used in the video game F.E.A.R., and does a very good job at introducing some of the core concepts in planning in the context of game development. A little dated by this point, but very well done in describing some of the core intuitions.

An Introduction to PDDL

This is just a short set of slides that goes through the PDDL modeling language. Worth going through after reading the post above to get a little better sense of PDDL.

Planning Wiki

While mainly focused on forms of PDDL, and the planners capable of solving them, the planning wiki is a wonderful (and growing) resource of details on these aspects of planning. Definitely worth checking out, and bookmarking for future reference!

Planning.Domains

This is an online editor for PDDL. It isn’t necessarily a resource that you can use to passively learn, however, after reading through the above resources it will serve as the perfect testing ground for playing with planning models. Some of the features worth playing with:

  • Use the Import functionality to load existing domain / problem files to see plenty of examples.

  • Use the Solve functionality to try solving the problems and seeing what the solutions look like.

  • Use the Session functionality to save your session. For loading it later, use the Read/Write URL, and for sharing works in progress (e.g., if you’d like me or someone else familiar with planning to take a look at your models), use the Read URL.

As a note on privacy – currently, PDDL is saved in plain text remotely (heroku servers located in California) only if you save a session. Further, I (Christian Muise) am the only one with access to the database.

A Beginner’s Introduction to Heuristic Search Planning

This is a tutorial given at AAAI in 2015, and focuses mainly on the techniques used to solve classical planning. This goes further into the details on the research that has taken place over the last few decades towards solving planning problems in an automated and domain-independent way.

A Concise Introduction to Planning Models and Methods

Following on the thread of the previous tutorial, this one dives deeper into the various forms of planning (relaxing the assumptions of determinism, full observability, etc.). It is substantially more detailed, and likely only useful if you want to get a sense of the richer formalisms that exist.

Modeling a Simple Planning Domain

This is a course project designed to introduce students to planning and modeling for classical planners. Some of the links are broken (as it happens with old references on the internet to academic sources…), but the problem is nicely defined and would be a good challenge to start with if you don’t have any other ideas of a domain you’d like to model.

Education Portal

This site houses a growing list of educational resources for the planning field. From course notes/slides to example assignments.