Search

International audience; In this paper, we propose an ontology-based approach for representing and reasoning about certain and uncertain temporal data. Ithandles temporal data in terms of quantitative time intervals and points and the qualitative relations between them (e.g., “before”). Itincludes three parts.(1)We extend the 4D-fluents approach with certain ontological components to represent the handled temporaldata in OWL 2.(2)We extend the Allen’s interval algebra to reason about certain and uncertain time intervals. We adapt theserelations to allow relating a time interval and a time point, and two time points. All relations can be used for temporal reasoning bymeans of transitivity tables.(3)The extended Allen’s algebra instantiates the 4D-fluents-based representation. Inferences are basedon SWRL rules. Based on this ontology, a prototype is implemented and integrated into an ontology-based memory prosthesis forAlzheimer’s patients to handle certain and uncertain temporal data inputs.

Objective Elderly people who live alone can be assisted by home monitoring systems that identify risk scenarios such as falls, fatigue symptoms or burglary. Given that these systems have to manage spatiotemporal data, human intervention is required to validate automatic alarms due to the high number of false positives and the need for context interpretation. The goal of this work was to provide tools to support human action, to identify such potential risk scenarios based on spatiotemporal data visualisation. Methods and materials We propose the MTA (multiple temporal axes) model, a visual representation of temporal information of the activity of a single person at different locations. The main goal of this model is to visualize the behaviour of a person in their home, facilitating the identification of health-risk scenarios and repetitive patterns. We evaluate the model's insight capacity compared with other models using a standard evaluation protocol. We also test its practical suitability of the MTA graphical model in a commercial home monitoring system. In particular, we implemented 8VISU, a visualization tool based on MTA. Results MTA proved to be more than 90% accurate in identify non-risk scenarios, independently of the length of the record visualised. When the spatial complexity was increased (e.g. number of rooms) the model provided good accuracy form up to 5 rooms. Therefore, user preferences and user performance seem to be balanced. Moreover, it also gave high sensitivity levels (over 90%) for 5–8 rooms. Fall is the most recurrent incident for elderly people. The MTA model outperformed the other models considered in identifying fall scenarios (66% of correctness) and was the second best for burglary and fatigue scenarios (36% of correctness). Our experiments also confirm the hypothesis that cyclic models are the most suitable for fatigue scenarios, the Spiral and MTA models obtaining most positive identifications. Conclusions In home monitoring systems, spatiotemporal visualization is a useful tool for identifying risk and preventing home accidents in elderly people living alone. The MTA model helps the visualisation in different stages of the temporal data analysis process. In particular, its explicit representation of space and movement is useful for identifying potential scenarios of risk, while the spiral structure can be used for the identification of recurrent patterns. The results of the experiments and the experience using the visualization tool 8VISU proof the potential of the MTA graphical model to mine temporal data and to support caregivers using home monitoring infrastructures.

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.

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.

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).

Our 3D-model-based Computer Vision subsystem extracts vehicle trajectories from monocular digitized videos recording road vehicles in inner-city traffic. Steps are documented which import these quantitative geometrical results into a conceptual representation based on a Fuzzy Metric-Temporal Horn Logic (FMTHL, see [K.H. Schäfer, Unscharfe zeitlogische Modellierung von Situationen und Handlungen in Bildfolgenauswertung und Robotik, Dissertation, 1996]). The facts created by this import step can be understood as verb phrases which describe elementary actions of vehicles in image sequences of road traffic scenes. The current contribution suggests a complete conceptual representation of elementary vehicle actions and reports results obtained by an implementation of this approach from real-world traffic videos.

