Transcript and QUALITATIVE CONSTRAINTS - Dipartimento di Informatica

Temporal Constraint Management
in Artificial Intelligence
Paolo Terenziani
Dipartimento di Informatica
Universita’ del Piemonte Orientale, Alessandria, Italy
TEMPORAL CONSTRAINT
- Introduction: time & temporal constraints
- The problem
- Survey of AI approaches to temporal constraints
Introduction (1/3)
The world evolves in time: time is an intrinsic part of human way of
approaching reality
 Time has to be taken into account in each approach modeling
(evolving) parts of the world
Time has a “peculiar” semantics, so that it deserves a
specific attention
Introduction (2/3)
Many different approaches in the literature, e.g.,
- simulation-based approaches (Petri Nets, Markov Models,
Workflows, ...)
- ….
- logical approaches (dynamic l., temporal l., nonmonotonic l.,
semantic nets, ….)
A MAIN DISTINCTION:
“general purpose”: modeling both (part of) the world and its temporal
phenomena
+
generality, homogeneous framework to deal with phenomena
computationally not efficient
VS.
“specialised”: dealing only with some temporal phenomena
generality
+
computationally efficient
Introduction (3/3)
“Specialised” approaches
IDEA: modularity:
Building efficient solutions to well-defined parts of the whole problem
NOTICE: general (not ad-hoc) solutions to a slice of temporal
phenomena
IN AI:
“Knowledge Servers” [Brachman & Levesque] to be paired with other
systems/problem solvers
Trade-off between expressiveness and computational complexity of
(correct & complete) inferential mechanisms
Temporal Constraint Managers: the Problem (1/5)
Temporal Constraint (TC): a part of the problem that can
be isolated
e.g., A before B & B before C  A before C
REGARDLESS of the description of the events A, B, C
(1) Which constraints (representation language)?
(2) Which inferences?
Trade-off!!!
Temporal Constraint Managers: the Problem (2/5)
Digression
Intended vs. supported SEMANTICS
Temporal Constraints without Temporal
Reasoning (constraint propagation)
are useless
clash with users’ intuitions/expectations
Temporal Constraint Managers: the Problem (3/5)
(1.1) the end of A is equal to the start of B
(1.2) the end of B is equal to the start of C
(1.3) the duration of A is between 10 and 20 m
(1.4) the duration of B is between 10 and 20 m
(1.5) the duration of C is between 10 and 20 m
A
10-20
B
10-20
C
10-20
Implied constraint (temporal reasoning):
(1.6) C ends between 30 and 60 m after the start of A
Correct (consistent) assertion:
(1.7) C ends between 30 and 50 m after the start of A
Not correct (inconsistent) assertion:
(1.8) C ends more than 70 m. after the start of A
However: Temporal Reasoning is NEEDED in order
to support such an intended semantics!
Temporal Constraint Managers: the Problem (4/5)
DESIDERATA for Temporal Reasoning Algorithms
- tractability  “reasonable” response time
(important for Knowledge servers!)
- correctness  no wrong inferences
- completeness  reliable answers
Temporal Constraint Managers: the Problem (5/5)
(1.1) the end of A is equal to the start of B
(1.2) the end of B is equal to the start of C
(1.3) the duration of A is between 10 and 20 m
(1.4) the duration of B is between 10 and 20 m
(1.5) the duration of C is between 10 and 20 m
A
10-20
B
10-20
C
10-20
Implied constraint (temporal reasoning):
(1.6) C ends between 30 and 60 m after the start of A
Suppose that temporal reasoning is NOT
complete, so that (1.6) is not inferred
The answer to query (Q1) might be: YES
(Q1) Is it possible that C ends more than 70 m. after the start
of A?
Complete Temporal Reasoning is NEEDED in order
to grant correct answers to queries!
Survey (1/18)
Types of temporal entities
-
Time Points
-
Time Intervals
-
Sets of Time Points/Intervals (repeated/periodic events)
Survey (2/18)
Types of temporal constraints (1/4)
-
Qualitative: relative positions of entities (e.g., A during B)
-
Quantitative: metric time
- dates (A on 1/1/2003 from 9:00 to 11:33)
- duration (A lasted between 3 and 4 hours)
- delays (B started between 5 and 10 minutes after A)
-
Periodicity/repetition -based (qualitative and/or quantitative)
Survey (3/18)
Types of temporal constraints (2/4)
QUALITATIVE CONSTRAINTS on TIME POINTS

