Math for triangulation of 3 radio signals

Willsworld.org

Does anyone know how to solve the mathematics to locate a point using trianglation of 3 radio signals on an uneven terrain?· I know how to do it on a flat plane but can't figure out on an uneven terrain.

Robert Kubichek

It's the same, triangulation is a single plane function, so with elevation added
in u still set a single plane that u know the elevation of the 3 rf ransmitters.
Then add or subtract the elevation of the bot to bring it to that set plane..
From that plane it's all geometry..


Bob N9LVU

.

Willsworld.org

That only works if you know the elevation of the unknown point.· Imagine 3 triangulation robots and one unknown location robot up on the moon.· How can the unknown location robot determine where he is in relation to the other 3 tri-bots when the 3 tri-bots don't know his elevation.· If he sends a signal and waits for a return signal, through math you could triangulate the coordinates on a single plane, but if you are at a different elevation (unknown) the time differential would show you at a different location.· How can I determine the lost robots coordinates?· Any help solving this problem would be great.·

A few bullet points:

1.· Distance between lost bot and 3 tri-bots will be less than 500' radius and elevation difference.
2.· The lost bot will transmit a data string consisting its ID, and an instruction for the 3 tri-bots to respond.
3.· The 3 tri-bots will then transmit a data string consisting of its known coordinates, and an acknologment bit and the ID of the lost bot.
4.· On a level plane, a distance of 500' (calculation of rf speed/time) would be 500'.· But if the lost bot is 50 feet above the 3 tri-bots at a distance of 50', the calculated distance would be 71'.· This is a big difference between 71' and 50', so the coordinates would be off by as much....

Any suggestions.....

Franklin

Who tells the three bots their elevation and who is doing the math? Seems to me if the three bots are spaced around the lost bot the elevation error will be about the same for each giving the lost bot an area in which he resides. in order to do the math you need to know the elevation of all points.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
- Stephen

Willsworld.org

I am working on a system to colonize outer space.· The first robot to initiate on another planet is known as the CPU.· From here the second robot ( the 1st tri-bot) will travel at a predetermined distance from the CPU and will scan the area looking for an IR signal from the CPU.· This will determine the angle of inclination or declination from the CPU.· This direction from and elevation from the CPU will establish the ficticious N-S coordinate and established elevation.· The third robot ( another tri-bot) will do the same but heading in a E-W direction.· This establishes an initial coordinate system.· I'm trying not to build every robot (not tri-bot type) with a elevation detection system (trying to save on initial cost).· Can anyone come up with a location system that would be cost effective and simple.· I have the location system perfected on a single plane, but I'm looking for help on a 3-D location system.

Beau Schwabe

Willsworld,
·
I think you are going to need more than 3 points.· With only 3 points no matter where they are spatially you are going to form· a plane.· I think for proper 3-dimentional mapping you need·a total of 6 points.·
·

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Beau Schwabe

IC Layout Engineer
Parallax, Inc.

Tom Walker

You might be able to use the Time Of Flight (TOF) of your signals if they contain some info that can be referenced in the time domain (known transmission start time, encoded current time, etc...)...

Otherwise, I believe Beau is right, you don't have enough data in three points.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Truly Understand the Fundamentals and the Path will be so much easier...

daniel

Willsworld.org said...
4. On a level plane, a distance of 500' (calculation of rf speed/time) would be 500'. But if the lost bot is 50 feet above the 3 tri-bots at a distance of 50', the calculated distance would be 71'. This is a big difference between 71' and 50', so the coordinates would be off by as much.

and

Willsworld.org said...
This will determine the angle of inclination or declination from the CPU. This direction from and elevation from the CPU will establish the ficticious N-S coordinate and established elevation.

Somehow you knew 71 was the hypotenuse of the triangle with legs of 50. Use trig to use the elevation angle and the measured "distance" to solve for the "vertical" leg of the triangle. Combine this with the established planar location (x-y) you already have worked out for the x-y-z coordinates.

Or, perhaps for a more rigorous approach, you might try this chain of articles (one leads to the next):

en.wikipedia.org/wiki/Surveying

