1、Jason 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 ApproachesSpatial-temporal configurations ca
2、n 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 description is more adequateObject A collided with o
3、bject 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 necessaryHandles well with uncertaintyUncertainty represented by
4、 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 ReasoningRepresent space and time in a qualitative manner
5、Reasoning 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 subset of such algebras that its composition is asso
6、ciativeIt 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 to B,what is Bs relation to AIntersection/union:Defined s
7、et-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 reasonExample:2D Generic RegionsPoints in timeWeak-RepresentationHow the alge
8、bra 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 any two value there is a valueWe say the weak representation is a representat
9、ionAny 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(LN)Vertice VN(i)denotes the ith spatial-temporal variableLabel LN(i,j)denote the poss
10、ible 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 is part of EU and not on its boarderRussia is externally connected to EU and disconnecte
11、d 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-ConsistencyGreeceEURussiaCzechTPPNTPPECDCUUExample of Path-ConsistencyGreeceEURussiaCzechTPPNTPPECDCDC
12、UEC;NTPPi=DC Conv(NTPP)=NTPPiExample of Path-ConsistencyGreeceEURussiaCzechTPPNTPPECDCDCUDC;DC=U Conv(DC)=DCExample of Path-ConsistencyGreeceEURussiaCzechTPPNTPPECDCDCDC,EC,PO,TPPi,NTPPiTPP;NTPPi=DC,EC,PO,TPPi,NTPPi Conv(NTPP)=NTPPiExample of Path-ConsistencyFrom the information given,we were able t
13、o 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 satisfied.ConsistencyA nice property of a calculus,would be that path-consistency entails consistency for CSPs with only
14、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 ConsistencyPath-consistency is different to(general)consistencyConsider 5 circular disksAll externally connected to each otherThis i
15、s PC,but not Consistent!Important Problems in Qualitative Spatial-Temporal ReasoningA very nice property of a qualitative calculus is that if path-consistency entails consistencyIf the network is path-consistent,then you can get an instantiation in the domainUsually,it requires a manual proof Any wa
16、y to do it automatically?Important Problems in Qualitative Spatial-Temporal ReasoningComputational ComplexityWhat is the complexity for deciding consistency?P?NP?NP-Hard?P-SPACE?EXP-SPACE?Important Problems in Qualitative Spatial-Temporal ReasoningUnified theory of spatial-temporal reasoningMany spa
17、tial-temporal calculi have been proposedPoint Algebra,Interval Algebra,RCC8,OPRA,STAR,etc.How do we combine efficient reasoning calculi for more expressive queries.Important Problems in Qualitative Spatial-Temporal ReasoningUnified theory of spatial-temporal reasoningSome approaches combines two cal
18、culi to form a new calculi,with mixed resultsIA(PA+PA),INDU(IA+Size),etcBIG Calculus containing all information?Meta-reasoning to switch calculi?Important Problems in Qualitative Spatial-Temporal ReasoningQualitative representations may have different levels of granularityHow coarse/fine you want to
19、 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 Qualitative Spatial-Temporal ReasoningSpatial PlanningMost automated planning problems ignore spatial aspects of the problemMost real-life app
20、lications uses an ad-hoc representation for reasoningHow do we use make use of efficient reasoning algorithms to better plan for spatial-changeSolving ComplexityIf path-consistency decide consistency,the problem is polynomialIf not,then some complexity proof is requiredTransform the problem to one o
21、f the known problemsSolving ComplexityShow NP-Hardness,you need to show 1-1 transformation for a subset of the problems to a known NP-Complete ProblemDeciding consistency for some spatial-temporal networks Deciding the Boolean satisfiability problem(3-SAT)Transforming ProblemBoolean satisfiability p
22、roblem hasVariablesLiterals ConstraintsTransform each component to spatial networksTransforming ProblemShow deciding consistency is same as deciding consistency for SAT problem,and vice versaProgram written to do this automatically(Renz&Li,KR2008)SummaryQualitative Spatial-Temporal Reasoning uses co
23、nstraint 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 field.Further ReadingA.G.Cohn and J.Renz,Qualitative Spatial Representation and Reasoning,
24、in:F.van Hermelen,V.Lifschitz,B.Porter,eds.,Handbook of Knowledge Representation,Elsevier,551-596,2008.J.J.Li,T.Kowalski,J.Renz,and S.Li,Combining Binary Constraint Networks in Qualitative Reasoning,Proceedings of the 18th European Conference on Artificial Intelligence(ECAI08),Patras,Greece,July 200
25、8,515-519.G.Ligozat,J.Renz,What is a Qualitative Calculus?A General Framework,8th Pacific Rim International Conference on Artificial Intelligence(PRICAI04),Auckland,New Zealand,August 2004,53-64 J.Renz,Qualitative Spatial Reasoning with Topological Information,LNCS 2293,Springer-Verlag,Berlin,2002.The above can all be accessed at http:/www.jochenrenz.info
