Transcript Integration of Artificial Intelligence and Operations

Introduction to Spatio-temporal
Qualitative Reasoning
Debasis Mitra
Florida Institute of Technology
1
DEBASIS MITRA
Associate Professor, Dept. of Computer Sciences, Florida Institute of Technology
Ph.D., Computer Science, University of Louisiana at Lafayette, 1994
Ph.D., Physics, Indian Institute of Technology, Kharagpur, India, 1984
M.Sc., Physics, Indian Institute of Technology, Kharagpur, India, 1977
Dr. Mitra joined Florida Tech in the Fall semester of 2001 as an Associate Professor. Before that he
was a faculty member at Jackson State University in Jackson, Mississippi since fall of 1994. He
worked as an exploration geophysicist for some time in between his two graduate studies on
Physics and Computer Science. Dr. Mitra’s current research interest is on reasoning with space and
time, particularly with incomplete and qualitative information. This area broadly falls under the
Knowledge Representation branch within the Artificial Intelligence (AI). The primary methodology
deployed in this type of research is similar as in the Constraint Propagation. Apart from doing
theoretical/empirical works in the area Dr. Mitra is also interested in applying spatio-temporal
reasoning to other fields of computation outside the AI.
2
An introduction to spatio-temporal qualitative reasoning
ABSTRACT
Space and time are two of the most important entities dealt with in our lives. Although computer
programs routinely manage them using some quantitative measures (e.g., clock), from a humancentric angle it is also necessary to develop a qualitative framework for them. By qualitative
framework we mean handling terms like "overlap," "during," "Southeast," etc. Such terms appear
not only in the natural language context, but also in many other systems like databases (e.g.,
Geographical Information Systems). Systems managing these types of qualitative notions of time
and space can behave more intelligently than the traditional ones. Fortunately, these qualitative
frameworks form perfect relational algebras and so, can be handled normally within the context
of computation. In this talk I will introduce a few such algebras as examples, describe the graph
theoretical techniques deployed in representing and reasoning with them, some open problems in
the area, and mention my current works on this project. I will also briefly touch upon some other
projects that I am involved with or is planning to get involved with in the near future.
3
Time points
Linear time (like many other domains) is mappable to
real numbers.
Put a point (event) in a time-line:
The “space” gets divided into three equivalent
regions with respect to that point {<, =, >}
Three QUALITATIVE regions for a second point to be
placed on the time line.
4
Time point
<
a1
>
Point-based Reasoning
Input 1:
(a1 < a2) and (a2 < a3) ::
(a1 < a3)
Input 2:
(a1 < a2) and (a2 > a3) ::
(a1 <|=|> a3)
We need a relation not belonging to the set {<, >, =}
The full set needed for reasoning is {<, >, =, <=, >=,
<>, and also <=> , null }, the power set
Point-based Reasoning
Input 1:
(a1 < a2) and (a2 < a3) ->
(a1 < a3)
A starting point of reasoning: Composition table
a2->a3::
a1->a2
<
>
=
<
<
<=>
<
>
<=>
>
>
=
<
>
=
7
Point-based Reasoning
We have already decided to allow
disjunctions {< | = | >} in the language
Input 3:
(a1 <|= a2) & (a2 <|> a3) ::
(a1 <.< a3) | (a1 <.> a3) | (a1 =.< a3) |
(a1 =.> a3)
A disjunctive composition scheme: compose
base relations and union the results
8
Point Algebra
We need composition operation and set union
operation
Input 4:
(a1 <|= a2) & (a2 <|= a3) & (a1 <|> a3) ::
(a1 <|= a3) & (a1 <|> a3) ::
(a1 < a3)
The last operation is set intersection
Point Algebra
The set {<, >, =, <=, >=, <>, < = >, null} is closed
under composition, union, intersection, and inverse
operations
This is POINT ALGEBRA
This is a type of Relational Algebra
Nice things about an algebra is that you can reason
without getting outside the set.
{<, >, =} does not form an algebra under
composition.
Time Interval Relations
Basic Relations (13):
A
B
A
B
A
B
A
B A
A
B
B
A
B
A before (b) B
B after (a) A
A meets (m) B
B met-by (mi) A
A overlaps (o) B
B overlapped-by (oi) A
A starts (s) B
B started-by (si) A
A during (d) B
B during-inverse (di) A
A finishes (f) B
A equals (eq) B
B finished-by (fi) A
Allen’s Interval Algebra
Full Set is 2^{13 basic relations}
Forms algebra A under composition, union,
intersection, and inverse operations:
Interval Algebra
12
13
A Subalgebra of Interval Algebra
A subset of A: relations expressible as
conjunction of end-points of two intervals
a1 (before | meet | overlap) a2 ::
a1------ ------------ ---------------------- a2
(a1_start < a2_start) & (a1_end < = > a2_start)
& (a1_start < a2_end) & (a1_end < a2_end)
Pointisable Subalgebra
Set of interval relations which are expressible as
conjunction of point relations between their end points
form Pointisable Subalgebra (~150 relations)  A
{before | after} is not a pointisable relation: try it!
You can stick with only pointisable relations and
reason within the set (need for having algebra)
A Reasoning Problem Instance
Input:
GSA_meeting should be {b | a} StdA office hour
GSA_meeting should be {a} StdB office hour
GSA_meeting should be {b} StdC office hour
StdA should have office hour {overlap} that of StdB
StdB should have office hour {overlap} that of StdC
StdA should have office hour {b | m} that of StdC
[Note NOT all of 4C2 possible inputs need to be present in input]
Question 1: Is the information consistent? (decision problem)
Question 2: Develop a scenario, if it is consistent
Solution 1: No! [2, 3, and 5 contradicts]
The Reasoning Problem
Given a set of objects (points, intervals, …) and some
binary relations between some of them answer Question 1
and 2 as above.
Typical methodology: In a graph the objects are nodes and
the binary relations are labels on directed edges between
the nodes, algorithms are typically graph theoretical
17
StdB
(o)
(o)
StdA
StdC
(b | m)
(b)
(a)
(b | a)
GSA-mt
18
Allen’s Algorithm
Initialize a queue Q with all constrained edges
Do until Q is empty
e = pop (Q)
for all triangles (e, e1, e2) formed by e do
update e1 using (e and e2)
update e2 using (e and e1)
if ei becomes null return INCONSISTENCY
else if ei gets further constrained push(ei, Q)
Allen’s Algorithm
Complexity: O(N3) for N nodes in the graph.
Reasoning with Interval Algebra A is NP-hard!
Allen’s relaxation algorithm works fine for tractable
cases e.g., point algebra, pointisable interval
algebra
Allen’s algorithm does not return correct answer for
full Interval Algebra: not all inconsistencies are
detected [Approximate algorithm]
Current Focus of the STR Community
Finding tractable subalgebras
Maximal Tractable subalgebras: no proper superset
(other than the whole) forms a subalgebra. Note a subset
or superset of any subalgebra is not necessarily closed
under the said operations)
Hope: somebody would need such a subalgebra in a real
application
Finding subalgebras is interesting theoretically
21
Directional Interval Algebra (DIA)
Direction of an interval could be opposite to the linedirection: e.g., a car on a road
Twenty-six basic relations, e.g.,
----------
------------
------------
---------------
Renz (IJCAI-2001) proposed it and found some maxtractable subalgebras of it
22
Cardinal Algebra (Ligozat)
Nine Basic relations in a 2D space
North
Northeast
Northwest
Equal
West
Southwest
East
Southeast
South
23
Cyclic Algebra
Sixteen basic relations between intervals/arcs
on a directed circle
overlap
24
Partially-ordered Time
Four basic relations between points:
{<, >, =, ||}
||
Region-conncetion Calculus-5
Five basic relations between two sets:
26
Current Trends
Come up with new ontology / algebra
Prove NP-hardness (most of them are), and find
maximal tractable subalgebras
Develop data-structures and algorithms for
efficient reasoning
Find applications
27
Our Contributions
Domain-theoretic approach as opposed to
relational algebraic approach
Relational-algebraic approach: constrain
labels on arcs (set of symbols/ basicrelations), e.g. Allen’s algorithm
Domain-theoretic approach: create a
qualitative space and place each object
there. Example:
28
Canonical representation of intervals
(Ligozat’98)
Ending-pt
45 degree-line
(2, 5)
5
overlap
region
(-7, 4)
meet region
Not allowed
region
2
(-7, 2)
Starting-pt
Not allowed
region
29
Our Contributions: domain
theoretic algorithms
Reworking 1D (point) case for a better
understanding
(new result: solution for incremental adding a point
is “contiguous”)
Studying and developing algorithms for 2D and nD
Cardinal-algebra cases
Developing a generalized framework for “all”
ontology /algebra - based on a domain-theoretic
approach
30
Generalized Framework
An extreme symmetry between different algebra
(note canonical rep of Interval Algebra vs 2DCardinal Algebra): not studied traditionally
Max-tractable algebras (across different ontology)
seem to be have strong similarity
Understand these issues by studying a generalized
framework rather than working on each ontology
separately
31
Generalized Framework: Two approaches
Relational algebraic approach: study the
underlying algebra from an ontology
independent fashion
Domain theoretic approach: study the
underlying geometry of a qualitative space
and topology of relations
Examples of Qualitative space
Northeast
2D Cardinal
Intervals
meet
before
33
Why study generalized
framework?
A very clear theoretical direction is
suggested from current max-tractability
results: we just need to understand it!!!
Some new directions are bound to come up,
e.g., new tractable subsets (may not be
subalgebras)
Applications would benefit from this deeper
understanding
New ontology are better understood (PO
time, the least understood area)
34
Our Contributions: New ontology
Star Algebra - 2D
35
Possible applications of interest:
Ph.D. topic
Bio-informatics: Two 1D chromosome, proteins have
folding angles:: what type of ontology? (Merging
different labs’ data as a CSP)
Graphics / Visualization: Does “Qualiataive space”
make any sense in modeling / information-storage?
Robotics: Spatio-temporal modeling of the world,
pattern matching, e.g. DIA in traffic management by
autonomous traffic helicop (WITAS project)
Other future directions in the
project: Ph.D. topic
Add certainty information to the
incompleteness/disjunctions currently
handled: e.g. Analysis of Intelligence
Information
Study spatio-temporal reasoning needs in
tactical deployment (involve databases):
emergency management, battle entities, etc.
37
Other projects under development (or
dormant): MS Thesis/Project
AI Planning: application in componentoriented program development (with Dr.
Bond)
Empirical studies: of hard problems, and
their phase transition
Multi-dimensional Datamodeling: for
scientific databases
38
Other projects under development
(or dormant): MS Thesis/Project
Studying some search algorithms: a new heuristic
for “island-based” search technique (for computer
games??)
Studying some CSP problem: new heuristics for Nqueens problem that may have fundamental
implications
Quantum Computing: ….
39
Too much theory: how can one find
employment???
Research methodology: (1) Mathematics,
(2) algorithmics and programming, (3)
deeper understanding of space and time,
(4) interests in specific applications are
welcome
Skills on information systems
development: design your own research
product (e.g. GUI, backend database, etc.)
40
Pointers
My web page: www.cs.fit.edu/~dmitra
Bibliography linked from there
My publications list in my resume
Thanks!