Introduction. Time is an essential element in medical data and knowledge which is intrinsically connected with medical reasoning tasks. Many temporal reasoning mechanisms use constraint-based approaches. Our previous research demonstrates that electronic discharge summaries can be modeled as a simple temporal problem (STP).Objective. To categorize temporal expressions in clinical narrative text and to propose and evaluate a temporal constraint structure designed to model this temporal information and to support the implementation of higher-level temporal reasoning.Methods. A corpus of 200 random discharge summaries across 18 years was applied in a grounded approach to construct a representation structure. Then, a subset of 100 discharge summaries was used to tally the frequency of each identified time category and the percentage of temporal expressions modeled by the structure. Fifty random expressions were used to assess inter-coder agreement.Results. Six main categories of temporal expressions were identified. The constructed temporal constraint structure models time over which an event occurs by constraining its starting time and ending time. It includes a set of fields for the endpoint(s) of an event, anchor information, qualitative and metric temporal relations, and vagueness. In 100 discharge summaries, 1961 of 2022 (97%) identified temporal expressions were effectively modeled using the temporal constraint structure. Inter-coder evaluation of 50 expressions yielded exact match in 90%, partial match with trivial differences in 8%, partial match with large differences in 2%, and total mismatch in 0%.Conclusion. The proposed temporal constraint structure embodies a sufficient and successful implementation method to encode the diversity of temporal information in discharge summaries. Placing data within the structure provides a foundational representation upon which further reasoning, including the addition of domain knowledge and other post-processing to implement an STP, can be accomplished.

Temporal logics are well suited for the specification and verification of systems of communicating agents. In this paper we adopt a social approach to agent communication, where communication is described in terms of changes to the social state, and interaction protocols in terms of permissions and commitments among agents. In particular, we make use of a temporal action theory, where a protocol is defined as a set of temporal constraints, which specify the effects and preconditions of the communicative actions on the social state. The paper addresses the problem of combining two protocols to define a new more specialized protocol, and presents a notion of protocol specialization which is based on the well known notion of stuttering equivalence between runs. Moreover, the paper studies sufficient conditions (verifiable from the protocol specification) which guarantee that the combination of two protocols is legal.

In early moments of computer systems development, computer engineers typically draw interaction diagrams, occasionally annotated with timing constraints, to reason about the specification of the system behavior. One of the most popular of these diagrams is the Message Sequence Chart (MSC). However, not always does the intended behavior described by MSCs correspond to their actual behavior. To help the formal verification of their actual behavior, i.e. their temporal properties, this paper describes an interpretation of basic timed MSCs in a temporal framework that formally represents, in a unified model, both the qualitative and the metric temporal information conveyed in these intuitive diagrams. The framework solves the verification problems in polynomial time and lays the foundation of an automatic tool.

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).

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.

International audience; We propose in this paper a new approach for the modelling and recognition of temporal scenarii. A scenario is represented by three different structures. The first one models the logical dependency between the elements of the scenario, using possibilistic logic, while the second one is the minimal temporal graph representing all temporal constraints between the events. The third structure explains the way the matching between observations and scenarii has to be done. The consistency between the three structures is ensured.

This paper presents a formalism called Time Interval Petri Nets (TIPNs), which are designed to support a qualitative simulation of temporal concurrent processes. One of the key features of TIPNs is a uniform use of time intervals throughout the model. This enables a natural and efficient representation of temporal uncertainty in inputs, outputs, and intermediate states of the qualitative simulation. This is required because the exact time of key events, such as the start time of a fire crisis, is typically not known with certainty. Likewise, output conclusions of the qualitative simulation include earliest time and guaranteed time of key events that can be used by a decision maker to select the most appropriate action.Results are described of a TIPN-based qualitative simulator constructed in the domain of ship damage control. The simulator was created to replace an existing quantitative simulator which was too slow to support envisionment-based real-time decision making in this domain. The experimental results showed a speedup of four to five orders of magnitude which enables hyper-real time qualitative prediction of consequences of multiple competing actions. An automated shipboard damage control decision-making system incorporating a TIPN-based qualitative simulator achieved a 318% improvement over human subject matter experts in a large-scale simulated exercise of over 500 scenarios.

