Integrated Temporal Reasoning with Periodic Events

In many areas of Computer Science, including planning, workflows, guidelines, and protocol management, one has to deal with abstract plans, procedures, or schedules involving temporal constraints between classes of actions that have to be repeated at periodic times and may be instantiated in different ways for different executions of the plans (procedures, schedules). In this paper we propose an integrated framework to deal with both qualitative temporal constraints on classes of actions and temporal constraints between instances of actions, in which temporal reasoning is used to amalgamate both types of constraints and to check their consistency. In particular, we consider an expressive formalism to deal with temporal constraints between classes of actions (with special attention to periodic actions) which takes into account different components such as frame times, numeric quantification, periods, and qualitative relations. We define the notions of (contextual) concretization of qualitative temporal constraints between classes and use this notion to formally define the consistency of a knowledge base of temporal constraints between classes and a set of temporal constraints on instances, and to define the algorithm for checking such a consistency. An application for scheduling lessons in a school is shown in an example.     

Complexity classification in qualitative temporal constraint reasoning

We study the computational complexity of the qualitative algebra which is a temporal constraint formalism that combines the point algebra, the point-interval algebra and Allen's interval algebra. We identify all tractable fragments and show that every other fragment is NP-complete.     

Toward a comprehensive treatment of temporal constraints about periodic events

In this article, we propose an Allen‐like approach to deal with different types of temporal constraints about periodic events. We consider the different components of such constraints (thus, unlike Allen, we also take into account quantitative constraints) including frame times, user‐defined periods, qualitative temporal constraints, and numeric quantifiers and the interactions between such components. We propose a specialized high‐level formalism to represent temporal constraints about periodic events; temporal reasoning on the formalism is performed by a path‐consistency algorithm repeatedly applying our operations of inversion, intersection, and composition and by a specialized reasoner about periods and numeric quantification. The high‐level formalism has been designed in such a way that different types of temporal constraints about periodic events can be represented in a compact and (hopefully) user‐friendly way and path‐consistency‐based temporal reasoning on the formalism can be performed in polynomial time. We also prove that our definitions of inversion, intersection, and composition and, thus, of our path‐consistency algorithm, are correct. This article also sketches the general architecture of the temporal manager for periodic events (TeMP⁺), that has been designed on the basis of our approach. As a working example, we show an application of our approach to scheduling in a school. © 2003 Wiley Periodicals, Inc.     

Constraint Reasoning about Repeating Events: Satisfaction and Optimization

Effective manipulation of temporal information about periodic events is required for solving complex problems such as long‐range scheduling or querying temporal information. Furthermore, many problems involving repeating events involve the optimization of temporal aspects of these events (e.g., minimizing make‐span in job‐shop scheduling). In this paper, a constraint‐based formulation of reasoning problems with repeating events is presented, and its complexity is analyzed for a range of problems. Optimization constraints are interpreted formally using the Semiring CSPs (SCSP) representation of optimization in constraint reasoning. This allows for familiar algorithms such as branch‐and‐bound to be applied to solving them.     

Probabilistic temporal reasoning and its application to fossil power plant operation

Many real-world applications, such as industrial diagnosis, require an adequate representation and inference mechanism that combines uncertainty and time. In this work, we propose a novel approach for representing dynamic domains under uncertainty based on a probabilistic framework, called temporal nodes Bayesian networks (TNBN). The TNBN model is an extension of a standard Bayesian network, in which each temporal node represents an event or state change of a variable and the arcs represent causal–temporal relationships between nodes. A temporal node has associated a probability distribution for its time of occurrence, where time is discretized in a finite number of temporal intervals; allowing a different number of intervals for each node and a different duration for the intervals within a node (multiple granularity). The main difference with previous probabilistic temporal models is that the representation is based on state changes at different times instead of state values at different times. Given this model, we can reason about the probability of occurrence of certain events, for diagnosis or prediction, using standard probability propagation techniques developed for Bayesian networks. The proposed approach is applied to fossil power plant diagnosis through two detailed case studies: power load increment and control level system failure. The results show that the proposed formalism could help to improve power plant availability through early diagnosis of events and disturbances.     

A framework for knowledge-based temporal abstraction

A new domain-independent knowledge-based inference structure is presented, specific to the task of abstracting higher-level concepts from time-stamped data. The framework includes a model of time, parameters, events and contexts. A formal specification of a domain's temporal abstraction knowledge supports acquisition, maintenance, reuse and sharing of that knowledge.

The knowledge-based temporal abstraction method decomposes the temporal abstraction task into five subtasks. These subtasks are solved by five domain-independent temporal abstraction mechanisms. The temporal abstraction mechanisms depend on four domain-specific knowledge types: structural, classification (functional), temporal semantic (logical) and temporal dynamic (probabilistic) knowledge. Domain values for all knowledge types are specified when a temporal abstraction system is developed.

