Optimization Models
Home
Software
Links
Index
Contact
1. Introduction
1.1. Overview
1.2. Optimization Models
2. Linear Algebra
2.1. Vectors
2.2. Matrices
2.3. Linear Equations
2.4.  Least-Squares
2.5. Eigenvalues
2.6  Singular Values
3. Convex Models
3.1. Convexity
3.2. LP and QP
3.3. SOCP
3.4. Robust LP
3.5. GP
3.6. SDP
3.7. Non-Convex Models
4. Duality
4.1. Weak Duality
4.2. Strong Duality
4.3.  Applications
5. Case Studies
5.1. Senate Voting
5.2. Antenna Arrays
5.3. Localization
5.4. Circuit Design

Problem Statement

Localization > Problem | Next

The localization problem

We are given anchor positions x_i in mathbf{R}^3, and associated distances from these anchor points to an unknown object, R_i, i=1,ldots,m. The problem is to estimate a position of the object, and associated measure of uncertainty around the estimated point. Geometrically, the measurements imply that the object is located at the intersection of the m spheres of centers x_i and radiuses R_i, i=1,ldots,m. The main problem is to provide one point in the intersection located at some kind of ‘‘center’’, and also a measure of the size of the intersection.

alt text 

Localization problem with three range measurements in two dimensions, with data

begin{array}{l} X = (x_1,x_2,x_3) = left(begin{array}{ccc}-0.46&0.19&0.480.03&0.54&-0.49 end{array}right), R^T = (R_1,R_2,R_3)= left(begin{array}{ccc} 0.5&0.6&0.85 end{array}right). end{array}

The goal is to find the ‘‘center’’ of the intersection area, where an object is located. Also we would like to quantify the size of the area.

Issues to be addressed

In general, the measurements may not be consistent, in the sense that the intersection of all the spheres may be empty. We will first address the problem of checking consistency, and adjust our measurements if necessary. Assuming then the measurements to be consistent, so that the spheres do intersect, in general the intersection may not be reduced to a unique point, which means that the measurement only allow to estimate the position with some level of uncertainty. We aim to provide both an estimate of the position, and a measure of the uncertainty.

There are two approaches to this problem. One consists in finding an inner approximation to the intersection, which is the largest sphere (or box) contained in it. This is in a sense an ‘‘optimistic’’ approach. Another approach is ‘‘pessimistic’’ and consists in finding the smallest sphere (or box) that contains the intersection. In both cases, the optimal radius of the sphere (or size of box) is a measure of uncertainty, and its center is the estimated position.