Search

Spatial-temporal reasoning is a challenging task in Artificial Intelligence (AI) due to its demanding but unique nature: a theoretic requirement on representing and reasoning based on spatial-temporal knowledge in mind, and an applied requirement on a high-level cognitive system capable of navigating and acting in space and time. Recent works have focused on an abstract reasoning task of this kind -- Raven's Progressive Matrices (RPM). Despite the encouraging progress on RPM that achieves human-level performance in terms of accuracy, modern approaches have neither a treatment of human-like reasoning on generalization, nor a potential to generate answers. To fill in this gap, we propose a neuro-symbolic Probabilistic Abduction and Execution (PrAE) learner; central to the PrAE learner is the process of probabilistic abduction and execution on a probabilistic scene representation, akin to the mental manipulation of objects. Specifically, we disentangle perception and reasoning from a monolithic model. The neural visual perception frontend predicts objects' attributes, later aggregated by a scene inference engine to produce a probabilistic scene representation. In the symbolic logical reasoning backend, the PrAE learner uses the representation to abduce the hidden rules. An answer is predicted by executing the rules on the probabilistic representation. The entire system is trained end-to-end in an analysis-by-synthesis manner without any visual attribute annotations. Extensive experiments demonstrate that the PrAE learner improves cross-configuration generalization and is capable of rendering an answer, in contrast to prior works that merely make a categorical choice from candidates., Comment: CVPR 2021 paper. Supplementary: http://wellyzhang.github.io/attach/cvpr21zhang_prae_supp.pdf Project: http://wellyzhang.github.io/project/prae.html

Summarization: Most of the existing work in the field of Qualitative Spatial Temporal Reasoning (QSTR) has focussed on comparatively small constraint networks that consist of hundreds or at most thousands of relations. Recently we have seen the emergence of much larger qualitative spatial knowledge graphs that feature hundreds of thousands and millions of relations. Traditional approaches to QSTR are unable to reason over networks of such size. In this article we describe ParQR, a parallel, distributed implementation of QSTR techniques that addresses the challenge of reasoning over large-scale qualitative spatial and temporal datasets. We have implemented ParQR using the Apache Spark framework, and evaluated our approach using both large scale synthetic datasets and real-world knowledge graphs. We show that our approach scales effectively, is able to handle constraint networks consisting of millions of relations, and outperforms current distributed implementations of QSTR. Παρουσιάστηκε στο: Knowledge-Based Systems

Video saliency detection often suffers from two issues: hard to disentangle the temporal motion patterns and spatial layout patterns, and hard to capture the temporal motion patterns. Thus a novel deep learning network architecture is proposed for video saliency in this paper. The proposed network consists of three parts: high-level representation module, attention module, and memory and reasoning module. The high-level representation module and attention module are used for capturing spatial saliency that is mainly learned from static images. The memory and reasoning module is used to infer the saliency from the information about spatial layout in frames and temporal motion between frames. Because high-level representation module and attention module could concentrate on high-level representation of spatial patterns, and the memory and reasoning module could concentrate on spatial and temporal saliency reasoning, the temporal patterns and spatial patterns could be disentangled efficiently. The quantitative and qualitative results show the proposed method achieves a promising results across a wide of metrics.

Discovering social relations, e.g., kinship, friendship, etc., from visual contents can make machines better interpret the behaviors and emotions of human beings. Existing studies mainly focus on recognizing social relations from still images while neglecting another important media--video. On one hand, the actions and storylines in videos provide more important cues for social relation recognition. On the other hand, the key persons may appear at arbitrary spatial-temporal locations, even not in one same image from beginning to the end. To overcome these challenges, we propose a Multi-scale Spatial-Temporal Reasoning (MSTR) framework to recognize social relations from videos. For the spatial representation, we not only adopt a temporal segment network to learn global action and scene information, but also design a Triple Graphs model to capture visual relations between persons and objects. For the temporal domain, we propose a Pyramid Graph Convolutional Network to perform temporal reasoning with multi-scale receptive fields, which can obtain both long-term and short-term storylines in videos. By this means, MSTR can comprehensively explore the multi-scale actions and storylines in spatial-temporal dimensions for social relation reasoning in videos. Extensive experiments on a new large-scale Video Social Relation dataset demonstrate the effectiveness of the proposed framework.

This paper presents and evaluates a method to combine time-based granulation and three-way decisions to support decision makers in understanding and reasoning on the learned granular structures conceptualising spatio-temporal events. The method uses an existing approach to discover periodic events in the data, such as periods of intense traffic in a city, and provides an original approach to conceptualize such events to support decision makers in: (i) better comprehending the causes that lead to the repetition of such events and/or (ii) increasing the awareness of their effects and consequences. The formal concept analysis is the central tool of the proposed method. This tool is used as a guide in the phase of time-based granulation, which relies on the principle of justified granularity, and as a support for reasoning and making three-way decisions. The main contribution of the paper is an effective and simple method for time-based granulation of events, their observation, and interpretation to support decision making. The method is described with an illustrative example and evaluated on a real data set on forest fires, showing how to define a spatio-temporal DSS model to support decisions in environmental monitoring problems.