The knowledge-based temporal abstraction method has been implemented in the RÉSUMÉ system and has been evaluated in several clinical domains (protocol-based care, monitoring of children's growth and therapy of diabetes) and in an engineering domain (monitoring of traffic control), with encouraging results.     

An intensional approach to qualitative and quantitative periodicity‐dependent temporal constraints

In this paper, we propose a framework for representing and reasoning about qualitative and quantitative temporal constraints between periodic events. In particular, our contribution is twofold: (i) we provide a formalism to deal with both qualitative and quantitative “periodicity‐dependent” constraints between repeated events, considering user‐defined periodicities as well; and (ii) we propose an intensional approach to temporal reasoning, which is based on the operations of intersection and composition. Such a comprehensive approach, to the best of our knowledge, represents an innovative contribution that integrates and extends results from both the artificial intelligence and the temporal databases literature. © 2009 Wiley Periodicals, Inc.     

Dynamic consistency of fuzzy conditional temporal problems

Conditional Temporal Problems (CTPs) can deal simultaneously with uncertainty and temporal constraints, allowing for the representation of temporal and conditional plans. CTPPs generalize CTPs by adding preferences to the temporal constraints and by allowing fuzzy thresholds for the occurrence of some events. Here we focus on dynamic consistency of CTPPs, the most useful notion of consistency in practice. We describe an algorithm which allows for testing if a CTPP is dynamically consistent and we study its complexity. Simple temporal problems with preferences and uncertainty (STPPUs) are another formalism to model temporal constraints where preference and uncertainty coexist. While uncertainty is CTPPs is modeled via conditions on the execution of variables, in STPPUs it is modelled by means of events whose occurrence time is not known. We consider the relation between CTPPs and STPPUs and we show that the former framework is at least as expressive as the second one. Such a result is obtained by providing a polynomial mapping from STPPUs to CTPPs.     

Combining task execution and background knowledge for the verification of medical guidelines

The use of a medical guideline can be seen as the execution of computational tasks, sequentially or in parallel, in the face of patient data. It has been shown that many of such guidelines can be represented as a ‘network of tasks’, i.e., as a number of steps that have a specific function or goal. To investigate the quality of such guidelines we propose a formalization of criteria for good practice medicine a guideline should comply to. We use this theory in conjunction with medical background knowledge to verify the quality of a guideline dealing with diabetes mellitus type 2 using the interactive theorem prover KIV. Verification using task execution and background knowledge is a novel approach to quality checking of medical guidelines.     

A knowledge server for reasoning about temporal constraints between classes and instances of events

Reasoning with temporal constraints is a ubiquitous issue in many computer science tasks, for which many dedicated approaches have been and are being built. In particular, in many areas, including planning, workflow, guidelines, and protocol management, one needs to represent and reason with temporal constraints between classes of events (e.g., between the types of actions needed to achieve a goal) and temporal constraints between instances of events (e.g., between the specific actions being executed). The temporal constraints between the classes of events must be inherited by the instances, and the consistency of both types of constraints must be checked. In this article, we design a general‐purpose domain‐independent knowledge server dealing with these issues. In particular, we propose a formalism to represent temporal constraints, and we point out two orthogonal parameters that affect the definition of reasoning algorithms operating on them. We then show four algorithms to deal with inheritance and to perform temporal consistency checking (depending on the parameters) and we study their properties. Finally, we report the results we obtained by applying our system to the treatment of temporal constraints in clinical guidelines. © 2004 Wiley Periodicals, Inc. Int J Int Syst 19: 919–947, 2004.     

Querying Temporal Constraint Networks: A Unifying Approach

We develop the scheme of indefinite constraint databases using first-order logic as our representation language. When this scheme is instantiated with temporal constraints, the resulting formalism is more expressive than standard temporal constraint networks. The extra representational power allows us to express temporal knowledge and queries that have been impossible to express before. To make our claim more persuasive, we survey previous works on querying temporal constraint networks and show that they can be viewed as an instance of the scheme of indefinite constraint databases.     

TCPN的组合可调度分析

时间约束Petri网(Timing Constraints Petri nets,简称TCPNs)是一类重要的时间Petri网系统.针对TCPNs中变迁可调度原始语义的不足,本文对相关定义重新定义,丰富并完善了TPCNs理论.本文首先给出了新的针对单个变迁或变迁序列的可调度分析策略.如果一个特定的变迁序列是可调度的,则相应的活动序列也同样可以顺利地完成自身的执行;否则,不可调度的变迁需要调整自己的时间约束;然后提出了组合式的可调度分析策略以分析复杂变迁序列,最后提出时序一致性的概念.     

First-order temporal pattern mining with regular expression constraints

Previous studies on mining sequential patterns have focused on temporal patterns specified by some form of propositional temporal logic. However, there are some interesting sequential patterns, such as the multi-sequential patterns, whose specification needs a more expressive formalism, the first-order temporal logic. Multi-sequential patterns appear in different application contexts, for instance in spatial census data mining, which is the target application of the study developed in this paper. We extend a well-known user-controlled tool, based on regular expressions constraints, to the multi-sequential pattern context. This specification tool enables the incorporation of user focus into the mining process. We present MSP-Miner, an Apriori-based algorithm to discover all frequent multi-sequential patterns satisfying a user-specified regular expression constraint.     

Dynamic simulation of action at operations level

The attempt of using lumped or agent-based simulation models to support operations management in production systems puts action modelling to the fore. To fill the gap of classical decision-support systems ignoring human agents’ practices, a modelling framework of action at operations level is proposed. This framework aims at answering two questions: How to represent action? How to represent the management of action? Every action (i.e., what is actually done by an agent) is represented by a binary function of time governed by events detected upon processes of various kinds: artefacts (clocks or schedules), external processes occurring in the environment, other actions. In turn, every action exerts its effect on target processes. This modelling framework allows one to simulate the interpretation of ongoing actions by using temporal or propositional logics and operations management behaviors through plan specification and execution, action composition, and resource allocation to concurrent actions. It enables complex activity systems to be represented and management options to be tested by simulation. These capacities are illustrated on the example of a farming system. The main benefits and issues raised by this dynamical system approach close to the ‘situated’ (vs. ‘planned’) action paradigm are discussed in the light of related works in Artificial intelligence. Future directions of research are drawn, namely that of how to scale up this lower-level representation of action to the higher-level representation of agents endowed with skills relevant at the level of the individual (e.g., anticipation).     

Proximity measures for link prediction based on temporal events

Link prediction is a well-known task from the Social Network Analysis field that deals with the occurrence of connections in a network. It consists of using the network structure up to a given time in order to predict the appearance of links in a close future. The majority of previous work in link prediction is focused on the application of proximity measures (e.g., path distance, common neighbors) to non-connected pairs of nodes at present time in order to predict new connections in the future. New links can be predicted for instance by ordering the pairs of nodes according to their proximity scores. A limitation usually observed in previous work is that only the current state of the network is used to compute the proximity scores, without taking any temporal information into account (i.e., a static graph representation is adopted). In this work, we propose a new proximity measure for link prediction based on the concept of temporal events. In our work, we defined a temporal event related to a pair of nodes according to the creation, maintenance or interruption of the relationship between the nodes in consecutive periods of time. We proposed an event-based score which is updated along time by rewarding the temporal events observed between the pair of nodes under analysis and their neighborhood. The assigned rewards depend on the type of temporal event observed (e.g., if a link is conserved along time, a positive reward is assigned). Hence, the dynamics of links as the network evolves is used to update representative scores to pairs of nodes, rewarding pairs which formed or preserved a link and penalizing the ones that are no longer connected. In the performed experiments, we evaluated the proposed event-based measure in different scenarios for link prediction using co-authorship networks. Promising results were observed when the proposed measure was compared to both static proximity measures and a time series approach (a more competitive method) that also deploys temporal information for link prediction.     

On point-duration networks for temporal reasoning

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.     

Incorporating cardinality constraints and synonym rules into conditional functional dependencies

We propose an extension of conditional functional dependencies (CFDs), denoted by CFDcs, to express cardinality constraints, domain-specific conventions, and patterns of semantically related constants in a uniform constraint formalism. We show that despite the increased expressive power, the satisfiability and implication problems for CFDcs remain NP-complete and coNP-complete, respectively, the same as their counterparts for CFDs. We also identify tractable special cases.     

Causal temporal constraint networks for representing temporal knowledge

In this work we describe causal temporal constraint networks (CTCN) as a new computable model for representing temporal information and efficiently handling causality. The proposed model enables qualitative and quantitative temporal constraints to be established, introduces the representation of causal constraints, and suggests mechanisms for representing inexact temporal knowledge. The temporal handling of information is achieved by structuring the information in different interpretation contexts, linked to each other through an inference mechanism which obtains interpretations that are consistent with the original temporal information. In carrying out inferences, we take into account the temporal relationships between events, the possible inexactitude associated with the events, and the atemporal or static information which affects the interpretation pattern being considered. The proposed schema is illustrated with an application developed using the CommonKADS methodology.