1. Introduction

In contrast to conventional narrative-based systems mainly pursuing dramatic interests, Virtual World (VW)-based pedagogical systems strive to provide realistic experiences in immersed situations [1-3]. The extent and depth of planning and associate execution of the events constituting each situation determines the scope of pedagogical experience in situations and consequently the quality of immersive learning based on a simulated world. A realistic situation generally comprises a number of planned and unforeseen events from each agent’s perspective. While each individual multi-event plan would be coherently drawn up by an agent for its respective goal, those independently-made plans might be coincidentally intertwined in their execution, presenting unforeseen events for other agents. We develop a plan-based simulation method for situation involving many independent agents’ plans. This method is aimed to afford high situation variability, still achieve authoring (or implementation) scalability. In an overall perspective, each instance of intra-event planning in our model is no more than a (small) part of progression of an entire situation involving those independent multi-event plans. This wide perspective is in a sharp contrast to that in planning for a single task of an individual agent or a cooperative group in conventional planning [4-8]. Further, those pre-planned events themselves, let alone unforeseen events, are inherently non-deterministic due to its relevant background-world conditions incessantly changing [4].

While all the variations of a storyline are conceived and pre-authored in conventional narrative systems [5,7], all potential events identified by a planning agent in our method are initially planned as an articulated sequence of events and dynamically coupled to each other across independent plans later in the execution time into a multi-plan situation. Each articulation corresponds to a junction between a pair of events, which is not permanent but is actually connected or not in the execution time depending on its associated background-world condition. This dynamic inter-event coupling is dictated by a set of inter-event association rules under the current conditions of their common background world. This late, indirect event connection based on articulated sequencing of (schematic) events allows for dynamic planning of a multi-plan situation in contrast to ‘monolithic’ storyline based on static planning in conventional narrative systems [5,7]. This dynamic planning leads to immediate reflection of current background-world conditions on each plan, i.e., those pre-planned events are instantiated with up-to-date parameter values, and to integration of individual agents’ plans into a globally coherent situation. The resulting global plan along with environmental (natural) events is reminiscent of Gottfried Leibniz's theory of pre-established harmony embracing mechanism and teleology. This dynamic planning also allows the story author to avoid authoring every possible sequence of events in its entirety [9]. The advantages of the dynamism in our planning extend to enhanced situation variability, which would inherently be limited to only pre-authored variations with a static event coupling as in conventional narrative systems [8]. A number of AI-based planning techniques, e.g., Situated Reasoning (SR), Heuristic Search Planning (HSP) [7], have been proposed to enhance narrative variations, only in limited ranges within the boundary of an individual event as determined by the story genre [10,11]. In addition, those originally-independent events from different plans may turn out to be coincidentally coupled with each other into an emergent situation [8].

Our fine coupling unit of the action allows events to be intimately connected via actions (e.g., walk, eat) of the agents cast in their roles [7]. To realize this intimate dynamic planning, we first need several essential components such as: parameterized event (functions) adaptable to variable background conditions (called schematic events); a full-blown background world to provide the coupling conditions among concurring plans in a situation and a historical context to those plans; a number of association rules to be used by planning agents and to dictate actual event coupling in reference to the background-world conditions. In reality, dynamic adjustment of a plan is interleaved with its execution as each agent in our model continually updates its recognition of the current condition. In reaction to an emergency situation, agents are designed to improvise a plan based on a case-based search [12] rather than the ordinary (time-consuming) generative search.

Combining independently-planned exogenous events into an augmented plan in role-casting time is based on an agent’s multitude of roles (or props) across those events, while coincidental coupling between mutually-unforeseen plans in the execution time is based on direct or indirect interaction via an inter-event association rule or a background-world factor they share. This coincidental coupling generating emergent situations could occur anytime with respect to each other, which further diversifies the contents of those emergent situations. Those inter-event association rule types include deontic associations as well as conventional causality [13]. The background-world conditions affect the contents of events and their coupling, and conversely the effects of event execution are directly reflected on the background world, and consequently affect (or initiate) all the relevant events therein. All these coupling factors are designed as part of the full-blown background world where all the events concur and produce their effects, which allows exogenous events to be coherently (i.e., semantically meaningfully) integrated with the original event. Also, a parameterized schematic event is separated from the background world (including agents) until it is instantiated into a historic occurrence, providing another clue for enhanced variability of situations [3, 5, 14].