Multimodal question answering tasks can be used as proxy tasks to study systems that can perceive and reason about the world. Answering questions about different types of input modalities stresses different aspects of reasoning such as visual reasoning, reading comprehension, story understanding, or navigation. In this article, we use the task of Audio Question Answering (AQA) to study the temporal reasoning abilities of machine learning models. To this end, we introduce the Diagnostic Audio Question Answering (DAQA) dataset comprising audio sequences of natural sound events and programmatically generated questions and answers that probe various aspects of temporal reasoning. We adapt several recent state-of-the-art methods for visual question answering to the AQA task, and use DAQA to demonstrate that they perform poorly on questions that require in-depth temporal reasoning. Finally, we propose a new model, Multiple Auxiliary Controllers for Linear Modulation (MALiMo) that extends the recent Feature-wise Linear Modulation (FiLM) model and significantly improves its temporal reasoning capabilities. We envisage DAQA to foster research on AQA and temporal reasoning and MALiMo a step towards models for AQA.

Reasoning about the behavior of real-world systems and processes faces problems such as repeating events or subprocesses , evolving component behaviors, and indefinite time horizons. To date, existing representations of time and uncertainty have been unable to fully address such requirements. They often tradeoff assumptions of available knowledge against richness of representing time and semantics for uncertainty. This has made representations either overly simplistic or cumbersome to model with, or both. In this paper, we present a new theoretical representation for reasoning about time and uncertainty extending our ability to better address real-world systems. Called cost-based temporal reasoning, we believe it is simple to understand, is rigorously defined, and allows for strong semantics of time and uncertainty. This paper formally details the definitions and proofs about the capabilities of cost-based temporal reasoning.

Despite great success has been achieved in activity analysis, it still has many challenges. Most existing work in activity recognition pay more attention to design efficient architecture or video sampling strategy. However, due to the property of fine-grained action and long term structure in video, activity recognition is expected to reason temporal relation between video sequences. In this paper, we propose an efficient temporal reasoning graph (TRG) to simultaneously capture the appearance features and temporal relation between video sequences at multiple time scales. Specifically, we construct learnable temporal relation graphs to explore temporal relation on the multi-scale range. Additionally, to facilitate multi-scale temporal relation extraction, we design a multi-head temporal adjacent matrix to represent multi-kinds of temporal relations. Eventually, a multi-head temporal relation aggregator is proposed to extract the semantic meaning of those features convolving through the graphs. Extensive experiments are performed on widely-used large-scale datasets, such as Something-Something and Charades, and the results show that our model can achieve state-of-the-art performance. Further analysis shows that temporal relation reasoning with our TRG can extract discriminative features for activity recognition., Comment: 14pages, 8figures

Vision and language understanding has emerged as a subject undergoing intense study in Artificial Intelligence. Among many tasks in this line of research, visual question answering (VQA) has been one of the most successful ones, where the goal is to learn a model that understands visual content at region-level details and finds their associations with pairs of questions and answers in the natural language form. Despite the rapid progress in the past few years, most existing work in VQA have focused primarily on images. In this paper, we focus on extending VQA to the video domain and contribute to the literature in three important ways. First, we propose three new tasks designed specifically for video VQA, which require spatio-temporal reasoning from videos to answer questions correctly. Next, we introduce a new large-scale dataset for video VQA named TGIF-QA that extends existing VQA work with our new tasks. Finally, we propose a dual-LSTM based approach with both spatial and temporal attention and show its effectiveness over conventional VQA techniques through empirical evaluations.

Time is deeply woven into how people perceive, and communicate about the world. Almost unconsciously, we provide our language utterances with temporal cues, like verb tenses, and we can hardly produce sentences without such cues. Extracting temporal cues from text, and constructing a global temporal view about the order of described events is a major challenge of automatic natural language understanding. Temporal reasoning, the process of combining different temporal cues into a coherent temporal view, plays a central role in temporal information extraction. This article presents a comprehensive survey of the research from the past decades on temporal reasoning for automatic temporal information extraction from text, providing a case study on the integration of symbolic reasoning with machine learning-based information extraction systems., Extended abstract of a JAIR article, which is to appear in the proceedings of IJCAI 2020 (the copyright of this abstract is held by IJCAI 2020)

Video Question Answering (Video QA) is a powerful testbed to develop new AI capabilities. This task necessitates learning to reason about objects, relations, and events across visual and linguistic domains in space-time. High-level reasoning demands lifting from associative visual pattern recognition to symbol-like manipulation over objects, their behavior and interactions. Toward reaching this goal we propose an object-oriented reasoning approach in that video is abstracted as a dynamic stream of interacting objects. At each stage of the video event flow, these objects interact with each other, and their interactions are reasoned about with respect to the query and under the overall context of a video. This mechanism is materialized into a family of general-purpose neural units and their multi-level architecture called Hierarchical Object-oriented Spatio-Temporal Reasoning (HOSTR) networks. This neural model maintains the objects' consistent lifelines in the form of a hierarchically nested spatio-temporal graph. Within this graph, the dynamic interactive object-oriented representations are built up along the video sequence, hierarchically abstracted in a bottom-up manner, and converge toward the key information for the correct answer. The method is evaluated on multiple major Video QA datasets and establishes new state-of-the-arts in these tasks. Analysis into the model's behavior indicates that object-oriented reasoning is a reliable, interpretable and efficient approach to Video QA., Comment: Accepted by IJCAI 2021. Please cite the conference version

