Detecting Duplicate States Is Worth It in Narrative Planning with Belief

Abstract

Narrative planning algorithms generate stories as a sequence of actions that align with an author-defined goal while ensuring characters act believably, often requiring reasoning over nested beliefs. When theory of mind is represented, states include not only the factual world but also each character’s beliefs about the world and other characters' beliefs, potentially to infinite depth. In such planners, detecting duplicate states can prune redundant paths in the search space, but it is unclear whether it is too computationally expensive to justify. This paper investigates the cost and benefit of duplicate state detection using the Sabre planner, which models infinitely nested beliefs deterministically. We compare two approaches: tree search, which does not check for duplicate states, and graph search, which uses a recursive equivalence algorithm to detect and avoid duplicates. We provide a polynomial-time algorithm for detecting duplicate states and empirically show that using it significantly reduces the number of nodes generated and the total planning time across several benchmark problems. These findings suggest that duplicate detection in epistemic narrative planning is both feasible and beneficial.