Home

Planning

Planning is another search problem, but it is slightly different than 8-puzzle, path-finding, etc. We use planning rather than simple search when the domain is very large and there are too many states to search with one of the search strategies we’ve learned previously.

Instead, a planner searches across partial state descriptions. We describe planning problems in a new language, PDDL, rather than an explicit function of possible transitions.

Motivation

In a planning problem, we typically do not completely describe a state. Rather, we give just partial descriptions, like on(monkey, floor), at(monkey, 5, 2). There might be lots of other things in the room besides the monkey, even things relevant to our planning problem, but we don’t want to describe all those other facts for every possible state transition. Breadth-first search, depth-first search, A*, etc. would have trouble with these kinds of states because they are incomplete.

But we can handle these incomplete states by treating them as a planning problem. The way the planning algorithm works, and the way we describe planning problems, is slightly different because we want to know how different actions add or remove facts from the state; the action does not describe all the facts of the state that will result.

Here is an example to illustrate the problem BFS/DFS/A* would face. Suppose we have 10 airports, 50 planes, and 200 pieces of cargo. All the cargo is at SFO and needs to be at JFK. Planes are assumed to have infinite capacity. There are three actions: load cargo, unload cargo, and fly the plane from one airport to another. Suppose each of the 50 planes can fly to 9 other airports, and that each of the 200 packages can be loaded on any plane. Then we have 9*50*50*200 possible actions at the start; that’s 4.5 million possible actions, just for the first move.

Types of planning problems

We will only focus on “classical” planning, although more sophisticated planning problems exist and remain active research.

Definition of a classical planning problem

Like the definition of a search problem, a classical planning problem is made up of an initial state, possible actions, and goal criteria. However, unlike the search problems we examined earlier, states in a planning problem are not fully described. Rather, conjunctions of “predicates” like at(monkey, 5, 2) or negated predicates like not(at(monkey, 5, 2)) are used instead to describe a state. When a predicate involves no variables, it is called a “literal.”

CSCI 431 material by Joshua Eckroth is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License. Source code for this website available at GitHub.