Localization with Few Distance Measurements
Abstract
A robot is placed inside a known polygonal workspace but in an unknown position and orientation. The robot is equipped with a distance sensor, namely, a device that can measure the distance from the sensor to the nearest object in a given direction. For simplicity, let’s assume that we only concern ourselves with the position (x, y) of the sensor (rather than of the whole robot) and the orientation θ of the ray that measures the distance, namely, the angle between the ray and the positive xaxis. Our goal is to determine where in the workspace our sensor could be, after carrying out one, two, or several distance measurements.
Two measurements
Query 1: d_{1} = 1, d_{2} = 1, θ = 90° 
Query 2: d_{1} = 1, d_{2} = √2, θ = 90° 
Query 3: d_{1} = 1, d_{2} = √2, θ = 45° Workspace: p5.txt 
Query 4: d_{1} = 1, d_{2} = √2, θ = 180° 
If only a single measurement is carried out at an unknown direction, the possible locations of the robot comprise twodimensional regions. Here, we concern ourselves with a variant of the problem where a query consists of three real numbers d_{1}, α, d_{2} describing the following sequence of events: The sensor at its original state obtains the distance reading d_{1}, then the sensor is rotated (without translating) by α radians counterclockwise, and then it obtains a second distance reading d_{2}. The possible locations of the robot in this case comprise of onedimensional curves in the general case; see the figure to the right. If the query is augmented by a second rotation followed by a third measurement, the possible locations of the robot consist of one or more isolated points (in the general case).
A more complicated problem allows for a translation of the robot before the second measurement is taken. In this variant a query consists of four real numbers d_{1}, α, t, d_{2}, where t denotes a translation vector in the plane. If t != 0, the two measurements can be taken simultaneously. This is possible in practice, if two distinct sensors are at our disposal. We made experiments with a real robot equipped with two sensors.
Figure 1: Self localization with two measurements.

We start with an algebraic analysis of the problem. Here, we concentrate at a local view of the problem, where we only consider two walls (edges) of obstacles and ignore everything else; see Figure 1. Let L_{1}: a_{1} x + b_{1} y + c_{1} = 0 and L_{2}: a_{2} x + b_{2} y + c_{2} = 0 denote the two underlying lines of edges of obstacles hit by the two measuring rays, respectively. Let p = (x,y) denote a point in the workspace our sensor could be located at. Let p_{1} = (x_{1},y_{1}) denote the point on L_{1} hit by the first measuring ray, and similarly, let p_{2} = (x_{2},y_{2}) denote the point on L_{2} hit by the second measuring ray. The following equations must be satisfied:
 a_{1}·x_{1} + b_{1}·y_{1} + c_{1} = 0,
 a_{2}·x_{2} + b_{2}·y_{2} + c_{2} = 0,
 p  p_{1} = d_{1},
 p  p_{2} = d_{2}, and
 d_{1}^{2} + d_{2}^{2} = p_{1}  p_{2}^{2}  2·cos(α)·d_{1}·d_{2}
Two measurements in Opposite Directions
This is similar to above, with two additional constraints listed below, which makes the problem more tractable. First, α = π/2, which implies that the two measuring rays lie on the same line, say l. Second, either t == 0, or t also lies on l.
Links
 Barak Ugav
 Michael Bilevich
 Efi Fogel
Two Measurements: Algebraic Analysis [pdf]
Matlab [m]
Orthogonal and xaxis aligned: GeoGebra script [ggb]
Xaxis aligned : GeoGebra script [ggb], Solution [pdf]
Contact
Barak Ugav  
Michael Bilevich  
Efi Fogel  
Dan Halperin 