en.wikipedia.org/wiki/Delaunay_Triangulation

local.wasp.uwa.edu.au/~pbourke/papers/triangulate/index.html


Or maybe you want to use a spherical approach--start at en.wikipedia.org/wiki/Spherical_trigonometry.


How accurate do you need to be (see introduction of article at www.movable-type.co.uk/scripts/gis-faq-5.1.html)? For example, in planetary exploration as described, is 1km or 100m close enough, or do you need 0.1mm? Are your sensor's and their mountings up to the required resolutions?


Finally, Johann Borenstein's "Where am I?" (www-personal.umich.edu/~johannb/) and related works should be of interest.


HTH,
Daniel

Willsworld.org

Wow, I go to work today and miss all the exciting answers.· I briefly read and understood the answer by daniel, but the only thing I don't understand is :

Daniel said...
Use trig to use the elevation angle and the measured "distance" to solve for the "vertical" leg of the triangle. Combine this with the established planar location (x-y) you already have worked out for the x-y-z coordinates.

In our hypothetical situation, I know that #1 tri-bot is at elevation +10.· #2 tri-bot is at elevation +5.· And #3 tri-bot is at elevation +0.· Plug in any simulated time delayed distance (rf transmit/receive time calculation) and we won't know if the "lost" bot is +x or -x elevation.· Both + and - will be true, ah, just had a brain fart.· I could do the following:

With 2 tri-bots, there are 2 possible coordinates.· With 3 tri-bots, there is only one possible coordinate if all bots are on the same plane.· If the bots are·on different elevations, I will need more tri-bots to eliminate multiple true solutions to the equations, as noted by

Beau Schwabe said...
I think for proper 3-dimentional mapping you need·a total of 6 points.

My next problem is the exact equation and code for the program.
Is anyone up for a challenge of helping me write the program/s for this?· I am using a BS2 and the rf transmitter sold by Parallax (I'll get the model number later).· If it's ok with Parallax, I would like anyone who wishes to help, please contact me either here, or at my email.

Franklin

I think you are on the right track but I would recommend you forget the program for now and concentrate on the math. Once that is figured out see if the stamp will be capable of doing the job.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
- Stephen

Willsworld.org

Just had another brain storm.· The formulas for singular plane triangulation will be the same for spherical triangulation.· With 2 tri-bots, you will have 2 possible coordinates with 2 possible elevation points.· This gives you a total of 4 possible points.· The 3rd tri-bot will give you one possible coordinate and elevation.·

Now I need to know the formula to use.· Something like side-side-side, or side-angle-side.· Anyone know what I'm trying to get at?

Bruce Bates

Will -

It's been a number of decades since I took my last class in trig, but as I remember, S-S-S can only be solved for special cases, namely right triangles, and equilateral triangles. Beware the dangers there, if that is indeed the case.

Regards,

Bruce Bates

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔

daniel

Willsworld.org said...

Daniel said...

Use trig to use the elevation angle and the measured "distance" to solve for the "vertical" leg of the triangle. Combine this with the established planar location (x-y) you already have worked out for the x-y-z coordinates.

In our hypothetical situation, I know that #1 tri-bot is at elevation +10. #2 tri-bot is at elevation +5. And #3 tri-bot is at elevation +0. Plug in any simulated time delayed distance (rf transmit/receive time calculation) and we won't know if the "lost" bot is +x or -x elevation. Both + and - will be true...

Perhaps I misunderstood earlier statements. I assumed that you would know the difference between a + and a - elevation (that is, you had both a distance measurement and an elevation measurement). I postulated that given the direction and elevation measurements of one object relative to another meant that one object could be chosen as the vertical ZERO reference (like the sea-level reference), and then all other objects could, from that reference plane, be positioned on the vertical axis.

BTW, is the "lost bot" a 4th bot?

Does your extraterrestrial planet(oid) have a large enough diameter with respect to the territory being explored that you can assume that the problem domain is flat?


Daniel

Willsworld.org

Daniel....

Very close to what I am thinking.· I do know the elevations of the tri-bots.· These will be established during the initial landing and set up of the first 3-6 tri-bots.· I thought about GPS, but Mars doesn't have the technology yet (maybe they do, but we don't know yet...he he he).· This leaves me with developing an rf location system.· Triangulation is the key, and my problem is how to solve the math.· I think I've figured it out, but my trig and geometry from my surveying years is rusty.

