Objectives of the Project The three main objectives of this project were to: (1) learn how to program in C language; (2) build a functioning street intersection detector; (3) and, present my project at the Ontario Engineering Competition (OEC). Summary All objectives were met as the project progressed to completion. NVI is a device that will allow a person without the benefit of sight to determine where they are in a city by referencing street intersections. This information is presented to the visually impaired person via synthesized speech. NVI can accurately determine its own position by using a Global Positioning System (GPS) receiver. The GPS receiver obtains signals from at least four satellites, and from these readings it can determine the coordinates at which the receiver is positioned. This positional information is then transferred to the computer that compares this information with its internal data base of the city the person is in. The data associated with the matching street intersection is then sent out to the Intex Talker that converts the text into phonetics that are ultimately spoken to the person. Introduction History June 15,1992 Street Finder was a proposed fourth year project that would have used bar code readers to tell the visually disabled person at which street intersection they were standing. The main advantage of using the bar code method is its very low expense. The visually impaired would find it very hard to locate the bar code sticker on the street pole. Vandalism of the bar code stickers could not be prevented either. This method is also not very flexible; that is, the user must have physical contact with the pole. Because of the above analysis, this idea was not pursued. June 21,1992 Location Finder was next proposed as a possible fourth year project but it also was discontinued, as it would not be economically feasible to support the extensive grid of transmitters required to cover an entire city. Location Finder is an FM-based system. At each street intersection, a single solar celled transmitter would transmit an intermittent code cycling every 5 seconds. The hand-held receiver would pick up these FM signals and compare them with its internal data base. This enables the system to determine and articulate the user's current location. An advantage of using FM signals is that this system would not be just limited to visually impaired people. It could be expanded to include motorists, bicyclists, tourists, etc. The main disadvantage is that 60,000 transmitters would be required to cover all intersections in a city the size of Ottawa. September 27,1992 Dr. Harrison suggested that I should look into using the GPS system to determine the coordinates of the person instead of using FM transmitters at each intersection. Incorporation of GPS into my system was the basis of my entire project. The title of my system changed a number of times throughout the project. The initial title was Global Mapping System (GMS), followed by Audio Positioning System (APS). The final title was the Navigational System for the Visually Impaired (NVI). This system consists of a GPS receiver, a laptop computer, and an Intex Talker for speech synthesis. The integration of the system occurs through hardware cables and C language software that communicates between all devices. Contained within the software is the data base of the test site used to test the system, namely the streets of Carleton University. The advantage of this system over the previous ones suggested is that this system is already in place, and can be easily configured to suit the needs of the customer. A few disadvantages of the NVI system that must be overcome are: high cost of the GPS receiver, the collection of the data base for the city of Ottawa, miniaturization to a hand held device, and the accuracy of the GPS receiver. These issues are addressed in this report. Present A prototype of my project has been completed and is currently working with its limited database. The system currently weighs 15 Kg. and is quite cumbersome. The accuracy of the NVI is limited to + 100 meters, which is sufficient for this stage of its development. I have entered three competitions with my project. In the Ontario Engineering Competition I won the Social Awareness Award, sponsored by the Association of Professional Engineers of Ontario (APEO). I took first place in the Institute of Electronic and Electrical Engineers (IEEE) Carleton Papers Night, and represented Carleton in the Regional IEEE Papers Night. The final competition entered was the Association of Professional Engineers of Ontario (APEO) Papers night. Future A patent for this device is currently being considered. I would like to have a functional hand held NVI unit in two years. Miniaturization of this project will start this summer if funding is found to support the hardware development. Technical Background The Global Positioning System (GPS) utilizes some of today's most sophisticated electronics, but for my project I will explain the basics of GPS and how GPS is used in cooperation with my project. How GPS Works To make GPS more understandable, the system is described through five conceptual pieces: satellite triangulation, distance to the satellites, perfect timing, determining where the satellites are in orbit, and ionospheric delays. Triangulation from satellites is the basis of the system. To triangulate, GPS measures distance using the travel time of a radio message. To measure travel time, GPS needs very accurate clocks. Additionally, once the distance to a satellite is known, the position of the satellite in space must also be known. Finally, as the GPS signal travels through the ionosphere and the earth's atmosphere, it gets delayed. 1--Satellite Triangulation Ignoring for the moment that we do know the distance from ourselves to the moving satellites, we can assume that we are 18,000 km away from satellite A, for example. This significantly narrows the scope of the search for our location. It tells us that we are on an imaginary sphere that is centred on the satellite having a radius of 18,000 km. 1 Figure 1a) One Satellite It is also known that we are 19,000 km from satellite B. Presently with these two distances, we could be positioned anywhere on the circle where the two spheres intersect. 2 Figure 1b) Two Satellites With a measurement from a third satellite say 20,000 km from satellite C, we can pinpoint ourselves if we disregard the ridiculous answer. As the three imaginary spheres intersect, only two locations are possible: one will be the correct answer, and the other will either be at an impossible altitude or an impossible velocity. Figure 1c) Three Satellites Mathematically we need four measurements to determine our location in three-space, but if we disregard the ridiculous answer we could theoretically proceed with only three measurements. 2--Distance to the Satellites The GPS system works by timing how long it takes radio signals generated by the satellites to reach us, and then calculating distance from multiplying the speed of light by the time taken. The problem with this is that we do not know when the signals left the satellites. To get around this, the system synchronizes the satellites and receivers so that they are generating the same codes at exactly the same time. The digital codes called "pseudo-random" codes are generated by the satellites as well as the receivers. These carefully chosen codes repeat every millisecond. Figure 2) Timing Difference 3--Perfect Timing In the GPS satellites four atomic clocks are on board. One clock is needed for timing and synchronization, while the other three are for redundancy in case of a failure. Since atomic clocks are very expensive, the GPS receivers have clocks with nanosecond accuracy. Yet, even with this accuracy, the measurement can be off quite substantially. In the previous section, it was said that theoretically three measurements were needed to get a position fix. However, with four imperfect measurements, for a 3-d fix, any timing offset can be eliminated, as long as all the offset are consistent. Figure 3) Three Satellite Accurate Timing As can be seen in the case of incorrect timing (Fig. 3), the spheres do not intersect at a single point. The onboard computer in the GPS receiver uses an algebraic algorithm to determine the timing error associated with the readings. Once this timing error is known the arcs will all intersect at one point, the current location of the receiver. 4--Determining Where the Satellites Are in Orbit The satellites are in a non-geosynchronous orbit with an orbital period of 12 hours. During each orbital period the satellite passes over one of the Department of Defense (DoD) monitoring stations. The DoD monitors the satellites' altitude, position and speed. The variations they are looking for are called "ephemeris" errors: minor errors caused by gravitational pulls for the moon, sun, etc. This information is then relayed back up to the satellite. That satellite will then broadcast these minor corrections along with its timing information in a system "data message". This data message takes 30 seconds to read, and is required by the GPS receiver to accurately track the satellites' position. 5--Ionospheric Delays The ionosphere is a blanket of electrically charged particles 129 km to 193 km above the earth. These particles slow down the signals coming from the satellites. The velocity of light through the ionosphere is inversely proportional to its frequency squared.1 To overcome this error, some GPS receivers use what is known as "dual-frequency" correction. This compares the arrival times of two different parts of the GPS signal which are at different frequencies and deduce the time delay associated with the ionosphere. Frequencies of GPS Carrier Frequency Two carrier frequencies used by the GPS are 1227.60 MHz and 1575.42 MHz that are in the L-band frequency range. Course/Acquisition (C/A) Code The GPS code consists of 1023 binary pseudo-random codes at a chip rate of 1.023 MHz. A chip is the transition time for an individual bit in the pseudo-random sequence. The C/A code is the code used by the NVI system to get positional information. Pseudo-Random Codes By using pseudo-random codes, GPS signals can be very low power and can still be picked up by an antenna a few centimetres across. The GPS receiver compares its internally generated pseudo-random code with the signals obtained by the antenna. As the number of matches starts to increase, the satellite's C/A code is found and can then be tracked and utilized to get positional information. Pseudo-random codes are a sequence of 1023 binary bits that repeat every millisecond. These sequences are used to obtain timing information between the satellites and the GPS receivers. Differential GPS and Pseudolites The U.S. DoD purposely degrades the signals from the satellites for military reasons that introduce errors of + 100 meters to our readings. This is called Selective Availability or "S/A". By placing a stationary GPS receiver at a known location, it can be used to figure out exactly which errors the satellite data contains. It acts like a static reference point. This receiver called a "Pseudolite" can transmit an error correcting message to any other GPS receivers that are in the local area. These additional receivers can use the error message to correct their positional solutions (Fig 4). This concept works because the satellites are so far above the earth that errors measured by one receiver will be almost exactly the same for any other receiver in a given area. This correction factor not only corrects S/A but will also reduce ionospheric, timing, and atmospheric errors. Figure 4) Differential Correction -- Pseudolite NVI from the Beginning The first thing which had to be accomplished was understanding the GPS system, and in particular how the GPS receiver works. After obtaining a sound basis of the GPS system, an electronic map of the streets of Carleton had to be obtained. Creating the Internal Electronic Map With the GPS Pathfinder Basic (a GPS receiver), I walked around the streets of Carleton collecting data points every 10 seconds. This took approximately one hour to complete. Once the data points were collected, these points were differentially corrected to increase the accuracy from + 100m up to + 3m. This was accomplished with help from SurNav, a company which deals in GPS equipment. Once the points were differentially corrected they were plotted to scale, and overlaid on an actual map of Carleton to verify the accuracy of the GPS receiver (Fig. 5). As seen in Figure 5, there are some slight discrepancies at points A and B. These were caused by loss of a satellite. Three satellites were in view at these two points, which introduced errors into the measurements. After obtaining the entire electronic map of Carleton, I then proceeded to key the street intersections of Carleton into the data-base. These were taken directly off the differentially corrected map. Software Data-Base of Carleton Refer to Appendix A for the computerized data-base of the streets of Carleton. Figure 5) GPS Map of Carleton Communication In order for this software to communicate with the GPS receiver the receiver's comm port must be set to TSIP (Trimble Standard Interface Protocol). The software I am using was developed by Trimble and is called Toolkit. The specific source I am using is called pktmon, which is a C-language program. Pktmon was stripped down to protocol communication between the GPS receiver and the computer. Afterwards, it was rebuilt with additional features, such as: a help menu, search algorithms, and satellite strength information. Before communication can commence, an initialization code must be sent to the receiver so that the receiver will be sending correct information to the computer. That is, the GPS receiver is to send the positional information, only upon request, in a format which can be directly compared with the internal data-base. Refer to Appendix B for the I/O Options sent to the GPS receiver. Determining the Street Intersection Upon being queried by the user, the computer will send a command to the GPS receiver asking for the current position. After obtaining this position the computer will then search the data-base for the shortest distance (within a given radius), between the user's current position and all intersections. The radius depends on the accuracy of the positional information being obtained via the satellites. A small radius indicates fairly accurate positional information, where as a large radius could indicate an accuracy of + 300m. Refer to Appendix C for the intersection search algorithm. Programming the Intex Talker The Intex Talker is a text-to-phonetics converter. These phonetics are amplified and then sent to the speaker. After a match between the user's current location and an intersection has been made, this text string containing the names of the two intersecting streets is sent to the Intex Talker, which in turn audibly relays the information to the user. Refer to Appendix D for the communication between the computer and the Intex Talker. Hardware Interfaces GPS Receiver - Computer The GPS receiver is connected to the computer through the comm ports of both devices. The signal from the GPS receiver is in RS-422 format. The computer's comm port is RS-232 but it will accept RS-422 signals. Computer - Intex Talker The printer port of the computer is connected to the parallel port of the Intex Talker via a ribbon cable. With reference to the schematics of the LapTop computer and the Intex Talker, I made up the cable needed to connect these two devices together. The Intex Talker was originally run off 15v a.c.; with some help from Mike Kelly I was able to get the Intex Talker to run off a 12v d.c. gell cell. Applications NVI is not limited to just the visually impaired, as there are a number of other markets for such a device. There are at least four markets which I feel can benefit by using NVI, since it: (1) gives visually impaired the independence and confidence to navigate through a city unattended; (2) helps trainers of seeing-eye dogs keep on a specific route while training the dogs; (3) aids delivery personnel in finding specific destinations; and, (4) helps tourists find specific locations while travelling. Marketing & Economic Study: Executive Summary The NVI should be miniaturized, and test marketed in Ottawa. Ottawa is designated a test market city because it is representative of the entire country. The test market should include CNIB clientele: some with seeing-eye dogs, others with white canes, as well as those who can see well enough not to require a dog or a cane. Test marketing should also include seeing-eye dog trainers, and a segment of the general public. Since the support of the CNIB and the Seeing-Eye Dog Association has been given, funding to start full production after test marketing should not be a problem. Funding from the provincial government may also be considered. Problem Statement The problem facing the developer is whether to continue developing this device to the point where a hand-held device could be useful to a visually impaired person. Before test marketing can be completed the NVI must be miniaturized, and a detailed map containing all street intersections must be copied into the memory of the unit. There is also the problem of S/A (Selective Availability) which is a tactic used by the U.S. Department of Defence to purposely degrade the signal coming from the satellites for security reasons. This causes the accuracy to drop from + 3 meters to + 100 meters. For a GPS receiver to be accurate, the antenna must have a direct line of sight to the satellites. A person wearing the NVI must have the antenna visible to the sky at all times, and stand away from tall buildings because the buildings will block the line of sight of the antenna to the satellites. For this product to be marketable, the unit must be approximately the size of a Walkman tape player, weigh under 2 Kgs., contain all street intersections and possibly house numbers, cost under $1,000, and be accurate to at least + 3 meters. Analysis Internal : Product The NVI is a navigational system for the visually impaired, which will, when queried, (i.e. the operator presses a button) speak, telling the operator the current location with reference to the street intersection at which the operator is located. The current prototype is made up of three main components: a GPS (Global Positioning System) receiver, a INTEX TALKER (text-to-speech converter), and a lap-top computer. This system currently weighs approximately 12 Kgs. A production version will weigh approximately 1 Kg. Also the system must be integrated into a single package. Trimble Navigation Inc. has developed a GPS receiver called the "SVeeSix" which is approximately 10 x 9 x 2 cm and weighs 0.05 Kg. (see Appendix 1). This circuit board can be interfaced with a CPU and memory to run the software needed to take the geographical location and give the user the current location with reference to the street intersection. Therefore the lap-top and Intex Talker can be reduced in both size and weight to that of the GPS circuit board. The final prototype would be approximately 12 x 10 x 5 cm and would weigh less than 1 Kg. Since the antenna must have a direct line of sight to the satellites, the antenna must be placed on top of the user's head. There would be headphones for the person to hear the NVI speaking, as this provides a place for the antenna on top of the band going over the user's head connecting the speakers together. This will allow the antenna to always face the sky, and it will permit the user freedom of use of their hands. The antenna has a 3 cm radius and a 2 cm height. See Appendix 1 for more detail. External Environment In 1991, Canada had over 70,000 registered CNIB clients, with 9,000 new clients that year. In Ontario, approximately 30,000 clients were registered, of which 4,000 were new clientele. Refer to Appendix 2 for more accurate data. For this analysis the location of concern will be Ottawa. As of January 1, 1993, CNIB Ottawa had 2,500 registered clients. Of these 2,500 clients approximately 200 would be able to use such a device, since a majority of them would be over the age of 70 years of age, unable to walk outdoors alone. Competition In Canada, there is no comparable device since this is a continuous innovation, defined as an innovation that may not profoundly affect the course of human history. Therefore, this is a new product development problem. In Great Britain, a team of developers has been designing a navigational system for the blind, but it is not known what stage of development their project is at currently. Consumers The selected target markets for the NVI are visually disabled people between the ages of 18 and 69, the tourism industry, Seeing-Eye Dog Association, and the general public seeking a novelty item. A person who is visually impaired values independence above all else. Such a device will allow the user the freedom to walk around city streets, knowing exactly where they are without asking anyone for assistance. The CNIB said that for such a device to be useful to a visually impaired person it must be possible to enter the home address into memory and later ask the NVI unit how to get there. When queried, the NVI would say for example; "Turn down Bronson, cross over three streets, turn right onto Sunnyside and straight ahead one block." The tourism industry could use these devices to help people unfamiliar with a city to find their way around more easily. The NVI would have to be modified so that a tourist could key in where they wanted to go. The unit would then direct them how many blocks to the left, right or straight ahead. The Seeing-Eye Dog Association will buy these devices to help trainers who are visually impaired train the dogs. When training the dogs the trainer must memorize the route to be followed. While en-route the trainer must not only be aware of where they are but also what the dog is doing. With the NVI unit the trainer will not have to worry about an exact location, and will be able to concentrate on training the dog. The general public could also use the NVI unit when driving at night and trying to read an unlit street sign. Clearly when entering an unfamiliar neighbourhood the device can be very helpful and give a sense of security to a newcomer. Channels of Distribution This device would be sold from a few select outlets, namely the CNIB office, and the Seeing-Eye Dog Association building. Since both of these distributers are non-profit organizations, no distribution profit margin is needed. Economic Feasibility The current price of the GPS receiver "SVeeSix" is $1200. With mass production, this could be reduced to $500 with orders above 500 units. The cost to construct the rest of the NVI unit would be approximately $100. With the addition of $100 for overhead costs and profitability, the total cost of the NVI unit should be $700. To place this cost in perspective, it should be considered that a seeing-eye dog costs $25,000. Comparatively, the NVI costs only $700 and offers independence without reliance on a bystander. See Appendix 3 for a detailed forecast of profitability. Two problems must be dealt with for the unit to be economically feasible: developing an accurate survey of Ottawa; and, improving the accuracy from + 100 meters to at least + 3 meters. Currently the (RMOC) Regional Municipality of Ottawa-Carleton is engaged in updating their 911 emergency phone service, and in doing so will be using GPS and a computer data base to store this data. This data will be in a format which can be used by the NVI. It is currently unknown whether RMOC will make this data public, but with the backing of the CNIB and the Seeing-Eye Dog Association, it is felt that RMOC will recognize the value of this project and assist . The accuracy of the GPS receiver can be improved from + 100 meters to + 2 meters by using a "Pseudolite". This is a ground based differential GPS receiver. The Pseudolite will receive the same signals as the NVI unit and send out a correction signal to all the NVI's in the city. Recommendations The NVI should be miniaturized, and test marketed in Ottawa. Ottawa is designated a test market city because it is representative of the entire country. The test market should include CNIB clientele: some with seeing-eye dogs, others with white canes, as well as those who can see well enough not to require a dog or a cane. Test marketing should also include seeing-eye dog trainers, and a segment of the general public. Providing that test marketing is successful, a possible marketing strategy is as follows. Strategy i) Product Different packages could be offered. The basic package would only tell at which intersection the user is near without the help of the Pseudolite. The standard package could tell which corner of the intersection the user is standing at (with the aid of the Pseudolite correction), and could have the "find your way home" button. The advanced package could tell at which corner of the intersection the user is standing (with the aid of the Pseudolite correction), have a "find your way to a number of prestored locations" capability, and allow the user to enter the desired destination and advise on how to get there. All the above packages would come standard with a "current time" feature, but only the Advanced package would come with a keyboard, an LCD (Liquid Crystal Display), and the capacity to add extra memory. ii) Price The basic model would cost approximately $700, and the standard model anywhere from $800-$900. The Advanced model would cost approximately $1,000 to $1,100 depending on how much memory was added. The user would also have to buy a cartridge containing the street intersection locations of the city. This would cost approximately $50, of which $5 would go to labour and materials and $45 to the municipality which supplied the street data. Refer to Appendix 3 for the projected sales figures for the first year of full production. iii) Distribution This device would be available from a few select outlets, namely the CNIB office, and the Seeing-Eye Dog Association building. All major cities in Canada will be initially targeted, and as popularity increased the market would be expanded to include the United States. As the smaller cities updated their maps, these cities too could support the NVI. Each city which wished to support the more advanced features of the NVI would have to buy a Pseudolite, and larger cities probably would have to buy two or three of these depending on how spread out the city is. A Pseudolite would cost approximately $10,000. iv) Promotion To maximize the promotional investment, the NVI would be advertised in all tourist magazines, CNIB newsletters, and newspapers in all cities that support NVI. Future Design For this product to be a success, a few key points must first be addressed. An inexpensive detailed map of the city must be created. Miniaturization of the GPS receiver, computer, and voice synthesizer must also be accomplished for this product to be successful. Electronic maps currently exist for each city, and are continuously being updated. Canadian Marconi has designed a GPS receiver which consists of two chips. In contemporary "high-tech" society, to miniaturize a computer is trivial, as off-the-shelf products exist which I can use, such as voice synthesizers presently contained on a single chip. The NVI could be reduced to the size of a WalkmanTM and weigh well under 1 Kg. Refer to Appendix E&F for the proposed product configuration. Competitions Entered I have entered my project into three main competitions: 1) Ontario Engineering Competition (OEC) -- 'Design' - won the "Social Awareness Award", sponsored by APEO. 2) IEEE Papers Night - placed first in Carleton; came second in the Eastern regional competition 3) APEO Papers Night Conclusion The original objectives of the project were: (1) learn how to program in C language; (2) build a functioning street intersection detector; (3) and, present my project at the Ontario Engineering Competition (OEC). All of these objectives were accomplished. NVI is a device that will allow a person without the benefit of sight to determine where they are in a city by referencing street intersections. NVI can accurately determine its own position by using the Global Positioning System. NVI may someday help those who are visually impaired to get around a little easier in this visually dominated world. Acknowledgements George and Stan - video editing Jeff Lariviere - video taping Jon Harjo - use of video camera Dave Yule @ SurNav - use of GPS accessories Eric DeKemp @ Carleton - use of GPS receiver Brian Robar - use of laptop computer Trevor Pearce - use of Intex Talker Technicians @ Trible - technical assistance Dave Clarke - technical assistance Mike Kelly @ Carleton - technical assistance Dr. R. Harrison @ Carleton - supervisor Bibliography "Appendix A : Digital Communication Interface Definition", in TANS: Trimble Advance Navigation Sensor. (no author cited) Sunnyvale, CA: Trimble Navigation Ltd., 1991. pp.A-1 - A-40. Ciarcia, Steve. "Build the Microvox Text-to-Speech Synthesizer--Part 1: Hardware", Byte. Vol. 7, No.9. (September 1982), pp64-88. Ciarcia, Steve. "Build the Microvox Text-to-Speech Synthesizer--Part 2: Software", Byte. Vol. 7, No.10. (October 1982), pp40-64. General Reference: GPS PathfinderTM System. (no author cited) Sunnyvale, CA: Trimble Navigation Ltd., 1992. Hurn, Jeff. GPS: A Guide to the Next Utility.Sunnyvale, CA: Trimble Navigation Ltd., 1989.