CSCE 452/752: 11. Localization 1: Dudek-Romanik-Whitesides Localization

Introduction

Localization is the problem of determining and tracking the robot's position, relative to a map of its environment.

Localization is a big topic for mobile robots.

Several different kinds of problems share the name “localization.”
In many cases, the details of the algorithm vary depending on what sensors the robot has.

Today, we'll start with one example localization algorithm that uses a cell decomposition of the environment.

Types of localization problems

Passive vs. Active

Passive localization: Interpret sensor data to determine the robot's state.
Active localization: Choose actions designed to help determine the robot's state.

Local vs. Global

Local localization (“pose maintenance”): Start with good information about the robot's state. Keep track of this knowledge as the robot moves around.
Global localization: Start with no information about the robot's state. Try to eliminate this uncertainty.

Today: Active Global Localization

Suppose we have a robot in a polygonal environment, equipped with a range sensor and a compass. (...but without sensor noise.)

State space: $\mathbb{R}^2$ (position only; no orientation)

Today, we'll talk about the

active
global

localization problem for this system.

This is called Dudek-Romanik-Whitesides localization, after the roboticists that first solved it.

Sensor information: Visibility polygon

We can think of the range sensor as providing the visibility polygon of the robot's state $x$ in its environment.

\[ V(x, E) = \{ y \in E \mid \overline{xy} \subset E \} \]

The visibility polygon is expressed the robot's body frame.

The robot is located at the origin in this frame.
Visibility polygon vertices are expressed relative to the robot's position.

Possible states

Q: What can the robot conclude after its first sensor reading?

A: The robot receives a visibility polygon. It knows it is at one of the positions that has this visibility polygon.

The process of computing this initial set is called hypothesis generation.

Remember that the robot has a compass, so we don't need to consider rotations of the visibility polygon, only translations.

Hypothesis generation algorithm

Input:

Environment polygon. ($n$ vertices)
Visibility polygon. ($m$ vertices)

Output:

Set of states in this environment that have this visibility polygon.

Algorithms are known to solve this problem in $O(mn)$ time.

Can be much faster if we have multiple queries in the same environment polygon. (Space-time tradeoff.)

How many hypotheses can there be in the worst case?

Hypothesis elimination

Now that we have a small number of candidates, how can we determine which candidate is the correct state?

To solve this problem, we need a decision tree.

Internal nodes: Motion by the robot, followed by sensing the visibility polygon.
Edges: A visibility polygon returned by the sensor. (How do we know the number of edges is finite?)
Leaf nodes: A known final position for the robot.

The worst-case path length of such a decision tree is the amount of motion needed to go from the root to the most distant leaf node.

Bad news

The hypothesis elimination problem is NP-hard if we want the shortest path that localizes the robot.

Proof idea: Reduction from Abstract Decision Tree.

Visibility cell decomposition

So let's forget about optimality and just think about getting some kind of solution. What kinds of motions are helpful?

Visibility cell decomposition: Divide the environment polygon by drawing rays

outward from each pair of mutually visible vertices, and
outward from the incident edges of each reflex vertex.

Why?

When the robot crosses one of these boundaries its visibility polygon gains or loses a vertex.

Equivalently, if the robot does not cross any of these boundaries, then the set of vertices in the visibility polygon remains the same.

Environment overlays

How does the visibility cell decomposition help us?

Imagine an overlay, with one copy of the environment for each candidate.
Translate each copy so that the candidate state is at the origin.

How does this overlay help with the localization problem?

Main idea: Choose a path that crosses a visibility cell boundary in one of the overlays, but not both.

Hypothesis elimination algorithm

Algorithm:

Compute the overlay (including visibility cell decompositions) for all of the candidate states.
Choose a destination that moves to a different cell in some, but not all, of the overlay layers.
Sense the visibility polygon the robot's new position.
Eliminate candidates that are not consistent with this sensor reading.
Repeat until only one candidate remains.

If we choose the destination points carefully, starting with $k$ candidates, we can get a solution that takes no more than $(k-1)$ times as much motion as the optimal strategy.