Temporal relations among multiple action segments play an important role in action segmentation especially when observations are limited (e.g., actions are occluded by other objects or happen outside a field of view). In this paper, we propose a network module called Graph-based Temporal Reasoning Module (GTRM) that can be built on top of existing action segmentation models to learn the relation of multiple action segments in various time spans. We model the relations by using two Graph Convolution Networks (GCNs) where each node represents an action segment. The two graphs have different edge properties to account for boundary regression and classification tasks, respectively. By applying graph convolution, we can update each node's representation based on its relation with neighboring nodes. The updated representation is then used for improved action segmentation. We evaluate our model on the challenging egocentric datasets namely EGTEA and EPIC-Kitchens, where actions may be partially observed due to the viewpoint restriction. The results show that our proposed GTRM outperforms state-of-the-art action segmentation models by a large margin. We also demonstrate the effectiveness of our model on two third-person video datasets, the 50Salads dataset and the Breakfast dataset.

Detection of earthmoving equipment in construction images and videos can increase the automation level of many construction management tasks such as productivity measurement, locating of machines, work-zone safety, and semantic image and video indexing. Some of the earthmoving plants, such as hydraulic excavator, have articulated shapes making them a difficult target for even state of the art object recognition algorithms. The goal of this paper is to develop a model for non-rigid equipment detection and pose estimation in construction images and videos. In this paper, we describe an object recognition system based on mixture of appearances of deformable body parts of the hydraulic excavator and compare its results with general Histogram of Oriented Gradient detectors in both images and videos. Then a spatial–temporal reasoning model is presented which uses time and space constraints of the excavators' moving patterns to improve the detection results in videos.

In this paper, we consider both the modelling and optimization of preferences in problems of constraint-based temporal reasoning. The Disjunctive Temporal Problems with Preferences (DTPP) – a formulation that combines the rich expressive power of the Disjunctive Temporal Problem with the introduction of metric preference functions – is studied, and transformed into a corresponding constraint system that we name the Valued DTP (VDTP). We show that for a broad family of optimization criteria, the VDTP can express the same solution space as the DTPP, under the assumption of arbitrary piecewise-constant preference functions. We then generalize the powerful search strategies from decision-based DTP literature to accomplish the efficient optimization of temporal preferences. In contrast to the previous state-of-the-art system (which addresses the optimization of temporal preferences using a SAT formulation), we instead employ a meta-CSP search space that has traditionally been used to solve DTPs without preferences. Our approach supports a variety of objective functions (such as utilitarian optimality or maximin optimality) and can accommodate any compliant valuation structure. We also demonstrate that key pruning techniques commonly used for temporal satisfiability (particularly, the removal of subsumed variables and semantic branching) are naturally suited to prevent the exploration of redundant search nodes during optimization that may otherwise be encountered when resolving a typical VDTP derived from a DTPP. Finally, we present empirical results showing that an implementation of our approach consistently outperforms prior algorithms by orders of magnitude.

Traditional approaches to temporal reasoning assume that time periods and time spans of events can be accurately represented as intervals. Real-world time periods and events, on the other hand, are often characterized by vague temporal boundaries, requiring appropriate generalizations of existing formalisms. This paper presents a framework for reasoning about qualitative and metric temporal relations between vague time periods. In particular, we show how several interesting problems, like consistency and entailment checking, can be reduced to reasoning tasks in existing temporal reasoning frameworks. We furthermore demonstrate that all reasoning tasks of interest are NP-complete, which reveals that adding vagueness to temporal reasoning does not increase its computational complexity. To support efficient reasoning, a large tractable subfragment is identified, among others, generalizing the well-known ORD Horn subfragment of the Interval Algebra (extended with metric constraints).

We introduce five new natural language inference (NLI) datasets focused on temporal reasoning. We recast four existing datasets annotated for event duration—how long an event lasts—and event ordering—how events are temporally arranged—into more than one million NLI examples. We use these datasets to investigate how well neural models trained on a popular NLI corpus capture these forms of temporal reasoning.

In many applications of temporal reasoning we are interested in processing temporal information incrementally. In particular, given a set of temporal constraints (a temporal CSP) and a new constraint, we want to maintain certain properties of the extended temporal CSP (e.g., a solution), rather than recomputing them from scratch. The Point Algebra (PA) and the Interval Algebra (IA) are two well-known frameworks for qualitative temporal reasoning. The reasoning algorithms for PA and the tractable fragments of IA, such as Nebel and Bürckert's maximal tractable class of relations (ORD-Horn), have originally been designed for “static” reasoning.In this paper, we study the incremental version of the fundamental reasoning problems in the context of these tractable classes. We propose a collection of new polynomial algorithms that can amortize their complexity when processing a sequence of input constraints to incrementally decide satisfiability, to maintain a solution, or to update the minimal representation of the CSP. Our incremental algorithms improve the total time complexity of using existing static techniques by a factor of O(n) or O(n2), where n is the number of the variables involved by the temporal CSP. An experimental analysis focused on constraints over PA confirms the computational advantage of our incremental approach.

