# High precision trilateration in a small space and without ultrasound

I need my robot to be able to find its position in a room with ±10cm accuracy. For that I have decided to place two radios right at where the door is and the third radio on the robot. The room is small, about 8x4 meters, and as I understand, on small distances the delay between radio signals, which is used for calculating our position using trilateration, would be very small. Signals from one radio will be received by another so fast, that Raspberry PI wouldn't be able to measure the delay accurate enough with its system clock to calculate an accurate position.

Can someone suggest how can I measure the position more accurately with the same set up -- two radios at the door and one on the robot and using trilateration. Maybe using some specific radios, or using something else instead of the Raspberry PI, or covering radios with something to slow down the signals, or something else.

Note: can't use ultrasound.

• Obviously, you're going to have to tell us the level of precision you're looking for. Also, have you considered optical methods (visible or IR)? The RaspberryPi has enough horsepower to do a significant amount of image processing, and there are many ways to use this to do navigation. – Dave Tweed Sep 20 '14 at 18:09
• So essentially you want to build a private GPS? It would be very difficult, if not impossible. – venny Sep 20 '14 at 18:09
• @venny and no attempt = certainty of never doing it, the best way to learn is to try and fail. – placeholder Sep 20 '14 at 18:13
• @DaveTweed I'm considering using image processing, but would like to think of something that could also work in dark. – Explosive Food Sep 21 '14 at 4:03

There is a lot of information that is lacking, so we'll have to make a few assumptions:

1. That the room is not reflective to the frequencies that you're using, it would be best that it be absorptive.
2. That system be as simple as possible
3. Update is on the order of a few 10's of Hz.
4. there is power limitations in the amount of energy you can broadcast.

You want avoid doing much in the way of direct mixing and phase detection, but you could use interference quite easily. I lifted this picture from (physicsclassroom) which is all you really need to understand the idea.

There are various schemes that you could do, but here is one that will probably work:

Drive both doorway antennas from the same source, which has steady state carriers at 3 (or more ) fixed frequencies that are mixed together and driven to the antennae. Each of these frequencies being at a different wavelength will create different nodal patterns within the room. And because they exist simultaneously, they will lie over top of each other.

On the receiver side you need the matching number of receivers for each of the transmitted frequencies that return the envelope or strength of each frequency. But this can come from one antennae and once down mixed should be a close to DC term, so easily read by a Arduino or that ilk.

There many variants that can played around with. Changing the phase of the transmitted frequencies from one antennae to the other. You'll notice that the pattern below is symmetrical, so you won't be able to determine left from right, changing the phase will fix that, and that needs to only happen on one frequency, as a guess.

There will be a general trend of decreasing power, so distance away from door can be roughly determined, but that is sufficient to reduce the solution domain of searching on board the robot to a smaller area.

You can do dead reckoning, meaning you track your position from the door way and then use that to predict outwards what the radio patterns will be in the adjacent neighbourhood. If you keep it active then you won't have the left/right symmetry problem stated above.

Other ideas: - chirping the transmitter waveform might be another way of having a dynamically changing pattern.

Caveats: - reflective walls will cause all sorts of other bounces. This complicates the computation and may render it impossible. But a pre-mapping may be the solution there.

• Also look up Lorentz beams from WWII – placeholder Sep 21 '14 at 16:07

Basically your robot needs to sense how far away it is from a number of "somethings". At the moment those somethings are two radios relatively close together, and yes telling them apart will be quite difficult.

So there is two basic strategies here. You can either use the whole room as the "somethings", or you can add another radio and spread them apart more.

For the first, ultrasonic range finders (aka Ping))) sensors in Arduino parlance) can be used to work out the distance from the four walls. You don't really care about the exact distance if you have 4 readings (left / right + front / back) since the ratio of left/right gives you your position across the room, and the ratio of front/back gives you your distance along the room. Of course, this depends on your robot (or ultrasonic sensors) remaining in the right orientation.

My thinking (correct me if I'm wrong) with the second option is to have at least 3 radios all transmitting on different frequencies positioned at strategic locations around the edge of the room - maybe 2 corners and a mid point of 1 wall opposite those corners to form a triangle. The important thing is that they surround the robot. Then you work out how far from each you are. You don't care about what they're transmitting, nor how long the signal takes to get to the robot. All you care about is the signal strength. If all three radios are transmitting at the same strength then the relative difference in strength between the three signals can give you your position in 2D space. Some fine tuning in the signal power so there's an easily measurable difference across the full range of the room may be in order.

• The only issue is that I'm not allowed to use ultrasonic and I can't place radios around the room -- only at the door. – Explosive Food Sep 21 '14 at 4:04
• This sounds like a homework question then - you have been handed a set of unreasonable random specifications that make no sense ;) – Majenko Sep 21 '14 at 9:50

It takes approximately $8m/3\cdot10^8ms^{-1} = 2.7\cdot10^-8s$ for electromagnetic radiation (EMR) to traverse 8m.

Hence $2.7\cdot10^-10s$, 270ps, or 3.7GHz for 1% resolution.

"covering radios with something to slow down the signals":
To transform 3.7GHz below the Nyquest-Shannon sampling theorem limit for a Raspberry-Pi, running at 700MHz, EMR would need to be slowed by a factor of roughly 10x.

I haven't found the numbers but, EMR isn't going to be slowed significantly more than a few 10's of percent by filling the room with a non-toxic material and with a fluidity sufficiently high for the robot to move. That approach isn't going to help.

Sound, by comparison travels at $340ms^{-1}$, i.e. $10^6, \text{ or } 1,000,000$ times slower.

So, by comparison sound takes $2.4\cdot10^{-2}s$, or 24 milliseconds, to cross the room, and hence $2.4\cdot10^{-4}s$ or 0.24 milliseconds, a wavelength of roughly 4kHz, for 1% resolution.

Ultrasound at 40kHzhas a wavelength of roughly 8.5mm, which should be good enough for reasonable resolution and accuracy.

• Thanks for the thoughtful answer, numbers really do help! I'm considering using BeagleBone Black (1000MHz) instead of Raspberry Pi (700MHz), but it doesn't look like it would help much in this case, the difference is still too big. – Explosive Food Sep 21 '14 at 3:57
• Also, I'm not allowed to use ultrasound. Let's forget the radios then, is there anything else I could do with placing things at the door? For example, I could place some image on the door and do image processing with a camera on the robot to determine how far from the door the robot is and robot's position. Can't think of any other way of robot determining its position without ultrasound. – Explosive Food Sep 21 '14 at 3:57
• @ExplosiveFood - To help people, please add the 'no ultrasound' constraint to your question. What resolution and accuracy do you need? Can you use audible sound? Have you, or have you access to, expertise and test equipment sufficient to solve the problem in the radio frequency domain? – gbulmer Sep 21 '14 at 11:26
• Accuracy of $\pm$10cm should be good enough. Can't use audible sound. As far as the expertise -- I'm more a computer science guy, so it's a bit new to me. Getting test equipment shouldn't be an issue as long as it would theoretically solve my problem of locating the robot. – Explosive Food Sep 21 '14 at 15:09
• @ExplosiveFood - Please add the ±10cm accuracy statement to your question. What update rate? As soon as you work in the Radio domain, rather than digital, it becomes much easier. There are vision-based solutions which would work to ±10cm in an 8m room. – gbulmer Sep 21 '14 at 18:50

Ultrasonic rangefinders, similar to those that were used in Polaroid cameras, could do the job. They have the range and are capable of accuracies on the order of one inch or maybe even better.

• Sadly, not allowed to use ultrasonic. – Explosive Food Sep 21 '14 at 3:59