Planning can be defined as “the reasoning side of acting” [auto_planning]. Solving a planning problem involves thinking about the available actions, considering their expected effects and identifying a sequence of them that will achieve the desired goal.
Planning problems can be specified in multiple ways. Often there is the concept of a goal state that is to be reached. This is the case e.g. in path planning, planning an assembly of some product, etc. However, some tasks are on-going and the concept of the goal state does not arise naturally – in those cases a more general definition of the objective is possible. One option would be to define some condition that needs to be satisfied over a sequence of states: this would align the planning problem more closely with constraint satisfaction problems. There may even be some cost function that needs to be minimized and that would bridge the area of planning with that of optimization.
The area of planning is also closely related to that of scheduling. Where planning deals with sequences of actions and states, scheduling deals with resource constraints – and this is an aspect that a planner would often need to take into account as well: e.g. it is no use planning two operations to run concurrently if they both require the same resource, which cannot be shared and multiple instances of it are not available.
The area of planning is also closely related to that of modeling: in order to create a plan, the planning method will generally need to consider the expected effects of actions, which requires some kind of model of the environment.
To give a toy-problem instance of planning, we may mention the 8-puzzle. The puzzle board consists of 9 squares. 8 of them contain blocks numbered from 1 to 8 and the one square is empty. The available actions include moving a block up, down, left or right, but only if the target square is empty. A planner would be required to come up with a sequence of actions that are going to get the blocks from some initial state into a goal state.
The 8-puzzle: an initial state (left) and the goal state (right).
Literature
- [auto_planning] Ghallab, M., Nau, D. and Traverso, P., 2004. Automated Planning: theory and practice. Elsevier.