This paper presents a real-time method for detecting a fall at different phases using a wireless tri-axial accelerometer and reports the classification performance when the sensor is placed on different body parts. The proposed hybrid framework combines a rule-based knowledge representation scheme with a time control mechanism and machine-learning-based activity classification. Real-time temporal reasoning is performed using a standard rule-based inference engine. The framework is validated for fall detection performance, false alarm evaluation, and comparison with a highly cited baseline method. Based on a data set with 14 fall types (280 falls) collected from 16 subjects, the highest accuracy values of 86.54%, 87.31%, and 91.15% are obtained for fall detection at pre-impacts, impacts, and post-impacts, respectively. Without post-impact activity information, the side of the waist and chest are the best sensor positions, followed by the head, front of the waist, wrist, ankle, thigh, and upper arm. With post-impact activity information, the best sensor position is the side of the waist, followed by the head, wrist, front of the waist, thigh, chest, ankle, and upper arm. Most false alarms occur during transitions of lying postures. The proposed method is more robust to a variety of fall and activity types and yields better classification performance and false alarm rates compared with the baseline method. The results provide guidelines for sensor placement when developing a fall monitoring system.

Over the past few years, a new constraint-based formalism for temporal reasoning has been developed to represent and reason about Disjunctive Temporal Problems (DTPs). The class of DTPs is significantly more expressive than other problems previously studied in constraint-based temporal reasoning. In this paper we present a new algorithm for DTP solving, called Epilitis, which integrates strategies for efficient DTP solving from the previous literature, including conflict-directed backjumping, removal of subsumed variables, and semantic branching, and further adds no-good recording as a central technique. We discuss the theoretical and technical issues that arise in successfully integrating this range of strategies with one another and with no-good recording in the context of DTP solving. Using an implementation of Epilitis, we explore the effectiveness of various combinations of strategies for solving DTPs, and based on this analysis we demonstrate that Epilitis can achieve a nearly two order-of-magnitude speed-up over the previously published algorithms on benchmark problems in the DTP literature.

High-level human activities often have rich temporal structures that determine the order in which atomic actions are executed. We propose the Temporal Context Graph (TCG), a temporal reasoning model that integrates probabilistic inference with Allen’s interval algebra, to capture these temporal structures. TCGs are capable of modeling tasks with cyclical atomic actions and consisting of sequential and parallel temporal relations. We present Learning from Demonstration as the application domain where the use of TCGs can improve policy selection and address the problem of perceptual aliasing. Experiments validating the model are presented for learning two tasks from demonstration that involve structured human-robot interactions. The source code for this implementation is available at https://github.com/AssistiveRoboticsUNH/TCG.

e18747 Background: Accurate longitudinal cancer treatments are vital for establishing primary endpoints such as outcome as well as for the investigation of adverse events. However, many longitudinal therapeutic regimens are not well captured in structured electronic health records (EHRs). Thus, their recognition in unstructured data such as clinical notes is critical to gain an accurate description of the real-world patient treatment journey. Here, we demonstrate a scalable approach to extract high-quality longitudinal cancer treatments from lung cancer patients' clinical notes using a Bidirectional Long Short Term Memory (BiLSTM) and Conditional Random Fields (CRF) based natural language processing (NLP) pipeline. Methods: The lung cancer (LC) cohort of 4,698 patients was curated from the Mount Sinai Healthcare system (2003-2020). Two domain experts developed a structured framework of entities and semantics that captured treatment and its temporality. The framework included therapy type (chemotherapy, targeted therapy, immunotherapy, etc.), status (on, off, hold, planned, etc.) and temporal reasoning entities and relations (admin_date, duration, etc.) We pre-annotated 149 FDA-approved cancer drugs and longitudinal timelines of treatment on the training corpus. A NLP pipeline was implemented with BiLSTM-CRF-based deep learning models to train and then apply the resulting models to the clinical notes of LC cohort. A postprocessor was developed to subsequently post-coordinate and refine the output. We performed both cross-evaluation and independent evaluation to assess the pipeline performance. Results: We applied the NLP pipeline to the 853,755 clinical notes, and identified 1,155 distinct entities for 194 cancer generic drugs, including 74 chemotherapy drugs, 21 immunotherapy drugs, and 99 targeted therapy drugs. We identified chemotherapy, immunotherapy, or targeted therapy data for 3,509 patients in the LC cohort from the clinical notes. Compared to only 2,395 patients with cancer treatments in structured EHR, this pipeline identified cancer treatments from notes for additional 2,303 patients who did not have any available cancer treatment data in the structured EHR. Our evaluation schema indicates that the longitudinal cancer drug recognition pipeline delivers strong performance (named entity recognization for drugs and temporal: F1 = 95%; drug-temporal relation recognition: F1 = 90%). Conclusions: We developed a high-performance BiLSTM-CRF based NLP pipeline to recognize longitudinal cancer treatments. The pipeline recovers and encodes as twice as many patients with cancer treatments compared with structured EHR. Our study indicates deep NLP with temporal reasoning could substantially accelerate the extraction of treatment profiles at scale. The pipeline is adjustable and can be applied across different cancers.

