An Answer Set Encoding for Narrative Planning with Theory of Mind

Abstract

There has been much research into making planning-based story generators more efficient; however, the question remains whether the same efficiency could be achieved by reducing the problem to a more widely-studied search problem and leveraging existing solvers. We investigate this question for the narrative planning formalism used by Sabre, which models character goals and beliefs with deeply-nested theory of mind. We use answer set programming to develop a declarative implementation of the same planning formalism. Benchmarking our implementation, we find that existing, specialized planners remain the state of the art for solving their target problems as quickly as possible. However, the compactness and modularity of our approach will make it easier for researchers to develop prototype generators for new solution spaces that build on existing models.