Navigation in the past has primarily relied on the use of a map, compass or other devices that must be interpreted visually. This project demonstrates the ability to navigate a user based on synthesized directional audio which allows the user to move to a known location without the use of a visual aid. The module uses a GPS, a digital compass, and an ATmega32 to generate sound based on the direction that the user must turn in order to face the correct direction.
Sound Byte
The goal of this project was to create a device that allows a user to navigate to a predefined location though the use of auditory guidance.
The module uses GPS and a digital compass to determine at what angle the user hears the sound pulses. On initial startup the user selects from a number of predefined locations through the use of an LCD screen. Once the GPS has a lock, the module determines the bearing (angle from true North) that the user must travel to get to the destination. This angle is compared with the compass output and a sound is made based on which direction the user must turn to face the final location. The sound consists of short pulses that are delayed between the right and left side and modulated in amplitude to give the effect of direction.
One example implementation of this is self guided tours. A user could be guided though a predetermined course by following the sound of a recorded person's voice. In such a setting, if the user were to veer off course, the system would guide then guide the user back on course. Also, the direction of the guide's voice could be used to highlight the object of interest along the tour.
The project idea came after Dr. Land mentioned that you could create the effect of a sound coming from a location by properly spacing the left and right channel by a certain distance. It seemed like a good idea to use this for navigation. This principle is based in the way that humans naturally hear perceive direction. Sound will reach each ear at a slightly different time and volume. Based on those differences, humans are able to determine the direction of sound in the horizontal plane.
Figure 1 shows the high level design of system.
Figure 1: High level system design
The GPS communication uses a standard format (NMEA0283 V 2.2). These standards include GGA, GSV, GSA, and RMC. Of these, RMC (Recommended Minimum Navigation Information) is used in the final product for simplicity. Useful information from this protocol includes time, status, latitude, longitude, speed, and date. The other standards were used for development and debugging.
At this time there is no knowledge of existing patents, copyrights, and or trademarks that are relevant to this project. There are many devices that utilize GPS or a compass, but not together with this synthesized audio.
Having three group members made it nice as there were three distinct portions to the project, GPS, compass, and the synthesized audio. Each portion was developed on its own while keeping the others in mind and brought together at the end. For example, planning for the project included allocating resources between the sub functions including timers, registers, and ports.
Bringing together the three separate parts was tricky because of the timing budget. It was known that the GPS could only refresh at 1 Hz, but the sound and compass must be run much faster. We wanted the sound direction to change smoothly during the course of turning your head (faster than 1 Hz). Therefore, the GPS was allowed to run as fast as it could, depending on how many satellites were locked, and how many sound and compass functions were packed in between. This became tricky when multiple satellites were locked and the data stream from the GPS is continuous. The main structure of the program can be seen in Figure 2.
Figure 2: Software flow chart
The digital compass module used was a Hitachi HM55B from Parallax, mainly because we already had it before the project. The communication between this device was done with three wires (clock, data, and enable) in an SPI like fashion. The communication is based on the Basic Stamp function SHIFTIN/SHIFTOUT which is a two wire communication. The challenge was to implement this in C for the ATmega32. Timer1 was used to control the timing of the function and three GPIOs were used for the three controls. The compare interrupt was used to generate the clock and data as this allowed for the clock time to be set at fine resolution resulting in the fastest possible operation of the compass. The clock signal was generated at twice the data rate so that data could be clocked on both the rising and falling edge of the clock in attempt to keep this function as general as possible in case of future use for other projects. To get data, the ATmega32 pulses the enable bit high for two clock cycles, then sends 0b0000 on the shared data_in and data_out line. After another enable toggle, 0b1000 gets sent to the compass signifying a start measurement command. The ATmega32 then sends 0b1100 and reads in four bits waiting for the data conversion to be done. When the compass sends back 0b1100, the data is ready. The ATmega32 then clocks in 22 bits (11 for x value, and 11 for y value) of 2s complement data MSB first. After properly formatting the data to get the proper sign an atan(x/-y) is called to result in an angle. This is then converted from radian to degrees and compensated for the difference between true and magnetic North (subtracting 12 degrees here in Ithaca). The whole function takes 60mS to run, which was determined to be fast enough.
The PWMs from timers 0 and 2 are used to generate sound pulses. Each timer is set to operate in fast PWM mode with a prescaler of one, giving the PWMs a sample rate of 62500 sample/second. The overflow interrupts of each timer are used to update the OCR.
Initially, timer1 of the Atmega644 was used to generate two PWM waveforms. The idea was that since timer1 has two output compare registers, it should be able to generate two PWMs. Timer1 was able to generate two PWMs, but since OCR1A was used as the top value and the PWM waveforms were not unique, the outputs of OCR1A and OCR1B toggled whenever the overflow interrupt was triggered. Using two timers prevented the overflow interrupt from toggling both pulses and also allowed for one timer to be used as a time based when an interrupt was triggered.
The code used for direct digital synthesis was adopted from lab2 written by Dr. Land4. The DDS process consists of a sin function quantized into a 256 entry table and a ramp table to linearly increase or decrease wave amplitude. For this project, two more tables were used to represent the phase offset and amplitude of the wave at a given source degree. These tables are precomputed to prevent extra computation during execution.
The premise of delaying sounds arriving at each ear to simulate sound localization is based upon interaural time difference. By delaying the sound arriving at one ear by up to 660 microseconds, the sound will have the appearance of coming from the side of the leading sound pulse.5 For example, if the channel going to the left ear is delayed, then the listener will interpret the delay as a sound source that is closer to the person's right ear.
The phase offset table is used to represent the delay that is present at each degree. It was constructed to achieve no offset at a zero degree heading (the source is directly in front of the user) and maximum offset at 90 or 270 degrees. If the sound source is behind the user, then the channel of the ear furthest from the source will be fully delayed, encouraging the user to turn his or her head to better discriminate the location of the sound.
To make the sound direction more apparent, the amplitude of the delayed channel is also reduced. The sound is scaled according to a normal distribution so that full intensity is delivered when the user faces the source with a zero degree difference. As the user rotates away from the source direction, the amplitude of the PWM wave channel furthest from the source is reduced while the closer channel maintains full intensity.
We used interrupt driven serial communication over the USART to receive data from the GPS. The GPS outputs NMEA sentences approximately once a second at 4800 baud. An example of one packet of NMEA sentences is shown below.
$GPGGA,144739,4251.9960,N,07806.0827,W,1,04,5.6,1898.0,M,34.5,M,,*61
$GPRMC,144739,A,4251.9960,N,07806.0827,W,1908.5,270.0,050510,5,E,A*2F
$GPGSV,8,1,32,01,12,205,-18,02,43,251,14,03,08,022,-22,04,05,271,00*75
$GPGSV,8,2,32,05,78,032,45,06,83,236,48,07,81,084,47,08,64,206,33*71
$GPGSV,8,3,32,09,90,086,52,10,42,202,13,11,26,284,-4,12,88,117,51*6C
$GPGSV,8,4,32,13,90,027,52,14,68,030,37,15,78,143,44,16,60,220,30*7E
There are several cases of redundant data between NMEA sentences and, for the purposes of this project; we only need one set of longitude and latitude. We decided to only read in the RMC (Recommended Minimum Content) sentence as a string and then extract the longitude and latitude from that string.
We use the USART character-ready interrupt which triggers as soon as a full character is received by the USART buffer. Once a character is ready in the USART buffer, the ISR writes the character to a string buffer and enters the state machine. The state machine successively checks for the characters that are expected to be seen at the beginning of the RMC sentence. If the program does not receive the expected header characters, it returns to the beginning of the state machine. If the input characters are ‘$’,’G’,’P’,’R’,’M’, and ’C’ in succession, program records the rest of the sentence as data. The sentence is terminated with the ‘\n’ character.
The data from the RMC sentence is written to a string buffer. Knowing the format of the RMC sentence, we use sscanf to extract the longitude and latitude. The longitude and latitude are sent in the format DDMM.MMMM where DD is in degrees and MM.MMMM is in seconds. We parse the data and recalculate the values in terms of degrees. It should also be noted that when writing to the string buffer, we ignored decimal points due to difficulties with sscanf reading in floating point numbers on the microcontroller. In order to compensate for this, we scaled the longitude and latitudes appropriately during the conversion into degrees and then radians.
We use the following equation to calculate the direction from the user’s current location to the final destination:
atan2(sin(dlon)*cos(lat2), (cos(lat1)*sin(lat2))-(sin(lat1)*cos(lat2)*cos(dlon)));6
where lat1=current latitude, lat2=target latitude, and dlon=difference in current and target longitude.
System Integration/Timing
In order for the interrupts to run at their desired speeds, we found that it was necessary that they not run at the same time. For this reason, we timed our system to first receive data from the GPS, and then run the compass data retrieval function and sound output as many times as possible before the next packet from the GPS.
We start the timing on the first packet received from the GPS and let the USART interrupt run until the entire RMC sentence is received. Once the RMC sentence is received, we turn off the USART interrupt in order to not interrupt on all of the characters of the other NMEA sentences. We then enable the interrupts for the compass function which takes approximately 60ms. As soon as the compass function ends, the sound function and its interrupts are run. The sound function will vary in length
based on its output, but it should never take more the 150ms. We then repeat the compass and sound functions again before turning the USART interrupt on, which will wait for the next RMC sentence. Running the compass and sound functions twice leaves enough time for the USART to be enabled before the next RMC sentence arrives.
The supporting hardware consisted of two active low pass filters used to buffer the audio. The wire routing was kept as compact as possible meaning that data lines ran close to the audio introducing a lot of noise. Using a custom PCB could remedy the problem, but was out of the scope of this project. A potentiometer was used on each channel to adjust the volume allowing ensuring equal volumes when pointing at the destination. Also, an LCD screen was used to select the initial destination. This was done with three buttons, screen up, screen down, and select. These were implemented active low with a 10k ohm pull up resistor and a 330 ohm resistor current protection.
It was found that overall the device worked as expected as multiple users were able to direct themselves to a location that they were unaware of. The rate at which the GPS acquires data is at best once a second and depends on the number of satellites locked. The sound and compass update twice a second. This is a little slower than desired, but is limited by the speed of the GPS and the computations of the bearing value. Three sound pulses might be possible if the math for the GPS (shown above) is changed from floating point to fixed point. A picture of the final device can be seen in Figure 3. LCD screen is located on the top of the device. This means that the user must take the device off to change location. This is acceptable as a compact unit was part of the project description.
Figure 3: Final Device
The accuracy of the device was found to be subjective to the user and their ability to recognize small differences in the sound pulses. However, it was found that in general the average user was able to resolve a direction to within +/- 10 degrees. The locations for the different data points were initially found with the use of a Motorola Droid and its internal GPS. This was found to be very accurate and provided a location to within a 3 meter radius.
Safety was not a big concern throughout the project, other than being alert and keeping your eyes open when navigating to the final destination. The project did not interface with other projects in a negative way, other than the occasional noise made while testing. The final project is a self contained unit that does not interfere with anything else.
This device could be used to solve a number of issues. As mentioned before, one could be used for self guided tours. Also, a boat operator might find it useful when navigating a boat at night time for far distance navigation. It can be understood that this would be useful for anyone needing navigation while not being able to look at a map. This could be useful for orienteering as you would not need to look at a map but could focus on the environment around you
Our initial goal was to guide a person by sound using data gathered from a GPS module. Before we started our project we acknowledged that the GPS module would have some uncertainty and there would be difficulty determining if the person was directly over the target location. Given the budget of this project we decided to sacrifice GPS accuracy in favor of staying within budget.
Our final prototype not only stayed within budget, but the GPS module performed to our expectations and the directional sound was sufficiently accurate. During the demo for this project, the professor, Dr. Land, was able to follow the sound pulses to a location about 5 minutes walking distance away. Dr. Land had no previous training with this device, but he was able to final the target location within 3 meters. Other curious bystanders were also able to identify the direction of target with very little direction.
If this project were to be improved, then a different GPS module capable of updating at 5Hz could be used instead of the 1Hz GPS used in the current prototype. This would increase the budget by about $25, but the code would also have to be altered to accommodate the more frequent updates. However more updates would require a faster clock speed, less frequent PWM pulses, or both. A different compass with a higher resolution than 6bits could also be used, but this would also increase the price of the project.
As mentioned in the introduction the GPS communication uses a standard format (NMEA0283 V 2.2). These standards include GGA, GSV, GSA, and RMC. Of these, RMC (Recommended Minimum Navigation Information) is used in the final product for simplicity. The other standards were used for development and debugging.
The code that was adapted from the 4760 website was from lab 2. This code consisted of using the PWM for DDS.
Intellectual property considerations:
This project was designed to aid a person in guiding them towards a destination. It is not intended to be used to assist a person purely based upon sound. The navigation data used by this device is based upon GPS data, therefore obstacles are not taken into consideration and this device will not guide a person around any potential hazards.
The device does not produce an electrical shock or any other hazard that may cause harm to the person wearing it. The device is powered by a household 9V battery, therefore all safety considerations that apply to the proper handling of 9V batteries also apply to this device. The bread board is insulated from the user by the headphones. The only safety consideration that may affect the individual wearing this device is if the person wears it in the rain. Although the device is insulated from the user's head, the device does not have a cover to prevent moisture damage. Therefore this device should not be worn in any circumstance where it could be contaminated by moisture.
The data gathered by the GPS is only stored long enough to determine the direction that the user must travel. The data is not stored or tracked by any other means. Therefore, the privacy of the user is not violated by tracking the location of user.
Task List
Nick - GPS, Audio buffering/Filtering, general debug
Matt - Sound (PWM), LCD/Buttons, general debug
Garret -Compass, Combined three main programs together
Compass Module - http://www.parallax.com/Store/Microcontrollers/BASICStampModules/tabid/134/ProductID/98/List/1/Default.aspx?SortField=UnitCost,ProductName
GPS Module - http://www.parallax.com/StoreSearchResults/tabid/768/txtSearch/GPS/List/0/SortField/4/ProductID/560/Default.aspx
ATmega 32 - http://www.parallax.com/StoreSearchResults/tabid/768/txtSearch/GPS/List/0/SortField/4/ProductID/560/Default.aspx
ECE4760 - http://instruct1.cit.cornell.edu/courses/ee476/
Interaul Time Difference- http://en.wikipedia.org/wiki/Interaural_time_difference
http://www.movable-type.co.uk/scripts/latlong.html
In order to make the sound more pleasing to the ear and not nauseating, we had to keep the pulses consistently spaced in a consistent pattern. We did this by timing how long each function took and then spacing them out based on this. We initially tried to run the compass and sound one by one while the USART was running in the background the entire time. The overlapping interrupts caused unpredictable delays which were not only nauseating, but caused the data updates to be too slow for reasonable use.
