1、Qualitative Spatial-Temporal ReasoningJason J. LiAdvanced Topics in A.I.The Australian National UniversitySpatial-Temporal ReasoningSpace is ubiquitous in intelligent systemsWe wish to reason, make predictions, and plan for events in spaceModelling space is similar to modelling time.Quantitative App

2、roachesSpatial-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 PerspectiveOften, a qualitative de

3、scription is more adequateObject A collided with object B, then object C appearedObject C was not near the collision between A and B when it took placeQualitative RepresentationsUses a finite vocabularyA finite set of relations Efficient when precise information is not available or not necessaryHand

4、les well with uncertaintyUncertainty represented by disjunction of relationsQualitative vs. FuzzyFuzzy representations take approximations of real valuesQualitative representations make only as much distinctions as necessaryThis ensures the soundness of composition Qualitative Spatial-Temporal Reaso

5、ningRepresent space and time in a qualitative mannerReasoning using a constraint calculus with infinite domainsSpace and time is continuousTrinity of a Qualitative CalculusAlgebra of relationsDomainWeak-RepresentationAlgebra of RelationsFormally, its called Nonassociatve AlgebraRelation Algebra is a

6、 subset of such algebras that its composition is associativeIt prescribes the constraints between elements in the domain by the relationship between them.Algebra of RelationsIt usually has these operations:Composition: If A is related to B, B is related to C, what is A to CConverse:If A is related t

7、o B, what is Bs relation to AIntersection/union: Defined set-theoreticallyComplement:A is not related to B by Rel_A, then what is the relation? Example Point AlgebraPoints along a lineComposition of relations ; = = ,= ; = ; = ,= = =Example RCC8DomainThe set of spatial-temporal objects we wish to rea

8、sonExample:2D Generic RegionsPoints in timeWeak-RepresentationHow the algebra is mapped to the domain (JEPD)Jointly Exhaustive: everything is related to everything elsePairwise Disjoint: any two entities in the domain is related by an atomic relationMapping of Point AlgebraDomain: Real valuesBetween

9、 any two value there is a valueWe say the weak representation is a representationAny consistent network can be consistently extendedDomain: Discrete values (whole numbers)Weak representation not representationNetwork of RelationsAlways complete graphs (JEPD)Set of vertices (VN) and label of edges (L

10、N)Vertice VN(i) denotes the ith spatial-temporal variableLabel 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 NExample of NetworksGreece is part of EU and on its boarderCzech Republic

11、is part of EU and not on its boarderRussia is externally connected to EU and disconnected to GreeceExample of NetworksGreeceEURussiaCzechTPPNTPPECDCUUPath-ConsistencyAny two variable assignment can be extended to three variables assignmentForall 1 = i, j, k = nRij = Rij Rik ; RkjExample of Path-Cons

12、istencyGreeceEURussiaCzechTPPNTPPECDCUUExample of Path-ConsistencyGreeceEURussiaCzechTPPNTPPECDCDCUEC ; NTPPi = DC Conv(NTPP) = NTPPiExample of Path-ConsistencyGreeceEURussiaCzechTPPNTPPECDCDCUDC ; DC = U Conv(DC) = DCExample of Path-ConsistencyGreeceEURussiaCzechTPPNTPPECDCDCDC,EC,PO,TPPi,NTPPiTPP

13、; NTPPi = DC,EC,PO,TPPi, NTPPi Conv(NTPP) = NTPPiExample of Path-ConsistencyFrom the information given, we were able to eliminate some possibilities of the relation between Czech and GreeceConsistencyA network is consistent iffThere is an instantiation in the domain such that all constraints are sat

14、isfied.ConsistencyA nice property of a calculus, would be that path-consistency entails consistency for CSPs with only atomic constraints.If all the transitive constraints are satisfied, then it can be realized.RCC8, Point Algebra all have this propertyBut many do notPath-Consistency and Consistency

15、Path-consistency is different to (general) consistencyConsider 5 circular disksAll externally connected to each otherThis is PC, but not Consistent!Important Problems in Qualitative Spatial-Temporal ReasoningA very nice property of a qualitative calculus is that if path-consistency entails consisten

16、cyIf the network is path-consistent, then you can get an instantiation in the domainUsually, it requires a manual proof Any way to do it automatically?Important Problems in Qualitative Spatial-Temporal ReasoningComputational ComplexityWhat is the complexity for deciding consistency?P? NP? NP-Hard? P

17、-SPACE? EXP-SPACE?Important Problems in Qualitative Spatial-Temporal ReasoningUnified theory of spatial-temporal reasoningMany spatial-temporal calculi have been proposedPoint Algebra, Interval Algebra, RCC8, OPRA, STAR, etc.How do we combine efficient reasoning calculi for more expressive queries.I

18、mportant Problems in Qualitative Spatial-Temporal ReasoningUnified theory of spatial-temporal reasoningSome approaches combines two calculi to form a new calculi, with mixed resultsIA (PA+PA), INDU (IA + Size), etcBIG Calculus containing all information?Meta-reasoning to switch calculi?Important Pro

19、blems in Qualitative Spatial-Temporal ReasoningQualitative representations may have different levels of granularityHow coarse/fine you want to define the relationsDo you care PP vs. TPP?What resolution do you want your representation?What level of information do you want to use?Important Problems in

20、 Qualitative Spatial-Temporal ReasoningSpatial PlanningMost automated planning problems ignore spatial aspects of the problemMost real-life applications uses an ad-hoc representation for reasoningHow do we use make use of efficient reasoning algorithms to better plan for spatial-changeSolving Comple

21、xityIf path-consistency decide consistency, the problem is polynomialIf not, then some complexity proof is requiredTransform the problem to one of the known problemsSolving ComplexityShow NP-Hardness, you need to show 1-1 transformation for a subset of the problems to a known NP-Complete ProblemDeci

22、ding consistency for some spatial-temporal networks Deciding the Boolean satisfiability problem (3-SAT)Transforming ProblemBoolean satisfiability problem hasVariablesLiterals ConstraintsTransform each component to spatial networksTransforming ProblemShow deciding consistency is same as deciding cons

23、istency for SAT problem, and vice versaProgram written to do this automatically (Renz & Li, KR2008)SummaryQualitative Spatial-Temporal Reasoning uses constraint networks of infinite domainsIt reasons with relations between entities, and make only as few distinctions as necessaryIt is useful for imprecise / uncertain informationMany open questions / problems in the