Home

SparQ User Manual V0.7 - SFB/TR8

1. A C ED 3BED A B er A B C es Definition 6 binary composition in ternary calculi In a ternary calculus lt B D gt the composition operation o is defined as binary operator ros AB D eD 3CED A B C er B C D e s 12 2 Reasoning with Qualitative Spatial Relations 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 SparQ Besides the definition of ternary composition employed in SparQ and by many oth ers for example 1992a ternary composition has also been defined as ternary operator more specifically a n ary operator in an n ary calculus Condotta et al 2006 Definition 7 n ary composition In a n ary calculus lt B D gt the n ary composition operation e is defined as follows e ri To E A142 An eE D IBeD Ai A An 1 B Eri A A1 A An 2 B An To A B A2 Aa An fn 2 3 5 Weak vs Strong Operations By definition of the operations it is not clear that for example the converse of a qualitative base relation itself is a base relation too In fact this is not the case for some calculi It may even be the case that no finite set of relations exists that describes the results of the operations Take for example the aforement
2. The action algebraic closure causes the module to enforce path consistency on the con straint network using Mackworth s AC 3 algorithm Mackworth 1977 or detect the inconsistency of the network in the process In case of ternary calculus the canonical ex tension of the AC 3 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 3 3 2In 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 23 3 Using SparQ is algebraically closed 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 algebraically closed sparq constraint reasoning dra 24 algebraic closure DA sal be 35 UA alll sells 3 Irri gt Modified network gt B Irrl C A rlir C A rllr B The result is an algebraically closed constraint network in which ells has been removed The output Modified network indicates that the original network was not algebraically closed and had to be changed Otherwise the result would have started with Unmodified network In the next example we remove the relation rllr from the disjunction between A and C This results in a constraint network for which
3. 43 A Implemented Calculi A 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 S 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 rd Dylla and Moratz 2005 and which has further been extended to DRA 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 calculus identifier dra 24 dipole coarse calculus parameters none arity binary entity type dipoles in the plane oriented line segments description 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 2000 Figure A 2 A dipole configuration dap 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 thre
4. 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 r111 ells 1111 1r11 Here the result is a disjunction of 10 base relations It is also possible to have disjunc tions 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 reve LIL gt rrll Note that you need to put relation specifications in quotes when giving them as argu ments on the command line SparQ can also process nested computations if individual parts are enclosed in paren theses e g computing the complement of the converse of a relation can be done as follows sparq compute relation dra 24 complement converse rr gt ells errs eses lere 1111 lllr llrl 1111 lrrl lsel rele rlll rllr rrll rrlr rrrl rser sese slsr srsl The following operations are currently implemented see section 2 3 1 spatial composition comp r s 5 ros ternary composition tcomp r s t gt e r s t n ary composition ncomp Fi sey fn erp y Tn converse cnv rer homing hm r e hm r 3 3 3 homingi hmi inverse inv r gt inv hm r r inv r shortcut sc re sc r 3 shortcuti scil r gt inv sc r 22 3 Using Spar
5. oi overlaps inverse s starts si starts inverse d during di during inverse f finishes fi finishes inverse eq equals Allen s interval algebra IA Allen 1983 relates pairs of time intervals Time inter val x is represented as a tuple of a starting point x and end point x with s lt Te using real numbers e g life of Bach 1685 1750 Altogether 13 base relations are distinguished by comparing the start and end points of the intervals relation term example definition b x before y XXX Te lt Ys bi y after x Yyy m x meets y XXXX Te Ys mi y met by x yyyy o x overlaps y XXXXX Ls lt ys lt Le oi y overlapped by x yyyyy Le lt Ye d x during y XXX Ls gt Ys di y includes x YY YY Y YY Te lt Ye S x starts y XXX Ls YsA si y started by x yyyyyyy Le lt Ye f x finishes y XXX Le YeN fi y finished by x yyyyyyy Ts gt Ys eq x equals y XXXXXXX Ls Ys YYYYYYy Te ye 41 A Implemented Calculi A 2 Cardinal Direction Calculus Cardinal Direction Calculus overview calculus identifier cardir calculus parameters none arity binary entity type 2D points description describes the orientation of two point regarding and absolute orientation base relations N NE E SE S SW W NW EQ references 1991 1998 introduced the cardinal direction calculus The euclidian plane P is partitioned into regions with respect to a refere
6. 8 Oriented Point Reasoning Algebra With Granularity m OPRA Oriented Point Relation Algebra OPR A overview calculus identifier 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 i j with 7 7 0 4m 1 if a and b have different posi tions i with 0 4m 1 if they have the same position references Morata et al 2005 Moraz 2006 The no of the Oriented Point Relation Algebra OPR Am Moratz et al 2005 Moratz 2006 is the set of oriented points points in the plane with an additional direc tion eer 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 pg 0 27 with respect to an absolute reference direction and thus D R x 0 27 The OPRA n 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 OPR Am 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 shows the partitions for
7. Anthony G Cohn and Shyamanta M Hazarika Qualitative spatial representation and reasoning An overview Fundamenta Informaticae 46 1 2 1 29 2001 URL citeseer ist psu edu cohn01qualitative html Jean Francois Condotta G rard Ligozat and Mahmoud Saade A generic toolkit for n ary qualitative temporal and spatial calculi In Proceedings of the 18th Interna tional Symposium on Temporal Representation and Reasoning TIME 06 Budapest Hungary 2006 Ivo D ntsch Relation algebras and their application in temporal and spatial reasoning Artificial Intelligence Review 23 4 315 357 2005 Frank Dylla and Reinhard Moratz Exploiting qualitative spatial neighborhoods in the situation calculus In 2005 pages 304 322 Frank Dylla and Reinhard Moratz Empirical complexity issues of practical qualita tive spatial reasoning about relative position In Workshop on Spatial and Temporal Reasoning at ECAI 2004 Valencia Spain August 2004 Andrew Frank Qualitative spatial reasoning about cardinal directions In Proceedings of the American Congress on Surveying and Mapping ACSM ASPRS pages 148 167 Baltimore Maryland USA 1991 Christian Freksa Using orientation information for qualitative 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 37 Bibliography Christian Freksa Temporal reasonin
8. 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 operations 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 more details on this issue we refer to Renz and Ligozat 2005 and the literature on individual calculi listed in Appendix A 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 question is if the network is consistent or not However if a constraint network contains relations that are not base relations like in Fig 2 3 a we might also be interested in finding a 2 Reasoning with Qualitative Spatial Relations s
9. Br A Definition 4 converse In a binary calculus lt B D gt the unary converse operation is defined as follows r A B A B D A B A er Obviously there are more ways to change perspectives in a general n ary calculus for n gt 2 Currently only ternary 3 ary calculi are also important to QSR For ternary calculi 5 unary operations are commonly considered that are defined analogously to the converse in binary calculi The following table gives a complete overview operation SparQ names _ effect binary calculi converse converse cnv ArB Br A ternary calculi inverse inv inverse A B r C B A inv r C shortcut sc shortcut A B r C A C sc r B shortcut inverse sci shortcuti A B r C A sci r B homing hm homing A B r C B C hm r A homing inverse hmi homingi A B r C C B hmi r A These operations may further be generalized for n ary calculi Given the unavailability of calculi with arities higher than 3 SparQ currently implements the operations for binary and ternary calculi only 2 3 4 Operations that Integrate Admittingly the heading of this paragraph is misleading in that there is only one kind operation defined that integrates relations the composition operations most notably the binary composition o Definition 5 binary composition in binary calculi In a binary calculus lt B D gt the composition operation o is defined as binary operator ros
10. Geometric Orientation Alignment Calculus A 8 Oriented Point Reasoning Algebra With Granularity m OPRAm A 9 Point Calculus Point Algebra A 10 Qualitative Trajectory Calculus Family B Quick Reference B 1 Command Summary B 2 Interactive Model B 3 List of Calculil A 11 The Region Connection Calculus family RCC A 12 Singlecross Calculus SCC About SparQ 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 framework that is re leased under the GPL license for freely available software
11. algebraic closure detects an inconsistency which means it is not globally consistent sparq constraint reasoning dra 24 algebraic closure A rllr B A ells C B 1rr1 C gt Not consistent gt B Irrl Cc A O C A rllr 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 example for algebraic closure we use the ternary double cross calculus sparq constraint reasoning dcc algebraic closure CA B 123 6 3 C BC 723 6 3 5 3 D A B 3 6 3 7 D gt Not consistent gt AB 3 6 37 D A B O C BC 53 63 73 D D C 04 15 25 35 36 327 4 4 5 3 63 7 3 la 0 If scenario consistency is provided as argument the constraint reasoning module checks if an algebraically closed scenario exists for the given network It uses a backtrack ing algorithm to generate all possible scenarios and checks them via algebraic closure 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 a
12. and can easily be included into applications Our aim is providing a common toolbox spanning across all techniques of qualitative reasoning thereby providing a universal toolbox to the user Currently we provide techniques for e mapping the continuos domain to qualitative representations e manipulating symbolical propositions e checking consistency of qualitative information e interfacing with other reasoning tools SparQ is designed for the application designer or researcher working in a field other than qualitative reasoning offering access to reasoning techniques in an easy to use manner If you are new to qualitative spatial reasoning see the following chapter for an introduction to this field and the services it can offer to your field SparQ is also designed for the researcher working on qualitative spatial reasoning It provides an implementation toolbox of key techniques in QSR making experimental analysis easier Furthermore SparQ offers an easy format to specify new calculi This eases distribution of new calculi and enables researches to more easily compare different calculi for example in an application context In this manner SparQ is a community effort it provides a rich repertoire of qualitative calculi to application designers We would be happy to include your calculus Last but not least SparQ offers tools for analyzing QSR calculi thereby supporting the calculus designer Contents This document provides answers t
13. 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 algebraic 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 Appendix A 15 3 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 3 11 The dashed parts are extensions planned for the future see section 4 2 qualify compute relation constraint reasoning SparQ EE neighborhood reasoning specifications Figure 3 1 Module architecture of the SparQ toolbox The general syntax for using SparQ is sparq lt module gt lt calculus gt lt module specific parameters gt where module designates the particular module to use calculus refers to the qual itative calculus to use and the remainder of the command line give command specific arguments which will be explained in the following SparQ can also be used in interactive mode see section 3 7 the general syntax is the same though Example sparq compute relation rcc 8 composition dc ntpp computes the composition
14. 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 2 Reasoning with Qualitative Spatial Relations 2 2 Constraint Networks Consistency and Consistent Scenarios A spatial configuration of a finite set of objects from the domain as given by sentences 1 5 can be described as a constraint network as shown in Fig 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 the union of all base relations expressing complete ignorance which is usually omitted ahead eo same ahead Figure 2 2 The situation described by sentences 1 5 as a constraint network
15. by the end of 2007 beginning of 2008 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 35 4 Internals 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 algorithms 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 36 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 Geolnformatica 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
16. calculus yet QTCp represents the relative distance change of two moving objects A and B at timepoints t and t 1 Intuitively the first character denotes whether A moves towards the starting position of B moves away or the distance stays the same O With dist x y denoting the distance between two positions and A denotes the position of ob ject A at time point t moving towards means dist A 1 Bi lt dist A Bi moving away means dist A 1 Bi gt dist A Bi and equidistant means dist A 1 Bi dist A Bi The second character represents the change in distance regarding B wrt A This results in nine base relations 3For avoiding the necessity to quote every single relation such that leading zeros are not ignored we realized the implementation with O s instead of zeros 53 A Implemented Calculi QTC in 1D With Distance and Velocity Qualitative Trajectory Calculus in 1D with velocity QTC B12 calculus identifier qtc b12 calculus parameters none arity binary entity type description describes the relative orientation between two trajectory seg ments base relations 0 0 0 ae OL i O O OOO references van de Weghe 2004 remarks no qualifier is available for this calculus yet The first two characters of QT Cp1s represent the same as QTCp11 The third char acter represents the relative velocitiy between A and B i e whether
17. 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 D ntsch 2005 and the references provided for particular calculi in Appendix 2 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 2 1 Thus our domain the set of spatial objects considered is the set of all 1D points B A ET c 0 UE DE A CDB E Figure 2 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 We now distinguish three relations between objects from our domain A boat can be This example has been borrowed from Ligozat 2005 2 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 t
18. just try out 3 2 1 Calculi Identifier SparQ commands require specifying a calculus For each calculus implemented in SparQ an identifier has been defined see the appendix for details on the calculi Calculi may have specific parameters for example the granularity parameter in OPRA These parameters are appended with a after the calculus base identifier opra 3 for example refers to OPR A3 17 3 Using SparQ calculus identifier s calculus section page allen aia ia cardir depcalc dep dipole coarse dra 24 double cross dcc alternative double cross adcc flipflop ffc ff geomori ori align point calculus pc point algebra pa rcc 5 rcc 8 reldistcalculus single cross scc opra qtc b11 Allen s interval algebra Allen 1983 Cardinal direction calculus Ligozat 1998 Sino OOD u Rasi and E my Moratz et al 12000 Double cross calculus Freksal 1992a using the original tuple naming scheme Double cross calculus Freksal 1992a using the alternative single number naming scheme FlipFlop calculus 1993 Geometric Orientation calculus Point algebra Vilain et al 1989 Region connection calculus RCC 5 Region connection calculus RCC 8 Exemplary calculus from this man ual Single cross calculus Freksa 1992a Oriented point reasoning algebra OPRAn ora PH Qualitative trajectory calculus in 1D with distance v
19. needs to be specified in order to obtain a particular calculus instance For instance for the OPRAm 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 40 A Implemented Calculi A 1 Allen s Interval Algebra IA Allen s Interval Algebra overview calculus identifier calculus parameters arity entity type description base relations references allen aia ia none binary intervals defined by a start and end point on a unidirectional time line describes the mereotopological relation between two intervals b before bi before inverse m meets mi meets inverse o overlaps
20. object A is slower than B is faster or both have the same velocity O Because the conditions of the three characters interfere in 1D only 17 out of 27 potential relations are feasible 54 A Implemented Calculi QTC in 2D With Distance Qualitative Trajectory Calculus in 2D QTC B21 calculus identifier calculus parameters arity entity type description base relations references remarks qtc b21 none binary dipole 2D trajectory positions at two different time points describes the relative orientation between two trajectory seg ments E 30 045 20 040 00 van de Weghe 2004 no qualifier is available for this calculus yet Q T C go is similar to QT Cp1 except dealing with trajectories in 2D instead of only 1D QTC in 2D With Distance and Velocity Qualitative Trajectory Calculus in 2D with velocity QTC B22 calculus identifier calculus parameters arity entity type description base relations references remarks qtc b22 none binary describes the relative orientation between two trajectory seg ments tt O x Dh O x t5 O van de Weghe 2004 no qualifier is available for this calculus yet Q I C go is similar to QTC 1a except dealing with trajectories in 2D instead of only 55 A Implemented Calculi 1D In contrast to QTCg a in 2D all 27 potential relations are feasible QTC in 2D With Distance and Side Qualitative Trajectory Cal
21. of the rcc 8 relations DC and NTPP SparQ prints the result dc ec po tpp ntpp to the shell which stands for DC EC PO T PP NTPP SparQ provides the following modules 16 3 Using SparQ qualify transforms a quantitative 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 3 1 Command Line Options Implemented switches v verbose mode primarily used for debugging purposes i interactive interactive mode see section 3 7 p lt port gt port in interactive mode listen for connection on TCP IP port rather using input from the shell 3 2 General Syntax SparQ is case insensitive so the notation leftOf and Leftof denote the same identifier When printing SparQ uses small letters for relations and capital letters for objects There are some characters that must not be used in specifiers for either relations or objects in particular parentheses punctuation and are not allowed Nearly all other character sequences may be used if in doubt refer to the ANSI Com mon Lisp standard on symbols or
22. this issue SparQ can use precise rational arithmetics and qualifiers imple mented in Lisp source code take advantage of this too For external C functions this is not possible though 32 3 Using SparQ al import socket import sys import time CRLF r n Define line endings def readline Read a line from the server Strip trailing CR and or LF input sockfile readline if not input raise EOFError if input 2 CRLF strip line endings input input 2 elif input 1 in CRLF input input 1 if len input 0 return readline if input 0 ignore comments return readline else return input def sendline line Send a line to the server sock send line CRLF unbuffered write create a socket sock socket socket socket AF_INET socket SOCK_STREAM connect to spargq sock connect localhost 4443 sockfile sock makefile rw qualify a geometrical scenario with DRA 24 sendline qualify dra 24 first2all A 4 6 9 0 5 B 5 502 C 4 5 6 0 read the answer and print it scene readline 6 read and throw away the sparq gt prompt print scene add an additional network B 4_1 C sendline constraint reasoning dra 24 refine scene B eses C scene2 readline 6 print scene2 check the new scenario for consistency sendline constraint reasoning dra 24 algebraic closure scene2 read consistency answer consistent readli
23. Q calculi theoretic closure r r2 m gt Cl r r2 Tpn Cl denotes the minimal set of relations that is closed under composition converse and inter section base closure Cl bra bra Drn Computes closure of the set of base relations set theoretic complement cmpl rer minus TS TNS union rs rUs intersection isec rsorns Commands marked Ware valid for binary calculi only commands marked are valid for ternary constraints only Note The commands closure and base closure are currently defined exclusively for binary calculi The closure of a set of relations may be very large and computation may consequently take very long 3 5 Constraint reasoning The constraint reasoning module reads a description of a constraint network which is a qualitative scene description that may include disjunctions and may be inconsistent and or underspecified and performs an operation on it e g a particular kind of con sistency check Which type of operation is executed depends on the first module specific parameter Currently four operations are implemented algebraic closure scenario consistency refine and extend action The actions currently provided are algebraic closure 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
24. QR is a generic constraint reasoner for binary calculi i e it provides an alterna tive implementation of SparQ s constraint reasoning module but limited to binary calculi For more information see https sfbtr8 informatik uni freiburg de RALogoSpace Resources GQR By invoking the export command SparQ creates a file filename two in the case of GQR export in SparQ s main directory 3 7 Interactive Mode SparQ can be started in interactive mode to process commands repeatedly This greatly reduces overhead of loading the program or calculi definitions Interactive mode is activated by the command line option i or interactive The command syntax is identical to the standard mode of operation there are some additional commands though 26 3 Using SparQ command description quit exits SparQ help prints short help message load calculus CALC loads a specified calculus into memory used as calculus specifier in commands stands for the calculus recently loaded into memory This avoids overhead of reloading a calculus 3 8 Including SparQ Into own Applications In interactive mode SparQ can be used as server that can easily be integrated into own applications We have chosen a client server approach as it allows for straightfor ward integration independent of the programming language used for implementing the application When run in server mode SparQ uses a TCP IP connection as input output and i
25. SFB TR8 Spatial Cognition Project R3 Q Shape SparQ User Manual V0 7 Jan Oliver Wallgr n Lutz Frommberger Frank Dylla Diedrich Wolter December 7 2007 Contents Installing SparQ 1 1 Requirements 1 2 Building the Executable 2 2222 on nn 2 1 What is a Qualitative Spatial Calculus o o S 2 3 Qualitative Constraint Caleuli 22222 Con on ied x Rem a ad E ADAE ORS LOEO ie ROAD E PIERDE OE ew a a SOMMER c r 2 3 5 Weak vs Strong Operations 2 2222 a 2 4 Checking Consistency llle dada dd Ge es BUE A er de hoe ae pera cT 3 21 Calculi Identifier ee ee A ee e Tes Sees es CT 3 3 Qualify 3 4 Compute relation 4 2 22 sss 3 5 Constraint reasoning gt 2 2 2 ee 3 6 Interfaces 3 7 Interactive Model lt s soe rh e ee 3 9 Adding new Calculi 22s uU wed d WOES REOR YUAN A dod JT beat dd UE uic ed ose si ud Contents 4 Internals 4 1 Implementation Details o o e e 4 2 Outlook Planned Extensions mn nn A Implemented Calculi A 1 Allen s Interval Algebra IA lt lt A 2 Cardinal Direction Calculus m nn A 3 Dependency Calculus A 4 Dipole Calculus Family o o on nn A 5 Doublecross Calculus DCC oo A 6 FlipFlop Calculus With ZR Refinement llle ns A 7 The
26. an de Weghe 2004 18 Ea ps ho gt w d gt o D on D gt D io El Ea 3 Using SparQ qtc b12 Qualitative trajectory calculus in 1D with velocity van de Weghe 2004 qtc b21 Qualitative trajectory calculus in 2D with distance van de Weghe 2004 qtc b22 Qualitative trajectory calculus in 2D with distance and velocity van de Weghe 2004 qtc c21 Qualitative trajectory calculus in 2D with distance and side 2004 qtc c22 Qualitative trajectory calculus in 2D with distance side and velocity van de Weghe 2004 3 2 2 Denoting Relations Relations are denoted using their name as a disjunction using C or by wild cards and Example using the RCC 8 calculus e nttp Ntpp both stand for the relation nttp e nttp eq po stands for the relation nttp U eq U po e p stands for all relations with a two letter name starting with p i e po U pp in case of the RCC 8 calculus e stands for the universal relation Please be aware that if you pass arguments to SparQ via the command line the shell will perform some replacements in particular if you are using parentheses or You need to wrap quotes around your arguments i e use po eq instead of po eq to avoid unwanted replacements 3 Using SparQ 3 2 3 Denoting Configurations Configurations are static scene descriptions that interrelate
27. ations by a Lisp function base relations lambda list closer farther same 29 3 Using SparQ yeuoryoung Any yoX you st oTelqe3Te uoryeoyrods iogmenb JOU IO 19J9UIB1I d e uo spu d p sn no eo oy 1oqgouA ueo ooqq snqno eo oy jo ureuiop sj2efqo siseq ayy Jo adAy opoo dsrT 10 uorpunj amp re1qi eu193Xo 04 aJue I9gJo1 UOT ISOdUIOD 119 pu suorje oi U JO SISI opoo dsrT 10 uorgjoung amp reJqI TEUIOIXI 03 92uo19 J91 uorgrsoduroo IY PUR suorje o1 OM JO SISI opoo dsrT 10 uorpunj reiqi 8uloyxa 03 oouodopol UOTYeTOI Surmoy Surpuodsoer1oo 1OY pue suorjeroz Jo SISI opoo dsrT 10 uon oung AIBIqIT euoyxo 03 adualejal uorye ol qn J10YS SUIPpuodsa1109 Mey pue suorje o1 JO SISH opoo dsrT 10 uorpunj reiqi 8uloyxa 03 oouo1opol UOTYeTOI os1IoAur SUTPUOASILIOS 1roq3 PUB suorje o1 JO SISI opoo dsrT 10 uon oung AIVIQI eu 193Xo 03 oouoJ9Jor1 uorye or1 9S19A uoo SUIPUOdSIIIO 1OY pue suorje orl JO SISI y y UP PU y USE suorje or oseq JO 4ST snme ayy jo Ayre gIT ous otexqa3tTe EHE 3 JuTod paqueto pz etodtp aurod pz Teazrequt qutod prT ous all dus uz ZI 11 ous ar1 dmo zata zx 11 ous SIT 0 11 T2 ous aIT 28 12 12 ous ar1 4Ut 12 12 D ous SIT 402 11 I2 XI ous JIT t 2 1 Kxeuze3 amp xeutq Jergrienb ort yoweLed 3TIU9 STSPQ uor3ezazed
28. ceedings of the 17th European Conference on Artificial Intelligence ECAI 2006 Riva del Garda Italy August 2006 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 Edinburgh Scotland July 2005 Marco Ragni and Alexander Scivos Dependency calculus Reasoning in a general point relation algebra In Proceedings of the 28th German Conference on Artificial Intelli gence KI 2005 pages 49 63 Koblenz Germany September 2005a 38 Bibliography Marco Ragni and Alexander Scivos Dependency calculus reasoning in a general point relation algebra In Leslie Pack Kaelbling and Alessandro Saffiotti editors IJCAI 05 Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence Edinburgh Scotland UK July 30 August 5 2005 pages 1577 1578 Professional Book Center 2005b ISBN 0938075934 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 ternat
29. cenario 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 2 3 b shows such a consistent scenario for the network in Fig 2 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 P30 behind behind behind behind behind behind a E e ahead A b c 3 a Figure 2 3 A non atomic constraint network a with possible consistent scenarios b and c The problems of determining consistency and finding consistent scenarios are sub sumed under the term constraint based reasoning throughout this text 2 3 Qualitative Constraint 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 a calculus needs to define Definition 1 qualitative calculus base relations arity A qualitative calculus lt B D gt defines a finite non empty set B of n ary qualitative base relations over some domain D ie B C 2P We call n the arity of the calculus For the purpose
30. 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 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 14 2 Reasoning with Qualitative Spatial Relations constraints and using path consistency as a decision procedure for the resulting CSPs with constraints from S 11992 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
31. cts 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 C 1 1 4 5 4 5 gt A rllr B A rllr C B 1lrr1 C If we had chosen first2all as mode parameter the relation between B and C would not have been included in the qualitative scene description 3 4 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 llrl dipole relation The corresponding call to SparQ and the result are In all the examples input lines start with Output of SparQ is marked with gt 21 3 Using SparQ 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
32. culus in 2D QTC C21 calculus identifier qtc c21 calculus parameters none arity binary entity type dipole 2D trajectory positions at two different time points description describes the relative orientation between two trajectory seg ments base relations 0 x 0 x 0 x 0 references van de Weghel 2004 remarks no qualifier is available for this calculus yet QTCc21 relations are given by a four character tuple The first two characters repre sent the same as a QT Cga relation The third character denotes whether A moves to the left to the right or on the reference line O spanned between A and B at ti The fourth character represents the change of B wrt to this reference line This results in 34 81 base relations 56 A Implemented Calculi QTC in 2D With Distance Side and Velocity Qualitative Trajectory Calculus in 2D with velocity QTC C22 calculus identifier qtc c22 calculus parameters none arity binary entity type description describes the relative orientation between two trajectory seg ments base relations 0 x 0 x 4 0 1 x 0 x 4 0 references van de Weghel 2004 remarks no qualifier is available for this calculus yet QT Cda relations are given by a five character tuple The first four directly map onto QTCca1 relations The fifth character represents the relative velocity between objects A and B denotes A being slower tha
33. d returns the disjunction sparq constraint reasoning dra 24 refine A rele errs B A errs Bp gt A errs B sparq constraint reasoning dra 24 extend A rele B A errs B gt A rele errs B Overview of commands operating on constraints consistency checking algebraic closure Enforces path consistency since this is a purely syn a closure tactical operation on the level of qualitative relations path consistency the term algebraic closure is more adequate How ever since path consistency is widely used in this meaning this name is supported too scenario consistency Computes algebraically closed networks containing base relations only 25 3 Using SparQ manipulating constraint networks refine Merges two networks by intersecting corresponding constraints extend Merges two networks by uniting corresponding con straints 3 6 Interfaces Currently SparQ provides only means for exporting calculi specification to formats used in other reasoners the syntax is as follows sparq export lt calculus gt lt type gt lt filename gt where type is one of gat QAT is a toolkit for qualitative spatial and temporal reasoning written in Java that uses an xml format for calculi specifications Currently only binary calculi can be exported into this format For more information see http www cril univ artois fr saade QAT gar G
34. e disjoint points are collinear Each base relation is a 4 44 A Implemented 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 d AB T3 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 A 5 Dipole relations are usually written without commas and parentheses e g rrll Thus the example in Fig Eos the relation d Ap Tul don 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 45 A Implemented Calculi A 5 Doublecross Calculus DCC Doublecross calculus DCC overview calculus identifier 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 37 4 0 5 1 5 2 5 3 6_3 723 4 4 b 4 4 a dou tri references 19922 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 A 3 right It can also be interpreted as the combination of t
35. e more operations unspecified However this may mean that certain computations cannot be performed for this calculus In addition to the calculus specification one could provide the implementation of a qualifier function which for a n ary calculus takes n geometric objects of the correspond ing base type as input and returns 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 not work for this calculus 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 28 3 Using SparQ the operations as implemented functions and uses a caching mechanism to store often required results 3 9 2 Specification Reference Any specification must be in the form def calculus lt NAME gt lt SLOT AND OPTIONS gt x where lt NAME gt is a textual description of the calculus enclosed in double quotes lt SLOT AND OPTIONS gt refers to a collection of calculus properties in no particular or der that consists o
36. ells us the following 1 A is behind B 2 Eis ahead of B 3 A is behind C 4 Dis on the same level as C 5 Ais 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 either 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 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
37. en origin a and relatum b and the orthogonal line thru b resulting in 11 base relations base relations 0 7 and b for b c dou tri references 19922 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 has originally been proposed in Freksa 19922 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 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 19922 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 Z B C b A B C dou and A B C tri A single cross relation relgcc is written as A Brelscc C e g A B 4 C or A B dou C The relation depicted in Fig A 9 is the relation A B 5 C Figure A 9 The Single Cross Reference System 60 B Quick Reference B 1 Command Summary compute relation c op arg 1 arg i Applies operation op of calculus c to arguments Operations spatial composition comp TS gt TOS converse cnv rer homing hm r e hm r homingi hmi r gt inv hm r inverse inv r inv r shortcut sc reo sc r shortcuti sci r gt inv
38. escribes the order between two 1D points values base relations lt gt references 1989 The Point Calculus PC Vilain et al 1989 relates pairs of 1D points represented by real valued numbers Pairs of values are categorized using the three base relations less than lt equal or greater than gt 52 A Implemented Calculi A 10 Qualitative Trajectory Calculus Family van de Weghe 2004 developed a family of trajectory calculi on the basis of relative trajectories of two moving objects He investigates representation where he combined subsets of the three different features change in distance change to the side and relative velocity He also investigated differences in representations based on one dimensional 1D and two dimensional 2D entities The most basic calculus is QT Cg dealing with change in distance in 1D enhanced with velocity in QTCp 12 The extensions to 2D entities is given in Q7Cp and QTCp2 QTCca QTCc22 extends QT C psi QTCpa2 by relative velocity QTC in 1D With Distance Qualitative Trajectory Calculus in 1D QTC B11 calculus identifier qtc b11 calculus parameters none arity binary entity type interval 1D trajectory positions at two different time points description describes the relative orientation between two trajectory seg ments base relations 0 0 O O OO references van de Weghe 2004 remarks no qualifier is available for this
39. f operating systems SparQ is written for POSIX systems Its functionality is continuously tested on Linux Solaris and Mac OS X but it should work on any Unix system 1 1 Requirements SparQ is currently not available in binary versions For installation some freely avail able standard tools are required Besides its calculi specifications as plain text SparQ comprises a set of C libraries and a main program written in Lisp For compilation we rely on availability of these tools e Steel Bank Common Lisp SBCL version 0 9 10 or higher e gcc and g version 2 95 or higher e GNU libtool version 1 4 3 or higher e XTEX for typesetting this manual 1 2 Building the Executable To build a running version of SparQ unpack the source code package enter the newly created SparQ directory called sparq lt version gt and run configure followed by make The executable will be installed within the SparQ directory Please note that you have to recompile SparQ if you move the directory to another place If you encounter any problems during the build process please contact the authors http sbcl sourceforge net On Mac Os X a newer libtool version may be required otherwise a manual patch may be necessary See INSTALL notes for details 2 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
40. f pairs of a so called slot specifier always starting with a colon and slot specific options Table 3 5 gives an overview The abbreviations SRC and LIB stand for source code specification and library link which are explained thereafter 3 9 3 Operation Specification Calculi comprise the definition of operations like converse or composition for which SparQ provides three principles ways of specification 1 Tabular form suits most standard calculi 2 Lisp source code 3 Reference to C function in external library The tabular form is straight forward In the case of a unary operation such as e g converse it is simply a space separated list of lists that give a relation and the respective outcome when applying the operation Note that the operation needs only to be defined for base relations In the case of the binary composition operation the tabular form is a list of lists that give the result for any combination of two base relations The last two options of operation specification are particular relevant for defining a quantifier or defining parametrical calculi i e calculi that are instantiated by some parameter s In SparQ these calculi use identifiers that end with a minus e g opra Lisp source operation specification Definitions may be supplied as Lisp function which then will be compiled by SparQ Lisp functions need to be denoted as lambda expressions Here is an slightly silly example for specifying base rel
41. g 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 P Ladkin and R Maddux On binary constraint problems Journal of the Association for Computing Machinery 41 3 435 469 1994 Peter Ladkin and Alexander Reinefeld Effective solution of qualitative constraint prob lems Artificial Intelligence 57 105 124 1992 G Ligozat Reasoning about cardinal directions Journal of Visual Languages and Computing 9 23 44 1998 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 G rard Ligozat Categorical methods in qualitative reasoning The case for weak repre sentations In Spatial Information Theory Cognitive and Computational Foundations Proceedings of COSIT 05 2005 A K Mackworth Consistency in networks of relations Artificial Intelligence 8 99 118 1977 Reinhard Moratz Representing relative direction as binary relation of oriented points In Pro
42. h shows three dipoles A B and C The quantitative scene description for this situation would be A 2080 B 7 2 2 5 C 1 1 4 5 4 5 Note Coordinates may be specified as either integers 2 3 floats 3 2234 le 07 or rational numbers 13 7 4 2 Using rational numbers can help avoiding effects of rounding errors Depending on the basis entity i e the domain of the qualitative calculus different values need to be supplied This table gives an overview 20 3 Using SparQ basis entity format semantics 1d point id x Real valued position of the point interval id s e Real valued closed interval 2d point id x y Real valued coordinates 2d oriented point id x y dx dy Real valued coordinates and direction of the orientation dipole id xs ys xe ye Directed line segment connecting the 2d points xs ys and xe ye The qualify module has one module specific parameter mode that needs to be specified It controls which relations are included into the qualitative scene description there are two settings all The relation between every object and every other object will be included In the case of a binary calculus SparQ prints out a configuration containing n relations if n is the total number of objects in the scene description first2all If mode is set to first2all only the relations between the first and all other objects are computed in the binary case or between the first two obje
43. he difference between weak and strong operations is not identifiable SparQ does not differentiate strong and weak operations syntactically 13 2 Reasoning with Qualitative Spatial Relations D partioned by base relations subset that cannot be described by base relations CS upper approximation using four base relations Figure 2 4 Illustration of a relation i e a subset of D represented as an upper approxima tion 2 4 Checking Consistency Determining consistency of a constraint network in which the constraints are given as qualitative 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 techniques 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 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
44. ic Orientation calculus Point algebra Vilain et al 1989 Region connection calculus RCC 5 Region connection calculus RCC 8 63 B Quick Reference reldistcalculus single cross scc opra qtc b11 qtc b12 qtc b21 qtc b22 qtc c21 qtc c22 Exemplary calculus from this man al u Single cross calculus Freksa 19922 Oriented point reasoning algebra OPRA Norton Qualitative trajectory calculus in 1D with distance van de Weghe 2004 Qualitative trajectory calculus in 1D with velocity van de Weghe 2004 Qualitative trajectory calculus in 2D with distance van de Weghe 2004 Qualitative trajectory calculus in 2D with distance and velocity van de Weghe 2004 Qualitative trajectory calculus in 2D with distance and side 2004 Qualitative trajectory calculus in 2D with distance side and velocity van de Weghe 2004 64
45. ional 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 Proceedings of the 11th International Conference on Principles and Practice of Constraint Programming CP 2005 pages 534 548 Sitges Barcelona Spain October 2005 Christoph Schlieder Reasoning about ordering In Proceedings bof COSIT 95 volume 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 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 Nico van de Weghe Representing and Reasoning about Moving Objects A Qualitative Approach PhD thesis Ghent University 2004 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 39 A Implemented 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
46. ioned point calculus over the domain of natural numbers i e lt lt gt N gt Here the composition lt o lt stands for the relation larger by at least 2 which cannot be described as a union of base relations provided by the point calculus Extending the set of relation by the respective relation lets call it 1 would only shift the problem since we would be facing a similar problem considering the composition lt o lt The framework of qualitative reasoning requires us to restrict ourselves to a finite set of relations the general relations So when we cannot express the true relations obtained by applying some operation we must use some form of approximation An upper approx imation of the true operation is utilized to accomplish this i e an approximation that fully contains the true relation Such upper approximations of operations are called weak operations as opposed to the true or strong operations Figure 2 4 gives an illustration In the case of the weak composition in a binary calculus lt B D gt it is defined as ro s BEB BN ros 40 Note that the use of an upper approximation of some operation still guarantees like in the case of strong operations that the empty relation can only be the result of con tradicting information However the use of a weak operation can lead to situations in which a set of not agreeable statements is not detected as such Given that from a syntactical point of view t
47. itional relations resulting in 9 base relations overall A LR relation reler is written as A B reler C eg A Br C as depicted in Fig Figure A 5 The reference frame for the LR calculus an enhanced version of the FlipFlop Calculus 48 A Implemented Calculi A 7 The Geometric Orientation Alignment Calculus The Geometric Orientation Alignment Calculus overview calculus identifier geomori ori align calculus parameters none arity binary entity type dipole description describes the alignment of two oriented line segments base relations P 0 remarks no qualifier is available for this calculus yet The Geometric Orientation Calculus also called Geometric Alignment Calculus re lates the alignment of two oriented line segments The alignment is derived by shifting both points of the second dipole such that the starting points of dipole A and B coin cide Dipole B may point in the same direction as A parallel in opposite direction as A opposite parallel somewhere to the left of dipole A mathematically positive or somewhere to the right of dipole A mathematically negative An example with two dipoles which are aligned positively is depicted in F igure A 6 The alignment of dipoles is part of the development of the fine grained Dipole Relation Algebra with paralellism in Dylla and Moratz 2005 Figure A 6 Example of two dipoles which are aligned positively 49 A Implemented Calculi A
48. n B is faster and O if both move at the same speed 57 A Implemented Calculi A 11 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 regions 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 calculus identifier 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 A 8 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 tp
49. named objects using quali tative relations of a particular calculus Named objects are related by enclosing object identifiers and relation by parentheses e g A po B configurations are specified using a list enclosed in parentheses no comma separation e g A po eq B B eq C 3 3 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 3 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 Te Ye Where 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 whic
50. nce point R and a global west east south north reference frame Any point P P belongs to one of the nine basic relations North NorthEast East SouthEast South South West West NorthWest or Equal The model is depicted in Figure N NW NE W EQ E SW SE S Figure A 1 Base relations of the cardinal direction calculus Frank introduced two different variants called projection based and cone based This calculus defini tion implements the projection based variant 42 A Implemented Calculi A 3 Dependency Calculus Dependency Calculus overview calculus identifier calculus parameters arity entity type description base relations references remarks depcalc dep none binary describes the order between nodes in a network lt gt Ragni and Scivos 2005a Ragni and Scivos 2005b no qualifier is available for this calculus yet The Dependency Calculus DC represents pairs of points regarding their dependen cies in a partial ordered structure Therefore it meets all requirements to describe dependencies in networks If x y are points in a partial order T lt the base relations are defined as follows Ragni and Scivos 2005a T lt y r Vy T gt y ry rey iff iff iff iff iff x lt y and not y lt x xz X y and y x y x and not z y dzz lt yAz lt aand neither z y nor y z neither dz z X y z zx nor z y nor y mr
51. nd allows to ask for the next solution until all solutions have been iterated 24 3 Using SparQ While computing scenario consistency algebraic closure is also used as a forward checking method during the search to make it more efficient For certain calculi the existence of an algebraically closed scenario implies global consistency However this again has to be investigated for each calculus cmp Section 2 4 As a future extension it is planned to allow to specify splitting subsets of a calculus for which algebraic closure decides global consistency and provide a variant of the back tracking algorithm that decides global consistency by searching for algebraically closed 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 slsr D C errs B A rser D A ells B A rele C 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 Not consistent The action refine returns the conjunction of two constraint networks Analogously exten
52. ne 6 print consistent and read the resulting constraint network net readline print net send quit command and wait for SparQ to exit sendline quit time sleep 1 and close the socket sock close Listing 3 1 Integrating SparQ into own applications an example in Python 33 3 Using SparQ 555 RELDISTCALCULUS def calculus Relative distance calculus reldistcalculus al 10 20 30 arity ternary identity relation same basis entity point qualifier lambda pi p2 p3 let d12 point distance2 pi p2 d13 point distance2 p1 p3 cond lt d12 d13 closer gt d12 d13 farther t same base relations same closer farther inverse operation same same closer farther closer same closer farther farther same closer farther shortcut operation same same closer farther farther closer homing operation same same closer farther closer same closer farther farther same closer farther 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 3 2 Specification of a simple ternary calculus for reasoning about distances 34 4 In
53. nsatisfiability The latter is particular important for reasoning the empty relation cannot be part of any consistent scene description Thus deriving that no relation other than the empty relation can hold between two objects means that the scene description is contradictory 2 3 1 Operations Let us now turn to the operations a calculus needs to define There are three groups of operations e Set theoretic operations on the level of general relations e Operations that represent a change of perspective e Operations to integrate distinct propositions 2 3 2 Set theoretic Operations The set theoretic operations on the level of general relations can be defined independent of the calculus at hand The following table lists the standard operations and their corresponding SparQ operation names R and S stand for general relations operation SparQ names definition union union RUS 1 T1ERVIES intersection intersection isec RNS f 1 X1ERATES complement complement cmpl R U R z zeUrnzeR The notation using sets like r s can be misleading as it syntactically identifies sets of relations with their unions However this notation is the established form 11 2 Reasoning with Qualitative Spatial Relations 2 3 3 Operations that Change Perspective In the case of a binary 2 ary calculus a change of perspective means that given we know the relation Ar B we can infer the relation r such that
54. nteracts with the client via simple plain text line based communication This means the client sends commands just like if using SparQ in interactive mode 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 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 3 1 which shows a small Python script that opens a connection to the server and performs some simple computations qualification adding another relation enforcing algebraic closure It produces the following output gt A rrll B A rrll C gt A rrll B A rrll C B eses C Not consistent gt B eses C A rr11 B A O B Special care may be given to line endings depending on the operating system The example code defines a function to strip line endings from the result lines Furthermore comment lines beginning with a semicolon have to be ignored Also note that every first 27 3 Using SparQ return line after a command comes with a preceeding sparq prompt so the first six characters are stripped of the result This behavior is due to compatibility reasons and will definitely change in later versions of SparQ downward com
55. o four topic areas e Installation of SparQ e A brief introduction to the field of QSR e Reference of SparQ commands and calculi specification syntax e Description of provided calculi For an up to date list of supported calculi and the newest version of this manual please visit our website http www sfotr8 uni brenen de project x3 apara 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 qshapeOsfbtr8 uni bremen de License SparQ is free software you can redistribute it and or modify it under the terms of the GNU General Public License as published by the Free Software Foundation either version 3 of the License or at your option any later version This program is distributed in the hope that it will be useful but WITHOUT ANY WARRANTY without even the implied warranty of MERCHANTABILITY or FIT NESS FOR A PARTICULAR PURPOSE See the GNU General Public License for more details A copy of the GNU General Public License is provided in the COPYING file dis tributed with SparQ If you can t access it visit As this software is being provided free of charge warranty as stipulated in sections 11 and 12 shall be governed by the provisions of German civil law concerning gifts Schenkungsrecht 1 Installing SparQ SparQ is built using several standard tools available for a variety o
56. o uor4rsoduoo zie u uor3eiedo uor4rsoduoo uotye sdo Zurtuoy uO0TIR19dO0 IN9I1O0US UO0TIRISdO SISAUT UO0TIRISdO SSISAUOD UOTIBTOSI AITIUOPT suoTIBT91 98eq 3T18 UO0IIdIIDSIP sjuouin Se 30 S Table 3 5 Overview of the slots in calculi definitions and their options 3 Using SparQ As can be observed relations are simply returned as lists of relations and symbols are used to represent base relations When specifying an operation that requires an input parameter to the function e g converse composition then these are the arguments passed to the provided function If a parametric calculus is defined then the parameter will be accessible in by the globally visible parameter calculi calculus parameter Altogether the exemplary specification from above is equivalent to base relations closer farther same Note Though you must use lambda expressions to specify lisp functions you may define additional functions or parameters in the calculus definition As the Lisp pro grammer would expect the calculus definition is processed by the Lisp compiler and def calculus is a quite complex compiler macro Lisp source qualifier specification Providing a lisp source definition for qualifiers is similar to specifying operations In the case of a binary calculus you need to provide a 2 argument function in the case of a ternary calculus a 3 argument function These arguments are exactly th
57. of constraint reasoning one usually requires that the set of base relations partitions D Definition 2 JEPD A qualitative calculus lt B D gt is called jointly exhaustive if the base relations cover D i e Upeg B D The calculus is called pairwise disjoint if no two base relations overlap i e VB B B BN B Q Jointly exhaustive and pairwise disjoint calculi are commonly referred to as JEPD calculi 10 2 Reasoning with Qualitative Spatial Relations In qualitative reasoning we consider a simple formal language that only allows relating unqualified objects by qualitative relations Here a infix notation is commonly used For example Ar B stands for A B r Uncertainty can be modeled by using unions of base relations e g to express that some objects may either stand in some relation r or s can be expressed by the relation r U s usually denoted fr s Definition 3 general relations In a qualitative calculus B D gt a general re lation B B i Bi Bim where Ba Bi Bj B represents the relation U j 12 m Bi obtained by uniting base relations We will denote set of general rela tions obtained from a set of base relations B by Rg Two special general relations are the empty relation and the universal relation U U peg B In this context the JEPD property is important in two regards 1 It offers a normal form of representing knowledge 2 The empty relation corresponds to u
58. ose of the command qualify but without the object identifier i e a qualifier for the point based calculus e g cardinal directions requested by the command qualify cardir A 2 3 B 13 C 3 2 will lead to calls passing the lists 2 3 1 3 or 3 2 as arguments Supplied functions are not required to do any error checking as this is taken care of already External operation libraries All operations may be specified by giving a reference to an external library by writing external lib LIBNAME C_FUNC Hereby LIBNAME must be a string delimited by dou ble quotes referring to a shared library inside SparQ s subdirectory Lib bin C_FUNC a string too gives the name of the corresponding C function to call In principal any programming language can be used as long as it allows for building a shared library that provides functions that follow the C calling convention The signature of the C function for unary operations must be const char C_FUNC const char param const char relation When called by SparQ C_FUNC is passed the currently active calculus parameters ig nore if your calculus does not use parameters i e all characters that are appended to the last in the calculus name As second argument the relation is passed The function needs to return the result in the same form SparQ uses as print form for re lations In case of returning disjunctions this means a space separated list enclosed in parenthe
59. p tangential proper part ntpp non tangential proper part tppi tangential proper part inverse ntppi non tangential proper part inverse Randell et al 1992 no qualifier is available for this calculus yet 58 A Implemented Calculi RCC 5 adcb a ec b a po D a eq b disconnected externally partially equal connected overlapping a tpp b a ntpp b a tppi b a ntppi b OO JO 9 tangential non tangential tangential proper non tangential proper part proper part partinverse proper part inverse Figure A 8 The RCC 8 base relations Region Connection Calculus 5 RCC 5 overview calculus identifier 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 no qualifier is available for this calculus yet remarks RCC 5 is a coarser version of RCC 8 The RCC 8 relations dc and ec are combined into one relation called dr Similarly ntpp and tpp are combined into pp and ntppi and tppi into ppi 59 A Implemented Calculi A 12 Singlecross Calculus SCC Singlecross calculus SCC overview calculus identifier Scc calculus parameters none arity ternary entity type 2D points description relates the referent c relative to the line betwe
60. patibility however will be granted 3 9 Adding new Calculi For most calculi it should be rather easy to include them into SparQ Adding a new calculus consists of two steps 1 Provide a calculus specification and store it in SparQ s subdirectory Calculi 2 Register your calculus in the calculus registry Calculi calculus registry lisp 3 9 1 Calculus Specification Let us start by giving an example for a simple calculus for reasoning about distances between three point objects that distinguishes only the three relations closer farther and same Following the intuition A B closer C holds if and only if A and B are closer to one another than A is to C Farther and same are defined analogously Listing 3 2 shows the specification which 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 shortcut 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 inverse shortcut and inverse homing operations cmp Section as these can be computed by applying the other operations e g inverse of shortcut yields inverse shortcut It is principally possible to leav
61. rks refine Merges two networks by intersecting corresponding constraints extend Merges two networks by uniting corresponding con straints export c format Exports calculus definition of c in format qat XML specification for QAT toolkit gar specification for GQR constraint reasoner B 2 Interactive Mode 66599 Using SparQin the interactive mode i e invoking it with the i command line option some additional commands are available 62 B Quick Reference command description quit exits SparQ help prints short help message load calculus CALC loads a specified calculus into memory used as calculus specifier in commands stands for the calculus recently loaded into memory This avoids overhead of reloading a calculus B 3 List of Calculi calculus identifier s calculus section page allen aia ia cardir depcalc dep dipole coarse dra 24 double cross dcc alternative double cross adcc flipflop ffc ff geomori ori align point calculus pc point algebra pa rcc 5 rcc 8 Allen s interval algebra Allen 1983 Cardinal direction calculus Ligozat 1998 So 20053 u Ragni and EE A Moratz et al 4 2000 Double cross calculus Freksa 1992a using the original tuple naming scheme Double cross calculus Freksal 1992a using the alternative single number naming scheme FlipFlop calculus 1993 Geometr
62. sc r calculi theoretic closure Pria ong CUPIS T2 in Cl denotes the minimal set of relations that is closed under composition converse and intersection base closure Cl bri bra brn Computes closure of the set of base relations set theoretic complement cmpl ror minus rs TNS union rs gt oruUus intersection isec rse gt rfMs For complex operations a Lisp style prefix syntax can be used i e nested expression enclosed by parantheses e g composition rell inverse homing rel2 com putes rello inv hom rel2 61 B Quick Reference qualify c opt scene Determines qualitative configuration from quantitative scene description c Calculus opt Either first2all or all sets which objects to relate scene List of lists containing objects id and coordinates e g Point A 12 2 34 8 Point B 2 3 2848 constraint reasoning c op confi conf2 Performs operation op on qualitative configuration with respect to calculus c consistency checking algebraic closure Enforces path consistency since this is a purely syn a closure tactical operation on the level of qualitative relations path consistency the term algebraic closure is more adequate How ever since path consistency is widely used in this meaning this name is supported too Scenario consistency Computes consistent networks containing base relations only manipulating constraint netwo
63. ses 31 3 Using SparQ When defining a binary operation composition the signature looks as follows const char C_FUNC const char param const char ri const char r2 Obviously two relations need to be passed to the composition operation External qualifier libraries Similar as with operation specification external libraries can be used for defining a qualifier module for SparQ The signature of the external functions is as follows const char C_FUNC const char param double P1 double P2 Put differently SparQ passes besides the calculus parameter all spatial information as double precision floats to the function The amount of parameters depends on e the arity of the calculus e the dimension of the calculus basis entities Let a denote the arity of a calculus either a 2 or a 3 and let d denote the dimension of the basis entity then a d double parameters are passed Dimensions of currently supported basis entities are as follows basis entity d 1d point 1 interval 2 2d point 2 dipole 4 2d oriented point 4 Limitations Passing coordinates as fixed precision floating point numbers can intro duce difficulties that arise due to rounding in computer arithmetics If no special care is taken then it can easily happen that the relation between A and B obtained by qual ification is not the converse of the relation obtained by qualifying the relation between B and A To avoid
64. ternals This section provides some information about the internals of SparQ together with planned extensions SparQ is under current development in the project R3 Q Shape If you have any questions additions or recommendations we d be glad getting into contact 4 1 Implementation Details TBD 4 2 Outlook Planned Extensions Besides extending the set of supported qualitative calculi the following extensions are currently planned for the future interfaces amp XML specification further interfaces to exchange calculus specifications are planned 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 will be available shortly much functionality is already waiting behind the scenes This module provides one additional add on algebraic qualification which means you do not need to provide a qualification functions if you supplied an algebraic specification of the base relations The qualifier gets derived automat ically Should be available by the end of 2007 quantification a module that analogous to the qualify module takes a consistent qualitative scene description and turns it into a prototypical quantitative scene description Related to algebraic reasoning this module is planned to be available as prototype
65. the cases m 2 a and m 4 b The orientation of the two points is depicted by the arrows starting at A and B respectively The regions are numbered from 0 to Am 1 region 0 always coincides with the orientation of the point An OPRA 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 n B with 7 Zam Thus the examples in Fig A 7 depict the relations A 2L B and A 4433 B Additional base relations called same m describe situations in which the positions of both oriented points coincide In these cases the relation is determined 2 Zam defines a cyclic group with 4m elements 50 A Implemented Calculi a m 2 AoA B b m 4 AaZ3s B c case where A and B coincide A2Z1B Figure A 7 Two oriented points related at different granularities by the number s of the region of A into which the orientation arrow of B falls as illustrated in Fig A 7 c These relations are written as A 2 s B A 2Z1 B in the example The complete set R of OPRA relations is the power set of the base relations de scribed above 51 A Implemented Calculi A 9 Point Calculus Point Algebra Point Calculus Point Algebra overview calculus identifier point calculus pc point algebra pa calculus parameters none arity binary entity type 1D points description d
66. verview of Doublecross base relation names in tuple notation and the alternative notation 47 A Implemented Calculi A 6 FlipFlop Calculus With CR Refinement FlipFlop calculus FFC overview calculus identifier 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 nine base relations base relations left r right f front b back i inside s start e end dou tri references 1993 Scivos and Nebel 2005 remark SparQ uses the LR refinement in its implementation of the FFC The FlipFlop calculus proposed in 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 It can for 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 A 5 Relations for the case where A and B coincide were not included in Ligozat s original definition 1993 This was done with the LR refinement that introduces the relations dou A B 4 C and tri A B C as add
67. wo single cross 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 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 CZB 4a AZ B C b_4 A BFC dou and A B C tri resulting in 17 base relations overall In Fig right the relation A B 5 3 C is depicted Figure A 3 The two Single Cross reference frames resulting in the overall Double Cross Calculus reference frame 46 A Implemented Calculi Alternative Doublecross Calculus DCC overview calculus identifier adcc alternative 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 12 a b dou tri references In the literature also a single numbered notation can be found We refer to this nomenclatur as the Alternative Doublecross Calculus Apart from relations b_4 4_a the mapping between tuple notation and alternative notation is given in Figure b_4 corresponds to b and 4_a to a dou and tri are defined as above 15 014 723 1 11 2 5 63 2 10 ie 35 4la 53 3 2 9 3 6 52 4 8 3 7 410 5_1 5 7 Figure A 4 Schematic o

SparQ User Manual V0.7 - SFB/TR8

Contents

Download Pdf Manuals

Related Search

Related Contents