1 Overview
1.1 Basic Terminology
All automated planning focuses on at least one of the following objects:
A state, which is a representation of the state of the world.
An action, which is a transformation of a state. Not every action can be performed in every state: an action must be applicable to a state in order to perform it on that state. Every action has a cost —
a nonnegative number indicating how much time, money, or some other scarce resource it takes to perform the action. Planning often involves minimizing costs. A goal, which is a statement about what kinds of states the planning agent should try to achieve.
A planning problem is a combination of an initial state, a collection
of actions, and a goal. An automated planner is a computer algorithm
that solves planning problems by producing a plan —
1.2 State Representations
To plan, one must consider the effects of one’s actions on the state of the world. Therefore, an automated planner is limited by its model of the world state, called the state representation. Choosing an appropriate state representation is the first step in solving any planning problem. The planning library ships with built-in support for three different state representations:
The set state representation, where the world state is a set and actions add and remove elements to and from the set. Goals are expressed in terms of elements that must be present or absent. This is a good general purpose state representation, but the lack of structure can make it awkward to work with.
The multiset state representation, where the world state is a multiset and actions add and remove multiple copies of elements at a time. Goals are expressed in terms of desired quantities of different elements. This representation is highly effective in planning domains that involve some sort of resource production or inventory management, such as chemical processing or videogame crafting systems.
The hash state representation, where the world state is a hash table and actions add and remove key-value entries to and from the hash table. Goals are expressed in terms of desired and undesired keys and entries. This representation is fairly effective at modeling objects located at different positions in the world, such as pieces on a game board or boxes in a shipping warehouse.
If you’re familiar with classical automated planning textbooks you might notice that the state variable representation is conspicuously absent. This is partly because in real-world code I found collection-oriented state representations to be easier to work with than variable-oriented representations, but only partly. Mostly it’s because it’s more complicated and I never had much personal interest in it. If you wish to use a state variable representation, please reach out to me so I can learn more about your use case.