What can I use to detect pinpoint location (inches) outdoors?

Question

I am getting back in to EE after some time so please excuse my ignorance. I am looking for a way to detect pinpoint location outdoors to navigate a robot for a project with my sons.
Is there a low cost way to triangulate or use GPS? I am looking for down to the inch precision. Also I do not care if I need to place some transmitters in different locations to give the device a reference.

This is for a robotic lawnmower. I have a 2 acre yard and my house is near the middle with several trees as obstacles.

Two of my three boys (14yrs, 11yrs, 5rys old) brought up the idea so the real goal of this project is to spend time with them and pique their interest in EE & CE.

With that said cost is a factor but I do not care if we work on it for the next 2 years and spend a little along and along.

Here are my current plans

• Include a Windows PC on board so I can code against the sensors.
• Microsoft Connect on board to help with obstacle detection (reason for Windows PC)
• Include a USB GPS for general location
• Include camera just for the fun of it

In 2 years if I have some money in it that is okay but I do not want to start with a crazy expensive GPS.

Thanks to everyone who has help me!!!!

Answer 1

You should consider flipping the system around. There is no need for the robot itself to determine the location. It only needs to know what to do. This can be communicated to it from a fixed PC via a WiFi link. With such a link it doesn't matter whether the robot figures out the location or whether that is done in the fixed installation and then the result transmitted to the robot. If the robot ever looses the WiFi connection, it could simply stop. That keeps it from getting out of range and therefore not getting the information that it should turn around, meanwhile mowing down all the flower gardens in the neighborhood. I think it's also a good idea to keep the robot as simple as possible and put as much of the burden onto the fixed installation where it's easier to monitor, fix, and work with.

I haven't actually done this, but here is something I came up with while musing about your problem. Have a rotating IR emitter on the robot. This might rotate once a second or so. It shoots out a fairly narrow vertical slit of modulated IR. Then you put fixed IR sensors around the place, mostly the periphery. These indicate when they sense the beam from the robot, which will only be for a small fraction of the repetition interval. By comparing the timing of the signals from the various sensors and knowing their locations, you should be able to compute the robot's position. The time offset from any two sensors divided by the beacon period tells you the relative angles of those two sensors as seen from the robot. With enough sensors and a bunch of math (easily done on any modern PC in a tiny fraction of a second), you can solve for the absolute position of the robot. The PC then sends appropriate commands to the robot over a TCP connection via the WiFi link.

The robot doesn't actually need the position information. All the "thinking" gets done on the fixed PC. All the robot needs is a small embedded system with a WiFI module and TCP/IP stack. You can send basic commands to the robot, like relative direction, speed, etc.

The data from any two sensors puts the robot on a arc that also includes the two sensors. The exact arc depends on the angle offset of the two sensors. In theory all you need is three arcs, which means three sensors. I would use several more so that individual sensors can drop out temporarily for various reasons. That will overconstrain the problem, but with the right algorithm you can make use of all this data and find the most likely location of the robot.

As I said, I haven't tried this, but I think you should be able to get accuracy good enough to control a lawn mower. At least this scheme doesn't rely on anything particularly expensive, hard to get, or anything pushing what you can measure reasonably in your own back yard (no nanosecond timing, for example).

Answer 2

Previous answers tackle the problem from the point of view of how the lawnmower can detect its position. However the sensor(s) could be external, i.e. on the house. Place cameras so that they can see the lawnmower anywhere on your yard. Put a symbol or a flag or something colorful on the lawnmower and some reference points (or use infrared reflectors or leds, this way you can install notch filter lenses on the cameras and only let ir in, trivializing the tracking code). Since the cameras are fixed, the location of the reference points and the lawnmower within the video frames should provide unambiguous localization data. Precision will depend on camera resolution. This way you don't have to spend as much on the on board electronics, and your image processing code can run 'from home'.

Answer 3

I can think of a couple of ways that this might be achieved depending on the range that you want to robot to move around in (meters, or 100s of meters?)

However, GPS is definitely not going to give you the inch level of precision with easily available hardware. To achieve that precision you will need to perform carrier phase differential correction. While this isn't too tricky, it isn't as simple as plugging in a module. You can look at this project to see an implementation of it.

An easier approach may to be use either IR or ultrasonic beacons and use sensors on the robot to determine the relative range between it and the various beacons. A servo mounted receiver can isolate angle to the transmitter and relative signal strength. Unfortunately you're not likely to get the inch level of precision this way.

Answer 4

Another option is to use a webcam and some well-known shapes/colors, and run simple image recognition. Use triangulation (perhaps rotating the web cam with a stepper motor) to figure out where you're at. This is doable if you have significant CPU oomph on board (e g, a BeagleBone or netbook) rather than something small like an Arduino.

Answer 5

I would look a different route from all these other answers. Bury a wire in your yard around the perimeter. Drive it with a little circuit that outputs a 100kHz (or something) signal. That would be very easy to detect with a mobile platform. It's the exact same technique used by those fenceless systems used to keep dogs in the yard. Hell, you could probably grab one of the units to use as the sensor.

