An Event Calculus for Event Recognition in Symbolic Artificial Intelligence

An Event Calculus for Event Recognition

1. An Event Calculus for Event Recognition Alexander Artikis , Marek Sergot , and Georgios Paliouras

2. Presented BY Amrat Zubair & Laveeza Maryam

3. Introduction Symbolic Event Recognition : It recognizes significant patterns (events) from a series of smaller events that happen over time. RTEC (Event Calculus for Run-Time Reasoning) : RTEC is a specialized language used for defining and recognizing events. It uses new techniques to process and identify events efficiently. Capabilities : Handles complex events, operates without filtering modules, manages delayed and revised event data.

4. Event Calculus Definition: It’s a logic programming framework used to describe events and their effects over time. RTEC Features: Linear time model with integer time-points. Supports both Boolean and value- fluents . Utilizes caching, interval manipulation, and indexing for efficiency.

5. Simple Fluents Fluents : Properties with values changing over time. Interval Calculation : Identifies periods during which a fluent holds a particular value. Implementation Example : Traffic density trend analysis. Rule: initiatedAt( densityTrend (S) = increasing, T) ← happensAt(traffic(S, Flow, Density), T), happensAt(traffic(S, Flow′, Density′), T+60), Density′ > Density + Density × 0.2 Description : Density is increasing if there is a >20% rise in density value in consecutive SDEs (Simple Derived Events).

6. Simple Fluents Example Scenario: Recognizing when two people are moving together. Rules: Rules to Initiate Moving Together: Rule 1: initiatedAt(moving(P1 ,P2 ) = true, T) ← happensAt(start(walking(P1 ) = true), T), holdsAt(walking(P2 ) = true, T), holdsAt(close(P1 ,P2 ) = true, T) Rule 2: initiatedAt(moving(P1 ,P2 ) = true, T) ← happensAt(start(walking(P2 ) = true), T), holdsAt(walking(P1 ) = true, T), holdsAt(close(P1 ,P2 ) = true, T)

7. Simple Fluents Example Rule 3: initiatedAt(moving(P1 ,P2 ) = true, T) ← happensAt(start(close(P1 ,P2 ) = true), T), holdsAt(walking(P1 ) = true, T), holdsAt(walking(P2 ) = true, T) Rules: Rules to Terminate Moving Together Rule 1: terminatedAt(moving(P1 ,P2 ) = true, T) ← happensAt(end(walking(P1 ) = true), T) Rule 2: terminatedAt(moving(P1 ,P2 ) = true, T) ← happensAt(end(walking(P2 ) = true), T) Rule 2: terminatedAt(moving(P1 ,P2 ) = true, T) ← happensAt(end(close(P1 ,P2 ) = true), T) Description : moving(P1, P2) is initiated when both people are walking and close to each other, and it is terminated when either stops walking or they are no longer close.

8. Statically Determined Fluents Statically Determined Fluents: Fluents (properties that change over time) defined using the intervals of other fluents. Example: Moving activity in public surveillance. Rule: holdsFor (moving(P1, P2) = true, I) ← holdsFor (walking(P1) = true, I1), holdsFor (walking(P2) = true, I2), holdsFor (close(P1, P2) = true, I3), intersect_all ([I1, I2, I3], I) Description : moving(P1, P2) holds when P1 and P2 are walking close to each other.

9. Statically Determined Fluents Constructs: Union, Intersection, Relative Complement. Union (union_all) Definition : Computes the union of lists of maximal intervals. Example : union_all([[(5, 20), (26, 30)], [(28, 35)]], [(5, 20), (26, 35)]) Description : Combines intervals from multiple lists into a single list covering all time-points included in any list. Intersection ( intersect_all ) Definition : Computes the intersection of lists of maximal intervals. Example: intersect_all([[(26, 31)], [(21, 26), (30, 40)]], [(30, 31)]) Description : Produces a list of intervals where each time-point is included in all input lists.

10. Statically Determined Fluents Relative Complement (relative_complement_all) Definition : Computes the relative complements of a list of maximal intervals with respect to other lists. Example : relative_complement_all([(5, 20), (26, 50)], [[(1, 4), (18, 22)], [(28, 35)]], [(5, 18), (26, 28), (35, 50)]) Description : Returns intervals from the first list that are not included in any of the other lists.

11. Statically Determined Fluents Fighting Activity Example Using Constructs Rules: holdsFor (fighting(P1, P2) = true, I) ← holdsFor (abrupt(P1) = true, I1), holdsFor (abrupt(P2) = true, I2), holdsFor (close(P1, P2) = true, I3), union_all([I1, I2], I4), intersect_all([I4, I3], I5), holdsFor (inactive(P1) = true, I6), holdsFor (inactive(P2) = true, I7), relative_complement_all(I5, [I6, I7], I) Description : Two people are fighting if they are both moving abruptly, close to each other, and at least one of them is not inactive