Many problems in scheduling, planning, and natural language understanding have been formulated in terms of temporal constraint satisfaction problems (TCSP). These problems have been extensively investigated in the AI literature providing effective solutions for some fragments of the general model. Independently, there has been an effort in the data and knowledge management research community for the formalization of the concept of time granularity and for its applications. This paper considers a framework for integrating the notion of time granularity into TCSP, and investigates the problems of consistency and network solution, which, in this context, involve complex manipulation of the periodic sets representing time granularities. A sound and complete algorithm for consistency checking and for deriving a solution is presented. The paper also investigates the algorithm's computational complexity and several optimization techniques specific to the multi-granularity context. An application to e-commerce workflows illustrates the benefits of the framework and the need for specific reasoning tools.

The “agent program” framework introduced by Eiter, Subrahmanian and Pick (Artificial Intelligence, 108(1-2), 1999), supports developing agents on top of arbitrary legacy code. Such agents are continuously engaged in an “event occurs→ think → act→ event occurs ... ” cycle. However, this framework has two major limitations: (1) all actions are assumed to have no duration, and (2) all actions are taken now, but cannot be scheduled for the future. In this paper, we present the concept of a “temporal agent program” (tap for short) and show that using taps, it is possible to build agents on top of legacy code that can reason about the past and about the future, and that can make temporal commitments for the future now. We develop a formal semantics for such agents, extending the concept of a status set proposed by Eiter et al., and develop algorithms to compute the status sets associated with temporal agent programs. Last, but not least, we show how taps support classical negotiation methods (as well as some new ones) and classical auction methods (as well as some new ones).

We propose a general and uniform modal framework for the Event Calculus (EC) and its skeptical and credulous variants. The resulting temporal formalism, called the Generalized Modal Event Calculus (GMEC), extends considerably the expressive power of EC when information about the ordering of events is incomplete. It provides means of inquiring about the evolution of the maximal validity intervals of properties relative to all possible refinements of the ordering data by allowing a free mix of propositional connectives and modal operators. We first give a semantic definition of GMEC and relate it to known systems of modal logic; then, we propose a declarative encoding of GMEC in the language of hereditary Harrop formulas and prove the soundness and completeness of the resulting logic programs.

We characterise the set of subalgebras of Allen's algebra which have a tractable satisfiability problem, and in addition contain certain basic relations. The conclusion is that no tractable subalgebra dial is not known in the literature can contain more than the three basic relations (≡), (b) and ( b⪰ ), where bϵd, o, s, f. This means that concerning algebras for specifying complete knowledge about temporal information, there is no hope of finding yet unknown classes with much expressivity. We also classify completely some cases where we cannot even express complete information (but close to complete), showing that there are exactly two maximal tractable algebras containing the relation (≺ ≻), exactly two containing the relation (≺ ≻ m m≤), and exactly three containing the relation (≺ m). The algebras containing (≺ ≻) can express the notion of sequentiality; thus we have a complete characterization of tractable inference using that notion.

In formal approaches to commonsense reasoning about actions, the Ramification Problem denotes the problem of handling indirect effects which implicitly derive from so-called state constraints. We pursue a new distinction between two kinds of state constraints which will be proved crucially important for solving the general Ramification Problem. Steady constraints never, not even for an instant, cease being in force. As such they give rise to truly instantaneous indirect effects of actions. Stabilizing state constraints, on the other hand, may be suspended for a short period of time after an action has occurred. Indirect effects deriving from these constraints materialize with a short lag. This hitherto neglected distinction is shown to have essential impact on the Ramification Problem: if stabilizing state constraints interact, then approaches not based on so-called causal propagation prove defective. But causal propagation, too, is shown to risk producing anomalous models, in case steady and stabilizing indirect effects are propagated indiscriminately. Motivated by these two observations, we improve the theory of causal relationships and its Fluent Calculus axiomatization, which both are methods of causal propagation, so as to properly handle the distinction between steady and stabilizing constraints.

