readme

利用空间表示的rcc8模型进行空间推理

This directory contains all files necessary to make performance
experiments on solving RCC8 CSPs as described in J. Renz, B. Nebel, 
"Efficient methods for Qualitative Spatial Reasoning", JAIR 15, 2001. 

After unpacking the tar archive you may want to edit the Makefile in order
to set the right compilation flags. Afterwards call 'make', which generates 
all the programs. They should compile and execute on all UNIX and Linux 
machines.

CONTENTS
========

1) Text files
	README 		- this file

2) Data files (ASCII)
	baserels	- the 8 base relations of RCC8
	closebaserels	- all relations contained in the closure of the 
			  set of base relations
	hornrels	- all relations of the maximal tractable set H^8
        c8rels	        - all relations of the maximal tractable set C_8
        q8rels	        - all relations of the maximal tractable set Q_8
        interrels       - intersection of H^8, C_8, and Q_8
        nprels          - all relations not contained in one of the three 
                          maximal tractable subsets
 
	basesplit	- gives for each possible relation in RCC8 it's 
			  (non-disjoint) union of base relations. This file
			  can be generated by the 'cover' program
	closebasesplit	- same for the relations of closebaserels
	hornsplit	- same for the relations of hornrels
	c8split	        - same for the relations of c8rels
	q8split	        - same for the relations of q8rels
        intersplit      - same for the relations of interrels

3) Configuration files
	Makefile	- check CFLAGS and CC. Used for generating all programs

4) Program modules
	rcc8.h		- defines representation of RCC8 relations
	rcc8io.h
	rcc8io.c	- I/O 
	rcc8op.h
	rcc8op.c	- basic operations in RCC8
	pc1.c	        - basic path-consistency algorithm
	pcvb.c		- van Beek's path-consistency algorithm
	pcwq.c		- weighted queue path-consistency algorithm
	backtrack.c	- backtrack algorithm for checking consistency
	
5) Programs
	cover.c		- compute cover sets. To compute hornsplit, e.g.,
			  call: cover < hornrels > hornsplit
	genall.c	- prints all 256 RCC8 relations to stdout
	gencsp.c	- generates RCC8 CSPs of a specified form
			  (a detailed description is given below)
	solve.c		- CSP-solver (a detailed description is given below)



Generating CSPs
===============

The program 'gencsp' generates a specified number of RCC8 CSPs on
standard output. The properties of the CSPs can be controlled by several
flags:
    gencsp [-ue] [-is number] [-cdlnCDLN min [max step]]  [-rx file] [-o name]

    Generates RCC8 CSPs. 
    options are:
       -u   uniform distribution of labels (50% probability for each label, 
            overwrites -l)
       -e   all possible relations are equally distributed (owerwrites -u 
            and -l)

       -i <number>  specifies number of instances to be generated (default 1)
       -s <number>  specifies the seed for the random function

      The following options expect either one value (particular value) or 
      three values (minimum value, maximum value and the stepwidth) which 
      specifies the range of the generated instances.
      Numbers in brackets specify the range of accepted values.
       -c   specifies the constraint density (default 0.0) [0.01 - 1.0]
       -d   specifies the average degree of a node (default 0) [0 - MAXCSP]
       -l   specifies the average labelsize (default 4.0) [1.0 - 8.0] 
       -n   specifies the number of nodes (default 3) [3 - MAXCSP]
      The following options restrict the output of the generated instances 
      to those within the given range; again either one value or three values 
      are expected. These options are by default unset. Do not set C without 
      setting c, D without d, L without l, and N without n. 
       -C   restricts the output constraint density [0.01 - 1.0]
       -D   restricts the output average degree of a node [0 - MAXCSP]
       -L   restricts the output labelsize [1.0 - 8.0]
       -N   restricts the output number of nodes [3 - MAXCSP]


       -r <file>  restricts all relations to be the ones mentioned in the file
       -x <file>  specifies the relations to be excluded

       -o <name>  specifies the prefix of the outputfile 
                  (default is none)

       The -c and -d options override each other.

For example, the following program-call generates 100 CSP instances
with 50 nodes, such that the average degree of the constraint graph is
9.5 and the labels are chosen from the set 'hornrels':

	gencsp -i 100 -n 50 -d 9.5 -r hornrels 