12. Semantics Hierarchical Definitions : Fluents (properties) and events are organized in a hierarchy where higher levels depend on lower levels. Levels : Level 0 : Input SDEs These are the basic events and statically determined fluents. Higher Levels : Depend on lower levels. Fluent Mapping: Fluent-values F = Vi and F = Vj can be mapped to different levels if Vi ≠ Vj. For simplicity, a fluent F is either simple or statically determined, but not both. Simple or statically determined, not both. Fluent-values can be at different levels. Examples: City Transport Management: Definitions for CE recognition. Public Space Surveillance: Similar hierarchical definitions.

13. Run-Time Recognition Efficiency and Scalability : Supports real-time decision-making. Handling Delays and Revisions : Processes delayed and revised SDEs efficiently. Query Times : CE recognition Performs recognition at specified times, like checking for congestion every minute (Q1, Q2, ...). Illustrative Example : CE Recognition at Query Time Q138 Steps: Initial State (Q137): Maximal intervals and SDEs before or at Q137−WM retracted. Processing (Q138) : SDEs and CE intervals in (Q138−WM, Q138] computed from scratch. Updating Intervals : New CE intervals computed considering delays and revisions.

14. Illustrative Example: CE Recognition at Query Time Q138 Step 1: Initial State (Q137) Action : Maximal intervals and SDEs before or at Q137−WM (Window Margin) are retracted. Explanation : At query time Q137, the system clears out old data (events and intervals) up to a specific point defined by the window margin. This ensures that the system only works with the most relevant and recent data. Example : If the window margin is 2 minutes and Q137 is 1:37 PM, the system removes data from before 1:35 PM. Step 2: Processing (Q138) Action : SDEs and CE intervals in (Q138−WM, Q138] are computed from scratch. Explanation : At query time Q138, the system processes all new events and intervals that occurred within the window margin leading up to Q138. Example : If Q138 is 1:38 PM and the window margin is 2 minutes, the system processes data from 1:36 PM to 1:38 PM. Step 3: Updating Intervals Action : New CE intervals are computed considering delays and revisions. Explanation : The system updates its recognition results by including any new or revised events within the working memory. This ensures that even delayed or corrected data are considered in the final analysis. Example : If new data arrives for an event that happened at 1:37 PM, it is included in the analysis done at 1:38 PM.

15. Recognise SD Fluent Algorithm Procedure : Computes and stores intervals of statically determined fluents. Steps : Retract Old Intervals : Remove outdated intervals and partial events. Amalgamate : Combine and check overlap with the current window. Compute New Intervals : Determine new intervals based on overlap. Evaluate : Apply rules to compute intervals that hold. Assert : Store the updated intervals and events.

16. Recognise Simple Fluent Algorithm Procedure: Computes and stores simple fluent intervals . Steps: Retract Overlapping Intervals : Check and discard intervals overlapping Qi−WM. Compute New Starting Points : Evaluate initiatedAt and terminatedAt rules for starting points . If there are starting points (SP), compute ending points (EP) for the complex events (CE_s). Create new intervals (I) using the starting and ending points.

17. COMPLEXITY ANALYSIS m(S,E): Number of time-points in the interval (S,E]. mWM : Number of time-points in the working memory WM. n: Number of SDE (Simple Deterministic Event) types. f: Number of fluent types. e: Number of event types. k: Number of interval manipulation constructs. l: Number of rules defining a simple fluent.

18. Forget mechanism The forget mechanism is essential for managing memory usage in RTEC (Event Calculus for Run-Time Reasoning). At each query time Qi​, RTEC forgets all SDEs ending before or at Qi−WM, where WM is the duration of the working memory. This mechanism ensures that only relevant information is retained, thus preventing memory overflow and improving performance. RTEC goes through the complete list of SDEs (Short-Duration Events) available at Qi.

19. WORST CASE To forget SDEs, the algorithm needs to scan and remove events from the list of stored events. This involves processing events that occurred between the initial time and Qi−WM. The worst-case cost of the forget mechanism is O(n(m(0,Qi)+m(0,Qi−WM))). where 𝑛 is the number of SDE types, and 𝑚(𝑆,𝐸) denotes the number of time-points in the interval (𝑆,𝐸]. This accounts for the total number of events processed from the start time to the current query time and from the start time to the boundary of the working memory. n(m(Qi−1​ − WM,Qi ​ )+m(Qi−1​ − WM,Qi ​ −WM)). This reflects the cost under typical conditions where SDEs are forgotten regularly.