Representing and reasoning about time dependent information is a key research issue in many areas of computer science and artificial intelligence. One of the best known and widely used formalisms for representing interval-based qualitative temporal information is Allen's interval algebra (IA). The fundamental reasoning task in IA is to find a scenario that is consistent with the given information. This problem is in general NP-complete.In this paper, we investigate how an interval-based representation, or IA network, can be encoded into a propositional formula of Boolean variables and/or predicates in decidable theories. Our task is to discover whether satisfying such a formula can be more efficient than finding a consistent scenario for the original problem. There are two basic approaches to modelling an IA network: one represents the relations between intervals as variables and the other represents the end-points of each interval as variables. By combining these two approaches with three different Boolean satisfiability (SAT) encoding schemes, we produced six encoding schemes for converting IA to SAT. In addition, we also showed how IA networks can be formulated into satisfiability modulo theories (SMT) formulae based on the quantifier-free integer difference logic (QF-IDL). These encodings were empirically studied using randomly generated IA problems of sizes ranging from 20 to 100 nodes. A general conclusion we draw from these experimental results is that encoding IA into SAT produces better results than existing approaches. More specifically, we show that the new point-based 1-D support SAT encoding of IA produces consistently better results than the other alternatives considered. In comparison with the six different SAT encodings, the SMT encoding came fourth after the point-based and interval-based 1-D support schemes and the point-based direct scheme. Further, we observe that the phase transition region maps directly from the IA encoding to each SAT or SMT encoding, but, surprisingly, the location of the hard region varies according to the encoding scheme. Our results also show a fixed performance ranking order over the various encoding schemes.

We present here a point-duration network formalism which extends the point algebra model to include additional variables that represent durations between points of time. Thereafter the new qualitative model is enlarged for allowing unary metric constraints on points and durations, subsuming in this way several point-based approaches to temporal reasoning. We deal with some reasoning tasks within the new models and we show that the main problem, deciding consistency, is NP-complete. However, tractable special cases are identified and we show efficient algorithms for checking consistency, finding a solution and obtaining the minimal network.

In many application areas, including planning, workflow, guideline and protocol management, the description of the domain involves composite and/or periodic events, mutually related by temporal constraints on the execution order. Such events represent ‘classes’, since they can be instantiated to specific executions of the plan, guideline etc., and each execution must ‘respect’ the temporal constraints imposed on the corresponding classes. The main goal of our work is to propose an approach dealing with the above-mentioned temporal phenomena. To achieve such an objective, the authors propose a tractable domain-independent temporal reasoner. This enhances the generality of our approach, which provides a domain-independent module that can be integrated with other software tools to solve temporal problems in specific domains. From the methodological point of view, the authors first devise a representation formalism coping with the aforesaid phenomena, and then they describe temporal constraint propagation alg...

We investigate the computational complexity of temporal reasoning in different time models such as totally-ordered, partially-ordered and branching time. Our main result concerns the satisfiability problem for point algebras and point algebras extended with disjunctions—for these problems, we identify all tractable subclasses. We also provide a number of additional results; for instance, we present a new time model suitable for reasoning about systems with a bounded number of unsynchronized clocks, we investigate connections with spatial reasoning and we present improved algorithms for deciding satisfiability of the tractable point algebras.

Video-grounded dialogues are very challenging due to (i) the complexity of videos which contain both spatial and temporal variations, and (ii) the complexity of user utterances which query different segments and/or different objects in videos over multiple dialogue turns. However, existing approaches to video-grounded dialogues often focus on superficial temporal-level visual cues, but neglect more fine-grained spatial signals from videos. To address this drawback, we proposed Bi-directional Spatio-Temporal Learning (BiST), a vision-language neural framework for high-resolution queries in videos based on textual cues. Specifically, our approach not only exploits both spatial and temporal-level information, but also learns dynamic information diffusion between the two feature spaces through spatial-to-temporal and temporal-to-spatial reasoning. The bidirectional strategy aims to tackle the evolving semantics of user queries in the dialogue setting. The retrieved visual cues are used as contextual information to construct relevant responses to the users. Our empirical results and comprehensive qualitative analysis show that BiST achieves competitive performance and generates reasonable responses on a large-scale AVSD benchmark. We also adapt our BiST models to the Video QA setting, and substantially outperform prior approaches on the TGIF-QA benchmark.

Temporal reasoning is one of the cognitive capabilities humans involve in communicating with others and everything appears related because of temporal reference. Therefore, in this paper a geometric dynamic temporal reasoning algorithm is proposed to solve the temporal reasoning problem, especially in autonomous planning and scheduling. This method is based on the representation of actions in a two dimensional coordination system. The main advantage of this method over others is that it uses tags to mark new constraints added into the constraint network, which leads the algorithm to deal with pending constraints rather than all constraints. This characteristic makes the algorithm suitable for temporal reasoning, where variables and constraints are always added dynamically. This algorithm can be used not only in intelligent planning, but also computational intelligence, real-time systems, and etc. The results show the efficiency of our algorithm from four cases simulating the planning and scheduling process.