The animation performance and action flexibility requirements are realized by a real-time animation method based on the priority queues, each corresponding to an independent and autonomous agent’s plan. Those actions from different plans are sequenced in an interleaved manner across those queues, collectively constituting a global plan corresponding to an entire situation. This fine level of animation unit allows for an intra-agent coupling of events beyond conventional inter-agent coupling, enabling parallel actions on one agent playing roles in different events (e.g., phone-calling and walking simultaneously) as judged possible by kinematic constraints on that agent [15]. This parallelism affords animation scalability against the infinite variability of changes occurring in our simulated world. It also enables new events to be efficiently animated in reaction to abrupt changes in relevant conditions. We first present planning of each agent and then the execution mechanism in a global scope. Finally we demonstrate with an analysis and an implementation that our approach based on the dynamic planning affords all this diversity of situations and is still scalable enough to underlie practical simulation systems. Admittedly, these advantages can be accomplished only at an expense of a limited visual realism, which is still in line with the requirements of our application domain.

2. Related Research

While episodes in edugame are independent of each other, as in ECHOES or FAtiMA [3,6] and actions in robotics are isolated occurrences [15,16], events in our model, corresponding to those episodes or actions, are interconnected (at least loosely) via ‘some’ association, if not parts of one coherent storyline. Discovery learning systems share with our pedagogical model the pedagogical paradigm of self-directed exploratory form of learning [17]. Whereas a scientific discovery learning system in particular emphasizes the student’s deep, conceptual understanding of its hard learning domain, however, our model is designed for shallow but broad-ranged subjects. Due to the dynamic generation of the situations, the scope of learning in our model is not confined to (part of) an original story plot [17] or to even each scene within [7,8].

Several techniques (e.g., Action Repair or Situated Reasoning) have been proposed into the conventional HTN planning to enhance narrative variability [7,8], but its scope is confined within the pre-authored domain of scenes. Supported by our dynamic (or coincidental) coupling among concurrent events, our planning based on generative search fully realizes ‘long-distance’ interactions or narrative variability pursued by search-based Interactive Storytelling (IS) techniques [7,8].

Behavior Tree allows sophisticated sequences of actions and contingencies to be represented as a concise graphical structure following a set of very simple rules with equivalent representations [9]. Behavior Trees are appropriate as tools for dealing with particular situations, but not for building a comprehensive virtual world due to the extensive intervention required of its author. While our model also expresses the story progression in terms of tree structure, it is decomposed into fragments to be assigned to different autonomous and independent agents and executed according to their order identified in planning.

A premise for simulating a situation consisting of a number of intertwined events is a stage for those events to be coherently coupled in a global spatio-temporal context. Our integrated background world representation scheme is designed to depict not only present time and its vicinity [9] but past and future (global) times [13]. The resulting multi-dimensional, multi-layered knowledge structure provides the model for a full-blown background world, a sophisticated version of Working Memory [13,18], rather than a passive backdrop as in conventional IS.

Unlike the player or lead character, non-player characters (NPCs) in IS are at best designed only to act reactively [7, 11, 19]. Every agent in our model is indiscriminately designed as an autonomous and independent type that behaves both reactively and proactively with their own belief and planning capability [20]. In this egalitarian community, any agent can be a candidate for any event role, and possibly assume multiple roles at once.

3. Generative Reasoning for Inter-Event Coupling

A schematic planning proceeds horizontally along several threads of reasoning via diverse candidate paths possible in a graph of events as illustrated in Figure 1. The associations between situations and events such as causality, deonticity, etc. [13] provide a key to reasoning of relevant events in planning for achieving a goal (situation.)

Figure 1. Generative reasoning for schematic planning

The relevant events are successively identified starting from an event able to directly satisfy the goal. The identifying is exemplified by a sequence ③→②→① for a goal situation in Figure 1 according to the functional association such that the Effect of an event produces a part of Precondition of another event. This horizontal identification process first proceeds backward over the set of candidate events or their composites until the Precondition of each event so far identified can be fully satisfied exclusively with the given background conditions [18,21]. Once identified in the horizontal planning, each selected event is further analyzed vertically with respect to its hierarchical composition.