20. Statically determined fluents In event calculus, fluents are properties or conditions that can change over time. Statically determined fluents are a type of condition or state whose values can be determined based on rules and the current known facts, without needing continuous updates from new events. They are computed using the events and states within a specific time window. RTEC (Real-Time Event Calculus) first looks for maximal intervals of the fluent under consideration that end within the time window [Qi-1-WM, Qi-1]. The worst-case computational cost for this step is O( mWM /2 + 1), where mWM is the maximum number of maximal intervals RTEC considers in its working memory (WM).

21. Evaluation of holdsForSDFluent Rule RTEC evaluates a holdsForSDFluent rule, which specifies how a statically determined fluent behaves over time. The cost of evaluating this rule is determined by: Retrieving intervals of the fluents (SDEs or CEs) mentioned in the rule's body from computer memory. Performing interval manipulation operations such as union, intersection, and relative complement.

22. Interval Manipulation Operations RTEC uses operations like union, intersection, and relative complement to manage sets of intervals efficiently. These operations are designed to handle lists of temporally sorted maximal intervals: Union: Computes the combined intervals from two lists. Its cost is bounded by the sum of the sizes of the input lists. Intersection: Finds common intervals between two lists. Its cost is also limited by the sum of the sizes of the input lists. Relative Complement: Computes intervals that are in one list but not in another. Its cost is similar to that of union due to the size constraints.

23. COST ANALYSIS The overall cost of evaluating a holdsForSDFluent rule is bounded by: f is the number of fluents (SDEs and CEs) in the rule's body. 𝑘 is the number of interval manipulation constructs used. This formula accounts for retrieving fluent intervals from memory and the computational cost of interval manipulation.

24. SIMPLE FLUENTS Simple fluents in RTEC (Event Calculus Runtime Engine) are defined by events that explicitly initiate and terminate them. These fluents directly depend on the occurrence of events, unlike statically determined fluents which rely on interval relations of other fluents . A fluent 𝐹 is considered simple if it holds due to explicit initiation and termination events. The conditions under which a simple fluent 𝐹 holds at a time 𝑇 can be expressed as follows: 𝐹 is initiated at time 𝑇 if an event occurs that triggers its initiation. 𝐹 is terminated at time 𝑇 if an event occurs that triggers its termination. These events are defined using initiatedAt and terminatedAt predicates.

25. FORMAL REPRESENTATION The initiation and termination of a simple fluent 𝐹 are represented by two sets of rules: Initiation Rules ( initiatedAt ): Specify the conditions under which 𝐹F starts to hold. Example: 𝑖𝑛𝑖𝑡𝑖𝑎𝑡𝑒𝑑𝐴𝑡(𝐹=𝑉,𝑇) if some event 𝐸 occurs at 𝑇 and certain conditions 𝐶 are true. Termination Rules ( terminatedAt ): Specify the conditions under which 𝐹 stops holding. Example: 𝑡𝑒𝑟𝑚𝑖𝑛𝑎𝑡𝑒𝑑𝐴𝑡(𝐹=𝑉,𝑇) if some event 𝐸′ occurs at 𝑇 and certain conditions 𝐶′ are true.

26. EVALUATION To evaluate a simple fluent, we need to follow these steps: Collect Initiation Points: Identify all time points where the fluent 𝐹 is initiated within the working memory (WM). Collect Termination Points: Identify all time points where the fluent 𝐹 is terminated within the WM. Compute Maximal Intervals: Determine the maximal intervals during which 𝐹 holds by finding the intervals between initiation and the next termination.

27. COMPLEXITY Identify Initiation and Termination Points: For each query time 𝑄𝑖, collect initiation points 𝑇𝑠 and termination points 𝑇𝑓 within the working memory. The number of these points is bounded by the number of time points 𝑚𝑊𝑀 in the working memory. Compute Maximal Intervals: Sort and merge the intervals between initiation and the next termination points. Sorting the points has a cost of 𝑂(𝑚𝑊𝑀log⁡𝑚𝑊𝑀). Merging the intervals has a cost of 𝑂(𝑚𝑊𝑀). Total Cost: Here, 𝑙 is the number of rules, 𝑒 is the number of events, and 𝑓 is the number of fluents .

28. Simple vs Statically Determined Fluents Representation: The "moving" CE can be represented as a statically determined fluent using the formula provided: holdsFor (moving(P1, P2) = true, I)← holdsFor (walking(P1) = true, I1), holdsFor (walking(P2) = true, I2), holdsFor (close(P1, P2) = true, I3), intersect_all ([I1, I2, I3], I). This indicates that P1 is moving with P2 if both are walking and are close to each other during the intervals I1, I2, and I3 respectively. Cost Calculation: The cost of this representation can be calculated using the complexity formula for statically determined fluents . For this particular representation: 𝑂(3+5𝑚𝑊𝑀/2) where 𝑓=3 (3 body fluents ) and 𝑘=1(1 interval manipulation construct).