While classical Description Logics (DLs) concentrate on the representation of static conceptual knowledge, recently there is a growing interest in DLs that, additionally, allow to capture the temporal aspects of conceptual knowledge. Such temporal DLs are based either on time points or on time intervals as the temporal primitive. Whereas point-based temporal DLs are well-investigated, this is not the case for interval-based temporal DLs: all known logics either suffer from rather limited expressive power or have undecidable reasoning problems. In particular, there exists no decidable interval-based temporal DL that provides for general TBoxes—one of the most important expressive means in modern description logics. In this paper, for the first time we define an interval-temporal DL that is equipped with general TBoxes and for which reasoning is decidable (and, more precisely, ExpTime-complete).

Time is deeply woven into how people perceive, and communicate about the world. Almost unconsciously, we provide our language utterances with temporal cues, like verb tenses, and we can hardly produce sentences without such cues. Extracting temporal cues from text, and constructing a global temporal view about the order of described events is a major challenge of automatic natural language understanding. Temporal reasoning, the process of combining different temporal cues into a coherent temporal view, plays a central role in temporal information extraction. This article presents a comprehensive survey of the research from the past decades on temporal reasoning for automatic temporal information extraction from text, providing a case study on how combining symbolic reasoning with machine learning-based information extraction systems can improve performance. It gives a clear overview of the used methodologies for temporal reasoning, and explains how temporal reasoning can be, and has been successfully integrated into temporal information extraction systems. Based on the distillation of existing work, this survey also suggests currently unexplored research areas. We argue that the level of temporal reasoning that current systems use is still incomplete for the full task of temporal information extraction, and that a deeper understanding of how the various types of temporal information can be integrated into temporal reasoning is required to drive future research in this area.

Performing driving behaviors based on causal reasoning is essential to ensure driving safety. In this work, we investigated how state-of-the-art 3D Convolutional Neural Networks (CNNs) perform on classifying driving behaviors based on causal reasoning. We proposed a perturbation-based visual explanation method to inspect the models' performance visually. By examining the video attention saliency, we found that existing models could not precisely capture the causes (e.g., traffic light) of the specific action (e.g., stopping). Therefore, the Temporal Reasoning Block (TRB) was proposed and introduced to the models. With the TRB models, we achieved the accuracy of $\mathbf{86.3\%}$, which outperform the state-of-the-art 3D CNNs from previous works. The attention saliency also demonstrated that TRB helped models focus on the causes more precisely. With both numerical and visual evaluations, we concluded that our proposed TRB models were able to provide accurate driving behavior prediction by learning the causal reasoning of the behaviors., Comment: Submitted to IEEE ICASSP 2020; Pytorch code will be released soon

Distant supervision (DS) is an important paradigm for automatically extracting relations. It utilizes existing knowledge base to collect examples for the relation we intend to extract, and then uses these examples to automatically generate the training data. However, the examples collected can be very noisy, and pose significant challenge for obtaining high quality labels. Previous work has made remarkable progress in predicting the relation from distant supervision, but typically ignores the temporal relations among those supervising instances. This paper formulates the problem of relation extraction with temporal reasoning and proposes a solution to predict whether two given entities participate in a relation at a given time spot. For this purpose, we construct a dataset called WIKI-TIME which additionally includes the valid period of a certain relation of two entities in the knowledge base. We propose a novel neural model to incorporate both the temporal information encoding and sequential reasoning. The experimental results show that, compared with the best of existing models, our model achieves better performance in both WIKI-TIME dataset and the well-studied NYT-10 dataset.

In order to solve the low utilization rate of spatio-temporal sequence information during non-cooperative target recognition of optical remote sensing images with deep learning method, this paper puts forward a new method for offshore non-cooperative target recognition and tracing based on spatio-temporal reasoning. In the first stage, this method uses YOLOv3 model through deep learning to recognize characteristics of large batch of offshore non-cooperative target images, and finish preliminary screening of suspicious target; in the second stage, it uses time weight function and Markov model to process and analyze temporal and spatial sequence information respectively during continuous tracing of the target and get the probability distribution of certain specific target in the two dimensions; in the third stage, it uses D-S evidence theory to process probability inforamtion in temporal and spatial dimensions and get target probability with higher reliability through fusion reasoning. The experimental verification shows the comprehensive recognition precision in the first stage is over 92%; subsequently the secondary recognition precision of the target can be improved for 35% through fusion reasoning of time weighted position distribution probability and Markov position transfer probability. Results show the reasoning elements of spatio-temporal sequences obvious improve precision of secondary discovery after the non-cooperative target is lost, and provide new thinking for non-cooperative target tracing with intelligent method.