That would give you the perimeter control. If you sense the 100kHz signal, you're at the edge. Of course test this without a mower first (perhaps your first design should be an R/C car modified to do this. I'd also ditch the Windows PC and grab an Arduino system. They're cheap and for an initial investment of a few hundred dollars and an R/C car, you've got your prototype.

As a parent I'm pretty sure you want to make this as safe as possible. This would mean NOT strapping a bunch of electronics to your trusty two-stroke. See if you can find an old copy of Radio-Electronics magazine from the 80s. They had a robotic mower design there called the Lawn Ranger. Of course you wouldn't recreate their original design but they had several novel innovations, including an easy-to-build sensor for detecting cut grass (obstacle avoidance, perimeter detection and navigation) and, more importantly, they had a unique design for the cutting blades which was significantly safer than a pound of sharpened, hardened steel being swung round. Their cutting system was essentially a pair of swinging discs with x-acto blades fastened to them. The discs would pivot, which meant if a rock (or foot!) got in the way it'd give, resulting in a less disastrous injury. I highly recommend checking out that series of articles and applying some of the principles to your modern design. You may be able to get them from your public library; I know mine had them.

Good luck, this sounds like a great project that will keep the young'uns interested and thinking.

Answer 6

I wonder if it would be possible to use the GPS with gyros for stable position tracking. One could apply fuzzy logic learning methods if one knew how and had stable position error signals (PES) from both sources. GPS for large scale position sensing +/- 10m and Gyro's or some other means for short range position tracking +/- 0.1m

Plan 1) Measure the GPS path tracking data for each child mowing the lawn using a Zigbee radio or onboard data collection system. Later analyze the stability, pattern, speed, effectiveness on a path analysis program that aggregates distance, analyzes slope jitter, overlap or effective number of tracks X & Y.

2) THen choose optimum path and memorize it. (cookie crumb) for recording various paths used by each child and evaluating the recorded path for path performance and safety.

3)Measure various path PES by mowing using orthogonal vectors, oblique vectors , circular tracks and determine effective tracking error for each vehicle guidance method and comment on aesthetic variances of cut lawn produced.

Just use recorded position signals accumulated for analysis then later attempt robotic tracking with 4 channel Servo controlled system. (Gas, steering, brake and other. )

The biggest lesson is learning how to communicate ( with kids, clients and engineers) LEarning how to write a spec before designing it, is the biggest lesson. What inputs, processes and outputs, environmental inputs and testable / measureable parameters with acceptance and rejection criteria. There should also be suitable rewards for each milestone and consequences for failure.

This is a thumbnail of the Project Plan, Design Spec & the DVT plan. ( Design validation test)

Your success depends on it. Good luck and have fun.

Answer 7

While this is only a starting point, I'd highly recommend you look at this PDF explaining the theory behind John Swindle's audio localizer. As I recall, it explains different methods of localization, and explains John's method, which is accurate to within half an inch! (The setup is non-trivial and code is not provided, but it is used to good effect for the DPRG's (Dallas Personal Robotics Group) RoboColumbus event).

Answer 8

https://electronics.stackexchange.com/a/23506/5439

See my answer to another question about LPS. Short answer is that this is a pretty tough problem and existing systems are quite expensive (starting at several thousand dollars). The suggestion of using ultrasonic sensors is a good one, if you Google you can find prior art on using ultrasound and even audible sound for this.

Answer 9

Currently udacity is offering a free, on-line, course Programming a Robotic Car which teaches you how Google does it for their self-driving cars. Basically they use GPS for gross positioning along with stored maps and vision sensing for localization to a high degree of accuracy. The software uses particle filters.

You could do it with GPS alone if you used the very expensive differential GPS equipment used by surveyors, but that would hardly be cost effective. As you suggest, if you use a couple of low cost (Xbee perhaps?) transceivers you could easily measure distance with an extremely high degree of accuracy by transmitting a pulse and measuring the time it takes to travel from the transmitter on the robot to the remote repeater and back. This is like RADAR except that instead of bouncing the signal off a passive surface it is being sent back by your stationary transponders.

EDIT: Since I got called out by Kevin on this one, perhaps I better explain ;-) (All in good fun, I have the highest respect for Kevin and he is is quite correct that I did not provide sufficient details to show how to implement this).

To measure the propagation delay between two points accurately requires primarily two things: 1) A straight line signal path since reflections will create distortions. 2) Some electronics on both ends using synchronized clocks and the ability to measure time intervals to the precision required.

Synchronized clocks are relatively easy as the receiving station can derive it's clock from the signal being transmitted by the other station. This is standard synchronous data transmission with clock recovery.

Here is a paper Measuring propagation delay over a 1.25 Gbps bidirectional data link where they easily get this kind of accuracy over a 10 km long piece of fiber optics. They state: "It should be able to synchronize ~1000 nodes with subnanosecond accuracy over lengths of up to 10 km."