29. Simple vs Statically Determined Fluents Representation: Alternatively, the "moving" CE can be represented as a simple fluent with six initiatedAt and terminatedAt rules. Each rule has three fluents and no events in the body. For example: initiatedAt (moving(P1, P2) = true, T)← happensAt (start(walking(P1) = true), T), holdsAt (walking(P2) = true, T), holdsAt (close(P1, P2) = true, T) and similarly for the termination conditions. Cost Calculation: Using the complexity formula for simple fluents : 𝑂(6𝑚𝑊𝑀(3+3𝑚𝑊𝑀/2)) which can be simplified to: 𝑂(3𝑚𝑊𝑀(3+3𝑚𝑊𝑀/2)) due to the structure of the initiatedAt and terminatedAt rules, which allows for at most three evaluations at any given time.

30. City Transport Management (CTM) DATA USED: PRONTO Project Data: Data about public transport vehicles, including their punctuality and driving quality. Dublin Transport Data: Traffic data from Dublin, Ireland. EXPERIMENTS: Single Vehicle Recognition: Tested how well the system works with different sizes of working memory (the amount of data it keeps at any time) and with different amounts of irrelevant data (data that doesn't matter for the task). The system tracked 20 different types of events per vehicle. Multiple Vehicle Recognition: Simulated a busy city with 1,050 vehicles and tested how well the system handles lots of data coming in quickly. Tested the system on one processor and also on multiple processors to see if it could handle the load better when working in parallel.

31. City Transport Management (CTM) LARGER & MIXED DATA: High Data Frequency: Tested with fake data simulating 10,000 vehicles sending a lot of data quickly. Mixed Data Streams: Combined data from buses and traffic sensors, recognizing complex events like traffic jams and disagreements between data sources. RESULTS: Irrelevant Data: The system wasn't slowed down much by irrelevant data, showing it can efficiently focus on relevant information. Parallel Processing: When using multiple processors, the system handled high data loads effectively, maintaining real-time performance even during busy periods.

32. City Transport Management (CTM)

33. Public Space Surveillance (PSS) DATA USED: CAVIAR Dataset: Surveillance videos with annotated activities like walking, running, meeting, and fighting. EXPERIMENTS: Forget Mechanism: Tested how well the system forgets old data that is no longer relevant. Entity Pair Recognition: Tracked multiple pairs of people in the videos. Tested on one processor and also on eight processors with different sizes of working memory. RESULTS: Forget Mechanism: The system efficiently forgot old data, improving its performance. Parallel Processing: Demonstrated real-time performance even when tracking multiple pairs of people in large datasets.

34. Public Space Surveillance (PSS)

35. RELATED WORK

36. SUMMARY The paper presents RTEC (Runtime Event Calculus), a dialect of the Event Calculus designed to efficiently recognize complex events (CEs) from large streams of simple derived events (SDEs). The paper emphasizes the efficiency and real-time capabilities of RTEC in complex event recognition for applications such as city transport management and public space surveillance. It introduces implementation techniques that enhance the efficiency and scalability of CE (Composite Event) recognition.

37. FURTHER WORK The authors note that while they have described the differences between their approach and other systems in detail, they have not conducted direct performance comparisons. This is due to the challenges of compiling a dataset that uses only common features across different systems. However, they plan to explore this possibility in future work.

38. REFRENCES J. Agrawal, Y. Diao, D. Gyllstrom , and N. Immerman . Efficient pattern matching over event streams. In SIGMOD, 2008. D. Anicic, S. Rudolph, P. Fodor, and N. Stojanovic . Real-time complex event recognition and reasoning. Applied Artificial Intelligence, 26(1–2):6–57, 2012. A. Arasu, S. Babu, and J. Widom . The CQL continuous query language: semantic foundations and query execution. The VLDB Journal, 15(2):121–142, 2006. A. Artikis , M. Sergot , and G. Paliouras . Run-time composite event recognition. In DEBS, pages 69–80. ACM, 2012. A. Artikis , A. Skarlatidis , F. Portet , and G. Paliouras . Logic-based event recognition. Knowledge Engineering Review, 27(4):469–506, 2012. Y. Bai, H. Thakkar, H. Wang, C. Luo, and C. Zaniolo . A data stream language and system designed for power and extensibility. In CIKM, pages 337–346, 2006.

39. THE END