In this paper, we introduce an automated reasoning system for learning object behaviors and interactions through the observation of event sequences. We use an existing system to learn the models of objects and further extend it to model more complex behaviors. Furthermore, we propose a spatio–temporal reasoning based learning method for reasoning about interactions among objects. Experience gained through learning is to be used for achieving goals by these objects. We take The Incredible Machine game (TIM) as the main testbed to analyze our system. Tutorials of the game are used to train the system. We analyze the results of our reasoning system on four different input types: a knowledge base of relations; spatial information; temporal information; and spatio–temporal information from the environment. Our analysis reveals that if a knowledge base about relations is provided, most of the interactions can be learned. We have also demonstrated that our learning method which incorporates both spatial and temporal information gives close results to that of the knowledge-based approach. This is promising as gathering spatio–temporal information does not require prior knowledge about relations. Our second analysis of the spatio–temporal reasoning method in the Electric Box computer game domain verifies the success of our approach.

Computation tree logic (CTL) is known to be one of the most useful temporal logics for verifying concurrent systems by model checking technologies. However, CTL is not sufficient for handling inconsistency-tolerant and probabilistic accounts of concurrent systems. In this paper, a paraconsistent (or inconsistency-tolerant) probabilistic computation tree logic (PpCTL) is derived from an existing probabilistic computation tree logic (pCTL) by adding a paraconsistent negation connective. A theorem for embedding PpCTL into pCTL is proven, thereby indicating that we can reuse existing pCTL-based model checking algorithms. A relative decidability theorem for PpCTL, wherein the decidability of pCTL implies that of PpCTL, is proven using this embedding theorem. Some illustrative examples involving the use of PpCTL are also presented.

Spatio-temporal reasoning plays a significant role in situation management that is performed by intelligent agents (human or machine) by affecting how the situations are recognized, interpreted, acted upon or predicted. Many definitions and formalisms for the notion of spatio-temporal reasoning have emerged in various research fields including psychology, economics and computer science (computational linguistics, data management, control theory, artificial intelligence and others). In this paper we examine the role of spatio-temporal reasoning in situation management, particularly how to resolve situations that are described by using spatio-temporal relations among events and situations. We discuss a model for describing context sensitive temporal relations and show have the model can be extended for spatial relations.

The research is based on the designing of Clinical Temporal Mediator for medical domain. The Clinical Temporal Mediator incorporates the concept of artificial intelligence for performing temporal reasoning tasks. The designing of reasoning system involves the implementation of various mathematical models of insulin-glucose metabolism. The reasoning system consists of three subsystems: Nuti-Diet subsystem, Insulin-Glucose subsystem and Therapy Planner and Diagnosis subsystem. The paper discusses about the designing of TPD subsystems. The temporal mediator perform diagnosis on patient's time oriented database and also suggest therapy planning for diabetes mellitus patient.

Robots used for inspection, package deliveries, moving of goods, and other logistics operations are often required to visit certain locations within specified time bounds. This gives rise to a challenging problem as it requires not only planning collision-free and dynamically-feasible motions but also reasoning temporally about when and where the robot should be. While significant progress has been made in integrating task and motion planning, there are still no effective approaches for multi-goal motion planning when both dynamics and time windows must be satisfied. To effectively solve this challenging problem, this paper develops an approach that couples temporal planning over a discrete abstraction with sampling-based motion planning over the continuous state space of feasible motions. The discrete abstraction is obtained by imposing a roadmap which captures the connectivity of the free space. At each iteration of a core loop, the approach first invokes the temporal planner to find a solution over the roadmap abstraction. In a second step, the approach uses sampling to expand a motion tree along the regions associated with the discrete solution. Experiments are conducted with second-order ground and aerial vehicle models operating in complex environments. Results demonstrate the efficiency and scalability of the approach as we increase the number of goals and the difficulty of satisfying the time bounds.

Aspects of time, change, evolution, temporal reasoning and decision-making remain in the focus of metadata and ontology engineering because many related challenges are yet to be fully addressed. In this paper, we present ontology ALLEN+ as a tool to reason with imperfect temporal information. We created a rule-set SWRL on top of OWL capable of temporal reasoning with partially incomplete and heterogeneous information. The ontology allows to have either quantitative, qualitative or hybrid information about temporal points and intervals, and the rules are capable of both ways transitions between different representations. We show how to use context of available imperfect temporal information to improve results of the composition operation of Allen's interval algebra, and we design rules for composition-in-context operation. We discover that additional context reduces the overall uncertainty of the composition and enables about 20% progress in overall quality of the composition and therefore in potential reasoning and decision-making.

A generalization of Allen's interval-based approach to temporal reasoning is presented. The notion of ‘conceptual neighborhood’ of qualitative relations between events is central to the presented approach. Relations between semi-intervals rather than intervals are used as the basic units of knowledge. Semi-intervals correspond to temporal beginnings or endings of events. We demonstrate the advantages of reasoning on the basis of semi-intervals: (1) semi-intervals are rather natural entities both from a cognitive and from a computational point of view; (2) coarse knowledge can be processed directly; computational effort is saved; (3) incomplete knowledge about events can be fully exploited; (4) incomplete inferences made on the basis of complete knowledge can be used directly for further inference steps; (5) there is no trade-off in computational strength for the added flexibility and efficiency; (6) for a natural subset of Allen's algebra, global consistency can be guaranteed in polynomial time; (7) knowledge about relations between events can be represented much more compactly.

