SparQ User Manual V0.6 - SFB/TR8
Contents
1. compute relation constraint reasoning SparQ FR Ko neighborhood x N N reasoning specifications N interface Figure 5 1 Module architecture of the SparQ toolbox The general syntax for using the SparQ main script which can be found in the main directory of SparQ is as follows sparq module calculus identifier module specific parameters Example sparq compute relation dra 24 complement lrll llrr where compute relation is the name of the module to be utilized in this case the module for conducting operations on relations dra 24 is the SparQ identifier for the dipole calculus DRA and the rest are module specific parameters here the name of the operation that should be conducted complement and a string parameter representing the disjunction of the two dipole base relations Irll and lirr The example call thus computes the complement of the disjunction of these two relations Unions of base relations are always represented as a space separated list of the base relations enclosed in parentheses in SparQ 26 5 Using SparQ Some calculi have calculi specific parameters for example the granularity parameter in OPRAm These parameters are appended with a after the calculus base identifier opra 3 for example refers to OPRA3 SparQ provides the following modules qualify transforms a quantitativ2. Allen 1983 relates pairs of time intervals A time interval x can be represented as a tuple of a starting point x and end point e s e of real numbers with x lt ze 13 base relations are distinguished cf Tab 4 2 before meets overlaps starts during finishes before inverse meets inverse overlaps inverse starts inverse during inverse finishes inverse equals The relations can be defined by comparing the start and end points of the intervals see Tab 4 2 The converse operation always takes an interval relation r to the corresponding inverse relation e g f to fi 24 4 Supported Calculi Basic relation abbrv Example Condition x before y b XXX Te lt Ys y after x bi yyy x meets y m XXXX Te Ys y met by x mi yyyy x overlaps y 0 XXXXX Ls lt Ys lt eA y overlapped by x oi yyyyy Te lt Ye x during y d XXX Ls gt Ys y includes x di yyyyyyy Ye lt Ye x starts y s XXX Zs JAN y started by x si YyyYYYY Te lt Ye x finishes y XXX Ze yeh y finished by x fi yyyyyyy Ts gt Ys x equals y eq XXXXXXX Ls ys yYyyyyyy Te Ye Table 4 2 The 13 basic Allen relations 25 5 Using SparQ SparQ consists of a set of modules that logically structure the different services provided which will be explained below The general architecture is visualized in Fig 5 1 The dashed parts are extensions planned for the future see Section 6 qualify
3. SparQ The definition of weak composition is identical to the binary case As we have not introduced a ternary calculus so far we resign from giving any examples here but some can be found later in Section 5 3 5 Path consistency and backtracking search Determining consistency of a constraint network in which the constraints are given as gualitative spatial relations from a particular calculus is a particular instance of a con straint satisfaction problem CSP Unfortunately the domains of our variables are typ ically infinite e g the set of all points in the plane and thus backtracking over all the values of the domain cannot be used to determine consistency The technigues developed for relational constraint problems are instead based on weaker forms of consistency called local consistencies which can be tested or enforced based on the operations of the calculus and which are under particular conditions suffi cient to decide consistency 11 3 Reasoning with Qualitative Spatial Relations One important form of local consistency is path consistency which in binary CSPs means that for every triple of variables each consistent evaluation of the first two vari ables can be extended to the third variable in such a way that all constraints are satisfied In the best case path consistency decides consistency for a given calculus This means that if we can make the network path consistent by possibly removing some base rela tions
4. sparq interactive port 4443 If no port is given SparQ interacts with standard input and standard output i e it can be used interactively from the shell An example of client server communication with SparQ is given in Listing 5 1 which shows a small Python script that opens a connection to the server and performs some sim ple computations qualification adding another relation checking for path consistency It produces the following output gt A rrll B A rr11 C gt A rr11 B A rr11 C B eses C Not consistent gt B eses C A O C A rr11 B 31 10 5 Using SparQ connect to sparq server on localhost port 4443 sock socket socket socket AF INET socket SOCK STREAM sock connect localhost 4443 sockfile sock makefile r qualify a geometrical scenario with DRA 24 sock send qualify dra 24 first2all sock send A 4 6 9 0 5 B 5 5 0 2 C 4 5 6 0 scene readline read the answer print scene add an additional relation B eses C sock send constraint reasoning dra 24 refine sock send scene B eses C scene2 readline read the answer print scene2 check the new scenario for consistency sock send constraint reasoning dra 24 path consistency sock send scene2 print readline print the answer print readline print the resulting constraint network Listing 5 1 Integrating SparQ into own applications
5. that takes the union of all base relations that have a non empty intersection with the result of the strong composition Weak composition R oweak S 1d T E BRAdETATN RoS Z0 For some calculi it is not yet known whether the defined composition operation is strong or not 10 3 Reasoning with Qualitative Spatial Relations 3 4 Ternary calculi and their operations While there is only one possibility to permute the two objects of a binary relation which leads to the converse operation there exist 5 such permutations for the three objects of a ternary relation This results in the following 5 operations introduced in Zimmermann and Freksa 1996 Inverse INV R y 2 2 a y z RI Short cut SC R 2 z y x y z E R Inverse short cut SCI R 2 7 y x y z ER Homing HM R y 2 7 a y z E RI Inverse homing HMI R z y x x y z R It is in general not needed to specify all these operations as some can be expressed by others but they are all available in SparQ nonetheless Composition for ternary calculi is defined accordingly to the binary case Composition Ro S w z z Jy D w x y RA 2 y z S Other ways of composing two ternary relations can be expressed as a combination of the unary permutation operations and the composition Scivos and Nebel 2001 and thus do not have to be defined separately and are also not accessible individually in
6. description 5 2 Compute relation The compute relation module allows to compute with the operations defined in the calculus specification The module specific parameters are the operation that should be conducted and one or more input relations depending on the arity of the operation Let us say we want to compute the converse of the lirl dipole relation The corresponding call to SparQ and the result are sparq compute relation dra 24 converse llrl gt r111 The result is always a list of relations as operations often yield a disjunction of base relations In this case however the disjunction only contains a single relation The composition of two relations requires one more relation as parameter because it is a binary operation e g sparq compute relation dra 24 composition llrr rllr gt lrrr llrr rlrr slsr lllr rllr rlll ells 1111 1r11 In all the examples input lines start with Output of SparQ is marked with gt 28 5 Using SparQ Here the result is a disjunction of 10 base relations It is also possible to have disjunctions of base relations as input parameters For instance the following call computes the intersection of two disjunctions sparq compute relation dra 24 intersection rrrr rrll rllr 1111 rr11 gt rrll 5 3 Constraint reasoning The constraint reasoning module reads a description of a constraint network which is a qualitative scene description that may i
7. instance be used to describe the spatial relation of C to B as seen from A For configurations with A B the following base relations are distinguished C can be to the left or to the right of the oriented line going through A and B or C can be placed on the line resulting in one of the five relations inside front back start C A or end C B cp Fig 4 1 Relations for the case where A and B coincide were not included in Ligozat s original definition Ligozat 1993 This was done with the CR refinement Scivos and Nebel 2005 that introduces the relations dou A B Z C and tri A B C as additional relations resulting in 9 base relations overall A ZR relation reler is written as A B reler C e g A Br C as depicted in Fig 4 1 r C Figure 4 1 The reference frame for the LR calculus an enhanced version of the FlipFlop Calculus 15 4 Supported Calculi 4 2 Singlecross calculus SCC Singlecross calculus SCC overview short name SCC calculus parameters none arity ternary entity type 2D points description relates the referent c relative to the line between origin a and relatum b and the orthogonal line thru b resulting in nine rela tions base relations 0 7 and b for b c references Freksa 1992a The single cross calculus is a ternary calculus that describes the direction of a point C the referent with respect to a point B the relatum as seen from a third point A the origin It h
8. name is the identifier of this particular dipole object and the rest are the coordinates of start and end point of the dipole Let us consider the example in Fig 5 2 which shows three dipoles A B and C The quantitative scene description for this situation would be 27 5 Using SparQ A 2080 B7 2 2 5 C 1 1 4 5 4 5 The qualify module has one module specific parameter that needs to be specified mode This parameter controls which relations are included into the qualitative scene description If the parameter is all the relation between every object and every other object will be included If it is first2all only the relations between the first and all other objects are computed in the binary case or between the first two objects and all other objects in the ternary case The resulting qualitative scene description is a space separated list of relation tuples enclosed in parentheses A relation tuple consists of an object identifier followed by a relation name and another object identifier meaning that the first object stands in this particular relation with the second object The command to produce the qualitative scene description followed by the result is sparq qualify dra 24 all A 2 0 8 0 B 7 2 2 5 C1 1 4 5 4 5 gt A rllr B A rllr C B lrrl C If we had chosen first2all as mode parameter the relation between B and C would not have been included in the qualitative scene
9. In Workshop on Spatial and Temporal Reasoning at ECAI 2004 Valencia Spain August 2004 Christian Freksa Using orientation information for gualitative spatial reasoning In A U Frank I Campari and U Formentini editors Theories and methods of spatio temporal reasoning in geographic space pages 162 178 Springer Berlin 1992a Christian Freksa Temporal reasoning based on semi intervals Artificial Intelligence 1 54 199 227 1992b Christian Freksa Markus Knauff Bernd Krieg Br ckner Bernhard Nebel and Thomas Barkowsky editors Spatial Cognition IV Reasoning Action Interaction Interna tional Conference Spatial Cognition 2004 volume 3343 of Lecture Notes in Artificial Intelligence Springer Berlin Heidelberg 2005 35 Bibliography P Ladkin and R Maddux On binary constraint problems Journal of the Association for Computing Machinery 41 3 435 469 1994 P Ladkin and A Reinefeld Effective solution of qualitative constraint problems Artificial Intelligence 57 105 124 1992 Gerard Ligozat Qualitative triangulation for spatial reasoning In Andrew U Frank and Irene Campari editors Spatial Information Theory A Theoretical Basis for GIS COSIT 93 Marciana Marina Elba Island Italy volume 716 of Lecture Notes in Computer Science pages 54 68 Springer 1993 ISBN 3 540 57207 4 Gerard Ligozat Categorical methods in qualitative reasoning The case for weak repre sentations In Spatial Informat
10. SparQ User Manual V0 6 Jan Oliver Wallgr n Lutz Frommberger Frank Dylla Diedrich Wolter N SFB TR 8 SPATIAL COGNITION Report Series of the Transregional Collaborative Research Center SFB TR 8 Spatial Cognition Universitat Bremen Universitat Freiburg Contact Address Dr Thomas Barkowsky SFB TR 8 Tel 49 421 218 8625 Universitat Bremen Fax 49 421 218 8620 P O Box 330 440 barkowsky sfbtr8 uni bremen de 28334 Bremen Germany www sfbtr8 uni bremen de O 2006 SFB TR 8 Spatial Cognition SFB TR8 Spatial Cognition Project R3 Q Shape SparQ User Manual V0 6 Jan Oliver Wallgr n Lutz Frommberger Frank Dylla Diedrich Wolter July 28 2006 Contents 1 Introduction 2 Installation of SparQ 2 1 Prereguisites 12 02 1075 Mende Yen Be a Be ie META BEG Porn 2 2 Obtaining the source code Ke 2 3 Building the binaries 2 2 2 Con on L 3 Reasoning with Qualitative Spatial Relations 3 1 What is a qualitative spatial calculus e 3 2 Constraint networks consistency and consistent scenarios 3 3 Binary and ternary spatial calculi ke 3 4 Ternary calculi and their operations se 3 5 Path consistency and backtracking search 4 Supported Calculi 4 1 FlipFlop calculus with LR refinement L 4 2 Singlecross calculus SCC 14 3204 34 aise G ee eave ok eee ECKE 4 3 Doublecross calculus DCC 2 fp ar a Na koti OW ay A eg 4 4 Dipole calculus family e 4 5 Oriented Point Relation Alge
11. an example in Python 5 5 Specifying calculi in SparQ For most calculi it should be rather easy to include them into SparQ The main thing that has to be done is to provide the calculus specification Listing 5 2 shows an extract of the definition of a simple exemplary calculus for reasoning about distances between three point objects distinguishing the three relations closer farther and same The specification is done in Lisp like syntax The arity of the calculus the base relations the identity relation and the different operations have to be specified using lists enclosed in parentheses e g when an operation returns a disjunction of base relations In this example the inverse operation applied to same yields same and composing closer and same results in the universal relation written as the disjunction of all base relations It is not required to specify the homing inverse short cut and inverse homing operations cmp Section 3 4 as these can be computed by applying the other operations e g inverse of short cut yields inverse short cut It is principally possible to leave more operations unspecified However this may mean that certain computations cannot be performed for this calculus In addition to the calculus specification it is necessary to provide the implementation of a qualifier function which for an n ary calculus takes n geometric objects of the corresponding base type as input and ret
12. as originally been proposed in Freksa 1992a The plane is partitioned into regions by the line going through A and B and the perpendicular at B This results in eight possible directions for C as illustrated in Fig 4 2 We denote these base relations by numbers from 0 to 7 instead of using linguistic prepositions e g 2 instead of left as originally done in Freksa 1992a Relations 0 2 4 6 are linear ones while relations 1 3 5 7 are planar In addition three special relations exist for the cases A B C bc A B z C dou and A B C tri A single cross relation relgcc is written as A B relscc C e g A BAC or A B dou C The relation depicted in Fig 4 2 is the relation A B 5 C Figure 4 2 The Single Cross Reference System 16 4 Supported Calculi 4 3 Doublecross calculus DCC Doublecross calculus DCC overview short name dcc double cross calculus parameters none arity ternary entity type 2D points description relates the referent C relative to the line between origin A and relatum B and the orthogonal lines through A and B resulting in 17 base relations base relations 0 4 1 5 2 5 3 5 3 6 3 7 4 0 5 1 5 2 5 3 6 3 723 4 4 4 b 4 a references Freksa 1992a The double cross calculus Freksa 1992a can be seen as an extension of the single cross calculus adding another perpendicular this time at A see Fig 4 3 right It can also be interpreted as the combination of two single cr
13. bra with granularity m OPRAm 4 6 The Region Connection Calculus family RCC 0 4 7 Allen s Interval Algebra IA 2 5 9 255 0466 Rr Rs 5 Using SparQ bob Quality VAA M oe fw a Re yop banc GA ag ne do ven ee le od 5 2 Computesrelation i e sol sone alse nee eae we ee kN 5 3 Constraint reasoning e 5 4 Including SparQ into own applications 5 5 Specifying calculi in Spar e 6 Outlook Planned Extensions 26 27 28 29 31 32 34 1 Introduction SparQ is a toolbox for representing space and reasoning about space based on qualitative spatial relations It is developed within the R3 Q Shape project of the SFB TR 8 Spa tial Cognition funded by the Deutsche Forschungsgemeinschaft DFG SparQ is based on results from the qualitative spatial reasoning QSR community which consists of researchers from a various disciplines including computer science artificial intelligence geography philosophy psychology and linguistics During the last two decades a mul titude of formal calculi over sets of spatial relations like overlaps left of north of have been proposed focusing on different aspects of space mereotopology orientation distance etc and dealing with different kinds of objects points line segments ex tended objects etc SparQ aims at making these qualitative spatial calculi and the developed reasoning techniques available in a single homogeneous framewo
14. classifies the calculi according to their arity binary ternary their domain points oriented points line segments regions and the aspect of space modeled orientation distance mereotopology 13 4 Supported Calculi arity domain aspect of space Calculus binary ternary point or point line seg region orient dist mereot FFC LR J SCC V V V DCC V NA 4 DRA V 4 4 OPRAm V V V RCC 5 8 v J Interval algebra NA Table 4 1 The calculi currently included in SparQ For entries marked by a x no qualifier is available yet Allen s Interval Algebra is originally intended for temporal reasoning but can also be interpreted spatially 14 4 Supported Calculi 4 1 FlipFlop calculus with CR refinement FlipFlop calculus FFC overview short name ffc ff flipflop calculus parameters none arity ternary entity type 2D points description relates the referent C relative to the line segment starting at origin A and ending at relatum B resulting in seven base rela tions base relations left r right f front b back s start e end dou tri references Ligozat 1993 Scivos and Nebel 2005 remark SparQ uses the LR refinement in its implementation of the FFC The FlipFlop calculus proposed in Ligozat 1993 describes the position of a point C the referent in the plane with respect to two other points A the origin and B the relatum as illustrated in Fig 4 1 It can for
15. e geometric description of a spatial configuration into a qualitative description based on one of the supported spatial calculi compute relation applies the operations defined in the calculi specifications intersec tion union complement converse composition etc to a set of spatial relations constraint reasoning performs computations on constraint networks We will take a closer look at each of these three modules in the next sections 5 1 Qualify The purpose of the qualify module is to turn a quantitative geometric scene description into a qualitative scene description composed of base relations from a particular calcu lus The calculus is specified via the calculus identifier that is passed with the call to SparQ Qualification is required for applications in which we want to perform qualitative computations over objects whose geometric parameters are known Figure 5 2 An example configuration of three dipoles The qualify module reads a quantitative scene description and generates a qualitative description A quantitative scene description is a space separated list of base object descriptions enclosed in parentheses Each base object description is a tuple consisting of an object identifier and object parameters that depend on the type of the object For instance let us say we are working with dipoles which are oriented line segments The object description of a dipole is of the form name s ys re Ye where
16. egions or non simple regions in the plane which can affect the correctness of the constraint based reasoning algorithms Since so far no qualifier for RCC is available in SparQ the exact domain is actually still not determined However we will assume the case of simple regions in the plane in the following RCC 8 Region Connection Calculus 8 RCC 8 overview short name calculus parameters arity entity type description base relations references remarks RCC 8 is the more fine grained variant of RCC calculi It distinguishes the eight base relations de disconnected ec externally connected po partially overlapping eq equal tpp tangential proper part ntpp non tangential proper part tppi tangential proper part inverse and nttpi non tangential proper part inverse which are illustrated in Fig 4 6 rcc 8 none binary simple regions in the plane describes the mereotopological relation between two regions dc disconnected ec externally connected po partially over lapping eq equal tpp tangential proper part ntpp non tangential proper part tppi tangential proper part inverse nttpi non tangential proper part inverse Randell et al 1992 Cohn et al 1997 no qualifier is available for this calculus yet 22 4 Supported Calculi adcb aecb a po b aeg b disconnected externally partially equal connected overlapping a tpp b a ntpp b tppi b nttpi b OO O O ta
17. er be ahead behind or on the same level as E The calculus in this case the PA defines a set of base relations ahead behind and same and provides the elementary reasoning steps in the form of operations defined over the base relations In our small example the applied operations were conversion which given the operation between x and y returns the relation between y and x thus the converse of ahead is behind and composition which takes the relations holding between X amp Y and Y amp Z and returns the relation holding between X amp Z e g composition of ahead and ahead is ahead Often the result of operations like the composition operation is not a single base relation but the union of more than one For instance knowing that X is ahead of Y and Y is behind Z yields the union of ahead behind and same Because of this the set of relations considered in a spatial calculus is not just the set of base relations but the set of all unions of base relations including the empty set and the union of all base relations the universal relation All operations of the calculus are then defined for all unions of base relations For example we can apply conversion to the information that X is either ahead or at the same level as Y to infer that Y is either behind or at the same level as X 3 Reasoning with Qualitative Spatial Relations 3 2 Constraint networks consistency and consistent scenarios A spatial configuration of a finite s
18. es 1 Introduction Section 3 offers a small introduction to qualitative spatial calculi and qualitative spatial reasoning in general and introduces the relevant terms required for working with SparQ The spatial calculi currently supported by SparQ are documented in Section 4 of this manual SparQ is designed in a way that makes it easy to specify and integrate new calculi For an up to date list of supported calculi and the newest version of this manual please visit our website http www sfbtr8 uni bremen de project r3 sparq For ques tions or feedback please send us an e mail to the address below We are always interested in suggestions for improvement and in hearing about your experience with SparQ The R3 Q Shape team qshape sfbtr8 uni bremen de 2 Installation of SparQ SparQ is written for POSIX systems Its functionality is continuously tested on Linux Solaris and Mac OS X but it should run on any Unix system without problems At the moment there is no Windows version available If you want to run SparQ on Windows please contact us 2 1 Prerequisites SparQ is currently not available in binary versions To install and use SparQ you need e gcc and g version 2 95 or higher e Steel Bank Common Lisp SBCL version 0 9 10 or higher 2 2 Obtaining the source code The source code of the actual version of SparQ and appropriate documentation is available at the SparQ homepage http www sfbtr8 uni bremen de projec
19. et of objects from the domain as given by sentences 1 5 can be described as a constraint network as shown in Fig 3 2 It consists of a variable for each object represented by the nodes of the network and edges labeled with relations from the considered calculus denoted as sets of base relations For instance sentence 1 is represented by the edge going from A to B labeled with behind If no edge connects two nodes this corresponds to an edge labeled with the universal relation U which is usually omitted ahead me same ahead Figure 3 2 The situation described by sentences 1 5 as a constraint network As we have seen in our example the information given in a constraint network can be inconsistent This means no objects from the domain can be assigned to the variables so that all the constraints given by the spatial relations annotated to the edges are satisfied If on the other hand such an assignment can be found the constraint network is said to be consistent or satisfiable or realizable Determining whether a constraint network is consistent is a fundamental problem of qualitative spatial reasoning Special techniques for determining consistency based on the operations of the calculus especially the composition operation have been developed However it is important to note that the soundness of these methods depends on the properties of the calculus at hand and are often still subject of ongoing investigations For
20. from the constraints without ending up with the empty relation we know that the original network is consistent If this cannot be achieved the network has to be inconsistent Unfortunately it is usually not the case that path consistency decides consistency However sometimes path consistency is sufficient to decide consistency at least for a subset S of the relations from R for instance the set of base relations On the one hand this means that whenever our constraint networks only contains labels which are base relations we again can use path consistency as a criterion to decide consistency On the other hand if the subset S exhaustively splits R which means that every re lation from R can be expressed as a union of relations from S this at least allows to formulate a backtracking algorithm to determine consistency by recursively splitting the constraints and using path consistency as a decision procedure for the resulting CSPs with constraints from S Ladkin and Reinefeld 1992 To enforce path consistency syntactic procedures called algebraic closure algorithms have been developed that are based on the operations of the calculus the composition operation in particular and work in O n time for binary calculi and O n for ternary calculi where n is the number of variables But again we have to note that these syntactic procedures do not necessarily yield the correct results with respect to path consistency as defined above Whether al
21. gebraic closure coincides with path consistency needs be investigated for each calculus individually and we again refer to the literature listed in the individual calculus descriptions in Section 4 12 4 Supported Calculi In this section we briefly describe the spatial calculi currently supported by SparQ Some calculi are actually calculi families for which a set of calculus parameters needs to be specified in order to obtain a particular calculus instance For instance for the OPRA n calculus the granularity number of partitioning lines has to be specified as a calculus parameter Each calculi description in this section starts with a box summarizing the main charac teristics of the considered calculus The meaning of the entries in the box are explained below short name the name used in SparQ to refer to this calculus calculus parameters the parameters that need to be specified whenever using this calculus arity the arity of the relations of this calculus binary or ternary entity type the spatial entities related in this calculus 2D points oriented 2D points line segments dipoles etc description a short description of the calculus base relations a naming scheme or list of the base relations of the calculus references references to literature about this calculus remarks special remarks concerning the calculus A quick overview on the implemented calculi is given in Tab 4 1 which also
22. gorithms are insufficient to decide consistency Again please feel free to contact us if you have any ideas or wishes concerning the extension or improvement of SparQ 34 Bibliography J F Allen Maintaining knowledge about temporal intervals Communications of the ACM pages 832 843 November 1983 A G Cohn B Bennett J M Gooday and N Gotts RCC A calculus for region based qualitative spatial reasoning GeoInformatica 1 275 316 1997 Anthony G Cohn Qualitative spatial representation and reasoning techniques In Gerhard Brewka Christopher Habel and Bernhard Nebel editors KI 97 Advances in Artificial Intelligence 21st Annual German Conference on Artificial Intelligence Freiburg Germany September 9 12 1997 Proceedings volume 1303 of Lecture Notes in Computer Science pages 1 30 Berlin 1997 Springer Anthony G Cohn and Shyamanta M Hazarika Qualitative spatial representation and reasoning An overview Fundamenta Informaticae 46 1 2 1 29 2001 URL http citeseer ist psu edu cohn0igualitative html Ivo Diintsch Relation algebras and their application in temporal and spatial reasoning Artificial Intelligence Review 23 4 315 357 2005 Frank Dylla and Reinhard Moratz Exploiting gualitative spatial neighborhoods in the situation calculus In Freksa et al 2005 pages 304 322 Frank Dylla and Reinhard Moratz Empirical complexity issues of practical gualita tive spatial reasoning about relative position
23. hus our domain the set of spatial objects considered is the set of all 1D points B A C gt C gt E gt A C D B E Figure 3 1 A possible situation in a boat race which can be modeled by 1D points on an oriented line and be described by qualitative relations from the Point Algebra C C gt SE D We now distinguish three relations between objects from our domain A boat can be This example has been borrowed from Ligozat 2005 3 Reasoning with Qualitative Spatial Relations ahead of another boat behind it or on the same level These relations can be used to formulate knowledge about the current situation in the race For instance our friend tells us the following 1 Ais behind B 2 Eis ahead of B 3 A is behind C 4 D is on the same level as C 5 A is ahead of D From this information we are able to conclude that our friend must have made an error probably confusing the names of the participants We know that A is behind C sentence 3 and D is behind A conversion of sentence 5 From composing these two facts it follows that C and D cannot be on the same level which contradicts sentence 4 On the other hand only taking the first three sentences into account we can conclude that E is also ahead of A by composing the facts A is behind B sentence 1 and B is behind E conversion of sentence 2 However this information is not sufficient to derive the exact relation between C and E as C can eith
24. ing algorithm to generate all possible scenarios and checks them for path consistency as described above A second module specific parameter determines what is returned as the result of the search return This parameter determines what is returned in case of a constraint network for which path consistent scenarios can be found It can take the values first which returns the first path consistent scenario all which returns all path consistent scenarios and interactive which returns one solution and allows to ask for the next solution until all solutions have been iterated Path consistency is also used as a forward checking method during the search to make it more efficient For certain calculi the existence of a path consistent scenario implies global consistency However this again has to be investigated for each calculus As a future extension it is planned to allow to specify splitting subsets of a calculus for which path consistency implies global consistency and provide a variant of the backtracking algorithm that decides global consistency by searching for path consistent instantiations that only contain relations from the splitting subset In the following example we use first as additional parameter so that only the first solution found is returned sparq constraint reasoning dra 24 scenario consistency first A rele C A ells B C errs B D srsl C A rser D D rrrl B gt B rlrr D C s
25. ion Theory Cognitive and Computational Foundations Proceedings of COSIT 05 2005 Reinhard Moratz Representing relative direction as a binary relation of oriented points In ECAI 2006 Proceedings of the 17th European Conference on Artificial Intelligence 2006 to appear Reinhard Moratz Jochen Renz and Diedrich Wolter Qualitative spatial reasoning about line segments In W Horn editor Proceedings of the 14th European Conference on Artificial Intelligence ECAI Berlin Germany 2000 IOS Press Reinhard Moratz Frank Dylla and Lutz Frommberger A relative orientation algebra with adjustable granularity In Proceedings of the Workshop on Agents in Real Time and Dynamic Environments IJCAI 05 2005 David A Randell Zhan Cui and Anthony Cohn A spatial logic based on regions and connection In Bernhard Nebel Charles Rich and William Swartout editors Principles of Knowledge Representation and Reasoning Proceedings of the Third In ternational Conference KR 92 pages 165 176 Morgan Kaufmann San Mateo CA 1992 Jochen Renz and G rard Ligozat Weak composition for qualitative spatial and temporal reasoning In Principles and Practice of Constraint Programming CP 2005 11th International Conference CP 2005 Sitges Spain October 1 5 2005 Proceedings volume 3709 of LNCS pages 534 548 Springer 2005 C Schlieder Reasoning about ordering In Spatial Information Theory A Theoretical Basis for GIS COSIT 95 vo
26. ions as implemented functions and uses a caching mechanism to store often required results 33 6 Outlook Planned Extensions Besides extending the set of supported qualitative calculi the following extensions are currently planned for the future neighborhood based reasoning a module for reasoning based on the notion of con ceptual neighborhood Freksa 1992b that could for instance be used for constraint relaxation and spatial planning quantification a module that analogous to the qualify module takes a consistent qualitative scene description and turns it into a prototypical quantitative scene description geometric reasoning based on Gr bner bases a module intended for calculus devel opers that for instance allows to derive composition tables automatically from algebraic descriptions of the base relations of the calculus cmp Moratz et al 2000 interfaces amp XML specification interfaces to exchange calculus specifications with other QSR frameworks e g W lfl and Mossakowski 2005 and a general XML format for the specification of qualitative calculi Further goals are to continue the optimization of the algorithms employed in SparQ for instance by applying maximal tractable subsets for the constraint reasoning part and to include new results from the QSR community as they become available in particular with respect to constraint reasoning techniques for calculi for which the standard algebraic closure al
27. lgebra OPRA overview short name opra calculus parameters granularity number of partitioning lines number of planar relations 2 must be gt 0 arity binary entity type oriented 2D points description relates two oriented points a and b with respect to granularity m base relations fi j with 7 7 0 4m 1 if a and b have different posi tions i with i 0 4m 1 if they have the same position references Moratz et al 2005 Moratz 2006 The domain of the Oriented Point Relation Algebra OPRAn Moratz et al 2005 Moratz 2006 is the set of oriented points points in the plane with an additional direc tion parameter The calculus relates two oriented points with respect to their relative orientation towards each other An oriented point O can be described by its Cartesian coordinates zo yo R and a direction 0 27 with respect to an absolute reference direction and thus D R x 0 27 The OPRAm calculus is suited for dealing with objects that have an intrinsic front or move in a particular direction and can be abstracted as points The exact set of base relations distinguished in OPRAn depends on the granularity parameter m N For each of the two related oriented points m lines are used to partition the plane into 2m planar and 2m linear regions Fig 4 5 shows the partitions for the cases m 2 a and m 4 b The orientation of the two points is depicted by the arrows
28. lsr D C errs B A rser D A ells B A rele C 30 5 Using SparQ In case of an inconsistent constraint network SparQ returns Not consistent as in the following example sparq constraint reasoning dra 24 scenario consistency first A rele C A ells B C errs B D srsl C A rser D D rllr B gt Not consistent The action refine returns the disjunction of two constraint networks Analogously extend returns the conjunction sparq constraint reasoning dra 24 refine A rele errs B A errs B A errs B V amp sparq constraint reasoning dra 24 extend A rele B A errs B A rele errs B VAR 5 4 Including SparQ into own applications SparQ can also run in server mode which makes it easy to integrate it into own ap plications We have chosen a client server approach as it allows for straightforward integration independent of the programming language used for implementing the appli cation When run in server mode SparQ takes TCP IP connections and interacts with the client via simple plain text line based communication This means the client sends com mands which consist of everything following the sparq in the examples in this text and can then read the results from the TCP IP stream SparQ is started in server mode by providing the command line option interactive i optionally followed by port p to specify the port
29. lume 988 of Lecture Notes in Computer Science pages 341 349 Springer Berlin Heidelberg 1995 Alexander Scivos and Bernhard Nebel Double crossing Decidability and computational complexity of a qualitative calculus for navigation In Proceedings of COSIT 01 Berlin 2001 Springer 36 Bibliography Alexander Scivos and Bernhard Nebel The finest of its class The practical natural point based ternary calculus LR for qualitative spatial reasoning In Freksa et al 2005 pages 283 303 Peter van Beek Reasoning about qualitative temporal information Artificial Intelli gence 58 1 3 297 321 1992 M B Vilain H A Kautz and P G van Beek Constraint propagation algorithms for temporal reasoning A revised report In Readings in Qualitative Reasoning about Physical Systems Morgan Kaufmann San Mateo CA 1989 Stefan Wolfl and Till Mossakowski CASL specifications of qualitative calculi In Spa tial Information Theory Cognitive and Computational Foundations Proceedings of COSIT 05 2005 K Zimmermann and C Freksa Qualitative spatial reasoning using orientation distance and path knowledge Applied Intelligence 6 49 58 1996 37
30. m the same Cartesian product the three set operations union intersection and complement are already defined for every calculus independent of its arity Unio RUS x zeRvxreS Intersection ROS x reERAxeS Complement R U R x rEUAr R where R and S are relations from R Using our set notation for relations from R these set operations directly transfer to these sets For example the intersection of the PA relations behind same and same ahead is the relation same and the complement of same is behind ahead The other operations depend on the arity of the calculus Operations of binary calculi For binary calculi two more operations are utilized These are the converse and compo sition operations we have already encountered above Converse R y x x y ER Composition Ro S x z Jy D x y RA y z S Again here are two examples from the PA The converse of behind is ahead and the composition of ahead and ahead same is ahead if A is ahead of B and B is ahead or at the same level as C than A has to be ahead of C For some calculi the composition operation defined does not comply to the strong definition above as this would result in a composition that is not closed for the set of relations R and no finite set of relations including the base relations exists for which this is the case In this case the used composition operation is the weak composition
31. more details on this issue we refer to Renz and Ligozat 2005 and the literature on individual calculi listed in Section 4 A constraint network in which every constraint between two variables is a base relation is called atomic or a scenario This means all spatial relations between two objects are completely determined with respect to the employed calculus and the remaining questions is if the network is consistent or not However if a constraint network contains relations that are not base relations like in Fig 3 3 a we might also be interested in finding a scenario that is a refinement of the original network meaning it has been derived by removing individual base relations from the sets annotated to the edges and that is consistent Fig 3 3 b shows such a consistent scenario for the network in 3 Reasoning with Qualitative Spatial Relations Fig 3 3 a If such a consistent scenario can be found we also know that the original network is consistent Otherwise we know it is inconsistent Of course it is possible that more than one consistent scenario exists for a given constraint network and we might be interested in finding only one or all of these An alternative consistent scenario is depicted in Fig 3 3 c behind behind behind behind behind behind O ond e ahead Ame a b c Figure 3 3 A non atomic constraint network a with possible consistent scenarios b and c The problems of determining consi
32. nclude disjunctions and may be inconsis tent and or underspecified and performs an operation on it e g a particular kind of consistency check Which type of operation is executed depends on the first mod ule specific parameter Actually four operations are implemented path consistency scenario consistency refine and extend action The actions currently provided are path consistency and scenario consisten cy which determine which kind of consistency check is performed as well as refine and extend which perform set operations on constraint networks The action path consistency causes the module to enforce path consistency on the con straint network using van Beek s algorithm van Beek 1992 or detect the inconsistency of the network in the process In case of ternary calculus the canonical extension of van Beek s algorithm as described in Dylla and Moratz 2004 is used We could for instance check if the scene description generated by the qualify module in Section 5 1 is path consistent which of course it is To make it slightly more interesting we add the base relation ells to the constraint between A and C resulting in a constraint network that is not path consistent sparq constraint reasoning dra 24 path consistency A rlir B A ells rllr C B 1rrl C gt Modified network gt B 1rr1 C A rllr C A rllr B The result is a path consiste
33. ngential non tangential tangential proper non tangential proper part proper part part inverse proper part inverse Figure 4 6 The RCC 8 base relations RCC 5 Region Connection Calculus 5 RCC 5 overview short name rcc 5 calculus parameters none arity binary entity type simple regions in the plane description describes the mereotopological relation between two regions base relations dr discrete from po partially overlapping eq equal pp proper part ppi proper part inverse references Cohn et al 1997 remarks no qualifier is available for this calculus yet RCC 5 is a coarser version of RCC 8 The RCC 8 relations dc and ec are combined into one relation called dr Similarly nttp and ttp are combined into pp and nttpi and ttpi into ppi 23 4 Supported Calculi 4 7 Allen s Interval Algebra IA Allen s Interval Algebra overview short name allen aia ia calculus parameters none arity binary entity type intervals defined by a start and end point on a unidirectional time line description describes the mereotopological relation between two intervals base relations b before bi before inverse m meets mi meets inverse o overlaps oi overlaps inverse s starts si starts inverse d during di during inverse f finishes fi finishes inverse eq equals references Allen 1983 remarks no qualifier is available for this calculus yet Allen s interval algebra IA
34. nt constraint network in which ells has been removed The output Modified network indicates that the original network was not path consistent and had to be changed Otherwise the result would have started with Unmodified network In the next example we remove the relation rlir from the disjunction between A and C This results in a constraint network that cannot be made path consistent which implies that it is not globally consistent 3In former versions of SparQ the refine action was called merge This naming is still valid for backward compatibility reasons but may vanish in the future 29 5 Using SparQ sparq constraint reasoning dra 24 path consistency A rllr B A ells C BlrrlC gt Not consistent gt B 1rr1 A O A riir B SparQ correctly determines that the network is inconsistent and returns the constraint network in the state in which the inconsistency showed up indicated by the empty relation between A and C In a last path consistency example we use the ternary double cross calculus sparq constraint reasoning dcc path consistency A B 7 36 3 O BC 7 36 3 5 3 D A B 3 6 3 7 D gt Not consistent gt AB 36 37 D A B 637 3 CO BC 5_3 6_3 7_3 D DC A If scenario consistency is provided as argument the constraint reasoning module checks if a path consistent scenario exists for the given network It uses a backtrack
35. on relates two dipoles using the FlipFlop relations between the start and end point of one dipole and the other dipole base relations 4 symbol words where each symbol can be either left r right s start or e end not all combinations are possible references Moratz et al 2000 Figure 4 4 A dipole configuration dag rill dcp in the coarse grained dipole relation algebra DRA The coarse grained dipole calculus variant DR A describes the orientation relation between two dipoles dag and dcp with the preliminary of A B C and D being in general position i e no three disjoint points are collinear Each base relation is a 4 18 4 Supported Calculi tuple r1 r2 r3 r4 of FlipFlop relations relating a point from one of the dipoles with the other dipole r describes the relation of C with respect to the dipole d AB T2 of D with respect to dap r3 of A with respect to dep and r4 of B with respect to dop The distinguished FlipFlop relations are left right start and end see Fig 4 1 Dipole relations are usually written without commas and parentheses e g rrll Thus the example in Fig 4 4 shows the relation d Ap TII dap Since the underlying points for a DRA relation need to be in general position r can only take the values left right start or end resulting in 24 base relations 19 4 Supported Calculi 4 5 Oriented Point Relation Algebra with granularity m OPRAm Oriented Point Relation A
36. oss relations the first describing the position of C with respect to B as seen from A and the second with respect to A as seen from B cf Fig 4 3 left The resulting partition distinguishes 13 relations 7 linear and 6 planar denoted by tuples derived from the two underlying SCC reference frames and four special cases A CZ B 4 a AF B C b 4 A BFC dou and A B C tri resulting in 17 base relations overall In Fig 4 3 the relation A B 5 3 C is depicted Figure 4 3 The two Single Cross reference frames resulting in the overall Double Cross Calculus reference frame 17 4 Supported Calculi 4 4 Dipole calculus family A dipole is an oriented line segment as e g determined by a start and an end point We will write dag for a dipole defined by start point A and end point B The idea of using dipoles was first introduced by Schlieder 1995 and extended resulting in the coarse grained Dipole Relation Algebra DRA Moratz et al 2000 Later a fine grained version of the dipole calculus DRA has been proposed Dylla and Moratz 2005 and which has further been extended to DRAr Dylla and Moratz 2005 In SparQ currently only the coarse grained version DRA is available Coarse grained Dipole Relation Algebra DR A Coarse grained dipole calculus DR A overview short name dra 24 dipole coarse calculus parameters none arity binary entity type dipoles in the plane oriented line segments descripti
37. rk that can easily be included into AI applications The current version of SparQ provides the following services which will be thoroughly explained later in this manual qualification A quantitative geometric description of a spatial configuration can be transformed into a qualitative description employing one of the supported spatial calculi computing with relations The operations defined in a calculus intersection union complement converse composition etc can be employed to perform algebraic computations with the spatial relations from one of the supported calculi constraint reasoning Techniques for solving relational constraint satisfaction prob lems CSPs based on the supported calculi can be used to check the consistency of spatial information determine if a particular relation can hold between certain objects or derive a concrete possible scenario from under specified information In its current state SparQ is a set of C libraries calculi specifications and a main program written in Lisp It is available for POSIX systems installation is explained in Section 2 The main program can either be used directly from the console or included into own applications via TCP IP streams The details of using SparQ are explained in Section 5 Using the libraries directly is neither documented nor recommended as their interfaces have not been unified so far and not all parts of the toolbox come in the form of librari
38. starting at A and B respectively The regions are numbered from 0 to 4m 1 region 0 always coincides with the orientation of the point An OPR A base relation relopn Am consists of a pair i j where i is the number of the region of A which contains B while j is the number of the region of B that contains A These relations are usually written as A A B with i j Z4m Thus the examples in Fig 4 5 depict the relations A 2 1 B and A 4 33 B Additional base relations called same relations describe situations in which the positions of both oriented points coincide In these cases the relation is determined 1 Zim defines a cyclic group with 4m elements 20 4 Supported Calculi Q 15 44 b m 4 A aZi B c case where A and B coincide A2 1B Figure 4 5 Two oriented points related at different granularities by the number s of the region of into which the orientation arrow of B falls as illustrated in Fig 4 5 c These relations are written as A 2 s B A 2 1 B in the example The complete set R of OPRA relations is the power set of the base relations de scribed above 21 4 Supported Calculi 4 6 The Region Connection Calculus family RCC The calculi from the RCC family RCC 8 and RCC 5 allow mereotopological reasoning reasoning about connection and part of relationships about simple regions in the plane Other domains involving regions can also be considered in the context of RCC e g 3D r
39. stency and finding consistent scenarios are sub sumed under the term constraint based reasoning throughout this text 3 3 Binary and ternary spatial calculi After giving a rather intuitive introduction to qualitative spatial calculi we want to give a more formal definition of a spatial calculus and especially the operations that need to be defined for a calculus This set of operations differs depending on whether we are dealing with a binary calculus like the PA in which all relations relate two objects or with a ternary calculus in which all relations relate three objects As we have seen an n ary qualitative spatial calculus consists of 1 a domain D which contains the considered spatial objects D could for instance be the R when we are considering point objects in the plane 2 a finite set BR of n ary relations on D which are called base relations typically the set of base relations is jointly exhaustive and pairwise disjoint which means that exactly one of the base relations holds for each n tuple from D 3 a finite overall set of relations R that is derived from BR by taking all possible unions of base relations as we have seen it is common to write these relations as sets of base relations in which case R 25 4 a set of operations closed over R 3 Reasoning with Qualitative Spatial Relations Let us now turn to the operations that need to be defined As all relations for a given calculus are subsets of tuples fro
40. t r3 sparg 2 3 Building the binaries To build a running version of SparQ unpack the source code package enter the newly created SparQ directory called sparg lt version gt and run configure Usually no errors should occur and you should be able to build the SparQ executables by running make All executables will be installed within the SparQ directory If you encounter any prob lems during the build process please contact the authors Inttp sbel sourceforge net 3 Reasoning with Qualitative Spatial Relations In this section we provide a brief introduction on qualitative spatial reasoning and explain the most important terms required when dealing with qualitative spatial calculi in SparQ For more in depth introductions to the field we refer to Cohn and Hazarika 2001 Cohn 1997 Ladkin and Reinefeld 1992 Ladkin and Maddux 1994 Diintsch 2005 and the references provided for particular calculi in Section 4 3 1 What is a qualitative spatial calculus A qualitative calculus consists of a set of relations between objects from a certain domain and operations defined on these relations Let us start with an easy example the spatial version of the Point Algebra PA Vilain et al 1989 Imagine we are being told about a boat race on a river by a friend on the phone We can model the river as an oriented line and the boats of the 5 participants A B C D E as points moving along the line see Fig 3 1 T
41. urns the relation holding between these objects The qualifier function encapsulates the methods for computing the qualitative relations from quantitative geometric descriptions If it is not provided the qualify module will 3 not work for this calculus 32 o 10 5 Using SparQ def calculus Relative distance calculus reldistcalculus arity ternary base relations same closer farther identity relation same inverse operation same same closer closer farther farther shortcut operation same same closer farther farther closer composition operation same same same closer farther same closer same closer farther same farther same closer farther closer same same closer farther closer closer same closer farther closer farther same closer farther farther same same closer farther farther closer same closer farther farther farther same closer farther Listing 5 2 Specification of a simple ternary calculus for reasoning about distances For some calculi it is not possible to provide operations in form of simple tables as in the example For instance OPRA has an additional parameter that specifies the granularity and influences the number of base relations Thus the operations can only be provided in procedural form meaning the result of the operations are computed from the input relations when they are required For these cases SparQ allows to provide the operat
Download Pdf Manuals
Related Search