Temporal Reasoning: the LaTeR system (LAyered TEmporal Reasoner)

PROJECT:

Temporal Reasoning: LaTeR

MAIN GOALS:

• Temporal knowledge server to be used in a loosely coupled way by other systems or problem solvers
• High level interface language for manipulating and querying a temporal knowledge base
• Ability to maintain multiple versions of a temporal knowledge base
• Dealing with Heterogeneous temporal information (quantitative and qualitative information)
• Efficient Temporal Reasoning
  • Complete temporal constraint propagation in polynomial time
  • Efficient query processing Complexity of answering different types of queries independent of the dimension of the temporal knowledge base

SPECIFICATIONS AND APPROACH

• Two layered architecture
• Low level based on constraint frameworks
  • constraints of the form a <= X - Y <= b (a, b Real)
  • isomorphic to distance between time points
• High level language
  • dealing with both punctual and durative situations (points and intervals)
  • dealing with heterogeneous temporal information: primitives for dealing with
    • location of points and intervals (precise or imprecise)
    • duration of intervals (precise or imprecise)
    • qualitative relations between points, intervals and point and intervals
    • delays between time points (precise or imprecise)
  • primitives for creating, modifying and querying a temporal knowledge base
    • Multiple versions of the knowledge base are maintained
      • the user can create a new version from any older one
      • the user can query any version
    • Temporal reasoning
      • automatic constant time translation of the temporal information in the high-level language into low-level constraints
        temporal reasoning (complete constraint propagation) performed on low-level constraints in time O(n3) (n number of variables)
        • constraint propagation gives as output the minimal network for the constraints
        • Reasoning (and consistency-check) are necessary before query processing
    • Query language; primitives for
      • extracting information
        WHEN (point or interval)
        HOW LONG (interval)
        RELATION (point or interval, point or interval)
        DELAY (point, point)
        YES/NO queries; modal operators (in order to deal with imprecise information)
        
        • MUST (conjunction of conditions) asking whether the conditions are necessarily true
        • MAY (conjunction of conditions) asking whether the conditions are possibly true
      • hypothetical queries: Query IF assumptions
      each query translated into a query on low-level constraints
    • Techniques for efficient query processing
      • Given the minimal network, all queries can be answered in time that depends only on the length of the query and independently of the dimension of the knowledge base
        • MUST queries and queries for extracting informations: time linear in the length of the query
        • MAY queries and hypothetical queries: time cubic in the length of the query (and assumptions)
        • for each version, the results of the propagation are stored
        • · during a session of alternated updates and queries
          • queries are dealt with as hypothetical ones
          • updates are performed off-line

APPLICATIONS

• Temporal relational databases
• Model-based diagnosis

IMPLEMENTATION TECHNIQUES

Two versions of the system

• LaTeR 2.6 on Macintosh; Developed in Prolog, graphical interface
• LaTeR 1.0 under UNIX, Developed in C

In order to get information on how to get the code,please e-mail to: lconsole@di.unito.it.

AN EXAMPLE

• Set of assertions in LaTeR's high-level language
  • John-work Since 14-14:30 Until 18-19
  • start(Mary-work) 10-40 min After start(John-work)
  • Mary-work Lasting AtLeast 4 hours:40 min
  • Mary-work Non-Strict-During John-work
  • Tom-work Since 14:15 Until 18:30
• Translation into low-level constraints
• Temporal reasoning on low-level constraints.
  The following constraints are inferred (among the others):
  • John-work Since 14-14:10 Until 18:50-19
  • Mary-work Since 14:10-14:20 Until 18:50-19
  • John-work Lasting 4:50 - 5:00 min
• Queries (examples):
  • POSS (start(John-work) At 14:15-14:25)
    "Is it consistent (possible) that John started working between 14:15 and 14:25"
    Answer: NO
  • NEC (start(Mary-work) 10-20 After start(John-work))
    "Is it necessarily true that Mary started working 10-20 minutes after John started?"
    Answer: YES
  • HOW LONG John-work
    "How long did John work?"
    Answer: John-work LASTING 4:50 - 5:00 min
  • POSS (Tom-work Non-Strict-During Mary-work)
    "Is it possibly true that Tom worked only during Mary's work?"
    ANSWER: YES
  • NEC (Tom-work Non-Strict-During Mary-work)
    "Is it necessarily true that Tom worked only during Mary's work?
    Answer: NO
  • NEC (Tom-work Non-Strict-During John-work) If (Mary-work Lasting 4:50)
    "If Mary worked for 4 hours and 50 minutes, is it necessarily true that Tom worked only during Mary's work?"
    Answer: YES
  • HOW LONG John-work If (Mary-work Lasting 4:50)
    "If Mary worked for 4 hours and 50 minutes, how long did John work?"
    Answer: John-work LASTING 5:00 min