Personal tools
You are here: Home Projects In-house Projects Localization with Few Distance Measurements Localization with Few Distance Measurements
« October 2022 »
October
SuMoTuWeThFrSa
1
2345678
9101112131415
16171819202122
23242526272829
3031
Log in


Forgot your password?
 

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 x-axis. Our goal is to determine where in the workspace our sensor could be, after carrying out one, two, or several distance measurements.

Two measurements

loc_square1 loc_sqaure2
loc_square2
loc_sqaure4
    loc_square5
 
Query 1: d1 = 1, d2 = 1, θ = 90°

Query 2: d1 = 1, d2 = √2, θ = 90°

Query 3: d1 = 1, d2 = √2, θ = 45°
Workspace: p5.txt
Query 4: d1 = 1, d2 = √2, θ = 180°

If only a single measurement is carried out at an unknown direction, the possible locations of the robot comprise two-dimensional regions. Here, we concern ourselves with a variant of the problem where a query consists of three real numbers d1, α, d2 describing the following sequence of events: The sensor at its original state obtains the distance reading d1, then the sensor is rotated (without translating) by α radians counterclockwise, and then it obtains a second distance reading d2. The possible locations of the robot in this case comprise of one-dimensional 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 d1, α, t, d2, 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.

two measurement geometry
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 L1: a1 x + b1 y + c1 = 0 and L2: a2 x + b2 y + c2 = 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 p1 = (x1,y1) denote the point on L1 hit by the first measuring ray, and similarly, let p2 = (x2,y2) denote the point on L2 hit by the second measuring ray. The following equations must be satisfied:

  1. a1·x1 + b1·y1 + c1 = 0,
  2. a2·x2 + b2·y2 + c2 = 0,
  3. |p - p1| = d1,
  4. |p - p2| = d2, and
  5. d12 + d22 = |p1 - p2|2 - 2·cos(α)·d1·d2

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 x-axis aligned: GeoGebra script [ggb]
    X-axis aligned : GeoGebra script [ggb], Solution [pdf]

Contact

Barak Ugav http://acg.cs.tau.ac.il/people/barak-ugav/barak-ugav null
Michael Bilevich http://acg.cs.tau.ac.il/people/michael-bilevich/michael-bilevich null
Efi Fogel ../../../people/efifogel null
Dan Halperin http://acg.cs.tau.ac.il/danhalperin null
Document Actions