I've figured out that with 1 tri-bot, the signal will be anywhere on a sphere with a radius of x distance (x being the computation of send/receive time of the rf signal).· Adding a second tri-bot, we will have only 4 points at which the 2 spheres will intersect, regardless of the elevation of the 2 tri-bots.· The information about those 4 points when referenced to the 2 tri-bots will tell us the relative elevation of the "Lost Bot" (yes, the 4th robot).· The 3rd tri-bot will narrow down the location to 2 points.· And finally the 4th tri-bot will narrow it down to a coordinate and elevation.

The math is as follows, with a little rust thrown in:

Side 1 = Distance between Tri-bot 1 and Tri-bot 2. (constant)

Side 2 = RF distance calculation of Tri-bot 1. (variable)

Side 3 = RF distance calculation of Tri-bot 2. (variable)

I have to go to work, I'll get some pics uploaded later.

daniel

Willsworld.org said...
...we will have only 4 points at which the 2 spheres will intersect...

Won't the intersection of the surfaces of two spheres be a circle? (And the volume of the intersection of the two spheres something like a "flying saucer". [noparse][[/noparse]grin] )

Adding additional intersections quickly pares both the volume to more closely match the "point" location.

Don't forget to eventually account for the variability (error) of your measurements. Although I'd probably ignore the error in the initial mathematical solution.

Good exploring.

Daniel

cyplesma

for us non rocket scientists:

you got three bots trying to find one bot in 3d space. If they were on the floor in the living room it would be 2d space.

Each locating bot need to be able to determine if the signal from the lost bot is below, equal, above the plane of your locating bot.

Do you have your locating bots capable of doing this function? and if so what resolution are you using, may I suggest you keep it simple with 8 points in each of the 3 axis. Including below. Your lost robot in the air will be able to find the 3 on the ground, without flying upside down.

or I guess you could keep sensors on sides and top of the bots and fly the incoming bot upside down.

Willsworld.org

Yes, Daniel, I thought of that on the way to work.· If you slice the two spheres where they overlap, you would get a circle.· Using two tri-bots would leave the lost bot somewhere on that circle (too many points to compute).· A third tri-bot should narrow it down to two points on that circle.· So a forth tri-bot would be needed to isolate the exact coordinate and elevation.

Cyplesma, the lost bot is not flying, but if it is higher than another tri-bot, it will still send and receive the radio signal.· In a two plane system, living room floor, it would be easy.· But, we have to work on the 3d system.· I have the concept, see paragraph above, but can't remember how to use trig to calculate the coordinate and elevation.· I used to do it many years ago when I was in construction surveying, but I've forgotten many of the formulas.

cyplesma

what type of signal are you using? radio (fm/am/uhf), microwave, ir

daniel

Willsworld.org said...
...can't remember how to use trig to calculate the coordinate and elevation...

Perhaps these trig identities ( en.wikipedia.org/wiki/Trig ) will help nudge the recollection. Don't neglect that little excursion through the history, and especially that interesting sketch from the 1728 Cylopedia (which reference covers spherical trigonometry in just over one column).

Daniel

cyplesma

"I used to do it many years ago when I was in construction surveying, but I've forgotten many of the formulas."


keep in mind you surveying equipment you adjusted you beam in an up/down fashion and focused the lens for distance. (2 degrees of measure not just one)



by the way how many sensor points does each bot have?

Willsworld.org

