Lecture 6 - Maps and Alignment

Question 1

What are the 4 different categories of maps?

Answer 1

Metric
• Map accurately represents lengths and angles

Topological
• Map is reduced to a graph representation of the structure of free space

Topometric
• Atlas: a combination of local metric maps (nodes) connected via edges

Sequence of raw time-series observations (e.g. video)
• No metric or topological information directly represented by the map

Question 2

What is a common type of metric map?

Answer 2

Occupancy Grids

Question 3

What are two common problems with Octrees and Quadtrees?

Answer 3

Problem 1: quadtrees and octrees are not
balanced trees. So, in the worst case an
occupancy query could be O(n) in the
number of nodes.
Problem 2: quadtrees and octrees are
sensitive to small changes in the location
of obstacles.

Question 4

Give one advantage and disadvantage of Occupancy Grids

Answer 4

Lookup is O(1).

Doesn’t scale well in higher dimensions.

Question 5

What’s the purpose of a signed distance function?

Answer 5

It allows smooth surfaces.

Question 6

What are the advantages and disadvantages of pointclouds

Answer 6

Advantages:

• can make local changes to the map without affecting the pointcloud globally
• can alight pointclouds
• nearest neighbor queries are easy with kd-trees or locality-sensitive hashing

Disadvantages:

• need to segment objects in the map
• raytracing is approximate and nontrivial

Question 7

What map category does a Generalized Voronoi Graph belong to?

Answer 7

A topological map. It is the set of edges that are at equal distances to obstacles.

Question 8

What is deformation retraction?

Answer 8

Generalized voronoi map with edges and obstacle points that are also equidistant.

Question 9

How does small changes in the object’s boundary affect the skeleton of a Voronoi Graph?

Answer 9

The Voronoi graph is highly sensitive to even the smallest changes.

Question 10

What is one advantage of Voronoi Graphes?

Answer 10

Can specify whether we pass on the left or right of each obstacle on our path to the goal.

Question 11

What are classes of paths that can be deformed without hitting obstacles called?

Answer 11

Homotopy Classes

Question 12

What’s the ICP-algorithm?

Answer 12

Iterated Closest Points (ICP).
• Associates each point in the source scan to its nearest neighbor in the target scan.
• Finds the optimal rotation and translation for this correspondence.
• Repeat until no significant drop in error.

Question 13

What’s the most common sensor to collect ranges?

Answer 13

Laser range-finder (2D or 3D) LIDAR.

Moves the vehicle, scans each location, then aligns all scans.

Question 14

How can you build a map with LIDAR?

Answer 14

Move the vehicle, scan each location, then align all scans.

Question 15

What is an advantage of topometric maps?

Answer 15

Main advantage: allows us combine accurate local maps into a global, typically inconsistent map that nevertheless provides sufficient navigation information.

Question 16

What’s the main idea behind maps of raw observations?

Answer 16

• Map = entire (unprocessed) sequence of observations, e.g. video.
• Do not try to support distance, collision, and raytracing queries.
• Instead, provide only a similarity/nearest neighbors query
• “Find the image in the video that is most similar to the one I’m seeing now.”
• History of observations determines a (set of) location(s) in the map

Question 17

What do we say about scan alignments where the correct correspondences are known?

Answer 17

We say that the data association is known/unambiguous.

Question 18

Where could scan correspondences come from?

Answer 18

• We could have an extra piece of knowledge
  like room numbers beside office doors
• We could run an algorithm to “match”
  similar looking places in the world (ideas in
  Computer Vision COMP 558)