Robotic Topoligical Mapping Through Gap Sensing

The Sensing Model

There are many different approaches to feature based mapping. In this project We describe an algorithm to incrementally construct a topological map similar to the reduced visibility graph. This algorithm relies on a specialized sensor that can detect all range discontinuities visible from the robot's location. The sensor will report ordering, orientation, and distance to the closer side for the discontinuities.

The reduced visibility graph is a graph representation of a planar 2d environment where each node corresponds to a vertex on the free space boundary. An edge between two nodes exists only if the straight line connecting the two vertices lies entirely in free space, and is a bitangent. The reduced visibility graph of a planar environment is a subset of its visibility graph.

A discontinuity in the distance to the free space boundary from the robot's perspective is called a gap. In a space with polygonal boundaries composed of smooth edges, each gap is caused by a vertex on the free space boundary. A discontinuity in depth implies that some portion of the world is hidden from the view of the robot. These obscured regions are bounded by extended tangencies.

Gaps are classified according to weather the obscured portion is on the left or right side of the vertex. A gap event occurs when the robot crosses an extended bitangent or non-convex edge. Each gap event implies some relationship between features causing the gaps and we wish to exploit this to facilitate more efficient construction of the tangency planner. The robot continuously queries its gap sensor as it moves and records gaps by adding the appropriate information to the graph. At any time, a gap is associated with some node in the graph.

Resolution is the process of enforcing constraints from local information to combine information and eliminate duplicate nodes. After circling a boundary, the robot recovers the marker and determines that it's final location is the same as it's initial location. Since it is assumed that the robot can consistently enumerate the neighbors of a vertex, the set of gaps visible at the starting position are easily matched with the set of gaps visible from the initial position. Each node in this set of correspondences may provide more pairs of corresponding nodes, and the affect of the resolution procedure can propagate recursively throughout the graph. However, merging the information from a pair of equivalent nodes is not always trivial. The two nodes may contain partial information, and ambiguities may arise. This problem can be solved by maintaining partial orderings on each set of neighboring nodes. A Last-in-first-out structure is used to keep track of nodes as they become concealed and revealed by other nodes. The LIFO ordering is motivated by the way that the bitangents extending through a vertex divide the free space around that vertex.

The Mapping Algorithm

while unvisited vertices exist
  reach vertex by gap chasing
  update graph and drop marker
  begin-follow-boundary()
  repeat
    handle-gap-events()
  until found marker
  if vertex reached, record neighbors
     merge start with finish
     Apply recursive merge procedure to matching node pairs

An example of how the graph is constructed as boundaries are explored. The topological structure of the world is shown in the last iteration