Practical assignment #2 (Geospatial navigation)

Gate

The gate for practical assignment is OPEN.

Gate name: ntuu.kpi@ukr.net

Requirements

Implement the algorithm identifying Receiver's location (latitude, longitude) out of the position of four GPS satellites given per variant. Identify the name of a city from its coordinates using the table of world capitals (List of capitals)

Considerations

Receiver's location is approximated by solving a system of equations for specific satellite coordinates:
(x−A1)2+(y−B1)2+(z−C1)2−(c(t1))2(x−A2)2+(y−B2)2+(z−C2)2−(c(t2))2(x−A3)2+(y−B3)2+(z−C3)2−(c(t3))2(x−A4)2+(y−B4)2+(z−C4)2−(c(t4))2=0=0=0=0

where x, y, and z are the rectangular coordinates of the receiver, A, B, and C are the coordinates of the satellites and t is the travel time for the signal from the satellite to the receiver, c is speed of light (299792 km/s).
Satellite equations can be solved e.g. by Cauchy minimization:

f(x,y,z) -> min

v^k+1= v^k - grad(f(v^k))*alpha^k,

where alpha^k is the step length unique for every iteration k. 

• Prepare minimization function by taking absolute values of each equation and adding four equations together;
• Start the search from equating initial guess vector v⁰ to (0,0,0);
• To find alpha^k substitute v^k+1 value into function f(v) and do linear search incrementing alpha until minimal value of function f(v^k+1) is found: start with alpha^k equal to 0 and increment on a some small step (e.g. 0.0001);
• When optimal alpha^k is found (usually in 100 iterations) proceed to a new iteration equating v^k = v^k+1. 

Note 1:
Satellite positions (Ai, Bi, Ci) can be found from spherical coordinates (ρi, φi, θi) as:
          Ai = ρcos(φi)cos(θi)
          Bi = ρcos(φi)sin(θi)
          Ci = ρsin(φi)
where ρ is the radius 26'551km made by the GPS orbit height 20'180km + the Radius of the planet Earth that equals 6'371km. Define radius in thousands of kilometers, otherwise target function may overflow.
During conversion take the Northern hemisphere with plus sign of latitude angle and Southern hemisphere with negative sign. Treat East longitude with plus sign and West longitude with negative sign.

Note 2:
Conversion from Cartesian system back to spherical system can be made as follows:

22

Variants

block 1

block 2

block 3