1. INTRODUCTION
The diversity of situations is crucial for a cyber-world as a platform for computer-based immersed learning [1]-[3]. A situation refers to a part of this world that concerns a human agent therein at a given time. Such a situation functions as a semantic unit that could contextualize its activities. The events are the comprehensive elements of a situation in that they involve all kinds of elements of the world. It is all the more so since they often exploit as their means diverse phenomena, each complex in itself. Unless its goal is simple enough to be achieved in one step, an agent should plan for an event to achieve its goal.
As generic a term as it is, planning referring to any process of organizing the activities required to achieve a goal has long been a significant research issue with respect to practical planning methods and formalisms in a wide range of application areas [4]-[10]. Planning can be differently defined between application areas, even within an area depending on its purpose. Whereas planning in Interactive Storytelling (IS), for example, pursues coherent and interesting development of a story while allowing user interaction [8], [11], planning in simulated-world–based pedagogical systems strives to provide realistic experiences in immersed environment [12]-[14]. Of those pedagogical systems, ones teaching declarative domain knowledge such as mathematics and linguistics [1], [15], [16] may not appear to be as relevant to event planning as ones for procedural domain knowledge, (whose pedagogical targets are the procedure itself in the form of sequence of actions directly resulting from planning) [13], [17]. Still, declarative domains have good reason to share implicate events as effective learning stage for their corresponding simulation, in that numerous opportunities of pedagogical experience could be immersively embedded in progression of those events [13], [17], [18]. The extent and depth of the event plan determines the scope of pedagogical experience in situations unfolding through events and consequently the quality of learning in an Intelligent Tutoring System (ITS) based on simulated world.
To provide immersed pedagogical experiences to the learners [2], we aim to simulate diverse virtual situations, which would develop within and without events and in between them. Our simulation views a situation as an accumulated result of all the relevant historical occurrences thus far. This view is reminiscent of the stance of Situational Calculus, where a situation is defined not as a snapshot state but as a finite sequence of actions [19]. Conversely, a world each human agent sees unfolds through a series of relevant situations as a result of events occurring within the world. Our target learning content consists basically of declarative knowledge, while both procedural and declarative aspects [20] are intertwined to a greater or lesser degree as specific events unfold through its procedure [21] in different classes of ITSs [12]-[15]. Though more intricate and involving events are likely to offer all the more extensive and concrete chances of experience, such a complicated event tends to involve not only many agents interrelated a priori in their common background world but also many subsidiary events coupled to each other via physical and social conditions. As a consequence, the scope of planning for our event simulation is not confined to an individual event (or story) as in typical storytelling or computer game, but often spills over to other events via multiplicity of an agent’s roles or other condition straddling events.
As the common background for all the events and associated agents and conditions the world in our simulation has greater significance than ones as passive backdrops [5], [9], [11], [14]. In fact the background world and events therein are not separated from, but integrated with, each other. As a result, events regardless of being main or not and their environments are likewise parts of the unifying ‘active’ background world. A situation, a part of the background world, is precisely modeled in terms of Cartesian product between the pairs of (entities, relations) and (existences, states), and their temporal change [22]. These entities include agents as the most sophisticated entity type with belief, desire and intention (or volition) [23], and relationships include the fundamental relation of location as one of the two axes forming historical context. The agents, the dominant entity type in our planning, are designed to be realistic agents of all sorts encountered in the virtual world, including rational agents [13], [23]-[25] and believable agents [26]-[28], and agents not classifiable to stereotypical characters. All those agents inhabiting the world use their respective minds and beliefs to govern their (autonomous) behaviors, enabling multiple intentional events to develop concurrently in an intertwined manner. Each instance of event planning originates from some desire and subsequent intended goal [23], [25], [29] of one of those autonomous agents. The transition from desire to intention is modulated by some utility function to reflect subjective or social value [29] though our planning focuses on intention as the final attitude on event planning and execution. This individualization of the background world already sophisticated in itself further enhances the play affordance, an important factor in effective learning by playing or doing in situations [30], [31]. Any agent is modeled to be an autonomous entity type acting on intention and has its own planning capability toward a goal it independently sets (consequently proactivity as well), unlike the other entity types whose actions are purely conditioned with no regard to intention (these actions are called phenomena.)
Our event simulation as prescribed by our pedagogical objective focuses on planning of intricate events in a macroscopic level rather than in individual event level, and on interactions (including negotiation for casting) among autonomous and independent agents. It is macroscopic in the sense that each entire plan usually involves a number of interconnected events which each may be handled by different agents and comprises another set of subsidiary events and recursively. An autonomous agent with its own belief and desire at least attempts to achieve its goal, though it does not always behave rationally [25]. An independent agent is originally in a free or an available state as part of the background world and remains free (i.e., on its own volition) even when assigned or bound to a task or role (only less free while cast in a role.) Such an agent can become a candidate for an event role it believes itself to be qualified for, but its actual undertaking is to be determined by some social relationship (and its intention.)
The event, the exclusive element for progressing situations in our simulated world, is defined differently in several ways from other definitions. An event in our approach is composed in a recursive structure, i.e., an event in general is recursively composed of smaller events, so it could be as simple as walking into room and as complex as constructing bridge. This recursive composition serves a pedagogical demand that every abstraction level of event specification be a potential target of user experience, which is in contrast to providing encapsulation units subjectively determined by authors for facilitating authoring complex interactions between characters and objects [10], [32]. In practice, role casting itself, though stated in the context of substituting agents in roles [33], presents diverse chances of experience throughout its associated event planning and execution. Candidate agents for a role might be evaluated with respect, at least to their own time-varying conditions and to relationships with the casting agent beyond individual traits or capabilities [27], [33]-[35].
Coupling between events in our planning is made via the preexisting background world in terms of individual parametric elements (or overarching norms), rather than directly between events in terms of the binary relationship between their precondition and postcondition [35], [36]. This coupling is similar to rule chaining in the rule based system. Like past events of relevance, future events also could be coupled if only those couplings are anticipated or projected by their associated agents, which rendering agents not just reactive but proactive. In summary, not only current conditions within the perspective of the main goal but their associated external causalities and historical contexts also are considered in our planning.
The applicable types of association between events plays a crucial role in planning in that it determines the identifiable range of events relevant to a given goal and the order among those identified events. While search in planning for related actions or events in IS or other scenario-based systems is mostly based on narrative causality only [8], [14], [17] our search method diversifies the applicable association types between events to account for a wider range of physical phenomena and normative events beyond behavioral actions of characters under a plot. It could be viewed as a generalization of goal and normative types of influence [37] to an entire spectrum of physical and social impacts.
Though causality is the most fundamental type of association, its specific implication varies depending on how it is used. First, it can be used to identify what events need to be performed to trigger or execute a given event. Conversely, it can be used to identify what events might be subsequently started as a result of executing a particular event. An occurrence of an event may obligate occurrence of its associated event as stipulated by some regulation. This deontic type of association is specified between a pair of events with no regard to an overarching event. For example, if a crime is committed its corresponding punishment is prescribed to be imposed. In case it is a convention that a (social) event proceeds in a regular order of its subsidiary events, those subsidiary events are of normative procedure association type. For example, an ancestral rites proceed in lighting candles, bowing, filling cups with alcohol, bowing, and so on. This type of association is not actually specified between events at the same level, e.g., lighting candles, bowing etc., but the order (or association) between these events are merely a consequence of arrangement by their overarching event, e.g., ancestral rites. Conversely a sequence of events of this association type constitute an overarching event, which can only be reasoned by case-based planning [20], [38] when their order is known to the planner. All the events judged to be relevant in terms of these four association types would be merged into the plan if they have reasonable chances of occurrence.
Our event planning is two dimensional, i.e., horizontal and vertical. The horizontal planning is an inter-event process based on search, while the vertical planning is an intra-event process based on hierarchical decomposition. Our planning first searches the world knowledge of a lead agent to identify the entire range of potential events and consequences derivable via the four association types starting from an initial goal set by that agent (in contrast to optimal or conditional searches [33], [39].) Each event that has been identified in this horizontal planning phase is recursively decomposed until the resulting subsidiary events all reduce to the primitive events of actions. A primitive event refers to a (simple) event that can be performed only by continuation or iteration of an action. Notice that each of these derived events in any planning phase is subject to another full-blown planning instance with that event as the initial event. In consequence the planning could be compounded by diverse exogenous events, which may have to be added to augment the ‘skeletal’ plan without contribution to achieving the main (or initial) goal. To sum up, the resulting plan comprises derived events in addition to the main event for the initial goal, forming a graph of events interconnected via their common conditional factors [40] or other types of association between events. A plan if successfully derived through the two phases is still in its schematic form, which is to be further elaborated in terms of quantitative aspects against relevant world states. These aspects include the existential properties of amount and count, the spatial relationships of location, and the spatio-temporal parameters of speed, duration, etc. [36]. All these quantitative aspects are formalized in spatiotemporal space [22].
The plot coherence in our approach is achieved in two levels: in an event level and in a macro-level. The event-level coherence is basically maintained by the conventional means of hierarchical decomposition of each event in a derivative of HTN planning while story variations are attained by means of search-based planning [8] with respect to external conditions of each event and meaningful types of association, respectively. The macro-level coherence across interconnected events is established via their common background world existing a priori. (It is reminiscent of the perspective any pairwise causality is only an intermediate one in an infinite chain of causalities.) The two-dimensional event planning and the inter-event planning together generate a semantically-rich and fine-grained event space from which numerous interesting situations could be derived through different courses of events or actions, which is an essential nature for high affordance of our simulated world. In fact, not only event failure itself but ensuing remedial actions [36] constitute another indispensable group of situations for pedagogical experience in the forms of alternative action, repair or withdrawal according to the event being essential or optional etc.
The planning and scheduling of a complex event could be further compounded in practice by many additional issues. Among them are the availability of candidate agents with respect to casting in its roles, disruption of occurrence due to failure of cast agent, subcontract and concurrent execution of its subsidiary events, critical path with respect to its minimum execution time, etc. Consequently its initial version based on the schematic knowledge is reified with respect to the particular agents cast in its associated roles and other initial conditions around. Thereafter, it is to be continuously revised according to its associated conditions including those agents’ states varying incessantly through its execution. In case any essential precondition turns out to be unsatisfiable along its execution, the plan may need to be rescheduled or can be judged as infeasible at any point during its execution.
The paper is organized as follows. Section 2 describes related works and contributions of this paper. Section 3 presents planning of an intentional event. From a schematic planning it is elaborated with respect to several associations among events and situations. Section 4 describes how a schematic plan is modified and augmented in its execution according to ever-changing internal and exogenous conditions on cast agents and background world. Potential disruption during its execution and additional issues are discussed with respect to the agents involved therein. Section 5 demonstrates and discusses the viability of our planning method through an implementation. Section 6 draws a conclusion with future research.
2. RELATED WORKS AND OUR CONTRIBUTIONS
To plan an event an agent first needs a representation model for the background world, goals and actions. Many feature-centric and action-centric models have been developed and applied to automatic planning [4], [6]. Those models are oriented to logical reasoning to find a plan to achieve a goal from a given state [41], while composite events with a hierarchical structure in practice cannot be properly modeled just in terms of fragmentary predicates in logic. In contrast we pursue a maximum diversity of situations by elaborating a plan with respect to its subsidiary events and associated agents. Our planning is characterized to be agent-centric in that the agents play the pivotal roles in elaboration of basic plans beyond a main event or story. Our agent’s composition is dichotomized into physical and mental parts. The physical part refers to the body or an actuator [42]. The mental part comprises sense, perception, emotion and social relationships [11] with belief (or knowledge) as its personal model of the background world [23]. This provides numerous internal and external factors by which the intention of an agent for an event could be diversified besides its basic driving forces [43]. Meanwhile, non-player characters (NPCs) have not generally been modeled in storytelling as independent agents unlike the player or lead character [44]. Those supporting agents are likely to be designed to act at best only reactively, and their personal conditions or belief are little considered in planning. Recently, the actors are generalized to include a few entities other than characters [35], and user model is used for implementing its proactivity [45]. We further these ideas by modeling an entity in general to have inherent (innate or acquired) capability of actions.
Compared to narrative worlds that usually are simplified in abstract forms or minimized in the forms of spatial configurations geared to serving as stage or environment for particular stories or behaviors in small domains [11], [14], [31], [5], [9], [10], [35], our full-blown virtual world, a sophisticated version of Working Memory [22], [40] is the central source of user experience as the common background stage for numerous events (or stories) to unfold in. To account for its complex nature the entire world is modeled in multiple layers, i.e., the reality composed of the physical and social worlds and thereover the conceptual worlds of its inhabitants or agents. An early agent model based on Time Tree with branching time future and a single past [23] lays down a formalism for virtual world model structured in many layers and facets. Rather than efficiency of its generation in constructing story world [14], [31], we pursue comprehensiveness and sophistication of the world composition. Specifically event in our simulation is roughly equivalent to plot point in [31], but world state specified in terms of NPCs, objects and places is generalized in our simulation into time-varying situation of entities and relationships. Still, our world model shares several basic elements with the problem domain definition in [10], only with some notable differences due to distinction in their target problem domains: such as relationships between entities being explicitly considered in our model as important elements of the domain or world as entities (roughly equivalent to objects and actors in [10]), and different agents having different conceptual worlds over the common background world (of reality.) Coupling between events through an autonomous and independent agent would have far-reaching implications not comparable with ones that coupling through an object (e.g., a diary or a key [10], [46]) might have. Their consequences would potentially reverberate as extensively as through the entire virtual world.
Whereas the development of narratives tends to be centered around the characters with other entities merely in supporting roles across character-based and plot-based storytelling [5], [37], [8], [44], [46], the other entities, e.g., props and organizations, are deemed not less significant elements than agents (or characters) in our planning either when those entities are linked with the agents or on their own, although believable agents [11], [26] being the key constituents of our realistic background world.
Once those independent agents have been cast into some event, they are likely to confront all the problems that are addressed by conventional planning methods in performing their roles within each of those events collectively comprising the world. In this respect, we can exploit diverse existing approaches, for example, to simulate interaction between agents or crowd of agents involved in an event [35], [36], [47]-[49] as the main mode for progression of multi-agent events [28] often identified in our planning. We expand the interaction patterns between agents from ones premised on spatial affinity [36] to include other types of relationships, for example, parties to a contract. As for allowing user intervention, existing techniques such as real-time search techniques [34] or replanning [9] are applicable to our model while it is beyond our present scope.
Whereas terminal actions in IS and other computer-simulated systems [8], [13], [14], [46] are those actions to be animated in the presentation, the action as an atomic element of events along with the other element of collision in our planning refers to an inherent function of an entity regardless of its animation. That is, an action is a function that its ‘host’ agent is capable of performing only with her inherent parts (e.g., walk) or a phenomenon whose procedure and effect is confined within its ‘host’ entity (e.g., burn.) Notice that ‘go to phone’ (a terminal action from [46]) for example, would be regarded as an event to be performed by means of (the action of) ‘walk’ in our planning. While an action in a parameterized behavior tree (PBT) [33] is roughly equivalent to an action (sometimes a motion) in our model, our action is only potentiality with no substance in reality until instantiated in terms of duration or the number of iterations to form a primitive event with a concrete temporal span. Note the timing of elements is essential information for reifying into a schedule a schematic plan that has been obtained from the front phase of planning. For realistic simulation of detailed scenes, the solutions to ‘bottom-up’ situations under their top-down planner [36] are applicable to our approach (though those solutions are largely subsumed by autonomy nature of our agents [32], [43]) despite wide difference in ultimate objective, entertainment vs experience. Each action being executed in our simulation is instantiated incrementally (or tentatively [14]) in its associated historical context, and is continued or iterated according to the plan along the progression of the occurrence.
In a technical perspective our vertical planning is a recursive decomposition process generating a hierarchically organized plan of events sequenced in partial order, whose representation is framed on an AND/OR graph similar to Hierarchical Task Network (HTN) [44], [46], [50]. A major difference of our vertical planning from HTN-based planning is that the primitive actions in our planning refer to performance of an entity’s innate capabilities instead of playable actions [8]. Another difference is that the durations of the identified events are further depicted on the timeline (i.e., a plan being elaborated to a schedule) [51] enabling their executability to be judged with respect to their associated agents’ temporal availability [47].
The combinatorial optimization approach and the plot adaptation algorithm [14], [31] also are candidate approaches to selection of the best quality plans and to personify objective (or neutral) plans generated in the early stage of our macro-level planning. Branching in bridge [31] could be adopted for our planning to implement the optional precondition for executing events. While degree of real-time constraint varies depending on the application areas [13], [15], [35], it is partially applicable to our simulation. In parts of our planning where real-time performance are required we could adapt relevant approaches developed in IS, ITS and other story-based systems with stringent time constraints [5], [9], [10], [14], [35].
The aspects in which the planner is interested, of props or roles other than the protagonist, e.g., roses or a flower pot [46] [33], are usually confined to those directly relevant to the main story plot, e.g., (existence of) roses or price of pot. In contrast any of their general aspects is a potential source of a new event in our planning, which could lead the story to digress off the main plot (though no digression in our perspective), e.g., the flower pot might turn out to be a smuggled antique treasure prompting (a complicated event of) police investigation to proceed in parallel with or in place of the main event. While side-quests or digressions may well be strictly restricted or supported externally to main storyline in [31], [46], our planning not only regards those side storylines as an inherent part of a plan due to branching via causality or the other (real-life) association types but also exploits them as another path to promote play affordance (or narrative interests) of the simulated world all the stories unfold in. As a consequence, a (main) goal in our planning is not fixed but variable according to how the situation progresses, to be exact the conventional concept of main goal or event being inapplicable to, or to be modified for, our model. In effect, a narrative goal is no more than a ‘square one’ or ‘flash point’ providing a clue for planning of relevant events. Incidentally, a domain by which a goal (or the precondition and postcondition) of an event can be specified is formed by all the possible situations in the world, which is a generalization of goal specification in [10]. Further generalization is possible in terms of its procedure [28] and other aspects [43] beyond mandatory execution of event [10].
While most narrative systems apply causality to identify what events might subsequently be started as a result of executing an event [8], [14], [17] and goal-directed search is often used in planning for parts of a plot [8], [10], [46], narrative causality between actions or events is not precisely specified. Our planning formalizes both backward and forward usages of causality to find the prerequisite events and the ensuing events, respectively. We further elaborate on the association via causality with respect to entities and relationships as condition parameters for event occurrences.
In most interactive narratives, actions are uninterruptible or atomic [20] and their sequential order with respect to their entireties is the only way they are related to each other. Coupling between actions is rationalized by parameterizing behavior tree [33], mainly for code reuse in the context of a single event rather than interplay between independent events. While integration of independent behaviors of characters is considered in case of their spatial affinity [36], our model monitors and considers assorted spatial relationships among entities beyond spatial affinity [52]. In reference to the simplifying assumptions [20] our planning can be evaluated with respect to its practicality, for example, the atomic time assumption is lifted, i.e., concurrent execution of actions is allowed [51] execution of an action is rendered interruptible; and its intermediate states are made visible and of concern to the planner. Consequently the roles progressing any event in our model are played by entities that happen to be cast from the background world instead of entities that are prepared specifically for particular event as in typical narrative systems. (Notice those agents cast in the roles preexist in the background world independently of those roles.) As a natural consequence, those background entities function as junctions for coupling events that are previously independent into events that concurrently interact in an intertwined manner via individual entities cast in multiple roles (or props) across those concurrent events.
Unlike in typical interactive narratives [8], [37] story plot in our system is not strictly controlled in a global perspective, but dynamically controlled (with no fixed global goal other than initial goal) as long as it is not detrimental to overall pedagogical objective. That is, plot control could be transferred onto another overarching event into which the story progresses (i.e., digresses) from the currently main event according to the user’s choice or pedagogical needs. To enhance play affordance, narrative interests such as failure of plan [23] and competing plans [8] are further augmented by additional aspects like inexistence (constituting absence, nonfeasance, avoidance, etc.) of entities, relationships or occurrences [23], [29], [36].
Contributions: We propose a two-level event planning, in a macro-level (i.e., inter-event level) and in an intra-event level, for providing pedagogical experiences with an objective of learning declarative knowledge, which is different from ones many conventional planning methods attempt to pursue. Rather than events following a main story plot, all the events potentially relevant to accomplishing an initial goal are derived in planning. Coupling between independent events is based on an agent’s multitude of roles (or props) across concurrent events. These events in a plan may progress concurrently or digress toward a new main goal replacing the current goal or event, and the plan could be merged or fragmented according to their respective lead agents’ intentions. As the pivotal source of event concurrency and intricacy the agents are modeled as not just autonomous but independent types, i.e., entities with their own beliefs and goals (and subsequent plans) in their respective parts of world.
Events in our model are integrated as parts of the unifying background world and conversely they collectively form the world. All the relationships including event occurrences are coupled with each other via their preexisting common background world. A full-blown virtual world is the central source of user experience as the common background stage for numerous concurring events to unfold in. For a precise description of its complexity and intricacy of events therein, the entire world is modeled in terms of entities and their interrelationships in multiple layers in a historical (time-varying) context. Coherency among events (loosely coupled by entities) is established via their common background world, which is contrast to pre-authored scenario prescribing intra-event coherency [8].
Our planning method proposes additional types of association between events besides the conventional causality. The association via causality is formalized in both directions, i.e., from causing event to affected event, and from requiring event to satisfying event, and further elaborated with respect to entities and relationships as condition parameters for event occurrences. In a social event, a regular order of its subsidiary events is dictated by the normative procedure type of association. The deontic type of association is specified between a pair of events with no regard to an overarching event.
By complete separation of roles from candidate agents our planning is expanded to include, as an integral part a plan, a potentially lengthy and complicated event of casting in terms of availability of agents, subcontracting etc. In addition, abnormal termination of plan execution due to unforeseen changes in agents’ individual conditions is formulated with respect to fragmented sub-plans.
3. PLANNING OF INTENTIONAL EVENT
Our event planning is conducted in two dimensions, horizontal and vertical, toward a given goal. The horizontal planning is an inter-event process based on search, while the vertical planning is an intra-event process based on hierarchical decomposition. In a horizontal planning phase, the world knowledge of a lead agent is searched via the four association types for all the events relevant to achieving an initial goal set by that agent. Each event that has been identified in this horizontal planning phase is recursively decomposed until all the resulting subsidiary events reduce to the primitive events of actions. Meanwhile, each of these derived events in any planning phase is subject to another general planning instance with that event as the initial event. To sum up, the resulting plan comprises derived events in addition to the main event identified for the initial goal, forming a graph of events interconnected via their common condition factors or other types of inter-event association. The horizontal planning in practice cannot be completed until its corresponding vertical planning is completed, and vice versa, unless the agent (unrealistically) has perfect knowledge of the event under planning. In effect these two phases of planning proceed in an interleaved manner [53] or the drawn plan may subject to proper modifications for elaborations or corrections.
By the execution time, any event in the plan eventually is to be decomposed and prepared in terms of the actions (and collisions.) The action plays a role analogous to a (primitive) action or operator described in domain theory in generative planning [20]. Those actions include agents’ inborn faculties and acquired motions (e.g., human’s smell and infant’s toddle), machine’s facility (e.g., run of automobile), and phenomena on substances (e.g., rust of iron.) Their actual occurrences (of the action type) are realized in terms of its iteration or continuation. Of various action types we focus on agents’ actions, which may involve tools, or merely trigger a phenomenon as a whole. An event in general refers to an activity that involves multiple agents assuming their respective roles therein. Each such role is designated to perform one or more actions for the event. An event is eventually carried out by performing those actions required of the agents cast in its associated roles. An action-type occurrence in effect constitutes a primitive event. Those action occurrences are to be properly arranged into a plan with respect to their global goal. This (initial) schematic plan derived through the two phases of planning is to be further elaborated in terms of quantitative aspects against relevant world states. These aspects include the existential properties of amount and count, the spatial relationships of location, and the spatio-temporal parameters of speed, duration, etc. as formalized in spatio-temporal space. In particular durations of occurrences are formulated in terms of duration along the timeline.
An instance of planning is initiated only if, given a goal, the lead agent is already aware of an event suitable for achieving the goal with respect to at least its effect and precondition. Unless the event is routine, generative planning [20] is to be performed from the goal. The vertical planning is based on case-based search, while the horizontal planning is based on generative search against its associated ontology [54]. The routine events range widely in their extent and nature according to knowledge and experience of the planner, e.g., from inborn ability of cry to acquired social activity of purchase. The routine events or actions identified as relevant plan fragments in case-based search are assembled (after necessary revisions [55]) into the main plan.
3.1 Schematic planning for events
A part of the background world relevant to an example situation is schematically described as follows. It is composed basically of entities (including human instances), relationships and events. The actions as primitive elements of event occurrences are specified on their associated entities. Linkage between events are indicated if they are in association with each other, such as deontic (below denoted by |→) and customary (by →). To briefly introduce some notations, the concept preceding entity instances grouped in [ ] denotes entity class, bold-type and underline for entities indicate system and region, respectively; name() denotes action and event with ‘;’ delimiting its parts; < > inside an event delimit its procedure part, and | partitions alternative path set, and roles (and props) are indicated by Italic type; { } enclose action set of entity class or instance; ≪≫ denotes action occurrence.
Though agent’s epistemic aspect in planning is a significant issue with respect to incomplete information, partial observability, etc. [5], [44], [45] we here take an omniscient view on the agents’ world knowledge. Against this background world, (schematic) events are instantiated into historical occurrences advancing the world forward. In general, some of alternative solutions toward a given goal are immediately executable under the current condition and the others require additional events (mere waiting considered an event as well) to be performed to satisfy their preconditions. When appointed to go to a place, for example, alternative procedures (each comprising events) might be evaluated to select the best one based on conditions and traits. That is, between taking metro (still may need walk to a station as a premise) or driving to the appointed place depending on, say, time constraint and disposition on walking.
A goal is a situation an agent intends to be in to fulfill her wish or obligation. The goal situation could be one that is newly created or preserved as it is. Unless such a goal is satisfied with the given conditions some event needs to be performed against the given condition in order to achieve the goal. Such an event in general is complex enough to demand a deliberate planning with smaller events selected by its agent. Initially a plan is drawn up based on a schematic knowledge. Specifically a schematic planning proceeds along several threads of reasoning, vertical and horizontal, via diverse candidate paths possible in a graph of events as illustrated in Fig. 1. The relevant events are successively identified starting from an event able to immediately satisfy the goal as exemplified by a sequence ③→②→① for a goal (situation) SG in Fig. 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 available events or their composites until the Precondition of each event so far identified can be fully satisfied exclusively with the given background conditions [40], [56]. Once identified in the horizontal planning, each selected event is vertically analyzed with respect to its hierarchical composition. An identified event may require other events to be added to the plan according to their association (to be detailed in 2.3.) For example, the original event A2 is premised on A1 indirectly through background conditions as led by ③&② chain, and legally entails A3 following link ④ as illustrated in Fig. 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 and their order is accordingly determined, 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. The resulting plan would be arranged to form a partially ordered set of events, denoted by Πk(Ak), with the ‘last’ event (one with its Effect ⊇ goal) as the only greatest element [56].
Fig. 1.Different threads of reasoning for schematic planning
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 action [56].
(Procedure of) an event in general, A, could be formulated as,
A() ::= ≪ai≫ | Π{≪ ai ≫, A}, where denotes a schematic action, ≪≫ indicates the repetition or continuation, and Π{} denotes a partially-ordered set with respect to ’precedes’ [56]
Definition
For Ai, Aj , Ak∈{Event}, Ai precedes Aj if partially satisfies and Ai precedes Ak if Ai precedes Aj and Aj precedes Ak.
Theorem
The precedence between events in the plan is a partially ordered relation.
proof)
Let T(A)=t1, T(B)=t2, T(C)=t3, where T(x) denotes the occurrence time of event x.
reflexivity: (The definition is extended from < to ≤ to include A precedes A.)
References
- E. Ohmaye, Simulation-based language learning, Northwestern Univ., Ph.D dissertation, 1992.
- J. Murray and S Malone, "The structure of advanced multimedia learning environments: Reconfiguring space, time story, and text," ITS '92, Montreal, Canada, 1992.
- C. Miller, J. Lehman, and K. Koedinger, “Goals and learning in microworlds,” Cognitive Science, vol. 23, no. 3, 1999, pp. 305-336. https://doi.org/10.1207/s15516709cog2303_2
- R. E. Fikes and N. J. Nilsson, “STRIPS: A new approach to the application of theorem proving to problem solving,” Artificial Intelligence, vol. 2, no. 3-4, 1971, pp. 189-208. https://doi.org/10.1016/0004-3702(71)90010-5
- M. Georgeff and A. Lansky, "Reactive reasoning and planning," Proc. 6th Nat'l Conf. on Artificial Intelligence, Seattle, WA, 1987.
- D. Nau, “Current trends in automated planning,” AI Magazine, vol. 28, no. 4, 2007, pp. 43-58.
- K. Erol, Hierarchical Task Network Planning: Formalization, Analysis, and Implementation, Dissertation, Univ. of Maryland, 1996.
- F. Charles, M. Lozano, S. J. Mead, A. F. Bisquerra, and M. Cavazzal, "Planning formalisms and authoring in interactive storytelling," Proceedings of TIDSE. vol. 3. 2003.
- J. Porteous, M. O. Cavazza, and F. Charles, “Applying planning to interactive storytelling: Narrative control using state constraints,” ACM Trans. on Intelligent Systems and Technology, vol. 1, no.2, Nov. 2010. https://doi.org/10.1145/1869397.1869399
- A. Shoulson, M. Gilbert, M. Kapadia, and N. Badler, "An Event-Centric Planning Approach for Dynamic Real-Time Narrative," MIG '13, Dublin, Ireland, Nov. 2013.
- J. Bates, B. Loyall, and W. Reilly, "An architecture for action, emotion, and social behavior," Lecture Notes in Computer Science, Vol. 830, 1994, pp. 55-68.
- W. Johnson, J. Rickel, and J. Lester, “Animated pedagogical agents: Face-to-face interaction in interactive learning environments,” International Journal of Artificial Intelligence in Education, vol. 11, 2000, pp.47-78.
- S. Marsella, W. Johnson and C. LaBore, "Interactive pedagogical drama for health interventions," Proc. of AIED 2003, Australia, 2003.
- A. Zook, S. Lee-Urban, M. O. Riedl, H. K. Holden, R. A. Sottilare, and K. W. Brawner, "Automated scenario generation: toward tailored and optimized military training in virtual environments," Proceedings of the International Conference on the Foundations of Digital Games, ACM, 2012.
- K. Koedinger, "Intelligent cognitive tutors as modeling tool and instructional model," Invited paper for the National Council of Teachers of Mathematics Standards 2000 Technology Conference, 1998.
- L. Amaral and D. Meurers, “From recording linguistic competence to supporting inferences about language acquisition in context,” Computer Assisted Language Learning, vol. 21, no. 4, 2008, pp. 323-338. https://doi.org/10.1080/09588220802343454
- W. Swartout, R. Hill, J. Gratch, W. L. Johnson, C. Kyriakakis, C. LaBore, R. Lindheim, S. Marsella, D. Miraglia, B. Moore, J. Morie, J. Rickel, M. ThiÚbaux, L. Tuch, R. Whitney, and J. Douglas, "Toward the Holodeck:Integrating graphics, sound, character and story," Int'l Conf. on Autonomous Agents, 2001.
- M. Riedl and R. Young, "The Importance of Narrative as an Affective Instructional Strategy," In R. Sottilare, A. Graesser, X. Hu, and B. Goldberg (Eds.), Design Recommendations for Adaptive Intelligent Tutoring Systems: Adaptive Instructional Strategies, vol. 2. Army Science Laboratory, 2014.
- R. Reiter, "The Situation Calculus Ontology," Electronic News Journal on Reasoning about Actions and Change, vol. 2, 1998.
- D. Weld, “An Introduction to Least Commitment Planning,” AI Magazine, vol. 15, no. 4, 1994.
- M. Georgeff and A. Lansky, "Procedural knowledge," Proceedings of the IEEE Special Issue on Knowledge Representation, vol. 74, 1986, pp. 1383-1398.
- J. Park, Formalization of Cyber-Microcosm, Tech. Report #99, AIMM Lab., KNU, 2013.
- A. Rao and M. Georgeff, "Modeling rational agents within a BDI Architecture," Proc. Of the 2nd International Conf. on Principles of Knowledge Representation and Reasoning, 1991, pp. 473-484.
- M. Wooldridge, Reasoning about Rational Agents, MIT Press, Cambridge, MA, 2000.
- W. Hoek and M. Wooldridge, Towards a logic of rational agency, Logic Journal of IGPL, vol. 11, no.2, Oxford Univ. Press, 2003, pp. 133-157. https://doi.org/10.1093/jigpal/11.2.133
- Mark O. Riedl and A. Stern, “Believable agents and intelligent story adaptation for interactive storytelling,” Technologies for Interactive Digital Storytelling and Entertainment, Springer Berlin Heidelberg, 2006, pp. 1-12.
- G. J. Burghouts, D. K. J. Heylen, M. Poel, Rieks op den Akker, and A. Nijholt, "An Action Selection Architecture for an Emotional Agent," In: Recent Advances in Artificial Intelligence. Proc. of the 16th International FLAIRS, St. Augustine, Florida, 12-14 May 2003.
- M. Riedl and R. Young, "An Intent-driven planner for multi-agent story generation," Proc. of the 3rd Int'l Joint Conf. on Autonomous Agents and Multi-agent Systems, 2004.
- M. Bratman, Intention, plans and practical reason, Harvard University Press: Cambridge, MA, 1987.
- J. Gibson, "The Theory of affordances," In R. Shaw and J. Bransford (eds.), Perceiving, Acting, and Knowing: Toward an Ecological Psychology, Hillsdale, NJ: Lawrence Erlbaum, 1977, pp. 67-82.
- K. Hartsook, A. Zook, S. Das, and M. Riedl, “Toward supporting stories with procedurally generated game worlds,” Proceedings of the 2011 IEEE Conference on Computational Intelligence in Games.
- J. Choi and J. Park, "An Effective implementation of agent's complex actions by reusing primitive motions," Proc. of Simultech, Vienna, Austria, Aug. 2014.
- A. Shoulson, F. Garcia, M. Jones, R. Mead, and N. Badler, “Parameterizing Behavior Trees,” In Motion In Games, Springer, 2011, pp. 144-155.
- D. Pizzi, F. Charles, J. Lugrin, and M. Cavazza, Interactive Storytelling with Literary.
- M. Kapadia, S. Singh, G. Reinman, and P. Faloutsos, “A behavior-authoring framework for multiactor simulations,” Computer Graphics and Applications, vol. 31, no. 6, 2011, pp. 45-55. https://doi.org/10.1109/MCG.2011.68
- M. Cavazza, F. Charles, and S. J. Mead, "Emergentsituations in interactive storytelling," Proc. of ACM Symposium on Applied Computing (ACM-SAC), Madrid, Spain, 2002.
- N. Sgouros, G. Papakonstantinou, and P. Tsanakas, "A Framework for plot control in interactive story systems," Proc. AAAI-96, AAAI Press, 1996.
- J. M. Niehaus, B. Li, and M. O. Riedl, "Automated Scenario Adaptation in Support of Intelligent Tutoring Systems," Proc. Of 24th FLAIRS Conference, 2011.
- N. Nilsson, Principles of artificial intelligence, Tioga Pub. Co., Palo Alto, CA. USA, 1980.
- P. Winston, Artificial Intelligence, Addison-Wesley, Reading, MA, USA, 1992, pp. 119-161.
- D. Poole and A. Mackworth, Artificial Intelligence: Foundations of Computational Agents, Cambridge University Press, 2010, pp. 349-355.
- R. Siegwart, I. R. Nourbakhsh, and D. Scaramuzza, Introduction to Autonomous Mobile Robots, 2nd edition, The MIT Press, Cambridge, MA, London, England, 2011.
- J. Park, Augmented model of behavioral occurrence, Tech. Report #72, AIMM Lab., KNU, 2009.
- J. Kelly, A. Botea, and S. Koenig, "Offline Planning with Hierarchical Task Networks in Video Games," Proceedings of the Fourth Artificial Intelligence and Interactive Digital Entertainment Conference, Palo Alto, CA, 2008.
- M. Si, S. Marsella, and D. Pynadath, "Evaluating directorial control in a character-centric interactive narrative framework," Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems, vol. 1, 2010, pp. 1289-1296.
- M. Cavazza, F. Charles, and S. Mead, "Interacting with virtual characters in interactive storytelling," ACM Joint Conference on Autonomous Agents and Multi-Agent Systems, Bologna, Italy, 2002, pp. 318-325.
- F. Charles, J. Porteous, M. Cavazza, and J. Teutenberg, "Timeline-based navigation for interactive narratives," Proceedings of the 8th International Conference on Advances in Computer Entertainment Technology, ACE 2011, Lisbon, Portugal, Nov. 8-11, 2011.
- El Mokhtar En-Naimi, Abdelhamid Zouhair, Benaissa Amami, Hadhoum Boukachour, Patrick Person, and Cyrille Bertelle, “Intelligent Tutoring Systems Based on the Multi-Agent Systems (ITS-MAS): The Dynamic and Incremental Case Based Reasoning (DICBR) Paradigm and the Inverse Longest Common Sub-Sequence (ILCSS) in the CEHL,” IJCSI International Journal of Computer Science Issues, vol. 9, issue. 6, no. 3, Nov. 2012.
- A. Shoulson, N. Marshak, M. Kapadia, and N. Badler, “ADAPT: the agent development and prototyping testbed,” Proceedings of the ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games 2013.
- R. Tsuneto, D. Nau, and J. Hendler, "Plan-refinement strategies and search-space size," Proceedings of the 4th European Conference on Planning: Recent Advances in AI Planning, 1997, pp. 414-426.
- H. Gebre and J. Park, "A Knowledge Representation Scheme Formalizing Spatio-Temporal Aspects of Dynamic Situations in the Virtual Environment," to appear in Journal of KCA, 2015.
- G. Jung and J. Park, “An Implementation of Spatio-Temporal Graph to represent situations in the virtual world,” Journal of KCA, vol. 13, no. 6, 2013, pp. 9-19
- E. Durfee and V. Lesser, "Incremental planning to control a blackboard-based problem solver," Proceedings of theFifth National Conference on Artificial Intelligence, Philadelphia, PA, 1986, pp. 58-646.
- J. Park, The Ontology about the Cyber-Microcosm, Tech. Report #55, AIMM Lab., KNU, 2004.
- A. Aamodt and E. Plaza, “Case-based reasoning: foundational issues, methodological variations, and system approaches,” Artificial Intelligence Communications, vol. 7, no. 1, 1994, pp. 39-52.
- S. Epp, Discrete Mathematics with Applications, Wadsworth, Inc. Belmont, CA, USA, 1990, pp. 294-295.
- I. Kim and J. H. Park, “Logical Simulation Platform of Discretionary Events in Spatio-Temporal Context,” Journal of KIISE, vol. 29. no. 6, 2002, pp. 377-385.
- J. Gruber, Lexical structure in syntax and semantics, North Holland Pub., New York, 1976.
- W. Frawley, Linguistic Semantics, Lawrence Erlbaum Associates, Hillsdale, NJ, 1992, pp. 197-249.
- B. Davey and H. Priestley, "Maps between ordered sets," Introduction to Lattices and Order (2nd ed.), New York: Cambridge University Press, 2002, pp. 23-24.
- N. Hiralla, B. Falchuk, and A. Karmouch, “A Temporal model for interactive multimedia scenarios”, IEEE Multimedia, vol.2, no. 3, 1995, pp. 24-31. https://doi.org/10.1109/93.410508
- C. Date, An Introduction to Database Systems, 7th ed., Addison-Wesley Pub. Co., Reading, MA, 2000.