Intro | Build it! | Command reference | How it works | Download | Customize | Todo | phpBB forum
Other projects: GPS Finder | One-LED clock for people with limited vision | GPS speedometer with setpoint and relay output

The Finder

Have you ever wished your keychain knew where your car was?

Finder photo Finder schematic

The Finder is a prototype of that device. It is a keychain-sized GPS device with two buttons, Save and Find. Pressing Save records your current location. Pressing Find visually leads you back to the saved location. Up to 9 locations can be saved.

Press the Save button, and the device displays S-1. Pressing Save again steps through the slots up to 9. Pressing Find, while S-# is displayed, saves the current location into the chosen slot. The display blinks slowly until the location is found, then strobes quickly and goes blank, indicating the location is saved. Pressing any button will stop the process and turn the device off.

Press the Find button, and the device displays F-1. Pressing Find again steps through the slots up to 9. Pressing Save, while F-# is displayed, navigates you to the chosen location. The display blinks while the GPS finds its position, and then changes to a three-digit distance, in yards or meters (meters constant to be added.) Start walking forward when the distance appears. One segment of the display will blink, indicating the direction to go. If the top segment of the middle digit blinks, go straight ahead. If segments to the left of center blink, turn left. If segments to the right of center blink, turn right. If one of the bottom segments blinks, turn around. Try to keep the top middle segment blinking. The distance will count down as you approach your destination. When you are done, press either button to turn the device off.

The Finder requires an ATMEGA88 or larger, a three-digit, common cathode LED display (Mouser BC56-11EWA or BC56-12GWA), an AARLOGIC GPS 3A or similar GPS module, and a 3.6 volt battery. A cell phone battery (3.7V) or three NiMH cells will work. If you use three Alkaline cells, use a series diode to reduce the voltage by 0.7 volts. Other parts required are four transistors, twelve resistors, a capacitor, and two buttons. The program is about 3500 bytes long.

The prototype shown above has all the parts mounted on the back of the display, and sealed with a glue gun. The flying wires could easily be eliminated. I used thick film resistor packs instead of individual resistors, and wired everything together with 30-gauge rework wire.

Other things you should know: If you leave the device in F or S mode without selecting a location, it will turn itself off. If you try to Find a location and get ---, that location has not been saved. Locations are stored in EEPROM on 24-byte boundaries. If the distance is more than 1000 yards/meters, the decimal points indicate the 1000s in binary. If the rightmost decimal is lit and the display says 430, the real distance is 1430. If the leftmost and center decimal are lit, the distance is 6430.

How it works: The Finder uses the Great Circle navigation algorithm explained in this Circuit Cellar article Stefan123.pdf by Jeff Stefan. The algorithm takes the From and To LAT/LON pairs, does some arithmetic and trigonometry, and computes a distance and course which are the shortest path on the surface of a sphere. It then subtracts the current course, indicated by the GPS module, from the computed course, and displays the relative course, which is the direction you should walk.

The program uses 64-bit, two's complement arithmetic. For most of the radians calculations, the first byte is integer and the rest fractional, so divide the binary integer by 2^56 to get the decimal number. The Great Circle algorithm requires precision COS and ARCCOS functions. The COS function is a polynomial approximation. The ARCCOS functions I looked at were very complex: one required two polynomials, a square root, and a division. Therefore, my ARCCOS uses Newton's method to invert the COS function. That is compact but relatively slow, and the algorithm requires about 1.3 million machine cycles to compute a great circle. The GPS provides one fix per second, and the CPU runs at 8 MHz, so this is not optimal but is plenty fast enough for this project.

There is a test program to check out the navigation program. To use it, enable SERIAL_DEBUG in the code, assemble it, and load it into a microcontroller. Connect the MCU's TXD and RXD lines to a PC using either a CMOS-level USB to serial converter, or a MAX3232 chip. The test program on the PC drives the microcontroller through a serial port, and checks its output.

You will need the serial comm drivers from www.rxtx.org and a Java development kit. Compile and run TestNav.java using the command line at the top of the source file. The parameters are port number, baud rate (9600), and number of iterations. Each iteration tests one distant pair (random points on the planet) and one near pair (a random point and a random small offset.) The navigation accuracy is good at larger distances, but the directional accuracy decays somewhat within a hundred yards. This is not unique to the Finder; I ran the equations on an HP48GX and got results that differed from both the Finder and the Java math libraries. It is just difficult to get accurate results with tiny angles.

The Finder code has potential uses besides a handheld navigator; for example, the directional output could steer a small autonomous vehicle.

Source code v0.1 for the ATMEGA88.
Clear the CKDIV8 fuse, so the MCU runs at 8 MHz.
Please post on the forum if you are building a Finder.