Point Algebra [Vilain & Kautz, 87]
-
base relations: <, =, >
-
composite relations: (<,=), (<,>), (=,>), (<,=,>)
Notice: P1(r1,r2,…rk)P2 means r1(P1,P2)  r2(P1,P2)  …  rk(P1,P2)

Continuous Pointizable Algebra [Vilain, Kautz, VanBeek]
-
base relations: <, =, >
-
composite relations: (<,=), (=,>), (<,=,>)
Survey (4/18)
Types of temporal constraints (3/4)
QUALITATIVE CONSTRAINTS on TIME INTERVALS

Interval Algebra [Allen, 83]
-
13 base relations, 213 relations
I before J (J after I)
I meets J (J met-by I)
I overlaps J (J overlapped-by I)
I finished-by J (J finishes I)
I contains J (J during I)
I equal J
I started-by J (J starts I)
Survey (5/18)
Types of temporal constraints (4/4)
>>>> QUANTITATIVE CONSTRAINTS: see below
CONSTRAINTS on SETS OF INTERVALS
(repeated/periodic events)

Periodicity-dependent durations [Loganantharaj & Gimbrone, 95]
e.g. On Mondays John goes to work in 40-45 minutes
On Tuesdays John goes to work in 30-55 minutes
 “Absolute” qualitative constraints on repeated events
[Morris et al., 93]
e.g. Meetings always precede Lunches
 Periodicity-dependent qualitative constraints on repeated events
[Terenziani, 95]
e.g. From 10/1/2003 to 31/3/2003, twice each Monday, two units of Math
precede one unit of Physics
Survey (6/18)
Temporal Reasoning (1/5)
Mostly: PATH-CONSISTENCY-based TR
I
C1
J
C2
K
C3?
C3NEW  C3OLD  (C1 @ C2)
Different instantiations, depending on the types of constraints (and on the
definitions of intersection and composition)
Survey (7/18)
Temporal Reasoning (2/5)
E.g., path-consistency on quantitative constraints between time points
(STP framework [Dechter et al., 91])
[0,10]
I
J
[10,10]
H
[10,30]
[10,20]
K
[10,20]
Survey (7/18)
Temporal Reasoning (2/5)
E.g., path-consistency on quantitative constraints between time points
(STP framework [Dechter et al., 91])
[0,10]
I
J
[10,10]
H
[10,20]
[10,20]
K
[10,20]
IHNEW= [10,30]  ([0,10][10,10]) = [10,20]
Survey (8/18)
Temporal Reasoning (3/5)
STP (Simple Temporal Problem) framework [Dechter et al., 91])
Conjunction of Bounds on Difference (b.o.d.) constraints
i
[c,d]
0  J-I  10
10  K-I  20
10  H-I  30
10  H-J  10
10  H-K  20
- < K-J < +
j

d
-c
i
 c j-i  d
j
I
J
K
H
I
0
10
20
30
J
0
0
+
10
K -10
+
0
20
H -10
-10
-10
0
Survey (9/18)
Temporal Reasoning (4/5)
All-to-all shortest path algorithm [Floyd-Warshall]
For k:=1 to N do
For i:=1 to N do
For j:=1 to N do
M[i,j]=Min(M[i,j],M[i,k]+M[k,j])
Property: Consistent iff no negative cycle
Complexity: O(N3)
Property: Correct & complete for b.o.d.
Survey (10/18)
Temporal Reasoning (5/5)
I
I
J
0
J -10
K -10
H -20
K
H
10
10
20
0
0
10
0
-10
0
-10
10
0
[10,10]
J
[10,10]
[0,0]
I
H
[20,20]
[10,10]
K
[10,10]
Minimal Network (shortest path between each pair of nodes)
Survey (11/18)
Approaches & Complexity (1/5)
QUALITATIVE CONSTRAINTS

