{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,7]],"date-time":"2025-11-07T20:40:25Z","timestamp":1762548025520,"version":"build-2065373602"},"reference-count":0,"publisher":"Association for the Advancement of Artificial Intelligence (AAAI)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["AIIDE"],"abstract":"<jats:p>Narrative planning algorithms generate stories as a\nsequence of actions that align with an author-defined goal\nwhile ensuring characters act believably, often requiring\nreasoning over nested beliefs. When theory of mind is\nrepresented, states include not only the factual world but\nalso each character\u2019s beliefs about the world and other\ncharacters' beliefs, potentially to infinite depth. In such\nplanners, detecting duplicate states can prune redundant\npaths in the search space, but it is unclear whether it is\ntoo computationally expensive to justify. This paper\ninvestigates the cost and benefit of duplicate state\ndetection using the Sabre planner, which models infinitely\nnested beliefs deterministically. We compare two\napproaches: tree search, which does not check for duplicate\nstates, and graph search, which uses a recursive\nequivalence algorithm to detect and avoid duplicates. We\nprovide a polynomial-time algorithm for detecting duplicate\nstates and empirically show that using it significantly\nreduces the number of nodes generated and the total\nplanning time across several benchmark problems. These\nfindings suggest that duplicate detection in epistemic\nnarrative planning is both feasible and beneficial.<\/jats:p>","DOI":"10.1609\/aiide.v21i1.36810","type":"journal-article","created":{"date-parts":[[2025,11,7]],"date-time":"2025-11-07T20:37:01Z","timestamp":1762547821000},"page":"62-69","source":"Crossref","is-referenced-by-count":0,"title":["Detecting Duplicate States Is Worth It in Narrative Planning with Belief"],"prefix":"10.1609","volume":"21","author":[{"given":"Fairoz Nower","family":"Khan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nabuat Zaman","family":"Nahim","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stephen G.","family":"Ware","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Judy","family":"Goldsmith","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"9382","published-online":{"date-parts":[[2025,11,7]]},"container-title":["Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment"],"original-title":[],"link":[{"URL":"https:\/\/ojs.aaai.org\/index.php\/AIIDE\/article\/download\/36810\/38948","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/ojs.aaai.org\/index.php\/AIIDE\/article\/download\/36810\/38948","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,7]],"date-time":"2025-11-07T20:37:01Z","timestamp":1762547821000},"score":1,"resource":{"primary":{"URL":"https:\/\/ojs.aaai.org\/index.php\/AIIDE\/article\/view\/36810"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,11,7]]},"references-count":0,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2025,11,7]]}},"URL":"https:\/\/doi.org\/10.1609\/aiide.v21i1.36810","relation":{},"ISSN":["2334-0924","2326-909X"],"issn-type":[{"value":"2334-0924","type":"electronic"},{"value":"2326-909X","type":"print"}],"subject":[],"published":{"date-parts":[[2025,11,7]]}}}