Advanced
A Knowledge Representation Scheme Formalizing Spatio-Temporal Aspects of Dynamic Situations in Virtual Environments
A Knowledge Representation Scheme Formalizing Spatio-Temporal Aspects of Dynamic Situations in Virtual Environments
International Journal of Contents. 2015. Mar, 11(1): 21-30
Copyright © 2015, The Korea Contents Association
  • Received : October 06, 2014
  • Accepted : December 19, 2014
  • Published : March 28, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Haymanot Alalo Gebre
Jun Seong Choi
Jong Hee Park
jhpark@ee.knu.ac.kr

Abstract
A simulated realistic virtual environment is inhabited by autonomous cyber-humans who play the roles of agents in events. A key element, which enables this realism, is the historical context formed by time and space. A knowledge-representation scheme, composed of both spatial and temporal aspects needed by the agent to respond to dynamically changing situations, is essential for the design of a realistic virtual agent. In this work, spatial and temporal aspects of dynamic situations in the virtual environment have been formalized as a key component of our knowledge-representation scheme. This scheme provides a mathematical framework to construct realistic virtual situations that change with time, and background knowledge for agents in the simulated environment to deduce new pieces of information and plan against changing situations.
Keywords
1. INTRODUCTION
The effectiveness of situated learning is proportional to the authenticity and diversity of the simulated virtual environment, where situations take place. A key element of a simulation platform needed to maximize those two natures is the historical contexts for the situations therein. The historical context at the intersection of the time and space is by nature multi-dimensional, multi-layered and highly complicated. Further a situation tends to involve a number of agents with their respective perspectives as well as numerous interrelated objects and concepts. In order to effectively handle these multitude and complexity and at the same time to accommodate diverse perspectives we devise mathematical framework and knowledge representation schemes for spatiotemporal aspects of the dynamic situations in the simulated virtual environment. This knowledge representation scheme is to be used as the basis for simulation of situations composing the virtual environment and for implementation of virtual agents' knowledge used to judge and evaluate the situations in the virtual environment. The spatial aspects are described in terms of a layered abstraction of diverse spatial relations elaborated by physics. The temporal aspects are organized in a complex hierarchy to reflect many-tiered viewpoints, which are supported by a logical zooming capability for intuitive perception [1] .
In our cyber-cosmos, a realistic virtual environment is inhabited by autonomous cyber-humans who play the agent roles in diverse intentional events. By realistic simulation of an environment we do not mean its visual realism but its orderliness. That is, it is dictated by natural laws on gravity, inertia, friction, etc. [2] . A key element that enables such a simulation is the historical context the time and the space together form, which all the situations are based on. A physical object in this environment occupies some range of a space provided by another object, which in turn occupies some space of yet another object, etc. in a hierarchical fashion. Meanwhile, those peer objects close to or contacting each other may be linked via diverse spatial interrelations. Those spatial relations could affect a situation in terms of not just its physical aspects but also of its social aspects indirectly through its associated agents. Pairing with the space, the time constitutes the other coordinate of the spatiotemporal base for historical context [3] . The temporal aspects of a situation are also hierarchically modeled from its resident cyber-humans’ perspectives in a conceptual world on top of the real world. Those temporal aspects are immensely expanded with respect to planning or projecting into the future along with its agents’ memory on a remote past. After it has been acquired by an agent the spatiotemporal knowledge enables the agent to understand a situation in a historical context and adaptively react to it [4] . The existing reactive types of agents have limited capability in handling diverse situations [5] , [6] , require a vast amount of memory in case of complex situations, and an unrealistic foresight to prepare a proper reaction to every possible situation [4] .
The spatiotemporal knowledge needed by an agent to behave adaptively to changing environments is composed of the spatial and the temporal aspects. In the spatial aspects, it includes spatial configurations of its peer physical objects sharing the same space and their spatial interrelations. Their temporal aspects are the other dimension to be grasped for the agent to be able to project or plan ahead against changing situations. We develop a mechanism by which autonomous agents could properly react to the spatial aspects of changing environments. Specifically, perceived spatial information is to be abstracted into knowledge and the agents are designed to be capable of using the abstract knowledge to adaptively act against changing situations. Towards this goal, we formalize spatiotemporal aspects of occurrences as a basis for the construction of realistic virtual situations with dynamic features and as a knowledge representation scheme by which autonomous agents in the simulated environment could properly react to the changing situations. To make things more concrete, we introduce a motivating example of agents involved in theft crime, which will be used throughout the presentation. This simple scenario involves numerous intertwined aspects, which encompass not only the spatial aspects related to the procedure breaking in the house and taking a valuable out, but the social concepts like family, ownership and crime and also the mental concepts like desire and intention [7] . We here focus on the spatiotemporal aspects that are readily perceptible among many aspects of the example situation.
We enhanced the existing Situation Calculus to represent dynamic situations with our specific scenario in terms of time and space. In this work we improved the conventional Situation Calculus by adding the temporal and spatial aspects of situations to represent and reason about actions.
This paper is composed of the following sections. Section 1 is a general introduction. In Section 2 we introduce related research areas. Section 3 presents how to place events in the historical context and explains spatial and temporal relations between objects along with their relevant physics. Section 4 describes how to represent events in the enhanced Situation Calculus by using the example scenario presented in Section 1. Section 5 depicts an implementation of the example situation based on the theories presented in the previous sections. The final section concludes this study.
2. RELATED RESEARCH
- 2.1 Ontology
Since the existing ontologies have been used mainly for capturing hierarchy or relations among concepts in specific application domains, they have been specialized to suit the purpose of knowledge sharing or reuse [8] .We specialize the general ontology with a purpose to provide a general foundation of knowledge structure for controlling the agents’ actions and their reasoning in a cyber-environment similarly to the humans in the reality. To serve this purpose our ontology should cover the entire spectrum of knowledge as humans know. That is, it sets out with Concept as the root node, and specializes into Entities, Relationships, Activities and Pure Concepts on the next level, each of which in turn is recursively broken down to a number of levels [3] . These numerous concepts have their respective compositions so their structures as well as their semantics need to be individually examined in order to be implemented into the virtual environment.
- 2.2 Spatial Relation Models in GIS
The 4-Intersection Model and its extended version of 9-Intersection Model are among the models to describe the topological relations between two objects in GIS [9] . The 4-Intersection Model represents an object in terms of its boundary and interior, while 9-Intersection Model added its exterior to those two parameters. To process the GIS queries about spatial concepts, Intersection Model defines the topological spatial relations applicable to diverse spatial relations between two objects in terms of the operators on the point sets. The entire set of relations consists of 16 kinds and those between two regions of 9 kinds. However, 4-Intersection Model allows only the topological elements of such spatial relations to be recognized.
- 2.3 Spatio-Temporal Database
Spatio-Temporal data is a special data type that records spatial changes of objects moving along the time, such as cellphone user data, traffic data and typhoon data. Among the representative Spatio-Temporal database, SOLAP (Spatial OnLine Analytical Processing) has an advantage of being describable in both maps and diagrams [5] . However it can handle only limited kinds of actions, and cannot express the meanings of temporal changes.
- 2.4 Situation Calculus
The Situation Calculus is a first-order logical language for specifying and reasoning about dynamical systems [10] . The basic concepts in Situation Calculus are Situations, Actions and Fluents. Actions are what make the dynamic world change from one situation to another when performed by agents. Fluents are situation-dependent functions used to describe the effects of actions. A Situation is the same as its history which is the finite sequence of actions that has been performed since the initial situation. The unique feature of Situation Calculus is that situations are first-order objects that can be quantified over. This is what makes Situation Calculus a powerful formalism for representing change. Though Situation Calculus can model temporal changes, it is not concerned with spatial aspects the other coordinate of the historical context.
- 2.5 Event Calculus
The Event Calculus is a logical language for representing and reasoning about events and their effects [11] . It models how the truth value of relations changes because of events occurring at certain times. Events are modeled as occurring at particular times. Time can be modeled as either continuous or discrete. The fluents are reified, that is, they are not formalized by means of predicates but by means of functions. The Event Calculus has a world view which differs in some aspects from the Situation Calculus view. In Event Calculus there is one real line of time points. Properties can hold or not hold at a certain time point [12] . Event Calculus like Situation Calculus does not considers the space as a structural factor unlike the time.
3. SPATIOTEMPORAL REPRESENTATION OF HISTORICAL CONTEXT
- 3.1 Spatiotemporal Graph (STG)
An event has its real meaning only in a historical context as far as humans are concerned. To place events in historical contexts we need the spatiotemporal space where they could be bound as shown in Fig. 1 . Such a space should also provide diverse perspectives from different people [13] . Spatiotemporal history can be specified into a set of successive states. Set ε of states is composed by possible state values ( s 0 , s 1 ... sf ).
PPT Slide
Lager Image
3-D temporal space
When an Object is instantiated into the virtual environment it is assigned a location and a spatial range. To mimic human conception of spatial relations among those Objects, their relative spatial positions in terms of distance, direction and orientation is modeled based on their respective locations in a space as shown in Fig. 2 [14] .
PPT Slide
Lager Image
Combined description of location, distance and direction
Collocation is a premise any occurrence can happen. This premise for the historical contexts of possible situations can be formalized into agent behavior as follows. We employ a robbery scenario as our running example situation. The overall scenario is described as: at the start the owner ( h 1 ) is in his house ( H 1 ) where the safe with valuables is kept, while the thief ( h 2 ) in house ( H 2 ) waits for the owner to leave. Then h 1 left in his car and h 2 breaks into his house and brings a valuable (safe) out.
Navigation : the movement of an agent from one location to another.
PPT Slide
Lager Image
Situation 1 – Theft
The collocation of the thief and the target object (a safe) in a very near distance in the absence of the owner is the appropriate situation for the theft to happen. An agent cannot carry out the action of picking up the target object unless it is near the object.
If((is_present(x, y, t, Thief)) ˄ (is_present(x, y, t, Safe)) ˄
D((Near)) ˄ (¬(is_present(x, y, t, Owner)) ˄ D(Far)) ⇒
Theft(), where x and y stands for the location and t denotes time.
Situation 2 – Detection
PPT Slide
Lager Image
Detection scope depends on the agent’s vision which refers to how agents perceive the objects in front of them. An agent has a limited range of vision and the perceivable information depends on the spatial distance from the agent to the target object, and also the brightness of the environment and relevant colors.
Luminance as a function of light is a major physical concept to be considered and it can be computed as the luminous intensity per unit area of light travelling in a given direction. In our running situation, an agent with bright-colored clothing would be more discernible than the one with dim-colored.
For a target object O, Perception P(O) = f(d, v) where d denotes the distance between the agent and objectand v denotes the visual capability of the agent. Vision determines the spatial distance within which the agent can differentiate an object.
Situation 3- Grabbing
For the thief to be grabbed, the owner has to be in a grabbing distance from which he could reach him with hands. Since the physical arm’s reach is confined to a small space around the agent’s body, a navigation capability (action) is often required for the agent to move to a position where the thief is close enough to be grabbed. Navigation may be required in order to secure different visual perspectives.
The grabbing distance G(O) = f(d, h), where O denotes the target object, d denotes distance between the agents and h denotes the hand position.
PPT Slide
Lager Image
3.1.1 Representation of actions and events in STG : An event is specified on the STG in terms of three parts: Precondition, Procedure and Effect [15] . The temporal development of an event constitutes an elementary but comprehensive component of a situation. Such an event starts if its Precondition is satisfied, but its subsequent Procedure could ramify to different directions according to the given conditions. The basic frame of an activity (i.e., action or event) is specified as an activity class in the ontology as shown in Fig. 3 (a). An activity class provides the common properties by which we could substantiate its past and present occurrences or project its future occurrences. An occurrence attains its existence in the historical context if an activity class is selected and instantiated in terms of specific attribute values associated with the cyber-objects playing a role therein. As shown in Fig. 3 (b) the events correspond to the oval nodes in the STG, sequenced according to their time of occurrence. That is, the past and future occurrences each are positioned left and right to the ever-advancing present time as the reference. Their effects are accumulated in the STG and IG (Instance Graph) with respect to the attribute values of their relevant instances. Those values are used to determine the existence and states of the instances. Using these pieces of knowledge collectively the cyber-agents perceive, evaluate and judge the situations synthetically and multi-dimensionally in a historical context.
PPT Slide
Lager Image
Modeling of historical occurences in ST Graph
- 3.2 Spatial relations
3.2.1 Space object and relations between objects : The space object refers to a space surrounding the agents. All the spaces except the universe are derived spaces from physical objects. An object provides its external and internal spaces. Those spaces may be occupied by other objects and those residing objects also provide their shares of spaces, and so on. The primary space all human objects reside on is part of the earth’s surface, and the space a family resides in is the inner space provided by a house object. Those Derived Space Objects form different environments according to their characteristics, and the inclusion relations among them are exploited to organize them in a layered structure [14] .
Relations between space and object : If the spatial region of an Object is included in that of a Space, i.e., S⊃P, the Object is IN the Space, i.e., IN(P,S). Otherwise it is OUT. This inclusion relation is transitive, so if, given Object P and Space S1 and S2 as shown in Fig. 4 , S2⊃P & S1⊃S2 then S1⊃P.
PPT Slide
Lager Image
Inclusion relations between space and object
We derive spatial relations between Objects modeled on CSG-tree by applying the relevant physical constraints to 4-Intersection model [16] . Out of many possible relations we select only 7 kinds of topological relations as needed for our work, and they could be combined to describe complicated relations. These spatial relations are attached with their corresponding semantics as tabulated in Table 1 and will be used by agents for grasping spatial relations in the virtual environment.
Selected physics-based spatial relations (PSR)
PPT Slide
Lager Image
Selected physics-based spatial relations (PSR)
3.2.2 Physics-based Description of Situations : Together with the location the physical phenomena relevant to the earth environment also are to be considered in order to correctly describe the spatial relations occurring on the earth. For example two objects may contact each other by merely sitting side by side, one lying on the other, or one leaning against the other, among numerous ways. To further distinguish these relations from each other the relative positions between their associated objects are to be elaborated with respect to additional often invisible factors like the gravity besides to the distance among them. In general modeling of physical phenomena involves diverse physical factors, such as gravity, humidity, buoyancy, friction among others. An example situation illustrated in Fig.5 concerns the following parameters such as mass (m), Gravity (G), humidity (h), friction coefficient (μ), buoyancy (bu), density (de), etc. The objects in the situation include a wall (denoted by Object-A), a ladder (by Object-B) and a thief (by Human-A). The relevant environmental factors are collectively described by weather (t) = {clear, rainy, snowy,windy} [13] .
PPT Slide
Lager Image
Example configurations involving diverse physical factors
Of numerous physical factors kinetic force causes the objects to move or to be deformed. An object starts to move if the force thrusting it overcomes its resistance force. In the situation shown in Fig.6 the ladder leaning against the wall exerts a force on the wall and the force is countered by a resistance from the wall. The force from the ladder could be computed as: m * G * sinθ * cosθ * a, and that from the wall as: M * G * b. If the force from the ladder grows beyond the resistance due to, e.g., a person stepping on it, the wall could collapse and the ladder would subsequently fall to the ground as shown in the scene on the right-hand picture [14] . Different physical and environmental factors, i.e., fragility can be taken into consideration to determine whether the ladder is to collapse. Fragility is dependent on moisture or aging. A rainy weather could cause moisture in the environment which can affect the physical property of object-B. In ordinary use, wood shrinks as it gives off moisture and swells as it absorbs moisture. These dimensional changes put stresses on joints of the ladder and this high stress can cause a bond failure. Buoyancy is an upward force exerted by a fluid that opposes the weight of an immersed object. Specifically, buoyant force ( Fbu ) is equal to the weight of the fluid that is displaced by the submerged object. If the buoyant force is greater than or equal to the weight of the object then it will float, otherwise it will sink.
PPT Slide
Lager Image
PPT Slide
Lager Image
Example chained phenomena due to forces and reactive forces
- 3.3 Temporal Relations
Unlike with the fixed objects, spatial relations between mobile objects like two humans generally demand further information in the time axis so as to estimate the expected distance or spatial relations changing between those objects on the move. The temporal relation is the most basic physical relation because every concept in the virtual environment is dictated by time. The temporal relation is applied to the time as pure natural concept as well as the time as conventional logical entity such as day, month and year. In addition, this relation is also applied to the attributes of activity, relation and entity whose domain is time such as duration of activity [17] .
Definition 3.3 Let T denote the set of all times at which the activity occurs. Then the set T is ordered, meaning that there is a total order such that, for all t1, t2 and t3 in T:
  • (1) If t1 ≤ t2 and t2 ≤ t1 then t1=t2 (anti symmetry)
  • (2) If t1 ≤ t2 and t2 ≤ t3 then t1 ≤ t3 (transitivity)
  • (3) If t1 ≤ t2 and t2 ≤ t1 (completeness)
An activity proceeds only forward along the timeline T( t 1 , t 2 , t 3 ... tn ) In [18] Allen categorizes time into two types: point and interval. A time point is an instantaneous time that is generally associated with some transition in the world, such as a light turning on as the agent enters.
An interval of time is an extended stretch of time over which some event occurs. An interval has its duration (e.g. five minutes long), while a point cannot have duration [19] . Interval of time is defined as a pair of two time point: start time St and end time Et . The duration is defined by subtracting Et - St . The relation between two time points is divided into three relations – ‘temporally equal’, ‘temporally precede (or before)’ and ‘temporally follow (or after)’. According to Definition 3.3, two time points t1 and t2 are temporally equal if t1= t2. If t1 < t2, then t1 temporally precedes t2. If t1>t2, then t1 temporally follows t2. The relation between two time intervals (duration) is defined by using this time point relation and their start time and end time.
4. ENHANCING SITUATION CALCULUS TO REPRESENT EVENTS IN SITUATION
The original situation calculus by McCarthy and Hayes is a first-order language with some limited second-order features specifically designed for representing dynamically changing worlds. The language has disjoint sorts for actions, situations, and objects where a situation represents a world history as a sequence of actions. The constant S 0 is used to denote the initial situation where no actions have been performed. Sequences of actions are built using the function symbol do, such that do( a, s ) denotes the successor situation resulting from performing action a in situation s . A fluent is a predicate or function whose last argument is a situation, and thus whose value can change from situation to situation, and the predicate Poss( a, s ) states that action a is executable in situation s.
In this work we enhance the original Situation Calculus by adding the temporal and spatial aspects of situations in representing and reasoning about actions. Specifically, Poss( a, s ) in the original Situation Calculus would be elaborated into Poss( a ( x,y ), s , t ), where (x,y) denotes the location where the action is executed and t denotes the time at which the action is executed by the agent. A situation is the conceptual unit constituting our virtual environment, and it develops in occurrences of actions.
In the simplest description of situation calculus, each action is represented by its precondition and effect described in terms of a situation. That is, a situation represents a history of a finite sequence of action
PPT Slide
Lager Image
a denotes actions. Actions are what make the dynamic world change from one situation to another when performed by agents [20] . Precondition axioms determine the conditions when (time) and where (place) it is possible to execute the action. We use Poss ( a,s ) to mean that it is possible to execute action a in situation s .
PPT Slide
Lager Image
Formalization of the world includes at least one precondition axiom for each action. The precondition of an action is a proposition that must be true before the action can be carried out. The Effect axiom describes what happens when a possible action a is executed at a certain time t .
PPT Slide
Lager Image
Reasoning about the results of actions is central to the operation of a knowledge-based agent. In addition to single actions, it is also needed to reason about action sequences. We can define the results of sequences in terms of individual actions [12] .
As for our running example situation, the owner and the thief were at their own homes at the start and no action is executed from both sides (empty sequence) leaves the situation unchanged.
PPT Slide
Lager Image
Executing a nonempty sequence is the same as executing the first action and then executing the rest of actions in the resulting situation:
PPT Slide
Lager Image
An agent should be able to deduce the outcome of a given sequence of actions to act ( the projection task ). With a suitable inference algorithm, it should also be able to find a sequence that can achieve a desired effect ( the planning task ). The agent h 2 is at ( H 2 , t 0 ) and the safe ( 0 ) is at ( H 1 , h 0 ). The goal is to have the safe at ( H 2 , tf ) The Fluent predicates are At ( o,x,y ), where x indicates location of the safe and Holding ( o,s ) then the initial knowledge base might include the following description:
PPT Slide
Lager Image
We demonstrate that the agent h 2 can achieve its goal by going to ( H 1 , t 0 ), grabbing the safe and returning to ( H 2 , tf ). That is, At ( 0 , [ H 2 , tf ], Result ( Go ([ H 2 , tf ],[ H 1 , t 0 ]), Grab ( o ), Go ([ H 1 , t 0 ],[ H 2 , tf ], So ))
In constructing a plan to get the safe, which can be achieved by answering the query: “what sequences of actions causes the safe to be at the goal situation ( H 2 , tf )?” The following section describes what has to be in the knowledge base for these queries to be answered.
The precondition axioms for this scenario states that an agent h 2 can go between adjacent locations, grab the safe box in the current location and release. That is,
PPT Slide
Lager Image
The collapsing of the ladder due to gravity or fragility can be expressed as:
PPT Slide
Lager Image
where the variable s stands for situations, α () for actions, b for safe box, x and y for the locations including the agent’s house, t for the time points and l for the ladder.
Effect axioms states that, if an action is possible, then certain properties (Fluents) will hold in the situation that results from executing the action. For example, going from location x to y results in being at y , grabbing the safe results in holding it, stepping on the ladder results in collapse of the ladder and releasing the safe results in not holding it.
PPT Slide
Lager Image
The time precedence denoted as ( t 1 , t 2 ,...) in the above sequence of actions shows the elapse of time over which the event occurs. The time duration for the event occurrence is computed by subtracting tf - t 0 .
A situation is described in terms of the entities and their interrelationships changing over time. Change in Situation Calculus is manifested in the properties of entities and the relations between them. In the terminology of Situation Calculus, entities are continuant objects that exist in their entirety at any time instant of their spatiotemporal history O = { o 1 , o 2 ,... on }, where their properties and relations to other entities in a particular situation are referred to as Fluents, Փ:
PPT Slide
Lager Image
The agent’s in our example scenario can change their positions or relations to the other objects with time, depending on the physical situations in the environment.
PPT Slide
Lager Image
where O denotes objects in the robbery scenario. Applying the relations and sub relations of PSR in Table 1 which may hold between entities the Fluents can be described as:
PPT Slide
Lager Image
In a dynamic system, attributes of an object and relationships between objects change over time, and relational and functional Fluents capture such dynamics. While continuants represent the static part of reality, the occurrences correspond to the dynamics of the world. The occurrences include events that specify the instantaneous beginning and change in objects through a procedure that bring change to the objects. The procedure is carried out using actions and events which are represented by means of a function f that takes a state of the world, s, as input and returns another state s' as output. s' is the state the world will be in after that action has been performed when the world was in state s. Since the action of f may involve various entities in the world, it will also have other arguments representing the relationship between those entities or their properties such as color, size, location...etc. For example, with the action “push ( o 1 , o 2 )”:
PPT Slide
Lager Image
Intuitively, this says that if an entity o 1 happens to be where entity o 2 is, in state s, time t and while in that state s, o 1 performs a push action on o 2 to some location loc, this will change the world to a new state written as push( o 1 , o 2 ,loc,s',t') in which o 1 is still where o 2 is and t'indicates the change in time.
At ( o 1 , o 2 ,s) → At( o 2 ,loc,push( o 1 , o 2 ,loc,s)) is a “change axiom” which expresses how a “push” action changed the situation At ( o 1 , o 2 ,s) is a precondition for push: in order for one to push something, one must be where it is. And the result of this axiom is that o 1 is still where o 2 is. When pushing something, the object being pushed moves to the location where it is pushed to. In case the owner could grab the thief, he may push him in order to take him to a location like a police station.
5. APPLICATION TO EXAMPLE SITUATION
The idea behind Situation Calculus is that reachable states are definable in terms of the actions required to reach them. These reachable states are called situations. What is true in a situation can be defined in terms of relations with the situation as an argument [21] . Using the algorithm in Table 2 , the thief might identify the following sequence of actions in a situation corresponding to the associated sub goals: s ( α 1 , α 2 , α 3 , α 4 , α 5 )
PPT Slide
Lager Image
Inference algorithm used by the agent to find a sequence that can achieve the desired effect
PPT Slide
Lager Image
Inference algorithm used by the agent to find a sequence that can achieve the desired effect
In ontologies activity occurrence is an event or action that takes place at a specific place and time i.e. α 3 and α 3 ' in our enhanced Situation Calculus are sub-occurrences of the action “Enter”.
This algorithm is developed by applying the concept of our enhanced Situation Calculus to the spatial and temporal relations provided in Section 3. Each sequence of actions denoted as Poss( α, s ) in the original Situation Calculus are further elaborated by adding the time parameter t and locations such as “in”, “out”, “near” and “far”.
Starting from one to be able to satisfy the goal, those actions are successively identified based on the association between their Precondition and Effect such that the Effect of an action produces a part of Precondition of another action. For example, the effect of attempting to unlock the door depends on the location of the agent and whether it is carrying the appropriate key written as:
PPT Slide
Lager Image
One possible representation of the effect and precondition of actions is to explicitly enumerate the states as shown in Fig. 8 and for each state, specify the actions that are possible in that state.
The effects of actions can be described in terms of how the actions affect the states. For example, the action of the thief’s stepping on the ladder can result in a collapse of the ladder if the force from the ladder exceeds the resistance: Step ( thief, ladder ) ⇒ collapse
In reference to Fig. 7 , a state contains all of the information necessary to predict the effects of an action and to determine if it is a goal state. State-space searching in our work assumes that:
  • The agent has knowledge of the state space and can observe what state it is in;
  • The agent has a set of actions that have known deterministic effects;
  • A solution is a sequence of actions that will get the agent from its current state to a goal state.
PPT Slide
Lager Image
the states (a) and actions (b) needed to describe the theft scenario
In Fig. 8 we present the formulation of intelligent action for the agents in the example scenario in terms of state space. It shows part of the search space starting from the state where the thief and owner are at their respective houses. The Owner kept the safe home, Thief wants the safe and proceeds to the state where thief walked to the owner’s home and picked the safe after the owner left his home. After picking the safe the thief decided to step out using the ladder and fell down because the ladder collapses due to gravity.
PPT Slide
Lager Image
State-space for the example scenario
6. CONCLUSION
Spatio-temporal aspects of dynamic situations have been formalized in this work. We first described spatio-temporal representations of historical contexts in terms of spatiotemporal graph as it is the basic constituent to simulate virtual situations. By redefining objects with respect to space and time and also elaborating the spatial and temporal relations among objects, we proposed a mathematical framework to represent actions and events in Situation Calculus. The existing Situation Calculus has been elaborated on this work by adding the temporal and spatial aspects of situations to represent and reason about actions.
Those spatio-temporal properties were further elaborated by applying physical laws like the gravity for realistic description of spatio-temporal relations and presented in terms of its mathematical framework and associated semantics. It is applied to example situation with typical types of 3-D physical objects and associated physical laws in order to demonstrate its feasibility in practice. In order to comprehensively describe the situations in a historical context and handle various kinds of actions, this approach is designed to accommodate multidimensionality in structure, generality in occurrence types, and flexibility in views.
The ultimate goal of the proposed system is to lay a basis for construction of realistic virtual situation in terms of space and time and provide background knowledge for the agent’s residing in the simulated virtual environment.
Acknowledgements
This research was supported by Kyungpook National University Research Fund, 2012.
BIO
Haymanot Alalo Gebre
She received her B.S. in Computer Science from University of Gondar, Ethiopia in 2007, Currently M.Sc. student, in Kyungpook National University, Korea. Her research interest in Artificial Intelligence, specifically formalizing spatial and temporal aspects of dynamic situations in the virtual environment
Jun Seong Choi
He received his M.S in Electronics Engineering from Kyungpook National University in 2011, He is currently in a Ph.D program in Kyungpook National Unversity, Korea. His research interest is Artificial Intellingence, especially natural occurrence of events and actions of an autonomous agent in virtual world.
Dr. Jong Hee Park
He acquired his Ph.D in Computer Eng. From Univ. of Florida in 1990. He has since been on the faculty at Kyungpook Nat’l Univ. in Korea. His research interests focuses on intelligent research interests focuses on intelligent systems based on cyber-worlds. The specific research topics encompass intelligent tutoring systems for immersed language learning, futuristic simulation games, and simulation of cyber-worlds for diverse applications.
References
Choi J. , Park J. 1995 “Design and implementation of a graphic user interface with a logical zooming for retrieval of object-oriented databases,” J. of IEIE 32 (1) 1 - 10
Hiralla N. 1995 “A Temporal model for interactive multimedia scenarios,” IEEE Multimedia 2 (3) 24 - 31    DOI : 10.1109/93.410508
Park J. 1999 Knowledge for constructing cyber-microcosm, Tech. Report, AIMM lab Kyungpook National University
Wooldridge M. 2000 Reasoning about Rational Agents MIT Press
Finin T. 1995 KQML as an agent communication language University of Maryland Baltimore County
Matias R. 2005 “Spatial On-Line Analytical Processing (SOLAP): A Tool to analyze the emission of pollutants in industrial installations,” IEEE, Artificial intelligence
Park J. 2009 An Augmented model of behavioral occurrence, Tech. Report, AIMM lab. KNU
Jung K. 2007 “An Ontology-based object recognition technique in Cyber-world,” Journal of Korea Contents Association 9 (4) 45 - 54    DOI : 10.5392/JKCA.2009.9.4.045
Egehofer M. , Franzosa R. 1991 “Poing-set Topological spatial Relations,” Int. Journal of Geographical Information Systems 5 (2) 161 - 174    DOI : 10.1080/02693799108927841
Reiter 2001 Knowledge in Action: Logical Foundations for Specifying and Implementing Dynamical Systems The MIT Press
Kowalski R. , Sergot M. 1986 “A Logic-based Calculus of Events, in New Generation Computing,” 4 (1) 67 - 95
Belleghem Van 1995 Marc Denecker, Danny De Schreye, Combining Situation Calculus and Event Calculus, Kluwer Situation Calculus and Event Calculus Kluwer Academic Publishers Higham
Jung G. , Park J. 2013 “Implementation of Spatio-Temporal Graph to represent situations in the virtual world,” Waset Zurich, Swiss
Park J. , Kim T. 2012 “Representation of physical phenomena and spatial relations in Virtual Reality,” J. of Korea Contents Association 12 (6) 21 - 31    DOI : 10.5392/JKCA.2012.12.06.021
Park J. 2004 Modelling the natural events in spatio-temporal context, Tech. Report, AIMM Lab. KNU
Lim Y. , Park J. 2006 “Spatial Relations between Physical Objects with Property of Container in Virtual Environment,” Int. Journal of Information Technology 12 (4)
Ji Se Jin , Ph.D dissertation 2007 A knowledge model for simulating Human-like behavior of virtual inhabitant Kyungpook National Univ. Ph.D dissertation
Allen JF 1983 “Maintaining knowledge about temporal intervals,” communication of the ACM 26 (11) 832 - 843    DOI : 10.1145/182.358434
van Harmelen F. , Lifschitz V. , Porter B. 2008 Handbook of Knowledge Representation Elsevier B.V.
Kelly TG 1998 Modelling Complex Systems in the Situation Calculus University of Toronto
Poole D. , Mackworth A. 2010 Artificial Intelligence: Foundations of Computational Agents Cambridge University Press