An identified event may require other events to be added to the plan according to their association detailed above. For example, the originally identified (overarching) event A2 is premised on A1 indirectly through background conditions as led along ③&② chain to a premise association, and legally entails A3 following link ④ to a deontic association, as illustrated in Figure 1. These derived events A1 and A3 are to be added to the original event A2. Two subsidiary events in A3 are identified by a case-based search [12] and their order is accordingly determined as from A31 to A32, and the planning with A32 is similar to that with A2. These identified events in the corresponding order constitute a plan in a schematic form, which is subject to elaboration recursively. The resulting plan would be arranged to form a partially ordered set of events, denoted by ∏𝑘(𝐴_𝑘) , with the ‘last’ event (one with its Effect ⊇ goal) as the only greatest element [21]. In general, any partially ordered set of functionally interrelated events could be defined as a (composite) event, a clue leading to a layered organization of the event. Such a set forms a tree rooted at the event whose effect represents the overall function of the associated composite event. Each leaf node of the tree corresponds to an animated action.

4. Individual Agent’S Schematic Planning

A situation in our simulated world generally involves a number of independent plans, each of which comprises a (branched) sequence of subsidiary events as planned by its associated agent with a goal. Those independently-planned events could be coincidentally coupled with each other in their execution time according to their relevant background conditions non-deterministically changing. As a premise of enabling those couplings to occur in the action level, each overarching event corresponding to a plan is first to be planned in terms of actions.

As for goal state SG, the schematic planning would proceed in several steps such as:

1) Find, if any, an event with the goal in its effects.

2) Decompose the found event into subsidiary events recursively until all its subsidiary events are an action type.

3) Extract the Precondition of each event by recursively integrating those of its subsidiary events.

4) Augment the plan to include exogenous events found to be associated with each event.

5) Identify all the events whose successive execution can satisfy the goal.

6) Arrange those identified events into a plan according to their functional precedence.

