GPS in the small

J. A. Streich

I'm sorry if this post seems to ramble a bit but I don't think I express my thoughts without the whole thought train. My understanding of G.P.S. is that it requires 3 "fixed" points (in the case of real GPS geosynchronous satellites (call them a, b and c), for our purposes we'll call them a, b and c. Now, the G.P.S. unit, in this case let's call it bot, sends out a time stamp to each of these stations. Each of which independently return two pieces of information: time stamp and it's absolute location. The bot then would then calculate the distance from each using the time stamps and the speed of signal through open air.

Lets say:
a is at (a_x,a_y) at a distance of i from the bot
b is at (b_x,b_y) at a distance of j from the bot
c is at (c_x,c_y) at a distance of k from the bot

Thus, the bot is logically at the intersection of the circles with centers at a, b and c and with radii of i, j and k respectively.
Which happens to be where:
(x-a_x)²+(y-a_y)²-i²=(x-b_x)²+(y-b_y)²-j²=(x-c_x)²+(y-c_y)²-k²

Now, I figure the same idea would work in the small, and the stations acting like the GPS satilites could be placed such that:
a = (0,0) 'we get to define our origin... so why not.
b = (1,0) '1 foot or 1 meter away from a
c = (0,1) '1 foot or 1 meter away from a, and sqrt(2) foot or sqrt(2) from b
This should make the math easy to simplify....
Looks like:
x = (j-i)/2
y = (k-i)/2
if I math-ed correctly.

Would it work in the small, say for mapping out a room, using units like feet? If the above is all correct (or at least close -- it's late, so my math is probably very off) there is one major problem I see with implementing this in the small. What can I send to the stations that will have a large enough delay over short distances to be measured (but has a constant speed) with the clock speed of a propeller chip. Suggestions on hardware or setup for such a system?

sylvie369

"Now, the G.P.S. unit, in this case let's call it bot, sends out a time stamp to each of these stations. Each of which independently return two pieces of information: time stamp and it's absolute location"

Your GPS unit doesn't transmit anything to the satellites. I don't think that affects the rest of your post, but the GPS unit you put on your bot is simply a receiver, receiving time-of-day and orbital position information from the GPS satellites.

This is very important. If a GPS satellite had to receive and process signals from·hundreds of thousands of GPS units requesting information, there'd be a nightmarish problem with the precise timing that GPS depends upon. But the work is done in each ground GPS unit, not in the satellites, so it doesn't matter how many people are trying to track their locations. The satellites don't know or care whether there's no-one listening or hundreds of thousands of units.

Also the GPS satellites are not in geosynchronous orbits. In fact I think they go around any spot on the ground twice per day. Of course that makes no difference to the rest of your post either.

Now, I may have misunderstood you entirely. Some of your post seems to suggest that you're thinking about making some other kinds of "stations" to use instead of the GPS satellites. I think you'd find that if those "stations" were located too close together, the precision you'd need in your timing measurements is WAY out of reach. I don't think that you can expect to set up three stations in the room and measure differences in signal travel time - you'd need either MUCH slower signals or·MUCH longer baselines. Adding a delay to the retransmission won't help you - what you need to measure is the difference in time, not the absolute time.

Measuring a difference in signal strength might be a better direction to take, though I'd think that reflected signals would cause a lot of problems, and I don't know that you could have an antenna whose reception was sufficiently uniform.

There's a lot of "it can't be done" - now I'll bet someone has figured this out and has already done it. I'm reminded of the military's little robot that locates the source of small arms fire aimed at our troops by measuring differences in the sounds from various directions, though of course that's sort of the inverse of your problem.

Post Edited (sylvie369) : 12/15/2007 12:22:04 PM GMT

Mike Green

One thing you could experiment with would be ultrasound, like the PING))), but working it differently. You couldn't use the PING))) itself, but similar sensors. Although the speed of sound is temperature sensitive, it's not likely to change quickly in a typical enclosed room. Even plumes of warm air over radiators and the like are probably stable for times on the order of seconds. The trick is to have 3 sensors at fixed locations that look for an address in pulses of U/S, then respond with a single pulse at a fixed time in relation to the last received pulse. Your program can measure the time to the response for each sensor and calculate the distance to each based on the return pulse time. The temperature in the room is likely to be fairly uniform, so the ratios of the times should be fairly accurate. You could either have a map showing where the sensors are located or have them each tell your system where they are (after the timing pulse, you could have a small amount of data). You'd need to make several sets of measurements for reliability and either average them or discard the outliers.

