2d trilateration

Question

I am writing some code to participate in an AI challenge. The main objective for the AI challenge is to take a simulated robot and navigate it through a maze to a destination zone. The secondary objective which is optional is to find a recharger placed in the maze at an unknown location. This is all done in a 2D grid.

My program can call a method to get a distance measurement from the recharger. So using trilateration I should be able to locate the recharger by calling this method, recording my ai's current position and the distance the recharger is away from that point 3 times over.

I found this example of trilateration on wikipedia http://en.wikipedia.org/wiki/Trilateration but this applies to a 3d space. I'm only dealing with a 2D space. Also I don't understand how to use the formula shown in Wikipedia, searching the web for a working example with numbers plugged in and boiling down to the final coordinates is scarce with Google searches.

I'm not a math major; I am just an enthusiast exploring AI problems.

An explanation and step by step example of how to calculate the problem is what I need as mathematics are not my strong point. Below is some sample data:

• Point 1: x=39, y=28, distance=8
• Point 2: x=13, y=39, distance=11
• Point 3: x=16, y=40, distance=8

Any example using my sample data would be greatly appreciated. The programming to this will be very straight forward once I can wrap my head around the mathematics.

Liquid

Just take the 3D formulas and set height to zero. – Pebble

That would definitely work, but I don't know how to use the formula on wikipedia. I'm looking for a step by step example of how to go through the calculations. – Liquid

May I ask which AI challenge? – Meda

www2.mohawkcollege.ca/events/amazebot Mohawk College's amazebot challenge. It's a great academic project. It's purely optional, no grades will be given for this. – Liquid

Answer 1

As the Wikipedia trilateriation article describes, you compute (x,y) coordinates by successively calculating: e_x, i, e_y, d, j, x, y. You have to be familiar with vector notation, so, for example, e_x = (P2 - P1) / ‖P2 - P1‖ means:

• e_x,x = (P2_x - P1_x) / sqrt((P2_x - P1_x)² + (P2_y - P1_y)²)
• e_x,y = (P2_y - P1_y) / sqrt((P2_x - P1_x)² + (P2_y - P1_y)²)

Your data is:

• P1 = (39, 28); r₁ = 8
• P2 = (13, 39); r₂ = 11
• P3 = (16, 40); r₃ = 8

The calculation steps are:

1. e_x = (P2 - P1) / ‖P2 - P1‖
2. i = e_x(P3 - P1)
3. e_y = (P3 - P1 - i · e_x) / ‖P3 - P1 - i · e_x‖
4. d = ‖P2 - P1‖
5. j = e_y(P3 - P1)
6. x = (r₁² - r₂² + d²) / 2d
7. y = (r₁² - r₃² + i² + j²) / 2j - ix / j

Pebble

perfect thank you. Now I can understand where these variables are coming from. I'll have to do some practice with vectors of course but this is a good start. Thank you Don :). – Liquid

and the last step to get real coordinates of unknown point as tells Wiki are as follows: 8. p1,2 = P1 + x*ex + y*ey gives the points in the original coordinate system since ex and ey, the basis unit vectors, are expressed in the original coordinate system. -- a comment from an edit from anonymous user – Erbium

#23400851 could you check this post too, please? – Ravish

@OnurÇağırıcı, too far away? It could mean that the input coordinates are bad. Collinear coordinates might do that, for example. – Pebble

@DonReba I check collinearity. My points are [-0.8092775327548827, -19.576297388406005, 0.0], [0.8541381922861269, -9.975819993705937, 0.0] and [-0.597554605602997, -18.347159283433726, 0.0]. y = 13233.037425080443. – Ravish