CS401 Homework 6 Range-only based localization-Solved

Overview
Range only based localization is the technique of using only distance measurements from stations to determine the location of a target, with no information about the direction from which this distance was measured. Given a coordinate and a measured distance, the set of all points for which the target could be located forms a circle; the coordinate is the circle center and the distance is the circle radius. It is a classic problem in navigation and target tracking, and also applicable to problems such as using time-domain reflectometry to determine locations of faults in modem connections.

For example, a GPS receiver uses trilateration (a type of range only based localization algorithms) to determine its exact location from its measured distances from at least three satellites, each satellite is at the center of a sphere and where they all intersect is the position of the GPS receiver. For detail of GPS localization, please refer to How GPS Receivers Work - Trilateration vs Triangulation.

Localization of a single target
To simplify the problem, here we only consider the location in the two-dimensional plane.

We simulates an 802.11az network consisting of a station (STA) and multiple access points (APs). With only one station (STA), there are infinitely many points on the circle where the targets could be located. With two stations whose distance circles intersect, the possible target location is reduced down to two possible points. With three or more stations that intersect at a single point, the target location can be isolated to that point.

Thus, to estimate the position of a STA, the network requires a minimum of three APs.

The following demo simulates a ranging measurement exchange for each STA-AP pair, then trilaterates the position of the STA by using these distance measurements.

Suppose the known coordinates of AP1, AP2 and AP3 are

, respectively.

Also, the calculated distances from AP1, AP2, and AP3 to the STA are

, respectively.

Question 1
How to calculate the exact position

of the STA in the current coordinte space?

Note1: Linear least square method can be used to solve the problem analytically.

Mathematical Derivation

The distance equations between known APs and unknown STA are as following:

As we can see these equations are nonlinear, and we substract the third equation from the first and second equations, after that we can can obtain a linear equation:

Least square method can be used to solve this linear equation and the solver is:

Question2
However, even with accurate sensors, it is unlikely that three circles would intersect at exactly the same point at which the STA is located. This means that attempts to tackle this problem analytically will almost always fail. Instead, an optimization-based approach can be used; it infers the STA's location by finding the point which minimizes the squared euclidean distances between the STA and all the APs.

Please formulate an error function which calculates the euclidean distance between the STA and all APs:
is the total number of APs.

Question3
This problem is not convex. It is also worth noting that gradeint-based optimization methods such as Gauss-Newton(GN) and Levenberg–Marquardt (LM) algorithm used require a Jacobian (gradient) function. Thus, in this homework, we solve the problem using numerical optimization methods which are derivative-free methods. For example, Covariance matrix adaptation evolution strategy (CMA-ES) which uses the principle of biological evolution, namely the repeated interplay of variation (via recombination and mutation) and selection: in each generation (iteration) new individuals (candidate solutions) are generated by variation, usually in a stochastic way, of the current parental individuals. Then, some individuals are selected to become the parents in the next generation based on their fitness or objective function value. Like this, over the generation sequence, individuals with better and better function values are generated.

Please use CMA-ES algorithm to solve the localization problem, you can refer to the usage of CMAES in python from the link.

Code for questions
Note1: The question one is simple, please finish the function code in trilateration.py by refering to the above mathematical derivation.

Note2: Given the coordinates of a finite number of radio stations, and given their distances to the source (derived from the intensities of the signal they received in a previous step) computes the most probable coordinates of the source, please complete the quadratic function (the error function formulation) in distance_only_localization.py.

Note3: Please complete the optimization section of main function in the file distance_only_localization.py