Continuous Pointizable Algebra [Vilain, Kautz, VanBeek, 89]
O(N3)

Point Algebra [Vilain & Kautz, 87]
O(N4)

Interval Algebra [Allen, 83]
Exponential
Maximal tractable fragments [Nebel & Buckert, 95],
[Drakengren & Jonsson, 97]
Survey (12/18)
Approaches & Complexity (2/5)
QUANTITATIVE CONSTRAINTS

STP [Dechter et al., 91]
O(N3)

TCSP [Dechter et al., 91]
Exponential (many optimizations)
[10,20][30,35]
I
J
Survey (13/18)
Approaches & Complexity (3/5)
QUALITATIVE+QUANTITATIVE CONSTRAINTS

[Vilain & Kautz, 91]
Combining two TRs
Does the exchange of constraints between TRs end?

[Meiri, 91]
“two sorted” formalism + mapping operators

[Brusoni, Terenziani et al., 95]
mapping onto STP
Survey (14/18)
Approaches & Complexity (4/5)
STP (and TCSP) and QUALITATIVE CONSTRAINTS
STP (and TCSP) can also represent (a subset of) qualitative
constraints



Continuous Poitizable relations
e.g., P1<P2  0<P2-P1
Some Interval Algebra relation
e.g., I (started-by,contains, finished-by,equal) J
 0  Start(J)-Start(I)  0 < End(I)-End(J)
BUT NOT ALL RELATIONS
e.g., P1(<,>)P2
 0 < P1-P2  0 < P2-P1 (in TCST but not in STP)
e.g., I (before,after) J
 0 < End(I)-Start(J)  0 < End(J)-Start(I)
(neither in STP nor in TCSP)
Survey (15/18)
Approaches & Complexity (5/5)
SURVEY NOT EXHAUSTIVE !!!
E.g., relative duration
E.g., “A lasted more than B”

[Pujary & Sattar, 99]

[Jonsson & Backstrom, 98] homogeneous approach based on
linear programming
Survey (16/18)
TRs & Applications
MANY TRs (knowledge servers) in AI






TMM [Dean & McDermott, 87]
Timelogic [Koomen, 89]
MATS [Kautz & Ladkin, 91]
Timegraph Gerevini & Schubert, 95]
…..
Later [Brusoni, Terenziani et al., 95]
Comparison of several systems in [Allen & Yampratoom, 93]
Survey (17/18)
TRs & Applications
MANY APPLICATIONS




…..


Scheduling
Planning
Natural Language Understanding
Diagnosis
Multimedia Presentations
Clinical Guidelines
Survey (18/18)
TRs & Applications
REFERENCES TO SURVEYS




M. Vilain, H. Kautz, and P. VanBeek. "Constraint Propagation
Algorithms for temporal reasoning: a Revised Report", D.S.
Weld, J. deKleer, eds., Readings in Qualitative Reasoning about
Physical Systems. Morgan Kaufmann, 373-381, 1990.
J. Allen, “Time and Time Again: The Many Ways to Represent
Time”, Int’l Journal of Intelligent Systems 6(4), 341-355, 1991.
E. Yampratoom, J. Allen, “Performance of Temporal reasoning
Systems”, Sigart Bull. 4(3), 26-29, 1993.
L. Vila. 1994, "A Survey on Temporal Reasoning in Artificial
Intelligence", AI Communications 7(1):4-28, 1994.
…..
 P. Terenziani, “Reasoning about time”, Encyclopedia of
Cognitive Science, Macmillan Reference Ltd, Vo.3, 869-874,
2003.