Using the View Matcher and the View Server

The View Server program allows a client to store and match views in an SSH map. The core of the View Server consists of two programs: the View Compiler and the View Matcher.

Using the View Server

The View Server is written in LISP and is accessible via a TCP socket connection or locally in the same LISP environment. To start the view server:

  USER> :ld /u/robot/ssh+/views/system
        ...
  ;   Fast loading /u/robot/ssh+/views/symbolic/view-server.fasl
  USER> (start-view-server)

  ;;; The View Server is now accepting connections on port 3333.
  3333

The View Server currently loads Algernon and the SSH in order to store views in the SSH map.

Once the View Server is loaded and started, it will receive any number of clients through a socket connection to the appropriate port. Once connected, the (:HELP) command will display the available commands.

  arachne:/u/hewett $ telnet localhost 3333
  Trying 127.0.0.1...
  Connected to localhost.
  Escape character is '^]'.

  (:help)
  View Server @ arachne.cs.utexas.edu:3333    (use distances in meters)

  (:MAKE-VIEW VIEW-NAME &REST SEGMENTS)
      Creates or replaces a view description.
  (:FIND-VIEW SEGMENT-LIST)
      Finds the highest match among the known views.
  (:MATCH-VIEW VIEW-NAME SEGMENT-LIST MIN-POSITIVE-VALUE)
      Returns the match score with the given view.
  (:WHERE-IS-VIEW VIEW-NAME &OPTIONAL (REF-FRAME :REF))
      Returns the (x y z theta ref-frame) of a view.
  (:DESCRIBE-VIEW VIEW-NAME)
     Returns the segments that make up the view description.
  (:VIEW-OFFSET VIEW-NAME SEGMENT-LIST)
     Returns the (x y z theta) offset of the view from the segment list.
  (:BEST-MATCH VIEW-NAME SEGMENT-LIST)
      Returns the two segments that best match from the view and the segment list.
  (:TRACE-MATCH-VIEW VIEW-NAME SEGMENT-LIST MIN-POSITIVE-VALUE)
      Traces a :MATCH-VIEW operation
  (:FORGET-VIEWS)     
      Remove all known views.
  (:STATUS)           
      Shows values of constants.
  (:LIST-VIEWS)       
      Display a list of the known views.
  (:HELP)             
      Print this message.
  (:QUIT)             
      Close the connection to the View Server.

  (:make-view mike1 ((-1.71756 -1.71756) (-1.63272 4.25339))
   ((-1.73821 5.04812) (-1.35848 5.88422))
   ((-1.66928 9.46696) (-0.952525 10.8874))
   ((-0.397961 5.6911) (1.00525 5.70105))
   ((1.10822 5.70129) (1.56332 4.81139))
   ((1.46701 4.26051) (1.4928 0.57303))
   ((1.49317 0.54347) (2.32612 0.410157))
   ((10.5925 0.555127) (10.6214 -3.4511))
   ((1.50069 -0.546206) (1.50702 -1.45531)))
  MIKE1
  
  (:match-view mike1 (((-1.71756 -1.71756) (-1.63272 4.25339))
   ((-1.73821 5.04812) (-1.35848 5.88422))
   ((-1.66928 9.46696) (-0.952525 10.8874))
   ((-0.397961 5.6911) (1.00525 5.70105))
   ((1.10822 5.70129) (1.56332 4.81139))
   ((1.46701 4.26051) (1.4928 0.57303))
   ((1.49317 0.54347) (2.32612 0.410157))
   ((10.5925 0.555127) (10.6214 -3.4511))
   ((1.50069 -0.546206) (1.50702 -1.45531))) 0.0)
  1.0

  (:quit)

The View Matcher

The View Matcher returns a match score between 0.0 and 1.0, or NIL if the match score did not exceed the minimum positive score specified in the :MATCH-VIEW command. The incoming view description is converted to a symbolic description which is sent to the view-match function associated with the pre-stored view to be matched. Several parameters control the functionality of the view matcher:

*min-match-score* [0.4]: (view-compiler.lisp) When finding the best correspondence between two sets of segments, each individual match must be greater than this value.
*max-number-of-segments* [100]: (view-compiler.lisp) When filtering segments, don't keep more than this number.
*min-wall-length* [0.4 meters]: (view-match.lisp) When the set of segments is being filtered to the N largest segments, only the segments larger than this length are allowed to pass.
*robot-x-axis* [((0.0 . 0.0) (1.0 . 0.0))]: (view-match.lisp) Specifies the coordinate system of the robot.
*robot-y-axis* [((0.0 . 0.0) (0.0 . 1.0))]: (view-match.lisp) Specifies the coordinate system of the robot.
*max-alignment-angle* [15.0 degrees]: (view-match.lisp) The matcher will adjust incoming segments for rotational variations if the detected rotation is less than this amount.
*max-alignment-distance* [0.5 meters]: (view-match.lisp) The matcher will adjust incoming segments for translation variations if the detected difference is less than this amount.
*default-angle-std-dev* [10.0 degrees]: (view-match.lisp) This determines the width of the Gaussian function used to calculate the match between the angles of two segments.
*default-length-std-dev* [10.0 degrees]: (view-match.lisp) This determines the width of the Gaussian function used to calculate the match between the lengths of two segments.
*default-distance-std-dev* [10.0 degrees]: (view-match.lisp) This determines the width of the Gaussian function used to calculate the match between the distances of two segments.
*use-view-match-functions* [T]: (view-match.lisp) Determines whether the compiled functions or the much, much slower Algernon code is used. Don't use the Algernon code.

Although the view matcher is designed to be general-purpose, it currently assumes that the input is a list of line segments, and the code in some places depends on this.

The view matcher first finds the best correspondence between the given segments and the stored view's segments. For example, the stored view may consist of four segments, but the input view may consist of three segments. The correspondence routine figures out the best possible match between the segments. (FYI: it uses an algorithm based on the UNIX 'diff' file comparison algorithm). Extra segments do not affect the match, but missing segments will lower the match score in proportion to their relative length.

Next it attempts to account for small rotational and translational variations by detecting differences in corresponding segments. It de-rotates and de-translates the incoming segments by the detected amount. It then matches both the original segments and the de-rotated segments against the stored segments and returns the highest match score.

Units and Data Format

The View Matcher uses degrees and meters as the basic units. Several match functions don't work correctly if meters are not used as the distance unit.

When sending input, follow these conventions:

Point: (X Y)
Segment: (point point)
Segment-List: (segment segment ...)
View: name (no quotes, spaces or string delimiters)

The segments of a view are sorted by the View Server so that they are in counter-clockwise order from the robot's point of view.

The View Compiler

The View Compiler constructs either an Algernon rule or a LISP function that will match the incoming description. The LISP function is several orders of magnitude faster, so the Algernon rule generator should be considered to be obsolete.

It converts the incoming segments into a symbolic description and then compiles the symbolic description into a LISP function. The LISP function is then compiled and stored in a table from which it is retrieved when needed.

The compiled function actually does more than just match views. Its signature is:

  (CONTAINS-VIEW-<view-name> (OP &OPTIONAL FEATURE-SET TRACE)

It can perform several operations as shown below and determined by the OP parameter:

:START-POINT Returns the start point of the first segment.
:END-POINT Returns the end point of the first segment.
:SEGMENTS Returns the segments that compose this view.
:DESCRIPTION Returns the symbolic description of the view.
:BEST-MATCH Returns the best match between the view's segments and the input segments.
:MATCH Perform view matching.

Directories and Files

The home directories for the View Server are:

  /u/robot/ssh+/attn/views
  /u/robot/ssh+/attn/views/symbolic
  /u/robot/ssh+/attn/views/symbolic/data

There is also a non-symbolic directory, which is currently empty.

[Robotics home]

Author: Micheal S. Hewett
Email: hewett@cs.utexas.edu
Last Updated: Wednesday, March 29, 2000