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.
In a planning problem, we typically do not completely describe a state. Rather, we give just partial
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.
- Classical: each state is “atomic”, like a single node in a graph; the outcome of every action is known; each action takes a single unit of time to complete.
- Temporal: like classical except actions take variable time to complete, so multiple actions may be performed simultaneously; deadlines may be involved.
- Partially-observable: states cannot be fully observed, instead there is a probability of a state having certain properties; effects of actions are not fully known.
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.”
Initial state: a conjunction of positive “literals” (no variables), e.g.,
on(monkey, floor), at(monkey, 5, 2), at(box, 3, 0), on(bananas, box)
Actions: a set of possible actions to take. Each action has an action name, relevant variables, preconditions, and effects. Think of an action like a function with arguments. The preconditions say under what conditions the action is valid; they can refer to the arguments. The effects say what the result of the action is; they can also refer to the arguments, and can include positive and negative effects, sometimes separated as “add” effects and “delete” effects. For example, the
moveaction might involve variables
to, have precondition
at(thing, from)and postcondition or effect
not(at(thing, from)), at(thing, to).
Goal criteria: another conjunction of literals. Both positive and negative literals are allowed. E.g.,
on(monkey, box), not(on(bananas, box)).