Exploring Regression-Based Narrative Planning Stephen G. Ware and Orion Fisher Narrative Intelligence Lab, University of Kentucky Lexington, Kentucky, 40508 sgware@cs.uky.edu, orion.fisher@uky.edu Abstract terms of the whole sequence, or even in terms of the space of possible sequences. Consider intentionality. Narrative plan- A valid and believable narrative plan must often meet at least ners often require that every action taken by an agent con- two requirements: the author’s goal must be satisfied by the end, and every action taken must make sense based on the tribute to a sequence of actions to achieve that agent’s goal. goals and beliefs of the characters who take them. Many nar- Because goals are achieved at the end of the sequence, it rative planners are based on progression, or forward search is difficult to know at the beginning whether the actions an through the space of possible states. When reasoning about agent is taking will contribute or not. goals and beliefs, progression can be wasteful, because either In this paper, we propose a regression-based narrative the planner needs to satisfy the author’s goal first and then planning algorithm that starts at the author’s and agents’ explain actions, backtracking when an explanation cannot be goals and works backwards to the initial state. Regression found, or explain actions as they are taken, which may waste planning was described as early as 1975 (Waldinger 1975), effort explaining actions that are not relevant to the author’s but is rarely used in classical planners. We propose it is a goal. We propose that regression, or backward search from good fit for narrative planners for two reasons: goals, can address this problem. Regression ensures that ev- ery action sequence is intentional and only reasons about the 1. Intentions are goal-directed, so searching backwards from agent beliefs needed for a plan to make sense. goals ensures the planner does not spend effort consider- ing actions that don’t contribute to goals. Introduction 2. When we allow for a theory of mind (what x believes y believes, etc.), belief propositions can be infinitely nested. Narrative planning algorithms search for a sequence of ac- Regression can limit the planner to reasoning only about tions that tell a story and that make sense for each char- the beliefs that are relevant to the plan. acter involved in the actions. Many search strategies have been adapted from classical planning research, including We begin with a description of our particular narrative plan- partial-order causal-link planning (Young 1999; Riedl and ning formalism. We then present our regression algorithm Young 2010; Ware and Young 2011), constraint satisfaction and explain why it is promising. We conclude with a fully (Thue et al. 2016), and answer set programming (Dabral and worked example to demonstrate the process. Martens 2020; Siler and Ware 2020), to name just a few, but as in the classical planning community, many narrative plan- Narrative Planning ners are based on forward heuristic search though the space Narrative planners have modeled many kinds of story phe- of states (Charles et al. 2003; Teutenberg and Porteous 2013; nomena (see Young et al. (2013) for a survey). In this pa- Ware and Young 2014; Thorne and Young 2017). per, we build on a version of narrative planning described Forward search (or progression) starts at the initial state by Shirvani, Farrell, and Ware (2018) with these features: of the problem and checks which actions are possible in that • There is a system-level author goal that must be achieved state. Those actions are applied to generate the possible next by the end of the story. states. Then any actions which are possible in those states are applied, and so on, until a valid story is discovered. Plans • Agents have (possibly wrong) beliefs about the world and are constructed from start to end in order. other agents. Beliefs can be arbitrarily nested, meaning Narrative planning can be challenging because it places there is no depth limit on the theory of mind. complex constraints on what action sequences are consid- • Agents have intentions, or personal goals. For an agent ered valid stories, and these constraints may be defined in to take an action, the agent must believe the action can contribute to achieving their goal (whether or not it will). Copyright c 2020, for this paper by its authors. Use permitted un- der Creative Commons License Attribution 4.0 International (CC In this section, we formally define our model of narrative BY 4.0). planning, modifying Shirvani, Farrell, and Ware’s defini- tions slightly to include an explicit representation of the au- For Treasure Island, G(cA ) = T H, meaning Hawkins has thor as an agent and to redefine intentionality without using the treasure. Hawkins and Silver both want the treasure; causal links. We introduce our own version of the Treasure G(H) = T H and G(S) = T S. Island problem as a running example in Figure 1, which is a For simplicity, we define every agent to have exactly simplified plot of Robert Louis Stevenson’s 1883 novel. one goal for the whole story, though in our implementa- In the story, protagonist Jim Hawkins (H) finds a map that tion agents can have multiple goals which can be adopted gives the location of treasure (T ) buried by Captain Flint. or dropped during the story. Antagonist Long John Silver (S) is Flint’s former first mate, but does not know where the treasure is buried. Hawkins lets States and Actions it be known that he has the map, prompting Silver to recruit a A state must be able to determine the truth value of any pirate crew and sail to Treasure Island with Hawkins. There, proposition. It must define a value for every fluent, plus ev- Hawkins digs up the treasure. Both Hawkins and Silver hope ery agent’s beliefs about the values of every fluent, plus their to take the treasure for themselves, and Hawkins eventually beliefs about others’ beliefs, and so on infinitely. succeeds. Two functions are needed to define a state. For some state Formally, a narrative planning problem is a tuple s and some fluent f , let V (s, f ) → Df be the value of that hC, F, G, s0 , Ai. C is a set of agents, F a set of state flu- fluent in that state. For some agent c and some state s, let ents, G a goal function, s0 the initial state, and A a set of β(c, s) be the state that represents agent c’s beliefs in s. In actions that change the state. Each of these is defined in the other words, when the world state is s, agent c believes the sections below. world state is actually β(c, s). The proposition f = v holds in state s when V (s, f ) = Agents, Fluents, and Goals v. The proposition b(c, p) holds in state s when p holds in C is a set of objects that represent the agents, (i.e. characters) β(c, s). in the story. All domains include the special author agent cA The author agent cA does not have wrong beliefs about the that represents the author of the story. For Treasure Island, state of the world, so we define β(cA , s) = s for all states. C = {cA , H, S}. Note that β is a function, which implies that every agent F is a finite set of state fluents, each with an associated commits to a specific (but possibly wrong) belief about every finite domain Df . Each fluent f ∈ F is like a variable that fluent. This requirement simplifies problems significantly, can be assigned exactly one value from Df at any moment but means we cannot represent uncertainty (where an agent in time. The proposition f = v means that fluent f has value could hold one of several sets of beliefs). We have found v ∈ Df . In Figure 1, the fluent T represents the treasure’s lo- this a useful tradeoff in practice, though others have found cation, which can be buried on the island (B), unknown (N ), it valuable to model uncertainty (Mohr, Eger, and Martens dug up on the island (I), or in the possession of Hawkins (H) 2018). or Silver (S). We use the shorthand T B to mean “the trea- As an analog to the use of notation for membership of sure is buried on the island.” The constant N , for unknown, propositions, it is helpful to succinctly indicate that a propo- is simply a value and has no special semantics here. sition p holds true in a state s (equivalently, p is satisfied by We define a simple logical language which allows three s). This is indicated by s ` p. kinds of propositions p, expressed by this grammar: s0 is the initial state of the narrative planning problem. It describes the initial values of all fluents and all initial agent p := f = v | b(c, p) | p ∧ p beliefs. In Treasure Island, the treasure is initially buried on the The first kind, f = v, is defined above. The modal propo- island, T B, and Hawkins believes this. Using Shirvani, Far- sition b(c, p) means that some non-author agent c ∈ C be- rell, and Ware (2018)’s extension to the closed world as- lieves proposition p to be true (where p can be any proposi- sumption, we do not need to explicitly state b(H, T B); this tion, including another belief). We also allow conjunctions, is assumed because T B is true and Hawkins has no explic- p ∧ p. We assume this equivalency: itly stated belief that contradicts it. Silver does not know the treasure’s location, so b(S, T N ) must be explicitly stated. b(c, p ∧ q) ↔ b(c, p) ∧ b(c, q) Hawkins believes Silver does not know where the treasure These three kinds of propositions are sufficient to describe is, b(H, b(S, T N )), but this also is assumed by the closed our model, though our implementation (currently under de- world assumption and does not need to be stated. It is equiv- velopment) includes additional features like negation, dis- alent to say that b(S, T N ) holds in s0 and to say that T N junction, first order quantifiers, and conditional effects. holds in β(S, s0 ). In this simplified model, it is often convenient to use a The set A is the set of all actions that could be taken in a concept of membership in a proposition. Some proposition narrative planning problem. Every action a ∈ A has a pre- p, as defined above, is a member of a proposition q if p is condition, PRE(a), a proposition that must hold in the state itself a conjunction of any number of conjuncts from q. This immediately before a occurs, and an effect, EFF(a), a propo- is denoted by q |= p. sition which becomes true in the state immediately after a G is a function G(C) → p that defines the goal propo- occurs. sition of every agent c ∈ C. G(cA ) is the author’s goal, Action preconditions and effects should not be contradic- a proposition which must be true at the end of the story. tions. For example, an action may not have the precondi- Problem Fluents Initial State: 𝑠0 = 𝑇𝐵 ∧ 𝐻𝑃 ∧ 𝑆𝑃 ∧ 𝑏 𝑆, 𝑇𝑁 𝐻𝑃 = Hawkins is at port. 𝑓1 Goals: 𝐺 𝑐𝐴 = 𝑇𝐻 𝐺 𝐻 = 𝑇𝐻 𝐺 𝑆 = 𝑇𝑆 𝐻𝐼 = Hawkins is on Treasure Island. 𝑆𝑃 = Silver is at port. 𝑓2 𝑆𝐼 = Silver is on Treasure Island. Actions 𝑇𝐵 = Treasure is buried on Treasure Island. 𝒓𝒖𝒎𝒐𝒓 𝑇𝑁 = Treasure does not exist. PRE: 𝑏(𝐻, 𝑇𝐵) 𝑓3 𝑇𝐼 = Treasure is dug up on Treasure Island. 𝑇𝐻 = Hawkins has the treasure. EFF: 𝑏 𝑆, 𝑇𝐵 ∧ 𝑏 𝐻, 𝑇𝐵 ∧ 𝑏 𝑆, 𝑏 𝐻, 𝑇𝐵 𝑇𝑆 = Silver has the treasure. CON: 𝐻 OBS: 𝐻, 𝑆 𝒔𝒂𝒊𝒍 Key state 𝑎𝑐𝑡𝑖𝑜𝑛 edge Implied effects are PRE: 𝐻𝑃 ∧ 𝑆𝑃 highlighted in red. EFF: 𝐻𝐼 ∧ 𝑆𝐼 ∧ 𝑏(𝐻, 𝐻𝐼) CON: 𝐻, 𝑆 OBS: 𝐻, 𝑆 𝑛9 𝑇𝐵 ∧ 𝑆𝐼 ∧ 𝐻𝐼 ∧ 𝑏 𝐻, 𝑇𝐵 ∧ 𝑏(𝐻, 𝐻𝐼) 𝒅𝒊𝒈 𝒕𝒂𝒌𝒆(𝑯, 𝑻) 𝒕𝒂𝒌𝒆(𝑺, 𝑻) PRE: 𝐻𝐼 ∧ 𝑇𝐵 PRE: 𝐻𝐼 ∧ 𝑇𝐼 PRE: 𝑆𝐼 ∧ 𝑇𝐼 𝑑𝑖𝑔 EFF: 𝑇𝐼 ∧ 𝑏 𝐻, 𝑇𝐼 EFF: 𝑇𝐻 EFF: 𝑇𝑆 CON: 𝐻 CON: 𝐻 CON: 𝑆 𝑛8 𝑇𝐼 ∧ 𝑆𝐼 𝐻 OBS: 𝐻, 𝑆 OBS: 𝐻, 𝑆 OBS: 𝐻, 𝑆 𝑡𝑎𝑘𝑒(𝑆, 𝑇) 𝑛12 𝑇𝐵 ∧ 𝐻𝑃 ∧ 𝑆𝑃 ∧ 𝑏 𝐻, 𝑇𝐵 ∧ 𝑏 𝐻, 𝐻𝑃 ∧ 𝑏 𝐻, 𝑆𝑃 ∧ 𝑏 𝑆, 𝐻𝑃 ∧ 𝑏 𝑆, 𝑆𝑃 Silver’s plan to 𝑛3 𝑇𝑆 achieve 𝑇𝑆 𝑟𝑢𝑚𝑜𝑟 𝐻 𝑇𝐵 ∧ 𝐻𝑃 ∧ 𝑆𝑃 ∧ 𝑏 𝐻, 𝑇𝐵 ∧ 𝑏 𝐻, 𝐻𝑃 ∧ 𝑏 𝐻, 𝑆𝑃 𝑇𝐵 ∧ 𝐻𝑃 ∧ 𝑆𝑃 ∧ 𝑏 𝑆, 𝑇𝐵 ∧ 𝑏 𝑆, 𝑆𝑃 𝑛10 𝑛11 ∧ 𝑏 𝑆, 𝑇𝐵 ∧ 𝑏 𝑆, 𝐻𝑃 ∧ 𝑏 𝑆, 𝑆𝑃 ∧ 𝑏 𝑆, 𝑏 𝐻, 𝑇𝐵 ∧ 𝑏 𝑆, 𝐻𝑃 ∧ 𝑏 𝑆, 𝑏 𝐻, 𝑇𝐵 𝑆 𝑠𝑎𝑖𝑙 𝑠𝑎𝑖𝑙 𝐻 𝑆 𝑛6 𝑇𝐵 ∧ 𝐻𝐼 ∧ 𝑏 𝐻, 𝐻𝐼 ∧ 𝑏(𝐻, 𝑇𝐵) 𝑛7 𝑇𝐵 ∧ 𝐻𝐼 𝑑𝑖𝑔 𝐻 𝑑𝑖𝑔 𝑛4 𝑇𝐼 ∧ 𝐻𝐼 ∧ 𝑏 𝐻, 𝐻𝐼 ∧ 𝑏(𝐻, 𝑇𝐼) 𝑛5 𝑇𝐼 ∧ 𝐻𝐼 𝑡𝑎𝑘𝑒(𝐻, 𝑇) 𝐻 𝑡𝑎𝑘𝑒(𝐻, 𝑇) Author’s plan to Hawkins’ plan to 𝑛1 𝑇𝐻 achieve 𝑇𝐻 𝑛2 𝑇𝐻 achieve 𝑇𝐻 Figure 1: An example problem and example regression search space. tion T B ∧ T N , indicating that the treasure is both buried Valid Narrative Plans and nonexistent. Since a fluent may only have one value at a We use the function α to denote the state after a sequence of time, this is considered contradictory. This rule also applies actions. In state s, let α([a1 , a2 , ..., an ] , s) denote the state to beliefs. For example, an action cannot have the precondi- of the world after taking those n actions in order from state s. tion b(S, T B) ∧ b(S, T N ), which would indicate that Silver α is only defined if the preconditions of those actions are sat- holds two beliefs about the treasure’s location. To formally isfied immediately before they occur; that is PRE(a1 ) holds indicate that a proposition p is not a contradiction, we write in s, and PRE(a2 ) holds in α([a1 ] , s), etc. p 6|= ⊥. A sequence of actions is a valid story when it achieves the Actions also define CON(a), a set of 0 to many consenting author’s goal and when every action can be explained by the agents, who must have a reason to take the action. Not every beliefs and intentions of the agents who take them. agent involved in an action is necessarily a consenting agent. In a state s, an action a1 is explained for agent c iff there Consider the rumor action. Silver’s beliefs are modified, so exists a sequence of actions [a1 , a2 , ..., an ] such that: he is involved, but he is a passive participant. Only Hawkins needs a reason to take this action, so CON(rumor) = {H}. 1. α([a1 , a2 , ..., an ] , β(c, s)) is defined. Actions that happen by accident (i.e. actions agents cannot 2. α([a1 , a2 , ..., an ] , β(c, s)) ` G(c). anticipate) should have only the special author agent cA as the consenting character, which means only the author needs 3. All actions in [a2 , a3 , ..., an ] are explained. a reason for it to occur. 4. Unless c = cA , no action has cA as a consenting agent. Finally, every action a defines OBS(a), a set of 0 to many 5. No strict subsequence of those actions also meets these observing agents, which are non-author agents who see the same 5 criteria. action occur and update their beliefs accordingly. Because β(cA , s) = s by definition, the author effectively observes In other words, it makes sense for agent c to take action a1 every action. if and only if, according to c’s beliefs about what the cur- Belief propositions can be explicitly stated in precondi- rent state is, c can imagine a reasonable sequence of actions tions and effects. Consider the rumor action. Its precon- starting with a1 that achieves c’s goal (items 1 to 3). Item 4 dition is that Hawkins believe the treasure is buried on the means that accidental actions can only be explained for the island, b(H, T B), and its effect is that Silver now believes author; agents cannot plan for them to happen. Item 5 ex- the treasure is buried on the island, b(S, T B). See Shirvani, presses the idea that the plan the agent imagines should not Ware, and Farrell (2017) for full details on how effects are contain unnecessary or redundant actions. imposed on states. Some of the actions in the plan may be actions the agent Actions can have implied effects which are not explicitly must consent to, which we term actions the agent takes. authored but which still result from the action. Some of these Some of the actions are those that the agent anticipates will implied effects are marked in red in Figure 1. They can hap- be taken by other agents. This definition of anticipation is pen in two ways. drawn from Shirvani, Ware, and Farrell (2017). Anticipa- tion must be justified in the same way that we ensure actions The first implied effects are from surprise actions. It is to be taken are justified: it must be founded on those ac- possible for agents to observe actions they do not believe tions being explained for the agents who take them, accord- are possible. For example, if Silver does not know the trea- ing to the anticipating agent’s beliefs. In Treasure Island, sure’s location (i.e. he believes PRE(dig) is false), he would Hawkins anticipates that Silver will choose to sail to the is- be surprised to see Hawkins dig it up. When a surprise action land if he believes his goal can be achieved by acquiring the happens, agents first update their beliefs to correct wrong treasure. This anticipated action is necessary to explain how beliefs and then observe the effects. We accomplish this by Hawkins’ choice to spread the rumor of the treasure—to take copying any preconditions that remain unchanged into the the rumor action—is justified. effects of an action. Formally, Note that the explanatory action sequence only needs to ∀a, p : (PRE(a) |= p) ∧ (p ∧ EFF(a) 6|= ⊥) → EFF(a) |= p exist; it does not actually have to occur in the story. Silver is willing to sail to the island because he hopes to take the Consider the rumor action. Its precondition is b(H, T B), treasure, even if he never actually succeeds in executing this and Hawkins’ belief about the treasure is not changed by plan. This is Ware and Young’s (2014) model of conflict. It is the action’s effect, so this action implicitly also has the ef- important to note that explaining an action is, itself, a plan- fect b(H, T B). This is important, because when Silver hears ning problem. The high cost of explaining actions is one of the rumor, he not only believes the treasure is buried on the the motivations to use regression planning, which we discuss island, he also believes Hawkins believes this. in the following sections. The second kind of implied effects are from observations. In a state s, an action a1 is explained (in general) iff it is When a character observes an action, they believe its effects explained for every agent c ∈ CON(a1 ). In other words, an have occurred. Consider sail. It has the effect that Hawkins action makes sense when it makes sense for every agent who is on the island, HI, and Hawkins observes this action, so it takes it. implicitly has the effect b(H, HI). Formally: Finally, we can define that a sequence of actions [a1 , a2 , ..., an ] is a valid solution to the narrative planning ∀c, a, p : c ∈ OBS(a) ∧ (EFF(a) |= p) → (EFF(a) |= b(c, p)) problem iff: • α([a1 , a2 , ..., an ] , s0 ) is defined. 1. q 6|= ⊥. • α([a1 , a2 , ..., an ] , s0 ) ` G(cA ). 2. any state satisfying q satisfies PRE(a), so a can be taken. • All actions are explained. 3. EFF(a) partially satisfies p, formally: ∃l : p |= l ∧ EFF(a) |= l. Progression 4. p holds after applying EFF(a) to q. ∀r EFF(a) |= r and Progression, or forward search, begins at the initial state (r ∧ p 6|= ⊥ ). s0 and generates possible futures until a state is discovered Between nodes of the same agent an action edge represents where the author’s goal G(cA ) holds. A classical planner is a step the agent plans to take, or anticipates will be taken. finished once this node is discovered because any path to the Between nodes of distinct agents the action edge represents goal is a valid solution. evidence for the anticipation of that action. Consider node Progression is difficult for intention-based narrative plan- n10 in Figure 1. This node is a valid regression for a node ners, like ours, because solutions must meet two require- also owned by the author, n6 . It also contains the necessary ments: the author’s goal is achieved and every action is ex- beliefs to be supported by nodes n7 and n9 . A node hc, qi plained. Not every path to the goal is a solution. Planners like generated by expanding a node with action a is supported Glaive (Ware and Young 2014) first search for sequences if a regression can be found for at least one node for every that achieve the author’s goal and then try to explain the ac- agent in the consenting set except for c. That is, given γ is tions in the sequence. Significant work is wasted when an ac- the regression function defined in Algorithm 1: tion cannot be explained. Glaive’s heuristic tries to account for the number of yet-unexplained actions in its calcuations, ∀cother ∈ (CON(a) − {c}) but this is only effective in some cases. [∃hcother , pother i : q |= b(cother , γ(a, pother ))] Recent work on the density of narrative planning solu- tions (Siler and Ware 2020) suggests it may be valuable to When a node is supported, this indicates that all beliefs do progression the other way—the planner tries to explain necessary to ensure explainability of the actions leading out an action immediately after taking it, and when it cannot of that node are present, in particular those which provide be explained, that branch of the search can be pruned. This reason to anticipate the actions consenting agents will take. guarantees that any path to the author’s goal is a solution, but this approach risks wasting significant work by explain- Algorithm ing actions that are not relevant to achieving the author’s goal. IMPRACTical (Teutenberg and Porteous 2013) uses The regression of a single proposition over an action is given an explain-first approach, but actions are explained using by the procedure γ(a, p) in Algorithm 1. This function re- heuristics, so it cannot guarantee every action in the final turns the simplest proposition required for the action to be solution will be explained. acceptable for any plan continuing from that point, or it sig- nals failure. Regression Algorithm 1 γ(a, p) Regression, or backward search, starts at the goal G(c) and 1: Let a be an action, p is a proposition. generates plans from end to start until one is found that can 2: if (∃l : EFF(a) |= l∧p |= l)∧(∀r, EFF(a) |= r∧(r∧p 6|= be executed in the initial state s0 . ⊥)) then Consider Hawkins’ goal of acquiring the treasure, repre- 3: Let q be PRE(a). sented by T H. Only the take(H, T ) action has this as an 4: ∀l, p |= l : Let q be q ∧ l iff EFF(a) 6|= l effect. We can regress Hawkins’ goal T H over take(H, T ) 5: if q 6|= ⊥ then by removing the action’s effects from the proposition and 6: return q adding the action’s preconditions. The result is the proposi- 7: else tion T I ∧ HI. In other words, if we can find a state where 8: return failure the treasure is dug up and Hawkins is on the island, Hawkins 9: end if would have a way to achieve his goal—the plan take(H, T ). 10: else The search space for the regression is the space of valid 11: return failure and supported agent propositions, represented by hc, pi for 12: end if c ∈ C. The proposition p represents a goal that, if satisfied, indicates that the agent’s goal G(c) may be accomplished by continuing to follow some (potentially empty) plan. The The process of expanding the regression graph is given by criteria of being valid and supported define two key aspects the procedure SEARCH(C, G, A, s0 ) in Algorithm 2. If this of the search process, which come together to ensure that the function returns, it provides a plan that satisfies the author’s plan which follows from each such proposition is explained. goal, starting from the initial state. These nodes in the search space are connected by actions Search starts with the set of nodes {hc, G(c)i : c ∈ C} over which the regression is performed. A node hc, qi, which (line 3). The SEARCH algorithm is an iterative expansion was generated by the regression of hc, pi over action a is of the search space which proceeds by choosing a node to valid iff: expand (line 5) and an action to expand it with (line 9), then Algorithm 2 SEARCH(C, G, A, s0 ) used in some progression planners like Glaive (Ware and 1: C is the set of agents, G is a function of agents to agent Young 2014). Improving this check is an area for future goals, A is the set of actions, and s0 is the initial state. work. 2: Let X be ∅ 3: ∀c ∈ C : Let X be X ∪ hc, G(c)i Worked Example 4: loop Looking at Figure 1 in more detail, we can see how the al- 5: Choose a node hc, pi ∈ X. gorithm takes shape. Initially, we begin our search at the 6: if (c = cA ) ∧ (s0 ` p) then goals for each agent: Silver, Hawkins, and the author. Any 7: return the path from hc, pi to hcA , G(cA )i of these would be effective choices for our first expansion, 8: else but we choose to expand the author’s goal, n1 : Hawkins has 9: Choose an action a ∈ A. the treasure. 10: Let pnew be γ(a, p). We compute the regression of T H over take(H, T ): 11: for cother ∈ CON(a) : cother 6= c do γ(take(H, T ), T H) = T I ∧ HI. If the treasure is on the 12: Choose a node hcother , pother i ∈ X such island, and so is Hawkins, we can use take(H, T ) to ac- that γ(a, pother ) does not fail. complish the author’s goal. The resulting node is valid, but 13: Let pnew be pnew ∧ b(cother , γ(a, pother )) we must also ensure that the node is supported by find- 14: end for ing a regression over take(H, T ) from a node owned by 15: if hc, pnew i not redundant for hcA , G(cA )i then Hawkins, the consenting agent of take(H, T ). n2 serves 16: Let X be X ∪ {hc, pnew i} our purpose, and the regression is also T I ∧ HI. From the 17: end if perspective of the author, this is our expectation of what 18: end if the agent needs to think is true of the world in order to 19: end loop take the action, as opposed to what the true state of the world is. Therefore, this proposition is added as a belief: b(H, T I ∧ HI) = b(H, T I) ∧ b(H, HI). This is conjoined choosing nodes from the plans of consenting agents to es- with T I ∧ HI to get the final result. Regardless of whether tablish support for the action (line 12). All such chooses are he is correct, Hawkins believes that n4 will put him in the non-deterministic. position to take the treasure. Since he is correct, the author Each expansion produces nodes which describe the con- can accomplish that goal as well. ditions under which the plan—the chain of actions leading The next regression in the author’s sequence will be the back to the node hc, G(c)i for that same agent—will suc- regression of the proposition for n6 over the action dig, but ceed. These nodes also explain participation of all consent- we can only expand a node if we can find a regression for ing agents for each action to be taken. The search concludes it and for a node from every consenting agent as well as the when a node is found which is both owned by the author and current one. In this case, we must first expand n2 (Hawkins’ satisfied by the initial state (line 7). goal to have the treasure) to get n5 (Hawkins’ belief that he Recall that the sequence used to explain an an action can eventually get the treasure if he is on the island and it should not contain unnecessary or redundant actions (e.g. is too) and now we have everything necessary to produce n6 sailing back and forth to the island before digging up the in the same way that we did for n4 . When preforming this treasure). For now, we define a node hc, pi to be redundant regression over dig, we must be sure to remove the implied when it has an ancestor node hc, qi such that p |= q. In other effect b(H, T I), as we preform this regression from n4 , to words, a plan is redundant when it ends with a sequence of avoid the contradiction of Hawkins believing the treasure is actions that would also achieve the goal and would apply in buried and excavated at the same time. all of the same states (and possibly more). The process continues as we consider the dig actions for the author and Hawkins, and perform those expansions. As an example, consider regressing node n12 over Then prior to being able to consider the sail action, which rumor. This represents the obviously redundant story: requires Silver’s consent, we must expand upon Silver’s plan until his search space has a proposition which can be re- {rumor, rumor, sail, dig, take(H, T )} gressed over the sail action. We find that we can perform a Hawkins spreading the rumor that he has the map twice is regression of his goal over take(S, T ), and then regress over possible, but unnecessary, because the proposition produced the action dig. Hawkins is the only agent who must consent by this regression would be exactly the same as the proposi- to dig, so Silver must expect that Hawkins will have rea- tion for n12 . son to dig. This is an instance of anticipation. Anticipating Note that a node hc, pi is not redundant when it has an the dig action provides an explanation for why Silver should ancestor node hc, qi such that q |= p. The proposition for consent to a sail action, if it left the world in a state fitting node n12 is a strict subset of the proposition for n10 , but n9 . spreading the rumor is not necessarily redundant, because The most complicated proposition for this example is the plan represented by node n12 may apply in some states the result of the regression of T B ∧ HI ∧ b(H, HI) ∧ where n10 does not apply, e.g. any state where b(S, T N ) b(H, T B) over sail. sail requires consent from both holds—Silver believes the treasure does not exist. Hawkins and Silver, so we must retrieve their regression This definition of redundant plans is not as robust as ones results as well, and add their beliefs. The final proposition is given by: γ(sail, T B ∧ HI ∧ b(H, HI) ∧ b(H, T B)) ∧ a valid plan, a heuristic only needs to estimate the distance b(S, γ(sail, T B ∧ SI ∧ HI ∧ b(H, T B) ∧ b(H, HI))) ∧ between the initial state and a node’s proposition. b(H, γ(sail, T B ∧ HI))). Included in this, as an example of nested belief, is Silver’s belief that Hawkins believes the Acknowledgments treasure is buried—and therefore Hawkins will seek to dig This research was supported by the National Science Foun- up the treasure and give Silver the chance to take it. n11 is dation under Grant No. IIS-1911053. determined in much the same way, but only needs consider- ation of Hawkins’ and Silver’s goals, not the author’s. n12 is expanded in the same way as the others. References At every step the algorithm compares expanded author Charles, F.; Lozano, M.; Mead, S.; Bisquerra, A. F.; and nodes against the initial state, though we have left out men- Cavazza, M. 2003. Planning formalisms and authoring in tion of this until now. When n12 is compared with the ini- interactive storytelling. In Proceedings of the conference on tial state, we see that we have satisfied the needs of the Technologies for Interactive Digital Storytelling and Enter- problem—keeping in mind that, unless explicitly stated oth- tainment. erwise in the initial state, we assume that each agent has an Dabral, C., and Martens, C. 2020. Generating explorable accurate belief of the world. narrative spaces with answer set programming. In Proceed- We propose that regression planning has three major ad- ings of the 16th AAAI international conference on Artificial vantages: Intelligence and Interactive Digital Entertainment. (forth- • By searching backward from goals, we ensure action se- coming). quences are intentional. There is still a risk that search ef- Mohr, H.; Eger, M.; and Martens, C. 2018. Eliminating the fort will be wasted exploring sequences which can never impossible: a procedurally generated murder mystery. In be possible, but regression addresses the two criteria prob- Proceedings of the 5th Experimental AI in Games workshop lem described in the previous section. Heuristic search at the 14th AAAI international conference on Artificial In- can prioritize sequences that can reach the initial state, telligence and Interactive Digital Entertainment. and once such a sequence is found, it is guaranteed to be a Riedl, M. O., and Young, R. M. 2010. Narrative planning: solution, with no additional constraint checking required balancing plot and character. Journal of Artificial Intelli- afterwards. gence Research 39(1):217–268. • With no limit imposed on the model’s theory of mind, it Shirvani, A.; Farrell, R.; and Ware, S. G. 2018. Combin- can be difficult to know which beliefs are relevant to an ing intentionality and belief: revisiting believable character agent’s plan. Shirvani, Ware, and Farrell’s (2017) model, plans. In Proceedings of the 14th AAAI international con- on which we build, spends much effort generating all ference on Artificial Intelligence and Interactive Digital En- changes to beliefs that result from actions, many of which tertainment, 222–228. are not relevant. Regression reasons only about the beliefs which are needed to make a plan work. Shirvani, A.; Ware, S. G.; and Farrell, R. 2017. A possible worlds model of belief for state-space narrative planning. In • Narrative planners are often used in interactive systems Proceedings of the 13th AAAI international conference on where the narrative is replanned frequently. A regression Artificial Intelligence and Interactive Digital Entertainment, plan expresses only the requirements needed to ensure it 101–107. will work, so plans found this way can be easily reused in Siler, C., and Ware, S. G. 2020. A good story is one in many states. Consider node n5 in Figure 1. Hawkins has a a million: solution density in narrative generation problems. plan to get the treasure in any state where the proposition In Proceedings of the 16th AAAI international conference on T I ∧ HI holds, which might be multiple states during the Artificial Intelligence and Interactive Digital Entertainment. lifetime of an interactive story. (forthcoming). Conclusions and Future Work Teutenberg, J., and Porteous, J. 2013. Efficient intent- based narrative generation using multiple planning agents. The algorithm we detail here presents a method to manage In Proceedings of the 2013 international conference on Au- intention and belief in narrative planning problems in a sin- tonomous Agents and Multiagent Systems, 603–610. gle search process, with no requirement to check that actions are explained after reaching the author goal. By the nature Thorne, B. R., and Young, R. M. 2017. Generating sto- of the search space, nodes are only added to the search if the ries that include failed actions by modeling false character action being used for the regression is fully explained. beliefs. In Proceedings of the 10th workshop on Intelligent Our implementation of the algorithm is in development, Narrative Technologies at the 13th AAAI international con- and will be tested a suite of benchmark narrative planning ference on Artificial Intelligence and Interactive Digital En- problems to determine the experimental performance of the tertainment. method. We also intend to develop and test heuristics to Thue, D.; Schiffel, S.; Árnason, R. A.; Stefnisson, I. S.; and guide the regression effectively. Heuristics like the one used Steinarsson, B. 2016. Delayed roles with authorable conti- by Glaive are complicated because they attempt to account nuity in plan-based interactive storytelling. In Proceedings for the number of yet-unexplained steps in a plan. Since ev- of the 9th International Conference on Interactive Digital ery node produced by our regression planner is represents Storytelling, 258–269. Waldinger, R. 1975. Achieving several goals simultane- ously. Technical report, Stanford University. Ware, S. G., and Young, R. M. 2011. CPOCL: a narrative planner supporting conflict. In Proceedings of the 7th AAAI international conference on Artificial Intelligence and Inter- active Digital Entertainment, 97–102. Ware, S. G., and Young, R. M. 2014. Glaive: a state-space narrative planner supporting intentionality and conflict. In Proceedings of the 10th AAAI international conference on Artificial Intelligence and Interactive Digital Entertainment, 80–86. (awarded Best Student Paper). Young, R. M.; Ware, S. G.; Cassell, B. A.; and Robertson, J. 2013. Plans and planning in narrative generation: a re- view of plan-based approaches to the generation of story, discourse and interactivity in narratives. Sprache und Daten- verarbeitung, Special Issue on Formal and Computational Models of Narrative 37(1-2):41–64. Young, R. M. 1999. Notes on the use of plan structures in the creation of interactive plot. In Proceedings of the AAAI Fall Symposium on Narrative Intelligence, 164–167.