The following program-call generates 5 CSP instances for each even node size 
from n=10 to n=20 nodes and for each average constraint density from c=0.2 to 
c=0.6 with a step of 0.1 which contains only relations of the set 'nprels' 
such that each relation of 'nprels' is chosen with the same probability. 
Only those CSPs whose size is n=20 are written to stdout.

        gencsp -i 5 -n 10 20 2 -c 0.2 0.6 0.1 -e -N 20 -r nprels

Solving CSPs
============

The program 'solve' reads the file supplied as the argument (or if no
argument is given, it reads from standard input) and solves the CSP
instances in the file. There are a number of switches that control how 
and what CSPs are solved and what is given as output: 

  solve [-bdefnpqrsv] [-w[v]] [-z[p]] [-m[f] number] [-g number] [-ctx file] [-o file [number]] [-h[a|A file] order] [-li <file>] [-le <file>] [file1 file2 ...]  
    solves RCC8 CSPs.
  solve [-bdefnpqrsvwz] [-m number] [-ctx file] [-o file [number]] [-h[a|A file] order] [file1 file2 ...]  
       solves RCC8 CSPs.

    options are:
    -b    return brief summary info on stdout (even if -q)
    -c <file> use the coverage info in file to split relations
    -d    give debugging info on stderr
    -e    use environment constrainedness to select next node (van Beek)
    -f    fixed ordering of variables 
    -g <number>  solve only instances larger than <number> 
    -h[a|A <file>]  <order>  use the orthogonal combination of the different 
                    heuristic methods. (a = always run all methods, the maximal
                    number of visited nodes of following methods is restricted
                    by the number required by the previously best method; 
                    A = run all methods and write output in <file>) 
                    <order> specifies the order of the methods. 
                    1=H^/dyn/loc, 2=H^/dyn/glo/, 3=H^/sta/loc, 4=H^/sta/glo, 
                    A=B^/dyn/loc, B=B^/dyn/glo/, C=B^/sta/loc, D=B^/sta/glo,
                    a=B/dyn/loc, b=B/dyn/glo/, c=B/sta/loc, d=B/sta/glo,
                    s=C/dyn/loc, t=C/dyn/glo/, u=C/sta/loc, v=C/sta/glo, 
		    S=Q/dyn/loc, T=Q/dyn/glo/, U=Q/sta/loc, V=Q/sta/glo,
                    i=I/dyn/loc, j=I/dyn/glo/, k=I/sta/loc, l=I/sta/glo,
                    <order>=2B4a means that the order is 2,B,4 and finally a.
                    NOTE: It is assumed that the files hornsplit, 
       	            closebasesplit, c8split, q8split and intersplit exist. 
                    This option overrides the options -c <file>, -f, and -e.  
    -li <file>   Include all headers of the logfile <file>
    -le <file>   Exclude all headers of the logfile <file>
                 NOTE: `-li <file>' must be given before `-le <file>'. 
    -m[f] <number> maximal number of nodes to visit (default NV_UPPER_LIMIT)
                   if -mf is set (f=factor), then the maximal number of nodes 
                   to visit is the instance size multiplicated by <number> 
    -n    restrict summary to negative (inconsistent) cases
    -o <file> <number> solve only those CSP that are tagged with [-1,0,1] 
                       (default -1) (should be a log-file)
    -p    restrict summary to positive (consistent) cases
    -q    return 0 if (last) CSP was consistent (suppresses -v) 
    -r    use random variable ordering 
    -s    return summary info on stdout (even if -q)
    -t <file> print return summary to file after typeid changes
    -v    give verbose output on stderr after solving a CSP
    -w[v] use weighted queue scheme for computing path-consistency 
          (v = van Beek)
    -x <file> print CSPs that could not been solved to file
    -z[p] compute path-consistency only (p=print path-consistent CSP to stdout)

    file[i] are CSP-input files. If none specified, solve uses stdin. 
    More than one CSP can be specified in each file (each must be 
    terminated by a point '.').

    Format of the CSP should be <node1> <node2> '(' <relations> ')'.
    First line of CSP should contain maximum node id and typeid (string).

For example, the following program-call solves the CSP-file "hardproblem" 
by using the weighted queue scheme and splits the relations as given in the
'hornsplit' file. The Output is a summary restricted to those cases which turn
out to be non-consistent:

	solve -s -n -w -c hornsplit hardproblem




The experiments in the paper were done using the following program calls: 

Figure 4, path-consistency 
--------------------------

