《qualitativespatial-temporalreasoning-australiannational定性空间推理-澳大利亚国家》由会员分享，可在线阅读，更多相关《qualitativespatial-temporalreasoning-australiannational定性空间推理-澳大利亚国家（39页珍藏版）》请在金锄头文库上搜索。
1、Qualitative Spatial-Temporal Reasoning,Jason J. Li Advanced Topics in A.I. The Australian National University,Spatial-Temporal Reasoning,Space is ubiquitous in intelligent systems We wish to reason, make predictions, and plan for events in space Modelling space is similar to modelling time.,Quantita
2、tive Approaches,Spatial-temporal configurations can be described by specifying coordinates: At 10am object A is at position (1,0,1), at 11am it is at (1,2,2) From 9am to 11am, object B is at (1,2,2) At 11am object C is at (13,10,12), and at 1pm it is at (12,11,12),A Qualitative Perspective,Often, a
3、qualitative description is more adequate Object A collided with object B, then object C appeared Object C was not near the collision between A and B when it took place,Qualitative Representations,Uses a finite vocabulary A finite set of relations Efficient when precise information is not available o
4、r not necessary Handles well with uncertainty Uncertainty represented by disjunction of relations,Qualitative vs. Fuzzy,Fuzzy representations take approximations of real values Qualitative representations make only as much distinctions as necessary This ensures the soundness of composition,Qualitati
5、ve Spatial-Temporal Reasoning,Represent space and time in a qualitative manner Reasoning using a constraint calculus with infinite domains Space and time is continuous,Trinity of a Qualitative Calculus,Algebra of relations Domain Weak-Representation,Algebra of Relations,Formally, its called Nonassoc
6、iatve Algebra Relation Algebra is a subset of such algebras that its composition is associative It prescribes the constraints between elements in the domain by the relationship between them.,Algebra of Relations,It usually has these operations: Composition: If A is related to B, B is related to C, w
7、hat is A to C Converse: If A is related to B, what is Bs relation to A Intersection/union: Defined set-theoretically Complement: A is not related to B by Rel_A, then what is the relation?,Example Point Algebra,Points along a line Composition of relations ; ,= = =,Example RCC8,Domain,The set of spati
8、al-temporal objects we wish to reason Example: 2D Generic Regions Points in time,Weak-Representation,How the algebra is mapped to the domain (JEPD) Jointly Exhaustive: everything is related to everything else Pairwise Disjoint: any two entities in the domain is related by an atomic relation,Mapping
9、of Point Algebra,Domain: Real values Between any two value there is a value We say the weak representation is a representation Any consistent network can be consistently extended Domain: Discrete values (whole numbers) Weak representation not representation,Network of Relations,Always complete graph
10、s (JEPD) Set of vertices (VN) and label of edges (LN) Vertice VN(i) denotes the ith spatial-temporal variable Label LN(i,j) denote the possible relations between the two variables VN(i), VN(j) A network M is a subnetwork of another network N iff all nodes and labels of M are in N,Example of Networks
11、,Greece is part of EU and on its boarder Czech Republic is part of EU and not on its boarder Russia is externally connected to EU and disconnected to Greece,Example of Networks,Greece,EU,Russia,Czech,TPP,NTPP,EC,DC,U,U,Path-Consistency,Any two variable assignment can be extended to three variables a
12、ssignment Forall 1 = i, j, k = n Rij = Rij Rik ; Rkj,Example of Path-Consistency,Greece,EU,Russia,Czech,TPP,NTPP,EC,DC,U,U,Example of Path-Consistency,Greece,EU,Russia,Czech,TPP,NTPP,EC,DC,DC,U,EC ; NTPPi = DC,Conv(NTPP) = NTPPi,Example of Path-Consistency,Greece,EU,Russia,Czech,TPP,NTPP,EC,DC,DC,U,
13、DC ; DC = U,Conv(DC) = DC,Example of Path-Consistency,Greece,EU,Russia,Czech,TPP,NTPP,EC,DC,DC,DC,EC,PO,TPPi,NTPPi,TPP ; NTPPi = DC,EC,PO,TPPi, NTPPi,Conv(NTPP) = NTPPi,Example of Path-Consistency,From the information given, we were able to eliminate some possibilities of the relation between Czech
14、and Greece,Consistency,A network is consistent iff There is an instantiation in the domain such that all constraints are satisfied.,Consistency,A nice property of a calculus, would be that path-consistency entails consistency for CSPs with only atomic constraints. If all the transitive constraints a
15、re satisfied, then it can be realized. RCC8, Point Algebra all have this property But many do not,Path-Consistency and Consistency,Path-consistency is different to (general) consistency Consider 5 circular disks All externally connected to each other This is PC, but not Consistent!,Important Problem
16、s in Qualitative Spatial-Temporal Reasoning,A very nice property of a qualitative calculus is that if path-consistency entails consistency If the network is path-consistent, then you can get an instantiation in the domain Usually, it requires a manual proof Any way to do it automatically?,Important Problems in Qualitative Spatial-Temporal Reasoning,Computational Complexity What is the complexity for deciding consistency? P? NP? NP-Hard? P-SPACE? EXP-SPACE?,Impo