Communication can be more effective when several media (such as text, speech, or graphics) are integrated and coordinated to present information. This changes the nature of media-specific generation (e.g., language or graphics generation), which must take into account the multimedia context in which it occurs. This paper presents work on coordinating and integrating speech, text, static and animated three-dimensional graphics, and stored images, as part of several systems we have developed at Columbia University. A particular focus of our work has been on the generation of presentations that brief a user on information of interest

This paper presents an integrated view of a wide range of planning systems derived from different theoretical foundations. The work is motivated by the need to provide a clear foundation from which a systematic study of search and representation issues in planning can be conducted. An evolutionary path is identified which shows how the classical (state-based) planning strategy can be incrementally refined into strategies capable of generating parallel plans. This is achieved by considering a succession of planning strategies having a progressively deeper involvement with interval-based representations. Each strategy is defined in terms of a plan representation, truth criterion and an example plan generation procedure which maps out a clearly specified search graph. The capabilities and limitations of each strategy are compared. This approach enables much of the wisdom embedded in existing planners based on the specified strategies to be distilled and unified. The succession of planning strategies identified in this paper define a framework within which fundamental design issues can be considered such as the level of commitment a constraintposting planner should make during its search for a solution. The framework also highlights the need for practical planners to prevent synergistic interference between parallel actions in an efficient manner.

This paper continues Nebel and Burckert's investigation of Allen's interval algebra by presenting nine more maximal tractable subclasses of the algebra (provided that P ≠ NP), in addition to their previously reported ORD-Horn subclass. Furthermore, twelve tractable subclasses are identified, whose maximality is not decided. Four of them can express the notion of sequentiality between intervals, which is not possible in the ORD-Horn algebra. All of the algebras are considerably larger than the ORD-Horn subclass. The satisfiability algorithm, which is common for all the algebras, is shown to be linear. Furthermore, the path consistency algorithm is shown to decide satisfiability of interval networks using any of the algebras.

We propose three methods for obtaining solutions in fuzzy constraint networks and study their application to the problem of ordering fuzzy numbers. The techniques proposed may be classified as defizziification functions which are applicable to any set of mutually dependent fuzzy numbers in which the dependence relationships are represented by means of metric constraints. We suggest the use of these techniques for ordering linked variables in an efficient manner, and discuss their behavior regarding several quality criteria. The first application realm of these techniques is temporal reasoning.

In formal systems for reasoning about actions, the ramification problem denotes the problem of handling indirect effects. These effects are not explicitly represented in action specifications but follow from general laws describing dependencies among components of the world state. An adequate treatment of indirect effects requires a suitably weakened version of the general law of persistence. It also requires a method to avoid unintuitive changes suggested by the aforementioned dependency laws. We propose a solution to the ramification problem that uses directed relations between two single effects, stating the circumstances under which the occurrence of the first causes the second. We argue for the necessity of an approach based on causality by elaborating the limitations of common paradigms employed to handle ramifications—the principle of categorization and the policy of minimal change. Our abstract solution is realized on the basis of a particular action calculus, namely, the fluent calculus.

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

Constraint systems as used in temporal or spatial reasoning usually describe uncertainty by constraining variables into given sets. Viewing belief functions as random or uncertain sets, uncertainty in such models is quite naturally and more generally described by belief functions. Here a special class of constraint systems arising especially in numerical models underlying temporal and spatial reasoning is introduced. The computations are, as usual, plagued by combinatorial explosion in the general case. Structural properties of the knowledge base must therefore be exploited. It is shown that there are topological properties of a graph representing the model, which can be used to reduce computational complexity. Series-parallel graphs prove to be particularly simple with respect to computations. They play a role analogous to that of qualitative Markov trees in multivariate models. Moreover, the idea of reference elements leads to a natural hierarchical structuring of the knowledge base that permits computational simplifications.