Local Positioning System

Philldapill

I'm not sure if this has been done before, but it probably has. Regardless I want to re-invent the wheel.

A topic about Chip's walnut farm got me thinking about how to get a harvesting robot to know it's exact position. There were many idea's about how to do this, but I had one about using beacons set up around the robot that would act as repeaters. Basically, you would have at least 3 beacons set 100 feet or so around the robot. The robot would "ping" a beacon, and the beacon would respond with it's own signal. The distance measuring would come in by the robot measuring the time it takes for the signal from the beacon to be recieved. It would then use this time measurement and calculate the distance based on the speed of light.

Having fast enough electronics(propeller maybe???)·may be another issue but I may have stumbled into an obstacle. I know from optics that the whole reason your leg looks broken when you step into a pool is because of the different speeds that light travels through different materials. "c" is the speed of light in a vacuum, but the speed will always be slower when going through any other matter, even air. This also applies to longer wavelengths of EM such as radio waves.

I believe the problem with this method would be that the time it takes for the signal to "bounce" back wouldn't always translate into a nice uniform measurement. Not to mention the decreased signal strength, but as the signal goes through something like a wall or a tree or whatever, it will take longer for the signal to reach the robot, thus making it seem that the beacon is further away. Granted, when you are talking about a measurement of over 100 feet, the extra time it takes for the signal to pass through a wall is very small, but in some scenarios, this could add up quickly(in a building).

Basically, the whole point to these time measurements is to figure the distance to each beacon, and then calculating position based on triangulation of these beacons. I would be absolutely amazed if the prop could handle something like this. I know the calculation's could be done, but I'm not too sure about the speed of light issue... What do you guys think?

Philldapill

oh, btw, just so you don't have to do the calculation yourself, it takes about 3.33ns for EM waves to travel 1 meter. I'd love to have resolution of 10cm(333ps), but I can settle for a meter. [noparse]:)[/noparse]

Jonathan

I've been working on and off on a similar system, using ultrasonic beacons. The 'bot can request a ping from any of three beacons using a RF link. I got stalled in the math though, figuring out relative position from the ranges of the beacons was/is harder than I thought. The hardware is all working, I just gotta get me a math guru on the case (Hi Tracy! [noparse]:)[/noparse] ).

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
www.madlabs.info - Home of the Hydrogen Fuel Cell Robot

ElectricAye

I doubt you could get that kind of accuracy (1 meter) using light and the Prop in a straight timing method. But I would be curious to know if you couldn't set up some kind of signal generators whose signals could interfere with each other and thereby create something akin to standing wave patterns that you could make use of. I think such a system was tried out on the V-2 rocket experiments at White Sands back in the late 1940's but I can't remember what it's name was. I'm sure it evolved into something else, but I'd like to know if the same concept could be applied to acoustics. Your Prop would then be measuring and keeping track of the "beats" caused by signals from different beacons interfering constructively and destructively.

Edit: DOVAP was the system used on the V2 rocket.

Post Edited (ElectricAye) : 8/27/2008 10:32:32 PM GMT

VIRAND

This is a metaphor for my single-station local positioning system beacon.

Imagine a light-house that somehow always gets struck by lightning every time it beams north.

You know how far away the light-house is by difference in the arrival times of the lightning and thunder.
You know the rotary angle by the difference in arrival time between the lightning and the rotating beacon.
This "naturally and simply" gives your polar coordinates relative to the light-house.

Now you can use this metaphor to build a station with whatever parts you have that can
substitute well for the signals described in my light-house metaphor.
Notice the radar and sonar like aspects of this intentionally generalized metaphor.
__________________________________________________________________________________________________________________________
This information is intended for public domain share and this disclosure intended as prior art against future patent claims.

KeithE

> figuring out relative position from the ranges of the beacons was/is harder than I thought

Have you thought about iterating? A lot of GPS textbooks talk about finding the intersection of N spheres, but nobody computes a position that way. Instead you start with an intial guess, say the middle of your beacons, and then iteratively compute a solution. There might be some useful information on gps.psas.pdx.edu/

