7

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.

apaderno
  • 28,547
  • 16
  • 75
  • 90
Nebri
  • 773
  • 2
  • 8
  • 21
  • 2
    Just take the 3D formulas and set height to zero. – Don Reba Mar 17 '12 at 04:57
  • 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. – Nebri Mar 17 '12 at 15:39
  • May I ask which AI challenge? – gak Mar 17 '12 at 23:50
  • http://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. – Nebri Mar 18 '12 at 03:13

1 Answers1

14

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

  • ex,x = (P2x - P1x) / sqrt((P2x - P1x)2 + (P2y - P1y)2)
  • ex,y = (P2y - P1y) / sqrt((P2x - P1x)2 + (P2y - P1y)2)

Your data is:

  • P1 = (39, 28); r1 = 8
  • P2 = (13, 39); r2 = 11
  • P3 = (16, 40); r3 = 8

The calculation steps are:

  1. ex = (P2 - P1) / ‖P2 - P1‖
  2. i = ex(P3 - P1)
  3. ey = (P3 - P1 - i · ex) / ‖P3 - P1 - i · ex‖
  4. d = ‖P2 - P1‖
  5. j = ey(P3 - P1)
  6. x = (r12 - r22 + d2) / 2d
  7. y = (r12 - r32 + i2 + j2) / 2j - ix / j
Don Reba
  • 13,814
  • 3
  • 48
  • 61
  • 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 :). – Nebri Mar 18 '12 at 03:15
  • 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 – Dariusz May 09 '13 at 08:10
  • http://stackoverflow.com/questions/23400351/localizing-a-point-using-distances-to-three-other-points-in-3-d/23401529?noredirect=1#23401529 could you check this post too, please? – padawan May 01 '14 at 18:47
  • @OnurÇağırıcı, too far away? It could mean that the input coordinates are bad. Collinear coordinates might do that, for example. – Don Reba May 27 '14 at 04:45
  • @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`. – padawan May 27 '14 at 15:02