AAAI Publications, Twelfth Artificial Intelligence and Interactive Digital Entertainment Conference

Font Size: 
Fast and Diverse Narrative Planning through Novelty Pruning
Rachelyn Farrell, Stephen G. Ware

Last modified: 2016-09-19


Novelty pruning is a simple enhancement that can be added to most planners. A node is removed unless it is possible to find a set of n literals which are true in the current state and have never all been true in any of that plan's previous states. Expanding on the success of the Iterated Width algorithm in classical planning and general game playing, we apply this technique to narrative planning. Using a suite of 8 benchmark narrative planning problems, we demonstrate that novelty pruning can be used with breadth-first search to solve smaller problems optimally and combined with heuristic search to solve larger problems faster. We also demonstrate that when many solutions to the same problem are generated, novelty pruning can produce a wider variety of solutions in some domains.


Novelty Pruning; Narrative Planning; Computational Models of Narrative

Full Text: PDF  |  Erratum