generating instances: 
gencsp -i 10 -n 50 1000 50 -d 8.0 11.0 0.5 -l 4.0 

enforcing path-consistency: 
solve -z     -t pcnw  (no weights)
solve -z -wv -t pcaw  (approx. weights)
solve -z -w  -t pcew  (exact weights)

The average CPU times can be extracted and combined from the files 
pcnw, pcaw, and pcew (first value in line "CPU time").



Figures 5, 6, and 7, probability of satisfiability 
--------------------------------------------------


generating instances: 
A: gencsp -i 500 -n 10 100 2 -d 2.0 18.0 0.5 -l 4.0
H: gencsp -i 500 -n 10  80 2 -d 4.0 20.0 0.5 -l 4.0 -r nprels

solving instances: 
solve -w -c hornsplit -f -e -t probsat

The probability of satisfiability (second value in line "Consistent"), 
the median CPU time (second value in line "CPU times"), and the 
percentage points of incorrect path-consistency answers (second value 
(global) minus first value (path) in line "Consistent") can be 
extracted from the file "probsat". 



Table 1, Figure 9 and 10, evaluation of heuristics
--------------------------------------------------

generating instances: 
A: gencsp -i 500 -n 10 100 2 -d 2.0 18.0 0.5 -l 4.0
H: gencsp -i 500 -n 10  80 2 -d 4.0 20.0 0.5 -l 4.0 -r nprels

solving instances: 
solve -w -c <splitfile> <heuristic> -m 10000 -t heuristic<h> -x hardinst<h>

where <splitfile> is either hornsplit, q8split, c8split, closebasesplit, 
or basesplit. <heuristic> is either -f -e, -f, -e, or empty, and 
<h> is either _fe, _f, _e, or empty, respectively. 

The hard instances for the different heuristics are written in the file 
"hardinst<h>" where their number can be counted. 
The total number is the number of instances which occur in all 20 files. 
The CPU times of figures 9 and 10 can be extracted and combined from the 
files heuristic<h> (median: second value in line "CPU time", 99%-percentile: 
fifth value in line "CPU times")



Table 2 and 3, Figure 11, orthogonal combination of heuristics
--------------------------------------------------------

generate instances:
see above, hard instances are stored in the files hardinst<h>. 

compute percentage of solved instances: 
easily calculated from Table 1.

compute first response: 
we recommend to generate a file which contains the headers of all hard 
instances: grep # hardinst* -h | sort -u > hardheaders 
This avoids that instances which occur in multiple files are solved more 
than once.
solve -w -ha 1234stuvSTUVABCDabcd -li hardheaders -m 10000 -x hardestinst  
 hardinst*  > firstresponse

The first value of each line in firstresponse gives the consistency, 
(0 for inconsistent, 1 for consistent, -1 for unsolved)
the third value gives the method which solves the instance with the least 
number of visited nodes. this number is given as the second value. 

If instead of -ha we use -hA fullresponse, then the number of visited nodes 
of each heuristic is written in fullresponse. These values can be used to 
compute Table 3. 



Figure 12, solving the hardest of the H instances
-------------------------------------------------

generating instances:
The hardest instances are those which are stored in hardestinst as computed 
above.  

computing first response using at most 100,000 visited nodes: 
solve -w -ha 1234stuvSTUVABCDabcd -m 100000 hardestinst > firstresponse_h

The values of firstresponse_h are the same as described above for 
firstresponse. 



Figure 13 and 14, solving large instances with the best heuristics
------------------------------------------------------------------

generating instances: 
gencsp -i 100 -n 110 500 10 -d 2 18 0.5 -l 4.0


solving instances: 

solve -w -h 41sC -mf 2 -x largeunsolved -t largesummary


The instances which cannot be solved by any of the four heuristics 4,1,s, and 
C with at most 2n visited nodes are stored in largeunsolved. 
The probability of satisfiability (second value in line "Consistent"), 
the averag number of visited nodes (first value in line "Nodes v."), and 
the 70% and 99% percentile (third and fifth value in line "CPU time") 
is given in largesummary. 



All Programs are written by

	Ronny Fehling, Bernhard Nebel, Jochen Renz
	fehling,nebel,[e-mail]

	http://www.informatik.uni-freiburg.de/~sppraum 

			  Institut fuer Informatik                       
              	         Albert-Ludwigs-Universitaet                    
                               Am Flughafen 17                           
                           79110 Freiburg,Germany