Cyplesma, I intend on using the 2.4ghz transceiver sold by parallax (and I haven't had the chance to get the model number yet).· As far as sensors, none, just the radio signal and timing the out and in time with calculations for distance.· The transceiver has a range of 500' line of sight, so my precision should be within an inch or two.· That's acceptable for my design.· I'm using the transceiver to send a few bits of data telling the tri-bots to respond and then receive the signal back to the "Lost Bot".· That will give me a know distance from that particular Tri-bot, but not a direction nor elevation.

cyplesma

ok, so you use the three bots to triangulate the target bot. which is just a 2d plane. but now that I looked at that wiki site mentioned earlier two bots should get you that circle of possibilities (mentioned earlier) and use the third bot's distance measurement to find where on the circle.


Of course if you asking if any has any code or basic functions already written, I can't help with that, I'm just trying to help ya think it through.

If it was me, I'd make the sensor directional, do the transmit antenna omni directional, and make the receiving antenna directional. Even if the direction is controlled by either the bot's heading itself or by a motor turning the receiving antenna. break out excel and put the spreadsheet to use, that's how I usually do my math R&D.

Willsworld.org

Got the model number.....Stock#:·27985.· It's the 912 mhz transceiver.

Willsworld.org

Cyplesma,· I've set up a test in my room using known points and distances, but don't have the formula to check if it's correct.· My example is as follows:

Tri-bot 1 =· Northing- 1000'
················ Easting-··1000'
················ Elev.-········· 0'

Tri-bot 2 =· Northing- 1001.667'
················ Easting-· 1000'
················ Elev.-·······.42'

Tri-bot 3 =· Northing- 1000.833'
················ Easting-· 1001.667'
················ Elev.-······1.75'

Distance from············ to············· =
····· Tri-bot 1······ Lost Bot········ 12.5"
····· Tri-bot 2······ Lost Bot········ 14.5"
····· Tri-bot 3······ Lost Bot········ 17.5"

The elevation of the Lost Bot (as measured in this test) = .667'

In our solution, we can only use the tri-bot coordinates and the distances from.· The elevation of the lost bot will be a check to see if the formulas are correct.· Remember our tolerances are within an inch.

Willsworld.org

Easting on Tri-bot 3 = 1001.417'

cyplesma

so if I understand you right, then this picture should show where the 4th bot is. not the height just the north/east position.

yeah or am I way off?

where the red lines intersect

I did do a landscape view to look at the bots from the side, bot all three circles intersect below the surface, which wouldn't be right anyway since the bots are not on the same plane.


!!maybe that's what you need to do determine the plane all three bots are on to find the angle to use to find the height.

I would have to imagine some earthquake locating trig would work here. Especially if that math works for locating an earthquake below the ground.

Post Edited (cyplesma) : 8/25/2007 11:19:59 PM GMT

Willsworld.org

cyplesma, you are absolutely correct in your drawing with one exception....we have an elevation as well as direction.· What I am looking for is the math to figure the intersection point of your red lines.· It's something like a^2+b^2=c^2 or sin(a)/A = Sin(b)/b or (a+b+c)/2*sin(a)· or something like that.· I know the formula is out there, i just can't remember the exact form of the formula.· I do know that the last formula above is the beginning... side a + side b + side c.....then I forget the rest.· It's right up the alley of the law of sines or the law of cosines... or something like that.·

D Faust

This might be what you are looking for: http://www.clarku.edu/~djoyce/trig/oblique.html

Check other pages of the site if this doesn't suit you.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔

LOOKDOWN ThisThread, [noparse][[/noparse]Your_?, My_?, Cool_Thing], looknum
LOOKUP looknum, [noparse][[/noparse]1, 2, 3], subnum
ON subnum GOTO Hope_this_helps, Thanks!, WOW!!
END 

Franklin

What are you going to use to time the signal? The signal will be traveling 1 inch in approx. 0.000,000,0001 sec. (not sure of the math)

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
- Stephen

Willsworld.org

Franklin, why do you have to burst my bubble like that....he he he.· I haven't gotten that far yet.· But I guess I should think about that soon.· Electromagnetic waves travel at 11.802 inches per nanosecond.· At 30 feet (360 inches) that would be 30.5 nanoseconds.· I guess that is to fast for the BS2 to calculate.· Bummer.· THANKS FRANKLIN, GRRRRR....just kidding, guess I'll have to figure another way to solve this problem.· Any suggestions?

Franklin

Well, IR rangefinders do it si I guess it can be done, How I don't know though.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
- Stephen