In this note a method is described to determine the time offset between two nodes. These nodes are connected via an 8B/10B coded 1.25 Gbps bidirectional serial point to point communication channel, as for example is used by 1000BASE-X (Gigabit Ethernet). The time offset is determined by measuring propagation delay using a marker signal. The signal is sent from a master to a slave node and back using serializer/deserializer (SerDes) functionality in (Virtex-5) FPGAs. The recovered clock at the slave node is used as the transmit clock of the slave so the complete system is synchronous. For a 1.25 Gbps serial communication channel the delay is known with a resolution of a single unit interval (i.e. 800 ps). This resolution can be further enhanced by measuring the phase relation between the transmit and receive clock of the master node. The technique has been demonstrated to work over a single 10 km fibre that is used at two wavelengths, to facilitate a bidirectional point to point connection between master and slave node.

also

A first test setup was built to verify the principle of measuring propagation delay between a transmitter and a receiver using a coded serial communication channel operated at 3.125 Gbps. The transmitter and receiver reside in FPGAs on two separate development boards. This first test setup showed that it is feasible to measure propagation delay over a 100 km fibre with a resolution of one unit interval (i.e. 320 ps at 3.125 Gbps).

EQUIPMENT USED:

The test setup consists of two ML507 Xilinx development boards [7]. A Virtex-5 FPGA is mounted on each board. One ML507 development board is designated as master node, the other as slave node. Master and slave are connected via small form factor pluggable (SFP) transceivers and 10 km of fibre, creating a bidirectional link. A single fibre is used that is operated at dual wavelength.

Now clearly this particular setup is overkill for most hobby robotics projects, but it could easily be reproduced at home since it uses off the shelf development boards and requires no special talents to get working. In the case of the robot the link would be radio rather than a fiber optic cable. Perhaps it could even be an IR link like a TV remote although I suspect that outside in bright sunshine that might be problematic. At night it could work great!

Answer 10

Like others have said, localization is a hard problem and one-inch resolution at reasonable cost is very difficult. You might be interested to know that there is a college-level competition involving robotic lawnmowers: the ION Robotic Lawn Mower Competition. I was part of a team preparing for ION; in the end, we didn't compete, but we certainly spent a lot of time thinking about the problem, which is definitely harder than it seems. Note that most of the competitors at the last ION competition mowed less than 50% of the field in the allotted amount of time, with platforms costing tens of thousands of dollars! You have an advantage, though, because ION disallows external navigation aids, such as beacons, that make the problem a lot easier to solve. (And you have no time limit.) Looking through the teams' project reports would be a good source of ideas.

If I were embarking on a robotic lawnmower project like yours, I would probably use a combination of cheap GPS (for rough location), IR/ultrasonic/multicolor beacons (fine(r) location), encoders (position estimation), and computer vision (various). I wouldn't advise spending thousands of dollars on fancy GPS and IMU systems. The Kinect is a good idea, and is certainly a lot cheaper than Lidar; you'll definitely have a lot to chew on between the depth map and the camera.

I also recommend the Udacity course on programming self-driving cars for an introduction to the concepts involved.

Answer 11

Now that you have modified the question to remove the requirement of one inch resolution and have told us you will have a Windows PC and a Microsoft Connect onboard, I think you could do very good location with just that hardware on the robot.

Have you seen some of the cheap Golf Scopes that people use to find the distance to the tee?

The way they work is to measure the perceived height of the flag on the green (which is a fixed height) and show the distance to the tee. This is a simple right triangle where if you know the angle and the height of the far side you can compute the length of the base. This is exactly the kind of thing your sons will be learning in geometry and later in trigonometry.

Since your house seems to be visible from all parts of your lot, perhaps it would be easy to see 2 corners and compute distance?

Answer 12

Use the sound energy of the mower itself. It's its own pinger. Or maybe its noise can be used to mostly mask an audio chirp pinger added to the mower, maybe synchronized to the crankshaft or blade. Put a mic on the mower and at a few locations around the yard. Get a rough estimate of location based on loudness. The nearest mics won't have as much multipath problems. Then cross-correlate the audio from the nearest mics to estimate the time-of-flight sound delay. Average or Kalman filter to get rid of noise in the delay estimates, and apply trig. If you can hide (from humans) and detect (by cross correlation) a chirp or engine vibration on the mower, you might be able to get inches of accuracy.

Answer 13

Check out http://porcupineelectronics.com/uploads/LR3_Data_Sheet.pdf This little LR3 adapter (it's obsolete but a better one is on the way) allows you to interface a PC or a SBC to a Fluke 411D distance meter, accuracy to +/- 3 mm out to 30 M as I recall. The new unit coming out (LR4) works with newer Fluke meters. Combined with a camera on a pan/tilt platform so you can point it to known targets and a high resolution encoder on the pan servo for high precision angle measurements you should be able to triangulate your robot's position relative to a map of your yard with the accuracy you need. You will need some trigonometry in the code (above my high school math). I found the requisite equation on the internet (Wikipedia). I would include it here but am away from my home machine where the information is stored. The system can also facilitate generating the map. You may need a gyro stabilized platform with passive vibration isolation (lawn mowers have a lot of vibration). For measurements on the fly you may need tracking software to keep the laser on target as well. Accurate odometery will give you more time between "fixes" if your computational power is modest.