I know a guy that works for Locata on their GPS-like pseudolite based system. Even though it's not directly relevant to a solution realizable on the propeller you might find it interesting to read through the paper that they gave to investors a few years ago. It touches on many competing technologies. e.g. Did you ever hear about the proposal for positioning based on HDTV signals?

www.locatacorp.com/docs/Locata%20Primer%20v1.3,%20public%20rel,%20Feb%2005.pdf

I think that it's been used for things like open pit mining and monitoring the deformation of bridges and dams.

As a side note interest in GPS/Glonass combos is developing for consumer products. $$$ is going into the constellation, and more satellites is a good thing for navigation.

Post Edited (KeithE) : 8/28/2008 5:36:44 AM GMT

Sniper King

i dont think this is as hard as it is being presented. For instance if you have a beacon that acts like a transponder. You could poll that beacon and have it scream out a pulse (Sonic). then measure the time it takes to receive the sound. Do this at a known distance. Then subtact the very small latency that the propeller and glue logic creates and you have the distance. travel times will be linear unless multipath is introduced. Now you need to have multiple beacons that are individually addressable so the unit can "find" it's postion by going though the order of beacons until it starts to hear them.

In fact tell the software you have more than one beacon. Have the software start to poll up to a set max (say 500). If the software reaches 500 then have it display not found. Since the travel times on everything will be so small it could go through the list very quickly.

Once it has at least 3 beacons within a set range, it will continue to poll those until the range reaches max range. Then it should start polling again. This time not starting at beacon 1 but form whatever beacon that was lost. Do this in both directions ie Beacon 19 was used so, poll order would be 20,18,21,17,22,16,etc... This will most likely get you onto the next beacon in range sooner if the placement of beacons is in a logical order.

Here is the positioning math you need...

http://www.restena.lu/convict/Jeunes/beacon/Positioning.htm

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
·- Ouch, thats not suppose to be hot!··


Michael King
Application Engineer
R&D
Digital Technology Group

KeithE

>Here is the positioning math you need...
>
>http://www.restena.lu/convict/Jeunes/beacon/Positioning.htm

You might also see the section "Two of the most important methods of computing GPS receiver position and clock bias are (1) trilateration followed by one dimensional numerical root finding and (2) multidimensional Newton-Raphson calculations. These two methods along with their advantages are discussed" on the following page. And follow some of the links. Newton-Raphson was what I referred to as iterative.

en.wikipedia.org/wiki/GPS#Position_determination

steve_b

How about an RF synchro/resolver gimmicky setup!?

Have 3 RF receiver stations in a triangle pattern. Centered in that triangle you have a reference RF transmitter station.

The reference station sends out its CW or pulse signal and because it's a known distance, the other stations compute for latency or atmospheric conditions (humidity/temp play a role).
Then your little bot has an RF transmitter on it. This would probably have to be a pulsed signal done in such a manner to avoid 2nd trip (multi-path reflections) echo's.
So, now your bot transmits and it's a matter of figuring out the signal reception differences between each of the 3 receivers....just like in a synchro.
So if the top most receiver has the greatest signal and the other two stations have the same amount of signal, it's safe to say that the bot is straight up from that top station.

Of course, this means the stations know where the bot is...not necessarily that the bots knows where it is. So you'd have to get the position to the bot somehow....

Cheers

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
<FONT>Steve



What's the best thing to do in a lightning storm? "take a one iron out the bag and hold it straight up above your head, even God cant hit a one iron!"
Lee Travino after the second time being hit by lightning!

Ken Peterson

If all of your beacons are in light of sight, you could just scan the horizon for them and take note of their angular displacement. Used with a compass, this might also give you a way of determining your position. Each beacon could send a coded signal so you know which beacon sent it. This would be a mechanical solution where your receiver (or optics) would have to be rotated to scan the horizon. The calculations might be a little simpler than the time delay-based approach. Also, since the domain is assumed to be two-dimensional, you would only need to receive two beacons to calculate your position because it's the intersection of two lines on a plane.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
·"I have always wished that my computer would be as easy to use as my telephone.· My wish has come true.· I no longer know how to use my telephone."

- Bjarne Stroustrup