advanced math problem

[laasunde]

Originally posted by bennyandthejets
Hmmm. If you order the sensors from first received to last received (let's say A, B, and C) then you know the DIFFERENCE in distance between A B and C. You don't however yet know any distances. Ie:

'a' is the distance between object and A
'b' is the distance between object and B
'c' is the distance between object and C

∆AB is the time difference between A and B reception

so, b=a+(344*∆AB)

This means that distance 'b' is distance 'a' plus 344 times the time difference (assuming time is in seconds).

You could make a whole lot of those equations, but I don't think they could ever tell you a concrete distance, just a bunch of relations.

Does anyone think otherwise?

This is as far as I've gotten. Im pretty much stuck here.

[bennyandthejets]

Hmmm. I really don't think it's possible. I will however take the problem to my maths and physics teachers. Someone may know something.

Are you sure you can't just use the pulse send time? That would make things SOOOOOO much easier.

[adrianxw]

Once the pulse reaches the first receiver, you start your timing, once you have received the pulse at 3 transducers, you know how much further away from the second and third transducers are from the source.

Scaling problem then.

[bennyandthejets]

Fancy showing an example adrian?

I've tried using a number of different techniques, both graphical and algebraic, and nothing seems to work.

Once the pulse reaches the first receiver, you start your timing, once you have received the pulse at 3 transducers, you know how much further away from the second and third transducers are from the source.

That's already been established. I've written a billion equations stating the DIFFERENCE in distance from each receiver. None of these can be used simultaneously to get an actual distance.

Scaling problem then.

Scale away, I'm yet to be convinced.

[laasunde]

Originally posted by bennyandthejets
Hmmm. I really don't think it's possible. I will however take the problem to my maths and physics teachers. Someone may know something.

Are you sure you can't just use the pulse send time? That would make things SOOOOOO much easier.

I absolutely agree that knowing the sending time would greatly simplify this task but for the timing beeing I'd like to try and solve the problem without knowing the sending time.

[laasunde]

Originally posted by adrianxw
Once the pulse reaches the first receiver, you start your timing, once you have received the pulse at 3 transducers, you know how much further away from the second and third transducers are from the source.

Scaling problem then.

Agree it's a scaling problem but still dont know how to solve it. Would greatly appreciate if you could elaborate a bit, possibly with an example.

[savageag]

I think my earlier explanation was correct. Either it was not correct, or I did not explain it well enough. I did not write out the math, I figured you only needed help with the concept.


You can draw this out on paper to make it easier to understand.
To make it easier to think about first use the speed as 1 m/s.
Think of a box as the upper right area of a coordinate system. Where the first reciever is at point (0,0). Then think of reciever 2 at point (0,10) and reciever 3 at (10,0).

Now take the difference between the time at reciever 1 and reciever 2.

From just this information you will be able to find a list of solutions, which will all fall on a line.

For example, one possible solution is where the transmitter is on the line between point 1 and point 2. We know the total distance between point 1 and point 2 so finding that solution is simple. Say the time difference is 2 seconds (using a speed of 1m/s, the transmitter would be located at (0,4) if it is on the line between the two. So the time between transmission and recieving by reciever 1 is 4 seconds. Now if you supposed that the time between transmission and reception by reciever one is 5 seconds you also know that the time between transmission and reception by reciever 2 is 7 seconds. You can create a triangle then with sides of 10, 5, and 7. You can then figure the height of the triange and get the exact coordinates for this solution. Once you have two points you can find the equation of the line.

Once you have the line equation of all possible solutions for point 1 and 2, then do the same between points 1, and 3.

Now you have the equations for two lines and only have to solve for their intersection.

You still have to put in the math, but I think this should cover the idea of how to solve the problem. I feel pretty sure this solution would work, if someone knows otherwise, feel free to trash my solution.

[anonytmouse]

I was working on this before savageag posted so I'll post it even though it is similar.

Lets say the speed of the tranducer wave be 1 metre per second for simplicity.
Lets say the square measures 10 metres diagnally, again for simplicity.
Let A be the top left receiver, B be top right, C be bottom right and D be bottom left (ie. Clockwise).

A receives a signal and starts a timer.
C, in the opposite corner, receives a signal and works out the time difference between A and C.
Now if the bot was exactly in the middle of A and C the time difference would be 0.
The closer the bot is to A the greater the time the signal will take to reach C.
Now if the bot is at A (ten metres away from C) the time difference will be ten seconds(with signal travelling at one metre per second).
If the bot is halfway between A and the middle(7.5 metres from C, 2.5 metres from A) the time difference will be 5 seconds(7.5 seconds to travel to C minus 2.5 seconds to A).
So we have worked out how to find where it is on this line.

Time from A to C:
1s: 5.5m from C, 4.5m from A. (5.5 secs - 4.5secs)
2s: 6m from C, 4m from A. (6secs - 4secs)
3s: 6.5m from C, 3.5m from A. (6.5secs - 3.5secs)
4s: 7m from C, 3m from A. (7secs - 3secs)
6s: 8m from C, 2m from A. (8secs - 2secs)
9s: 9.5m from C, .5m from A. (9.5 secs - .5secs)

If the signal reaches C before A we can reverse these values.
Time from C to A:
2s: 6m from A, 4m from C. (6secs - 4secs)

We can do the same thing for the BD line.

When it is not on one of the intersecting lines the problem seems to get much harder. I think what we have to do is draw the possible curves.
If you haven't read this article I suggest you do it now:
http://travel.howstuffworks.com/gps.htm

For example: given a time of 2 seconds from signal received at A to C we look above and find 6m to C and 4m to A. So we get out our compass and draw a 4m arc from point A and a 6m arc from point C (you might have to do this in scale!).
We then do the same thing for the value we work out for B and D. Hopefully, we should find that the point is on the intersection of two of these arcs. The other arcs should not intersect.

To put all this in some sort of algorithm is beyond me but it should be possible.

Edit: After reading savageag's post it seems I was making the problem way too hard. I forgot we could also get the distance between A and D, etc. If you have the distance between A and C as well as A and D the problem becomes quite simple. The arc solution may work but is a lot more complex. If you try the arc solution, please tell me if it works!
End Edit.

Please post back when you find the solution to this problem.

[Waldo2k2]

I'm sure there's plenty of triangulation algorithms floating around the net....use one for an example to learn from

[savageag]

I think my earlier explanation was correct. Either it was not correct, or I did not explain it well enough. I did not write out the math, I figured you only needed help with the concept.


You can draw this out on paper to make it easier to understand.
To make it easier to think about first use the speed as 1 m/s.
Think of a box as the upper right area of a coordinate system. Where the first reciever is at point (0,0). Then think of reciever 2 at point (0,10) and reciever 3 at (10,0).

Now take the difference between the time at reciever 1 and reciever 2.

From just this information you will be able to find a list of solutions, which will all fall on a line.

For example, one possible solution is where the transmitter is on the line between point 1 and point 2. We know the total distance between point 1 and point 2 so finding that solution is simple. Say the time difference is 2 seconds (using a speed of 1m/s, the transmitter would be located at (0,4) if it is on the line between the two. So the time between transmission and recieving by reciever 1 is 4 seconds. Now if you supposed that the time between transmission and reception by reciever one is 5 seconds you also know that the time between transmission and reception by reciever 2 is 7 seconds. You can create a triangle then with sides of 10, 5, and 7. You can then figure the height of the triange and get the exact coordinates for this solution. Once you have two points you can find the equation of the line.

Once you have the line equation of all possible solutions for point 1 and 2, then do the same between points 1, and 3.

Now you have the equations for two lines and only have to solve for their intersection.

You still have to put in the math, but I think this should cover the idea of how to solve the problem. I feel pretty sure this solution would work, if someone knows otherwise, feel free to trash my solution.

[laasunde]

Originally posted by savageag
I think my earlier explanation was correct. Either it was not correct, or I did not explain it well enough. I did not write out the math, I figured you only needed help with the concept.


You can draw this out on paper to make it easier to understand.
To make it easier to think about first use the speed as 1 m/s.
Think of a box as the upper right area of a coordinate system. Where the first reciever is at point (0,0). Then think of reciever 2 at point (0,10) and reciever 3 at (10,0).

Now take the difference between the time at reciever 1 and reciever 2.

From just this information you will be able to find a list of solutions, which will all fall on a line.

For example, one possible solution is where the transmitter is on the line between point 1 and point 2. We know the total distance between point 1 and point 2 so finding that solution is simple. Say the time difference is 2 seconds (using a speed of 1m/s, the transmitter would be located at (0,4) if it is on the line between the two. So the time between transmission and recieving by reciever 1 is 4 seconds. Now if you supposed that the time between transmission and reception by reciever one is 5 seconds you also know that the time between transmission and reception by reciever 2 is 7 seconds. You can create a triangle then with sides of 10, 5, and 7. You can then figure the height of the triange and get the exact coordinates for this solution. Once you have two points you can find the equation of the line.

Once you have the line equation of all possible solutions for point 1 and 2, then do the same between points 1, and 3.

Now you have the equations for two lines and only have to solve for their intersection.

You still have to put in the math, but I think this should cover the idea of how to solve the problem. I feel pretty sure this solution would work, if someone knows otherwise, feel free to trash my solution.

Thank you for you reply.

I do not think your solution is correct.

Let me give you an example to try out, say I send out a pulse at an unknow time. This signal is picked up by each receiver at these times here:
receiver1 : 212,8284 seconds
receiver2 : 218,24621 seconds
receiver3 : 218,24621 seconds
receiver4 : 221,3137 seconds

The actual time isnt relevant in this context but the relationship between the four times is very important. So I could simply write,
receiver1 : 0
receiver2 : 5,4178
receiver3 : 5,4178
receiver4 : 8,4853

You can then calculate part of the distance from receiver2, receiver3 and receiver4 to the object. You dont not however know the distance between the object and receiver1. So I guess you can setup an equation that looks something like this :

dr1 = distance from object to receiver1

dr1 = x
dr2 = x + (5,4178 * 1m/s)
dr3 = x + (5,4178 * 1m/s)
dr4 = x + (8,4853 * 1m/s)

But how far does this get us ?

The area is 10*10 meters long. The speed is set to 1m/s.
Can you now please figure out what the position of the object was when sending the signal ?
Receiver1 is located at (0,0)
Receiver2 is located at (10,0)
Receiver3 is located at (0,10)
Receiver4 is located at (10,10)

Really appreciate everyones help.

Btw, I do know the answer to the above question just like to see if anyone manages to figure it out without me giving any clues.

[laasunde]

Originally posted by Waldo2k2
I'm sure there's plenty of triangulation algorithms floating around the net....use one for an example to learn from

Could you be so kind as to suggestion one ?

[savageag]

(2,2)

[confuted]

Originally posted by adrianxw
Once the pulse reaches the first receiver, you start your timing, once you have received the pulse at 3 transducers, you know how much further away from the second and third transducers are from the source.

Scaling problem then.

I didn't finish reading this thread, but here's an expansion of what Adrianxw said.

You have a sensor in each of the four corners of a 10*10 room. The distance between any two adjacent sensors is 10, and the distance between opposite sensors is sqrt(200) = sqrt(2^3*5^2)=10sqrt(2)

Order the sensors A,B,C, and D, in the order that they recorded the signal. Of course, you must also know the placement of each sensor within the room. For the example, the placement will be

A-B
| |
C-D

Because that's easy. Subtract the time A recieved the signal from the time the other three sensors recieved the signal...so you'll have the amount of time it took each sensor to get the signal after A got it. Let these three numbers be E,F, and G, respectively.

Now, you'll set up some triangles.

AC=AB=BD=CD=10
AD=BC=10sqrt(2)
Let the distance between the sensor and A be X (still unknown)
Let S be the speed of the wave.
Let H be the position of the sensor.

BH - AH = S*E
CH - AH = S*F
DH - AH = S*G

So we can get the distance of the sensor from B, C and D relative to the distance of the sensor from A.

Now you have some triangles. One triangle has these sides:
AH+SF,AH+SG,10
Another triangle:
AH+SG, AH+SE, 10
Another:
AH+SF, AH+SE, 10sqrt(2)
Another:
AH, 10, AH+SF
Another:
AH, 10, AH+SE

If we had AH, the solution would become completely trivial. If we had some angles, it wouldn't be hard. As it is... I need to do homework instead of thinking of this.

[savageag]

If you wanted x = 2.82.