# A Survey of Planning and Learning in Games
## 4 Planning in Games
### Planning Techniques
#### 4.1.4 Classical Planning  
Planning problems are usually described via a conceptual model and in particular by the model of state-transition systems, defined as a 4-tuple \(\Sigma=(S,A,E,\gamma)\)[154]. In the previous definition, \(S\) is the set of states, \(A\) is the set of actions (i.e., transitions controlled by the plan executor), \(E\) is the set of events (i.e., transitions not controlled by the plan executor), and \(\gamma\): \(S\times A\times E\to 2^{S}\) is a state-transition function. The planning problem may be simplified by restricting this model via a set of restrictive assumptions such as by assuming that \(S\) is finite, \(\Sigma\) is fully observable, actions are instantaneous, or that the planner is not concerned with any changes that might occur in \(\Sigma\) while it is planning.  
A family of planning techniques referred to as classical planning assumes a set of eight such assumptions and considers a restricted model of a fully observable, finite, deterministic, and static system with restricted goals and implicit time (i.e., \(\Sigma=(S,A,\gamma)\)). Another such family is neoclassical planning. Neoclassical planning still deals with restricted models but has introduced new techniques to the planning domain, such as planning-graph techniques, which introduce the planning-graph as a reachability structure in the state space, propositional satisfiability techniques, which treat planning as a satisfiability problem, and constraint satisfaction techniques, which view planning as a constraint satisfaction problem [154]. The term Automated Planning (AP) will be used henceforth to designate both classical and neoclassical planning. Finally, several components of the planning problem (e.g., the actions and the model of the world) are usually expressed via a planning representation language such as the Stanford Research Institute Problem Solver (STRIPS) [180], the Action Description Language (ADL) [181], and the Planning Domain Definition Language (PDDL) [182]; see Figure 8.  
Planning techniques dealing with restricted models, such as those discussed previously, are not well suited to cope with challenges such as uncertainty, partial observability, actions with different timespans, or several agents acting simultaneously, common in most video game environments. In fact, their restrictive assumptions exclude these environments. Furthermore, planning representation languages such as PDDL may not be expressive enough. For example, PDDL does not account for the creation or deletion of objects, such as units or buildings in RTS games. This has led to the proposal of several extensions to relax the restrictions imposed on the conceptual model (e.g., the Goal Oriented Action Planner, or GOAP [183], and Layered GOAP, or LGOAP [150]) and to the integration with techniques borrowed from other AI research fields, such as learning techniques (discussed in Section 5). In addition, several extensions have been proposed to augment PDDL, concerning, for example, the creation and deletion of objects and the use of concurrent actions [184]. Furthermore, new planning languages specific to games have also emerged. An example of this is ABL (A Behavior Language) [185], a reactive planning language designed with the objective of authoring believable agents.  
These progresses in turn have allowed AP techniques to find several applications in game AI. Examples of this include deriving agents that can reason about several goals simultaneously (e.g., macro and micromanagement in RTS games) [186], macromanagement in RTS games [187], implementing believable agents [188], deriving more adaptive and challenging AI opponents [189; 190], control and coordination of NPCs [191], real-time generation of narratives in interactive storytelling systems [192; 193] and [194] (also supporting intentionality and conflict), and adapting human-authored game plottines offline for role-playing games according to the player's entertainment preferences [195].