sylvie369

Mike Green said...
One thing you could experiment with would be ultrasound, like the PING))), but working it differently. You couldn't use the PING))) itself, but similar sensors. Although the speed of sound is temperature sensitive, it's not likely to change quickly in a typical enclosed room. Even plumes of warm air over radiators and the like are probably stable for times on the order of seconds. The trick is to have 3 sensors at fixed locations that look for an address in pulses of U/S, then respond with a single pulse at a fixed time in relation to the last received pulse. Your program can measure the time to the response for each sensor and calculate the distance to each based on the return pulse time. The temperature in the room is likely to be fairly uniform, so the ratios of the times should be fairly accurate. You could either have a map showing where the sensors are located or have them each tell your system where they are (after the timing pulse, you could have a small amount of data). You'd need to make several sets of measurements for reliability and either average them or discard the outliers.

If the sensors were in fixed, known-in-advance locations, it'd be simpler as you'd avoid having to send that information on the fly. You could just make it part of the data that the·bot already holds.

It sounds like that would work in your situation, right?

I'm talking out of my rear end on this, but it seems like it'd make sense to BOTH average several measures AND discard the outliers (that is, to use a trimmed mean). I imagine that's what Mike meant, but on the other hand, he's probably really done this, while I'm just thinking about it.

J. A. Streich

In general Averaging is bad idea for finding the rough middle, because outliers have great weight on mean. I think the median would be a better representation of the data... Though would require more memory and sorting takes more processor time than average.

Indeed, knowing or even setting the towers at known (and easy to calculate with) positions would be easier than sending them each time.

Now the question becomes does this have advantages over just using GPS? I assumed before looking that GPS for bot would be higher than the GPS kit Parallax sells, and after seeing that it is a lot less than I thought I am considering just going with GPS. Is it worth it to develop a local and smaller solution for more money for increased resolution...

Franklin

I saw (and don't ask me where) a project using both rf and ultrasound to locate bots in formation. The slave bots had three US receivers and a central rf receiver. When the master sent out both an RF and US pulse the slave got the rf and started a timer to record the three us receivers input then used the delay to compute the distance and direction to the master.

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

sylvie369

GameMaster said...
In general Averaging is bad idea for finding the rough middle, because outliers have great weight on mean. I think the median would be a better representation of the data... Though would require more memory and sorting takes more processor time than average.

Indeed, knowing or even setting the towers at known (and easy to calculate with) positions would be easier than sending them each time.

Now the question becomes does this have advantages over just using GPS? I assumed before looking that GPS for bot would be higher than the GPS kit Parallax sells, and after seeing that it is a lot less than I thought I am considering just going with GPS. Is it worth it to develop a local and smaller solution for more money for increased resolution...

I assume he's looking for a way to do this indoors. Unless my understanding of GPS is WAY off, GPS won't work unless you've got a clear view of the sky.

The median vs. trimmed mean question is probably one that could be answered empirically, though of course the criteria for "trimming" will make a huge difference, as will the distribution of the incoming data.

J. A. Streich

said...
I assume he's looking for a way to do this indoors.

He is me, and yes I was looking for a way indoors or out...

said...
Unless my understanding of GPS is WAY off, GPS won't work unless you've got a clear view of the sky.

A limitation I was unaware of, and a limitation that is disappearing in GPS in general, but Parallax's module doesn't support it yet...
http://www.theinquirer.net/en/inquirer/news/2003/09/12/you-can-receive-gps-indoors

said...
The median vs. trimmed mean question is probably one that could be answered empirically, though of course the criteria for 'trimming' will make a huge difference, as will the distribution of the incoming data.

I'll have to play with it... Looks like I will still need to create the stations... RF and Ultra Sonic doesn't sound like a bad idea.

The other idea I've had is IR tags similar to those used in Mediated Reality systems like MIT's MIThril.
http://www.cc.gatech.edu/~thad/p/journal/augmented-reality-through-wearable-computing.pdf

Post Edited (GameMaster) : 12/17/2007 2:49:49 AM GMT