In this paper we investigate if it is possible and useful to reason about time within social/normative multi-agent systems (MAS) by taking into account the general guidelines of tense logic. We focus on the combination of special-purpose logics: we provide a formal account in which a minimal temporalization helps in reasoning about time in an abstract way. We also explore a new variant of deontic tense logic by using a hybrid tense logic. The accounts provided allow to model temporal provisions within both particular norms and general legal principles, and also help in the detection of breaches of good faith and confidence., Facultad de Ciencias Jurídicas y Sociales, Facultad de Informática

This chapter focuses on the idea that one is born with a highly structured brain. This can be illustrated by the trion model of the cortex. The trion model is a highly structured mathematical realization of the Mountcastle organization principle with the column as the basic neuronal network in mammalian cortex. Studies of the trion model led to the prediction that music could enhance spatial-temporal reasoning. It also states that brain have the innate ability to recognize and manipulate patterns in space and time. This chapter presents behavioral experiments that support this prediction. These experiments include the Mozart effect listening experiment with college students and the preschool experiment involving piano keyboard lessons. It is observed that college students scored significantly higher on spatial-temporal reasoning after listening to the first 10 minutes of the Mozart Sonata, but not for other controls. It is also noted that the music training at an early age might act as exercise for higher brain function.

Temporal reasoning, in the form of propagation of temporal constraints, is an important topic in Artificial Intelligence. The current literature in the area is moving from the treatment of "crisp" temporal constraints to fuzzy or probabilistic constraints, to account for different forms of uncertainty and\or preferences. However, despite the huge amount of work in the area, the spectrum of possible solutions has not been fully explored. In particular, no probabilistic approach coping with quantitative temporal constraints has been proposed yet. We overcome such a limitation of the current literature by proposing the first approach providing (i) a probabilistic extension to quantitative constraints, supporting the possibility of expressing alternative distances between time points, and of associating a probability to each alternative, and (ii) a framework for the propagation of such temporal constraints.

Multi-dimensional spatial occlusion relation (MSO) is an observer-centred model which could express the relation between the images of two bodies x and y from a viewpoint v. We study the basic reasoning method of MSO, then extend MSO to spatial-temporal field by adding time feature to it, and the related definitions are given.

There exists a precise time period during which a given fact such as an event or a status is valid. In this paper, we propose a new approach to determine the validity time of a fact statement by leveraging unstructured and noisy data from the Web, while overcoming the limitations of existing natural language processing technologies designed for the same task. Given a fact and its temporal relevance text, the proposed solution first constructs a Semantic Bayesian Network, then estimates the validity probabilities of time points using the constructed network. In the interest of dealing with the semantic complexity of keywords, we also present a technique based on relative standard deviation to estimate distortion risks of keywords and incorporate their risk estimation into the process of probability computation. Our experiments on real data shows that the proposed approach can achieve considerable improvements in performance over 2 state-of-the-art alternatives, and the proposed risk reduction technique can effectively improve validity time reasoning’s precision.

Temporal reasoning is one of the cognitive capabilities humans involve in communicating with others and everything appears related because of temporal reference. Therefore, in this paper a geometric dynamic temporal reasoning algorithm is proposed to solve the temporal reasoning problem, especially in autonomous planning and scheduling. This method is based on the representation of actions in a two dimensional coordination system. The main advantage of this method over others is that it uses tags to mark new constraints added into the constraint network, which leads the algorithm to deal with pending constraints rather than all constraints. This characteristic makes the algorithm suitable for temporal reasoning, where variables and constraints are always added dynamically. This algorithm can be used not only in intelligent planning, but also computational intelligence, real-time systems, and etc. The results show the efficiency of our algorithm from four cases simulating the planning and scheduling process.

Human group activity recognition is still a challenging task in computer vision. However, most of the works focus on the feature extraction and the analysis of the motion trajectories for recognizing the multi-person or group activities in surveillance videos. A qualitative spatio-temporal relation based on Hidden Markov Model (HMM) method is proposed to classify human group activities. We first propose Unified QTCB relations to represent the relations of the group. And then Unified QTCB relation based on HMM is proposed for group activity classification. Experiments are successfully conducted on the human group activity video database, and the performance of our approach is evaluated and compared with some other methods. The results show that our approach is more suitable for recognizing group activities.

Reasoning with temporal information in natural language text has attracted great attention due to its potential applications in summarization, question answering and other tasks. For example, the chronological ordering of events described in a text is important for presenting the information in the summary. Linking information in a natural language text with temporal relations is essential in question answering system to address time sensitive and dynamic world. A crucial first step towards the computational treatment of the temporal information in these applications is the automatic extraction of events described in the text and identification of temporal relations to link these events. Much of the work done in this direction can be classified as -Annotation schemes for identification of events and time implicit in the text, linking the events using temporal relations and Temporal reasoning for solving practical applications. The present paper is a survey of various proposals to address these issues. Various annotation schemas developed to represent temporal information in natural language text. A discussion of the frameworks for temporal reasoning and tractable classes is described. The usefulness of these models to applications such as summarization and question answering are also presented.