An event in the schematic plan becomes instantiated into a historical occurrence by filling its associated roles (and props) with available instances from their respective domains. Given an initial situation at \(t=t_{0} S_{I}^{i}\left(t_{0}\right)\) such that \(S_{P}^{i}\left(t_{0}\right) \subseteq S_{I}^{i} \subseteq \Omega\) the entire set of situations in the background world, the effect from the execution \(A_{i}=\left(S_{P}^{i}, \Delta S_{i} ; \overline{S_{I}^{i}}\right.\) would be \(\overline{S_{I}^{i}}\left(t_{0}^{i}\right)+\Delta S_{i} \rightarrow S_{F}^{i}\) such that \(S_{F}^{i}\left(t_{0}\right) \subseteq S_{Q}^{i} \subseteq \Omega\) where \(S_{P}^{i}\) denotes the precondition and ⊿ 𝑆_i denotes a change in situation; an over bar denotes an average or a typical value;  \(\overline{S_{I}^{i}}\) denotes a typical initial situation; and \(S_{F}^{i}\) denotes a typical final situation. The overall result from the entire plan ∏_iA_i against the initial conditions \(\left\{S_{I}^{i}(0)\right\}\) is expected to be \(\Pi_{i} S_{I}^{i}\left(t_{0}^{i}\right)+\Delta S_{i} \supseteq S_{G}\) where \(S_{I}^{i}\left(t_{0}^{i}\right)\)denotes an initial situation for A_i with \(U_{i} S_{1}^{i}\left(t_{0}^{i}\right)\) constituting the initial background situations for ∏_iA_i.

To elaborate the planning steps,

(1) Casting event roles.

Before filling the roles of an event their candidate agents’ availability needs to be checked in a temporal context. Those candidate agents chosen for the roles in an event plan likely have their respective plans independent of the plan. That is, the agent E can be cast for event A such that \(T(A) \subseteq \cap_{i=1}^{m} \overline{T\left(A_{l}\right)}\), where m denotes the number of events E is involved in.

(2) Each newly-derived event is recursively decomposed until all the resulting subsidiary events reduce to the primitive events of actions. The schematic planning would proceed in several phases such as:

i. Find events {𝐴_j} such that \(\overline{S_{F}^{j}} \cap S_{P}^{i-1} \neq \emptyset\), where i denotes the i-th round of search starting from round 0 for the overall event 𝐴₀.

ii. Select the best one 𝐴_j from {𝐴_j}.

iii. Collect the events found in (1) for each \(s_{j} \in S_{P}^{i}\), to form the candidate event set \(\left\{\dot{A}_{J}\right\}\) such that \(\overline{S_{I}^{i}}+\Delta S_{j} \rightarrow \overline{S_{F}^{j}}\) and \(\overline{S_{F}^{j}} \supseteq S_{G}^{j-1}\).

iv. Sequence \(\left\{\dot{A}_{J}\right\}\) into \(\prod_{k=0}^{N} A_{k}\), where \(N=\left|\left\{\dot{A}_{J}\right\}\right|\).

The effects resulting from the identified events generally include side effects besides the effects required for the goal. The effects that are not part of the goal 𝑆_Gare referred to as side effects, i.e.,𝑆_f = 𝑆_F − 𝑆_G. Those side effects might be detrimental enough to scuttle the entire plan.

(3) Distribute plan fragments to cast agents such that the augmented plan \(\prod_{j=1}^{n+N} \dot{A}_{j}=\sum_{i=1}^{m}\left(\prod_{k=1}^{n} A_{k}^{H^{i}}\right)+\prod_{j=1}^{n} \dot{A}_{j}\), where \(\left\{H^{1}, H^{2}, H^{3} \ldots H^{m}\right\}=E\left(\prod_{j=1}^{n} \dot{A}_{j}\right)\), \(A_{k}^{H^{i}}\) denotes the events undertaken by 𝐻ⁱ in the main plan.

(4) Compare among events in terms of priority.

Select the highest-priority event \(\dot{A}_{k}\) such that if \( \dot{A}_{k} \in A_{n}^{L}\), \(\dot{A}_{k} \not > \prod_{n=1}^{N_{T}} \hat{A}_{k-n}^{L}\), where \(A_{n}^{L}\) denotes an arranged event in the main plan.

6. Global Execution Mechanism of Multiple Plans

We describe the design of our simulation model with respect to how preplanned and unforeseen events are dynamically coupled against the background-world conditions, and how agents’ cognition and the results of event execution on the background world affect the subsequent development of a situation. An event coupling can be either an intra-agent or inter-agent coupling. An intra-agent coupling presents a clue for parallelism between the action the agent currently performs and a future plan (or an unforeseen action) while an inter-agent coupling occurs in interaction among agents interrelated via the background world.

Figure 2 illustrates a (priority) queue-based execution mechanism of plans along a part of an example situation flow. Each priority queue corresponds to an agent’s plan, and all those queues collectively constitute a global plan. This execution mechanism is basically organized in three layers: agent (plan), action, motion layers in a top-down order. The agent layer arranges events, planned and unforeseen, in a situation according to their priority or urgency. Many sequences of actions corresponding to as many events are distributed into their associated agents’ queues according to their interleaved order (Notice different colors of actions in a queue indicating different events) as scheduled in a global (a situation) level. A pre-authored set of schematic actions, (e.g., walk(), hold()) are animated by being instantiated with the values that reflect the current background-world conditions (denoted by brown ovals.) Those parameters of an action also constitute its termination condition which is continually checked by its agent. A situation elaborated by this three-layered implementation mechanism is further differentiated by an agent’s cognition module, leading to branched situation flows. The actions Agent1 plans to execute are shown to be arranged in their sequential order as stored in its queue at T7, T13, and T1. Its plan is often modified according to the associated background-world conditions. Notice the content of the queue at T7 does not materialize as scheduled with phone(to:home) coincidentally intervening before hand-over(:cash) as the real action flow shows. The queue content at T1 is interrupted by an emergency event (action) of dodge(:ball1), which is a result further affected (supported) by its cognition of a ball flying toward. Each action is animated in terms of its component motions, which enables parallel actions of one agent to be efficiently animated, e.g., carry() in terms of walk() & hold() in Figure 2. Notice many aspects of the situation are sensitive to timing adding further non-determinism, such as the time an event occurs may affect its associated schedule, e.g, intervening at T16 of report(theft()) into chat() ongoing from T15 to be suspended until T16+Δt. If the party were ongoing instead of finished, the action flow would change to eat(t2) & chat(t9).

Figure 2. An Action sequence of Agent1 and corresponding plans at crucial times in example

The events are prioritized relative to each other and their associated actions are accordingly animated. Their priorities are rearranged possibly into a new order if exogenous events are enqueued. Since unforeseen exogenous events and pre-planned events all are of the same form in a queue, they are uniformly executed in a parallel or concurrent manner [22], as dodging a flying ball carrying a wine. This dynamic reprioritizing of events and associated rearranging of their component actions enables independent events to be coincidentally integrated via the background world. Note that the priority of a queue element is a composite variable to reflect both the precedence among the subsidiary events within an overarching event and the real-world priority among those overarching events.

7. Implementation of Multi-Plan Situation

We demonstrate feasibility of our dynamic planning method by implementing an example situation involving independent events (plans), each of which is composed of the animated unit of agents’ actions. Each action in turn is constructed by a small set of reusable primitive motions. Consequently, an intricate situation is shown to be implemented in terms of a small set of primitive motions.

Figure 3 shows an emergency situation involving two independent events (i.e., party and ball-play), both of which an agent plays roles (i.e., cook and victim) in. This emergent situation conditionally occurs only when the cook carrying dish for the party happened to be on a collision course with the stray ball. A reflexive action of dodge() is superposed on the currently-performed action of carry() to make a parallel action on the agent. This situation is implemented using the case-based reasoning scheme [12] and the real-time animation technique [22]. Notice this emergency situation involves all those three focal issues on dynamic event coupling, that is, coincidental interaction between agent and object, each agent’s handling of multiple roles, and prompt reaction to abrupt change of an ambient condition.

Figure 3. An Emergency situation involving ‘carry’ action and reactive action for ‘dodge’

In Figure 4, we apply in a comprehensive manner our planning method to the earlier example multi-plan situation involving the events of a party, a burglary and a (potential) police arrest. We demonstrate in animation how these independently-planned events can be dynamically inter-coupled to generate countless, many unforeseen, situation flows without pre-authoring every flow variation. All the possible scenes are animated in terms of a small set of basic actions such as ‘phone’, ‘talk’, ‘walk’, ‘grasp’, ‘push and ‘climb’. Further, each agent plays different roles in different situations, such as Agent1(party host, victim, reporter), Agent2(thief, suspect, escapee), Agent3(thief, suspect, escapee) and Agent4(policeman, arrester, chaser) along with props like phone, door and valuable, where bold & Italic indicates roles. The first-level subsidiary events as shown below include ‘colluding between accomplices’, ‘fence clearing’, ‘burglary reporting’, ‘house invading’, ‘cooperative carrying out of valuable’, ‘police arrest’, and ‘police chase’. These subsidiary events can be sequenced into countless flows according to their associated conditions including relative occurrence timing. Of those possible flows, a few would progress along A1, A1→A2, A1 ∥ B3→A2→A4→C6-1, A1→A2→A4→A5-1 ∥ B3, A1→A2 ∥ B3→A4→A5-1→C7-1→C7-2, where ∥ indicates parallel occurrence; A, B and C indicate independent events; i of Ai-j indicates a chronological order of the sub-event within an event, and j indicates order within the sub-event Ai. All these variations depend on the conditions of those agents and the rest of the background world. To name a few, a crucial condition to dictate the flow in the example situation is the ‘report’ event with respect not only to whether or not that event is initiated, but also to when it is performed. In fact, its occurrence time could be anywhere along the entire progression of this multi-event situation, e.g., during A1, before A2, long after A5-1, etc. each leading to a different flow. If it has been initiated at all, its progression may not be as expected due to various unfavorable conditions, and accordingly its results would vary non-deterministically. In general, each sub-event in any flow could go awry for diverse reasons, e.g., the phone Agent1 uses to report could be malfunctioning, creating new background-world conditions. A successful completion of the theft (along a flow up to A5-1 unrestrainedly) could result from a number of different conditions, e.g., Agent2 or Agent3 is not detected by Agent1 in the first place, or Agent4 was too far away to get to the scene in time. Conversely, the successful sequence of sub-events for the ‘theft’ could be severed anytime before its completion to divert to another situation flow. If Agent4 or any other policeman happened to be nearby on a patrol, the police could stop the theft in a collusion phase, and the flow would be as short as A1 (surely, this sub-event itself is intricate enough to ramify into a number of different flows.)

Figure 4. Branched sequence of scenes due to ‘theft’​​​​​​​

Within that arrest sub-event in the final part of the scenario, countless variations are possible along the continuum of exact relative timing between theft and police arrival. In case the policeman arrives just in time as in C6-1 or earlier, the suspects could be apprehended at the scene as in C6-2. Otherwise, his late arrival would entail a chase as shown in C7-1 unless they already are completely out of sight. The chase itself could branch off into many different flows according to those agents’ respective characteristics or environmental conditions, e.g., a suspect against Agent4’s attempt of capturing may shake himself free from Agent4 and run away, or they may have to thread their way through heavy rush-hour traffic, etc. Following C7-1, C7-2 shows a scene with Agent4 panting in frustration after losing the outpacing suspects.

Our model is by design greatly alleviated from authoring burden thanks to the dynamic event-coupling, assembly-based simulation method using reusable actions. We will analytically compare the estimated authoring burdens between a static (monolithic) method [7-9] and our dynamic method. Consider a composite plan, which is decomposable into n subsidiary events in our design. In case it is authored as a (single) monolith, the number of its possible variations at the event level would be approximately computed to be N1 ∙ N2 ∙ N3 ∙ … ∙ Nn where Ni denotes the number of candidate events to couple with the (i+1)st level subsidiary event. In case it is decomposed as in our model, the number exponentially reduces to N1 + N2 + N3 + … + Nn. Furthermore, as each event is elaborated in terms of its component parameters, the total variations could explode to a prohibitively large number, that is, N1 ∙ (i ∙ j ∙ k) ∙ N2 ∙ (i ∙ j ∙ k) ∙ N3 ∙ (i ∙ j ∙ k) ∙ … ∙ Nn ∙ (i ∙ j ∙ k) = N1 ∙ N2 ∙ N3 ∙ … ∙ Nn ∙ (i ∙ j ∙ k)n, where i, j and k denote the average number of (entity and relationship) instances per event, the average number of attributes per instance, and the average number of domain values per attribute, respectively. However, that number would be limited in our model to: N1 ∙ (i ∙ j ∙ k) + N2 ∙ (i ∙ j ∙ k) + N3 ∙ (i ∙ j ∙ k) + … + Nn ∙ (i ∙ j ∙ k) = (N1 + N2 + N3 + … + Nn) ∙ (i ∙ j ∙ k), and eventually minimized to: N1 ∙ k + N2 ∙ k+ N3 ∙ k + … + Nn ∙ k = (N1 + N2 + N3 + … + Nn) ∙ k, if the factors are differentiated to the primitive (attribute) levels. As another advantage, every related factor is automatically taken into consideration regardless of it being specified in its associated events, which constitutes a comprehensive, methodical way of narrative authoring.

8. Conclusion

We develop a simulation method that affords high variability of virtual pedagogical situations involving many independent plans, still achieves authoring (or implementation) scalability. Instead of story plot comprising predetermined single-event situations as in conventional IS systems, our inter-event planning method usually involves multiple plans dynamically coupled via their associated agents’ conditions and realistic associations between events in the background world. The specific techniques to realize our method include inter-event planning, autonomous and independent agents with real-time reaction capability, full-blown background world, dynamic event coupling via realistic association types, and a real-time animation technique. The action-level animation unit and reusable actions enable a real-time animation with an intra-agent coupling between plans for concurrent and parallel actions on one agent. We analyzed and implemented our simulation method to verify its viability.

Acknowledgments

This work was supported by the National Research Foundation of Korea(NRF) grant funded by the Korea government(Ministry of Education) (No. 2016R1D1A2B03935650).

Conflicts of Interest

The funders had no role in the design of the study; in the collection, analyses, or interpretation of data; in the writing of the manuscript, or in the decision to publish the results.