Speeding Up Narrative Planning Using Fog of War Pruning

Abstract

Narrative planning is the process of generating sequences of actions that form coherent and goal-oriented narratives. Classical implementations of narrative planning rely on heuristic search techniques to offer structured story generation, but often struggle with scalability because of large branching factors and deep search requirements. To improve the speed of narrative planning, we introduce Fog of War pruning, where Actions are only allowed if they involve people, places, and things that the protagonist character has discovered. This pruning technique restricts the planning to what is known from the perspective of the story's central character or characters, pruning branches of the search tree that involve actions beyond their current knowledge. This method is particularly useful in narratives where there is a strong protagonist focus and the story unfolds gradually as the character learns. This enables more efficient planning, while more closely aligning with how people would experience stories. Experiments across many narrative domains show that this technique not only speed up the search process, under identical search limits, also lets the planner solve more unique problems.