First-Hand:ETAK, an early vehicle navigation system: Difference between revisions
No edit summary |
|||
| Line 1: | Line 1: | ||
The ETAK Story: How we built the first car navigation system | The ETAK Story: How we built the first car navigation system | ||
Contributed by Stan Honey | Contributed by Stan Honey | ||
Origin of Etak | == Origin of Etak == | ||
In 1983, I was working at SRI and ocean navigating professionally. I’d use my vacation time, and take occasional leave-without-pay from SRI to navigate in offshore races. One of these projects was to navigate on an ocean racer that Nolan Bushnell was building in order to win the Transpac, the Los Angeles to Honolulu sailing race. Nolan Bushnell created Pong and started Atari. He is a legend in the video game world, and an amazingly creative guy. I got to know Nolan well through navigating his boat. I convinced Ken Milnes, a colleague at SRI, to help me build a custom instrument system for Nolan’s boat to analyze our performance, our strategic position on the course and to help us pick the fastest course to Hawaii. We ended up first-to-finish in the Transpac. | In 1983, I was working at SRI and ocean navigating professionally. I’d use my vacation time, and take occasional leave-without-pay from SRI to navigate in offshore races. One of these projects was to navigate on an ocean racer that Nolan Bushnell was building in order to win the Transpac, the Los Angeles to Honolulu sailing race. Nolan Bushnell created Pong and started Atari. He is a legend in the video game world, and an amazingly creative guy. I got to know Nolan well through navigating his boat. I convinced Ken Milnes, a colleague at SRI, to help me build a custom instrument system for Nolan’s boat to analyze our performance, our strategic position on the course and to help us pick the fastest course to Hawaii. We ended up first-to-finish in the Transpac. | ||
Nolan, who was just coming off the success of Atari and Pong and the early success of Pizza Time Theater, was interested in our projects at SRI, and interested generally in any technologies that could have a consumer application. So I brought up the topic of vehicle navigation. I described to Nolan the possibility of building a vehicle navigation system where the maps would be stored as a vector database and the vehicle could keep track of its location by measuring distances and headings travelled, i.e. “dead-reckoning”. The accumulation of error in the dead-reckoned position could be eliminated by cross correlating the dead-reckoned track against a map database, i.e. map matching. By comparing the path driven with the paths on the map, and by taking advantage of the fact that drivers tend to use roads, one could figure out where the vehicle must be. Remember that this was well before GPS. I was able to convince Nolan that the concept might work. Nolan was very insightful on technology. He quickly understood the approach and gave me the start-up money to start ETAK. I convinced Ken Milnes and Alan Phillips, colleagues from SRI, to join me in cofounding the company that became ETAK, and then within a few months several more SRI colleagues joined including George Loughmiller, Jamie Buxton, and Jerry Russell. In 1983 the six of us left SRI and started ETAK, with Walt Zavoli joining us shortly thereafter. ETAK’s original business plan focused on the consumer market, and we introduced the ETAK Navigator in 1985. The Navigator was on the cover of Popular Science that year and was one of Fortune Magazine’s products of the year. As it turned out, however, the market that first made ETAK profitable was the commercial market particularly for digital mapping. ETAK provided the digital map databases and software for routing and geocoding. “Geocoding” means finding the locations of addresses. For big companies like UPS, Federal Express, and Coca Cola, the geocoding of addresses is very important. Etak also provided vehicle navigation systems and fleet management for public safety fleets like ambulances. | Nolan, who was just coming off the success of Atari and Pong and the early success of Pizza Time Theater, was interested in our projects at SRI, and interested generally in any technologies that could have a consumer application. So I brought up the topic of vehicle navigation. I described to Nolan the possibility of building a vehicle navigation system where the maps would be stored as a vector database and the vehicle could keep track of its location by measuring distances and headings travelled, i.e. “dead-reckoning”. The accumulation of error in the dead-reckoned position could be eliminated by cross correlating the dead-reckoned track against a map database, i.e. map matching. By comparing the path driven with the paths on the map, and by taking advantage of the fact that drivers tend to use roads, one could figure out where the vehicle must be. Remember that this was well before GPS. I was able to convince Nolan that the concept might work. Nolan was very insightful on technology. He quickly understood the approach and gave me the start-up money to start ETAK. I convinced Ken Milnes and Alan Phillips, colleagues from SRI, to join me in cofounding the company that became ETAK, and then within a few months several more SRI colleagues joined including George Loughmiller, Jamie Buxton, and Jerry Russell. In 1983 the six of us left SRI and started ETAK, with Walt Zavoli joining us shortly thereafter. ETAK’s original business plan focused on the consumer market, and we introduced the ETAK Navigator in 1985. The Navigator was on the cover of Popular Science that year and was one of Fortune Magazine’s products of the year. As it turned out, however, the market that first made ETAK profitable was the commercial market particularly for digital mapping. ETAK provided the digital map databases and software for routing and geocoding. “Geocoding” means finding the locations of addresses. For big companies like UPS, Federal Express, and Coca Cola, the geocoding of addresses is very important. Etak also provided vehicle navigation systems and fleet management for public safety fleets like ambulances. | ||
The car navigation system | == The car navigation system == | ||
Hardware Challenges | === Hardware Challenges === | ||
The ETAK Navigator was a huge technical undertaking because many of the fundamental bits and pieces that we needed didn’t exist. In those days, computer power and memory were very expensive, graphic displays were too expensive, and the data storage devices that we needed for the maps didn’t exist. A good deal of work was thus needed to overcome these limitations. We also had to design and build our own differential wheel sensors. We ended up building variable reluctance sensors used in conjunction with magnetic tape that ran around the inside of the wheels. We had to design our own flux gate compass sensor which had to work well over a wide range of temperature. We had to build our own sensors to estimate the magnetic fields induced by the defroster current so we could subtract that out of the flux-gate compass measurement. We had to design our own graphic display because bitmap displays were then too expensive. | The ETAK Navigator was a huge technical undertaking because many of the fundamental bits and pieces that we needed didn’t exist. In those days, computer power and memory were very expensive, graphic displays were too expensive, and the data storage devices that we needed for the maps didn’t exist. A good deal of work was thus needed to overcome these limitations. We also had to design and build our own differential wheel sensors. We ended up building variable reluctance sensors used in conjunction with magnetic tape that ran around the inside of the wheels. We had to design our own flux gate compass sensor which had to work well over a wide range of temperature. We had to build our own sensors to estimate the magnetic fields induced by the defroster current so we could subtract that out of the flux-gate compass measurement. We had to design our own graphic display because bitmap displays were then too expensive. | ||
We developed a vector display where the CRT beam directly drew the roads and letters as vectors rather than highlighting pixels. We designed our own hardware system. We initially used an 8088 running at 4.77 megahertz with 128kB of memory. We designed our own mass storage device, which looked like a Phillips-style compact cassette, only it used a polycarbonate shell so that the tapes wouldn’t distort in the heat of a car. We did not use a capstan to control tape speed. It was very high tape speed driven by the tape spools. We stored 3.5 megabytes on a single tape. We tended to think about the data as three-dimensional: latitude, longitude, and then priority. You can prove that it’s not always possible to store adjacent map data adjacently on a single dimensional media like a tape. We were able to do a very good job of minimizing the long seeks on the tape by storing the map database in a hierarchical way, and using the inherent topology of the map itself to structure the data. | We developed a vector display where the CRT beam directly drew the roads and letters as vectors rather than highlighting pixels. We designed our own hardware system. We initially used an 8088 running at 4.77 megahertz with 128kB of memory. We designed our own mass storage device, which looked like a Phillips-style compact cassette, only it used a polycarbonate shell so that the tapes wouldn’t distort in the heat of a car. We did not use a capstan to control tape speed. It was very high tape speed driven by the tape spools. We stored 3.5 megabytes on a single tape. We tended to think about the data as three-dimensional: latitude, longitude, and then priority. You can prove that it’s not always possible to store adjacent map data adjacently on a single dimensional media like a tape. We were able to do a very good job of minimizing the long seeks on the tape by storing the map database in a hierarchical way, and using the inherent topology of the map itself to structure the data. | ||
Map Topology and Data Storage | === Map Topology and Data Storage === | ||
The need to store map data efficiently on a tape triggered us to develop one of the key technologies that ETAK had: the extremely efficient hierarchical storage of map data. This efficient storage system was essential for maps stored on tape, but when we used this topologically structured map storage structure on a disk drive on a conventional computer, the ETAK map retrieval and geocoding software was able to retrieve map data and geocode addresses many times faster than the other existing approaches prevalent at the time. That was one of the reasons why ETAK did well in commercial applications for delivery and public safety fleets. When we started doing geocoding of addresses, we found that we could match addresses 20 times faster on a PC, than delivery companies were accustomed to doing on a mainframe. | The need to store map data efficiently on a tape triggered us to develop one of the key technologies that ETAK had: the extremely efficient hierarchical storage of map data. This efficient storage system was essential for maps stored on tape, but when we used this topologically structured map storage structure on a disk drive on a conventional computer, the ETAK map retrieval and geocoding software was able to retrieve map data and geocode addresses many times faster than the other existing approaches prevalent at the time. That was one of the reasons why ETAK did well in commercial applications for delivery and public safety fleets. When we started doing geocoding of addresses, we found that we could match addresses 20 times faster on a PC, than delivery companies were accustomed to doing on a mainframe. | ||
Marv White was the key guy in developing this approach. The key was to apply topology to the inherent hierarchy in the map itself. I learned about it by reading papers in the field, many of them written by mathematicians at the US Census Bureau like Jim Corbett and Marv White, who worked on map storage structures as part of the work on the DIME file, which was a digital map that used to manage the census. Marv and his boss Corbett wrote what I thought were the most insightful papers about the topological structure of maps and how to use topology to structure a map database. So I tracked Marv down and hired him to join ETAK and to lead the development of the digital mapping technology. In my view Marv was the most expert guy in the country in the use of mathematics to intelligently store maps. | Marv White was the key guy in developing this approach. The key was to apply topology to the inherent hierarchy in the map itself. I learned about it by reading papers in the field, many of them written by mathematicians at the US Census Bureau like Jim Corbett and Marv White, who worked on map storage structures as part of the work on the DIME file, which was a digital map that used to manage the census. Marv and his boss Corbett wrote what I thought were the most insightful papers about the topological structure of maps and how to use topology to structure a map database. So I tracked Marv down and hired him to join ETAK and to lead the development of the digital mapping technology. In my view Marv was the most expert guy in the country in the use of mathematics to intelligently store maps. | ||
The other bit was we needed to come up with an efficient way of developing the digital map data. We could get some useful data from the Census Bureau––street names, address fields, but the Census Bureau coordinates weren’t accurate enough. So we had to come up with an efficient way of digitizing maps. We did that by scanning USGS quad maps and aerial photographs, and we came up with a very efficient way of improving the coordinates of a digital map database through comparison to those scanned images. | The other bit was we needed to come up with an efficient way of developing the digital map data. We could get some useful data from the Census Bureau––street names, address fields, but the Census Bureau coordinates weren’t accurate enough. So we had to come up with an efficient way of digitizing maps. We did that by scanning USGS quad maps and aerial photographs, and we came up with a very efficient way of improving the coordinates of a digital map database through comparison to those scanned images. | ||
Digitizing started in 1983. Digitizing maps was very labor intensive. Although the scheme that we came up with was still labor intensive, it was much faster and much more efficient than any other schemes that were used at the time, which were mostly based on big digitizing tables. What we would do is scan the imagery with a scanning microdensitometer. The imagery often had substantial distortion, as did all affordable, non-orthofied aerial photographs. Then we would identify key recognizable points for which we had good coordinates, measure the distortion, and then pre-distort our database to that same distortion, line everything up, do an “overlay” on the computer display, and update the coordinates in our database to the image. We’d then convert the measurements back to the coordinates of latitude and longitude. It was a very efficient way to do the digitizing. | Digitizing started in 1983. Digitizing maps was very labor intensive. Although the scheme that we came up with was still labor intensive, it was much faster and much more efficient than any other schemes that were used at the time, which were mostly based on big digitizing tables. What we would do is scan the imagery with a scanning microdensitometer. The imagery often had substantial distortion, as did all affordable, non-orthofied aerial photographs. Then we would identify key recognizable points for which we had good coordinates, measure the distortion, and then pre-distort our database to that same distortion, line everything up, do an “overlay” on the computer display, and update the coordinates in our database to the image. We’d then convert the measurements back to the coordinates of latitude and longitude. It was a very efficient way to do the digitizing. | ||
Prioritizing the roads was critical to map storage and for routing. We used the priority of the roads themselves to divide the map into a hierarchy. In topological terms, we had zero-cells, one-cells and two-cells. Zero-cells would be the intersections. The one-cells were the road segments in between intersections which are bounded by the zero-cells and co-bounded by two-cells, and then the two-cells were the areas. The two-cell areas have attributes such as city, county, park, water. The one-cells carry attributes such as the road name, address ranges, priority of the road and the direction of travel. Typically, we would use the high priority roads to divide the map into lower priority, smaller, sub-maps. Every element of this topology has pointers to its co-bounding and bounding elements. So wherever you were on the map, you could find out what was next to you and you could go to a higher priority map or you could go to a lower priority map, all by following pointers that you had handy. | Prioritizing the roads was critical to map storage and for routing. We used the priority of the roads themselves to divide the map into a hierarchy. In topological terms, we had zero-cells, one-cells and two-cells. Zero-cells would be the intersections. The one-cells were the road segments in between intersections which are bounded by the zero-cells and co-bounded by two-cells, and then the two-cells were the areas. The two-cell areas have attributes such as city, county, park, water. The one-cells carry attributes such as the road name, address ranges, priority of the road and the direction of travel. Typically, we would use the high priority roads to divide the map into lower priority, smaller, sub-maps. Every element of this topology has pointers to its co-bounding and bounding elements. So wherever you were on the map, you could find out what was next to you and you could go to a higher priority map or you could go to a lower priority map, all by following pointers that you had handy. | ||
The First Heads-up Display | == The First Heads-up Display == | ||
Our plan was to sell the ETAK car navigation system as an after-market product for use in automobiles. We used a CRT-based, vector display mounted in the front of the car. It was a heading-up display in the sense that the map was automatically rotated to orient it so that the direction in which the car was heading was always at the top of the display. The heading-up display was one of ETAK’s most valuable innovations, and the source of the name “ETAK.” It turns out that the Polynesians and Micronesian navigators used a similar cognitive-mapping approach. They imagined their canoes to be at the center of their cognitive “map” and as they sailed they kept track of the movement of the islands moving past them. Because of the similarities of the cognitive approach, we named the company ETAK. | Our plan was to sell the ETAK car navigation system as an after-market product for use in automobiles. We used a CRT-based, vector display mounted in the front of the car. It was a heading-up display in the sense that the map was automatically rotated to orient it so that the direction in which the car was heading was always at the top of the display. The heading-up display was one of ETAK’s most valuable innovations, and the source of the name “ETAK.” It turns out that the Polynesians and Micronesian navigators used a similar cognitive-mapping approach. They imagined their canoes to be at the center of their cognitive “map” and as they sailed they kept track of the movement of the islands moving past them. Because of the similarities of the cognitive approach, we named the company ETAK. | ||
It sounds odd now because everybody now thinks of in-car map displays as being heading up, but at the time we started ETAK, that wasn’t known. That was one of our original innovations. It was one of the most valuable patents that ETAK had of the 30 or so total patents. | It sounds odd now because everybody now thinks of in-car map displays as being heading up, but at the time we started ETAK, that wasn’t known. That was one of our original innovations. It was one of the most valuable patents that ETAK had of the 30 or so total patents. | ||
Map matching | Map matching | ||
| Line 30: | Line 36: | ||
Another valuable patent was map matching, removing the uncertainty and error in position through cross correlation between the measured movement of the car and the roads themselves. Interestingly, even when GPS later became available and it was easy to know where you were within several meters, people continued to use map matching because the systems that used map matching looked much more precise on the map display. They would show the car on roads, exactly at the correct intersection. Once GPS was introduced, the map matching was easier because GPS could get you in the right vicinity so you could never be miles off, and then the map matching could do the fine positioning on the road more accurately than the GPS. Map matching continues today to be a very important technology because it makes the in-car navigation system look crisp and accurate. Most in-car navigation systems today still use map matching in addition to GPS. The early patents that we applied for at ETAK in rotating maps and map-matching turned out to be more important than we could have imagined and companies are still fighting over them. | Another valuable patent was map matching, removing the uncertainty and error in position through cross correlation between the measured movement of the car and the roads themselves. Interestingly, even when GPS later became available and it was easy to know where you were within several meters, people continued to use map matching because the systems that used map matching looked much more precise on the map display. They would show the car on roads, exactly at the correct intersection. Once GPS was introduced, the map matching was easier because GPS could get you in the right vicinity so you could never be miles off, and then the map matching could do the fine positioning on the road more accurately than the GPS. Map matching continues today to be a very important technology because it makes the in-car navigation system look crisp and accurate. Most in-car navigation systems today still use map matching in addition to GPS. The early patents that we applied for at ETAK in rotating maps and map-matching turned out to be more important than we could have imagined and companies are still fighting over them. | ||
Hardware | == Hardware == | ||
The hardware components of the system consisted of a processor, which was about the size of a shoebox and was typically kept in the trunk of the vehicle; that contained the 8088 and 128kb of memory. There was the tape drive, which was mounted in the passenger compartment of the car because you needed to change tapes. Three tapes would cover the whole San Francisco Bay area. So you didn’t have to change tapes a lot, but if you wanted to drive to Sacramento, you had to change tapes. Then there was the compass, which was typically mounted in the rear window. It was about half the size of a deck of cards. There were the wheel sensors which were mounted on the two non-driven wheels. | The hardware components of the system consisted of a processor, which was about the size of a shoebox and was typically kept in the trunk of the vehicle; that contained the 8088 and 128kb of memory. There was the tape drive, which was mounted in the passenger compartment of the car because you needed to change tapes. Three tapes would cover the whole San Francisco Bay area. So you didn’t have to change tapes a lot, but if you wanted to drive to Sacramento, you had to change tapes. Then there was the compass, which was typically mounted in the rear window. It was about half the size of a deck of cards. There were the wheel sensors which were mounted on the two non-driven wheels. | ||
== Calibrating the system == | |||
We had a very powerful algorithm to calibrate the compass. The calibration ritual basically was as follows: install everything in the car; drive the car to an intersection; tell the system where it was; drive to some other intersection and tell it where it was; and then you’d drive the car in a few circles. The system would use the circles to calibrate the compass, and use the known distance and known heading between the two intersections to calibrate the wheel sensors and the rotation term of the compass. That was good enough for it to start navigating, and from then on, it would automatically improve its own calibration, both of the wheel sensors and of the compass. The longer the system was in the car, the better the calibration would become because it’s using map matching, the cross correlation between the measurements of car movement and the roads on the map, not only to figure out where it is on the map but also to fine tune the calibration. | We had a very powerful algorithm to calibrate the compass. The calibration ritual basically was as follows: install everything in the car; drive the car to an intersection; tell the system where it was; drive to some other intersection and tell it where it was; and then you’d drive the car in a few circles. The system would use the circles to calibrate the compass, and use the known distance and known heading between the two intersections to calibrate the wheel sensors and the rotation term of the compass. That was good enough for it to start navigating, and from then on, it would automatically improve its own calibration, both of the wheel sensors and of the compass. The longer the system was in the car, the better the calibration would become because it’s using map matching, the cross correlation between the measurements of car movement and the roads on the map, not only to figure out where it is on the map but also to fine tune the calibration. | ||
If you had radial tires, the distance calibration would get extraordinarily accurate to the point where we couldn’t use the spherical earth approximation for our navigation calculations. We had to calculate distances on the geode in order to reduce the noise in our distance calibration as drivers variously drove N-S, and E-W. The heading sensor would get extraordinarily accurate due to this continuous calibration. In fact, there was one experiment where the military was testing different vehicle dead-reckoning systems. They installed an ETAK system in a military vehicle, drove it around, and then compared it to much more expensive dead reckoning systems that were based on inertial navigation. They discovered to their astonishment that even off road when it was only dead-reckoning, the ETAK system outperformed very expensive inertial systems. So they came to us and asked how can it possibly work so well? The answer was that they had driven the ETAK system around enough on roads on the base and in the adjoining cities so that it had become extraordinarily well calibrated. When they were off road, the fact that it was a four-wheel drive vehicle meant that there wasn’t that much tire slip. There was a little bit more on dirt roads but if you’re driving all four wheels, there’s not that much more, and so the system out-performed the more expensive systems not because it had better sensors but because the simple sensors it had were extraordinarily well calibrated. | If you had radial tires, the distance calibration would get extraordinarily accurate to the point where we couldn’t use the spherical earth approximation for our navigation calculations. We had to calculate distances on the geode in order to reduce the noise in our distance calibration as drivers variously drove N-S, and E-W. The heading sensor would get extraordinarily accurate due to this continuous calibration. In fact, there was one experiment where the military was testing different vehicle dead-reckoning systems. They installed an ETAK system in a military vehicle, drove it around, and then compared it to much more expensive dead reckoning systems that were based on inertial navigation. They discovered to their astonishment that even off road when it was only dead-reckoning, the ETAK system outperformed very expensive inertial systems. So they came to us and asked how can it possibly work so well? The answer was that they had driven the ETAK system around enough on roads on the base and in the adjoining cities so that it had become extraordinarily well calibrated. When they were off road, the fact that it was a four-wheel drive vehicle meant that there wasn’t that much tire slip. There was a little bit more on dirt roads but if you’re driving all four wheels, there’s not that much more, and so the system out-performed the more expensive systems not because it had better sensors but because the simple sensors it had were extraordinarily well calibrated. | ||
The calibration algorithm that we developed for the compass used a discrete Fourier transform on the error data that we captured. Prior to applying for a patent we discovered that Lord Kelvin had come up with a similar scheme. It looked to us like Lord Kelvin actually was using the discrete Fourier transform in his calibration of compasses. This is prior to the discovery of the Fourier transform. If you measure the compass heading error (deviation), as a function of measured heading, and then do a DFT for the first three terms, the first or DC term describes the rotation of the compass in the car, the second (single sinusoid term) describes the error due to hard magnetism in the car, and the third (two sinusoid term) describes the error due to flux focusing due to soft iron in the car. It turns out that Kelvin had figured that out, and basically was doing a DFT in his method to calibrate compasses. He didn’t describe it that way but it appears that he was doing it. | The calibration algorithm that we developed for the compass used a discrete Fourier transform on the error data that we captured. Prior to applying for a patent we discovered that Lord Kelvin had come up with a similar scheme. It looked to us like Lord Kelvin actually was using the discrete Fourier transform in his calibration of compasses. This is prior to the discovery of the Fourier transform. If you measure the compass heading error (deviation), as a function of measured heading, and then do a DFT for the first three terms, the first or DC term describes the rotation of the compass in the car, the second (single sinusoid term) describes the error due to hard magnetism in the car, and the third (two sinusoid term) describes the error due to flux focusing due to soft iron in the car. It turns out that Kelvin had figured that out, and basically was doing a DFT in his method to calibrate compasses. He didn’t describe it that way but it appears that he was doing it. | ||
The Building a Business | == The Building a Business == | ||
The business part of ETAK was frustrating because we were very far ahead of our time. Back then if you told somebody that you’ve developed a vehicle navigation system, they had no idea what you were talking about except for possibly a vague recollection of a James Bond movie. At the time, nobody understood the product that we were selling. Telling somebody that we had a “vehicle navigation system” was very different than telling them about a portable telephone. They knew what a phone was and they knew what the term portable meant so they could understand a portable phone. Even sending a business plan, a complete description of the product, and details about our company did not always make our product clear to the investors that we were approaching. These were smart guys. They would read our material and discuss it with us. Then we’d go to take them on a test drive and as soon as we backed out, they’d look at the map and say, “it moved.” They were genuinely surprised that the ETAK system showed the location of the car on a map. As soon as we started to drive, potential investors would be amazed, even though they read the business plan and they had read about the technology. They were astonished that the map was scrolling and rotating as we drove. Only during an actual drive would they appreciate the fact that the map scrolling under and rotating around the car symbol showed surrounding roads that corresponded to what they saw looking out their window. That just illustrated to us how difficult it was going to be for us to find a market because when smart people who have read the business plan and read about the technology still don’t know what to expect when they got in the car––how difficult was it then going to be to sell this? We had to give everyone an extensive test drive in order to get past that incredulous reaction of, “how does it know where I am?” | The business part of ETAK was frustrating because we were very far ahead of our time. Back then if you told somebody that you’ve developed a vehicle navigation system, they had no idea what you were talking about except for possibly a vague recollection of a James Bond movie. At the time, nobody understood the product that we were selling. Telling somebody that we had a “vehicle navigation system” was very different than telling them about a portable telephone. They knew what a phone was and they knew what the term portable meant so they could understand a portable phone. Even sending a business plan, a complete description of the product, and details about our company did not always make our product clear to the investors that we were approaching. These were smart guys. They would read our material and discuss it with us. Then we’d go to take them on a test drive and as soon as we backed out, they’d look at the map and say, “it moved.” They were genuinely surprised that the ETAK system showed the location of the car on a map. As soon as we started to drive, potential investors would be amazed, even though they read the business plan and they had read about the technology. They were astonished that the map was scrolling and rotating as we drove. Only during an actual drive would they appreciate the fact that the map scrolling under and rotating around the car symbol showed surrounding roads that corresponded to what they saw looking out their window. That just illustrated to us how difficult it was going to be for us to find a market because when smart people who have read the business plan and read about the technology still don’t know what to expect when they got in the car––how difficult was it then going to be to sell this? We had to give everyone an extensive test drive in order to get past that incredulous reaction of, “how does it know where I am?” | ||
Today nobody ever asks the question, “How does something know where I am?” Everybody just assumes that everything knows where it is ––your phone, your car, your boat, your camera etc. Nowadays, awareness of location is considered to be a utility of nature with GPS. But back then, people thought about things differently and people were aware that you could be lost, just simply not know where you were. In fact, that was a normal state then. People were just astonished that this device could know where they were. They were incredulous. | Today nobody ever asks the question, “How does something know where I am?” Everybody just assumes that everything knows where it is ––your phone, your car, your boat, your camera etc. Nowadays, awareness of location is considered to be a utility of nature with GPS. But back then, people thought about things differently and people were aware that you could be lost, just simply not know where you were. In fact, that was a normal state then. People were just astonished that this device could know where they were. They were incredulous. | ||
The business breakthrough for ETAK came when we sold a map license to UPS. Our original goal was to go after the consumer market. But breaking into the consumer market proved to be too difficult, particularly when no one knew what vehicle navigation was. Although not a mass market, the commercial market, on the other hand, offered us some good business opportunities. These were applications involving the routing and scheduling of commercial fleets like fire fleets, ambulance fleets and delivery fleets, and some of them just wanted to match addresses. We did a deal with Coca Cola where they principally used the system just to geocode where all the stops were so they could cluster them and sequence them for the trucks. Just geocoding the stops so that they could do a very simple heuristic clustering and sequencing for the trucks––not solving the traveling salesman problem per se, but just doing a first order cluster and sequence. They found that they could meet their deliveries with 20% fewer trucks than the way they had been doing it. | The business breakthrough for ETAK came when we sold a map license to UPS. Our original goal was to go after the consumer market. But breaking into the consumer market proved to be too difficult, particularly when no one knew what vehicle navigation was. Although not a mass market, the commercial market, on the other hand, offered us some good business opportunities. These were applications involving the routing and scheduling of commercial fleets like fire fleets, ambulance fleets and delivery fleets, and some of them just wanted to match addresses. We did a deal with Coca Cola where they principally used the system just to geocode where all the stops were so they could cluster them and sequence them for the trucks. Just geocoding the stops so that they could do a very simple heuristic clustering and sequencing for the trucks––not solving the traveling salesman problem per se, but just doing a first order cluster and sequence. They found that they could meet their deliveries with 20% fewer trucks than the way they had been doing it. | ||
Our initial business plan for ETAK was to build vehicle navigation systems and sell them to consumers, and we did start selling ETAK vehicle navigation systems to consumers in the fall of 1985. But, as it turned out, that market would have to wait for 20 years to mature. In 1989, News Corporation acquired ETAK. Rupert Murdoch wanted ETAK because it had the highest quality digital roadmap database, and that database would be useful for people asking the question where is the nearest and how do I get to it? Rupert Murdoch figured that this would be a great way to make that kind of media more personal, to allow people to ask, “where is the nearest, and how do I get there” when they used the classified ads or yellow pages. It was a stunning leap then, which only seems obvious today now that we all use Google maps. In 1996, NewsCorp sold ETAK to Sony. Sony’s interest was more in the vehicle navigation system. Then ETAK merged into TeleAtlas, and then TeleAtlas was acquired by TomTom. | Our initial business plan for ETAK was to build vehicle navigation systems and sell them to consumers, and we did start selling ETAK vehicle navigation systems to consumers in the fall of 1985. But, as it turned out, that market would have to wait for 20 years to mature. In 1989, News Corporation acquired ETAK. Rupert Murdoch wanted ETAK because it had the highest quality digital roadmap database, and that database would be useful for people asking the question where is the nearest and how do I get to it? Rupert Murdoch figured that this would be a great way to make that kind of media more personal, to allow people to ask, “where is the nearest, and how do I get there” when they used the classified ads or yellow pages. It was a stunning leap then, which only seems obvious today now that we all use Google maps. In 1996, NewsCorp sold ETAK to Sony. Sony’s interest was more in the vehicle navigation system. Then ETAK merged into TeleAtlas, and then TeleAtlas was acquired by TomTom. | ||
[[Category:Automation|{{PAGENAME}}]] | |||
[[Category:Transportation|{{PAGENAME}}]] | |||
Revision as of 13:44, 20 February 2014
The ETAK Story: How we built the first car navigation system
Contributed by Stan Honey
Origin of Etak
In 1983, I was working at SRI and ocean navigating professionally. I’d use my vacation time, and take occasional leave-without-pay from SRI to navigate in offshore races. One of these projects was to navigate on an ocean racer that Nolan Bushnell was building in order to win the Transpac, the Los Angeles to Honolulu sailing race. Nolan Bushnell created Pong and started Atari. He is a legend in the video game world, and an amazingly creative guy. I got to know Nolan well through navigating his boat. I convinced Ken Milnes, a colleague at SRI, to help me build a custom instrument system for Nolan’s boat to analyze our performance, our strategic position on the course and to help us pick the fastest course to Hawaii. We ended up first-to-finish in the Transpac.
Nolan, who was just coming off the success of Atari and Pong and the early success of Pizza Time Theater, was interested in our projects at SRI, and interested generally in any technologies that could have a consumer application. So I brought up the topic of vehicle navigation. I described to Nolan the possibility of building a vehicle navigation system where the maps would be stored as a vector database and the vehicle could keep track of its location by measuring distances and headings travelled, i.e. “dead-reckoning”. The accumulation of error in the dead-reckoned position could be eliminated by cross correlating the dead-reckoned track against a map database, i.e. map matching. By comparing the path driven with the paths on the map, and by taking advantage of the fact that drivers tend to use roads, one could figure out where the vehicle must be. Remember that this was well before GPS. I was able to convince Nolan that the concept might work. Nolan was very insightful on technology. He quickly understood the approach and gave me the start-up money to start ETAK. I convinced Ken Milnes and Alan Phillips, colleagues from SRI, to join me in cofounding the company that became ETAK, and then within a few months several more SRI colleagues joined including George Loughmiller, Jamie Buxton, and Jerry Russell. In 1983 the six of us left SRI and started ETAK, with Walt Zavoli joining us shortly thereafter. ETAK’s original business plan focused on the consumer market, and we introduced the ETAK Navigator in 1985. The Navigator was on the cover of Popular Science that year and was one of Fortune Magazine’s products of the year. As it turned out, however, the market that first made ETAK profitable was the commercial market particularly for digital mapping. ETAK provided the digital map databases and software for routing and geocoding. “Geocoding” means finding the locations of addresses. For big companies like UPS, Federal Express, and Coca Cola, the geocoding of addresses is very important. Etak also provided vehicle navigation systems and fleet management for public safety fleets like ambulances.
Hardware Challenges
The ETAK Navigator was a huge technical undertaking because many of the fundamental bits and pieces that we needed didn’t exist. In those days, computer power and memory were very expensive, graphic displays were too expensive, and the data storage devices that we needed for the maps didn’t exist. A good deal of work was thus needed to overcome these limitations. We also had to design and build our own differential wheel sensors. We ended up building variable reluctance sensors used in conjunction with magnetic tape that ran around the inside of the wheels. We had to design our own flux gate compass sensor which had to work well over a wide range of temperature. We had to build our own sensors to estimate the magnetic fields induced by the defroster current so we could subtract that out of the flux-gate compass measurement. We had to design our own graphic display because bitmap displays were then too expensive. We developed a vector display where the CRT beam directly drew the roads and letters as vectors rather than highlighting pixels. We designed our own hardware system. We initially used an 8088 running at 4.77 megahertz with 128kB of memory. We designed our own mass storage device, which looked like a Phillips-style compact cassette, only it used a polycarbonate shell so that the tapes wouldn’t distort in the heat of a car. We did not use a capstan to control tape speed. It was very high tape speed driven by the tape spools. We stored 3.5 megabytes on a single tape. We tended to think about the data as three-dimensional: latitude, longitude, and then priority. You can prove that it’s not always possible to store adjacent map data adjacently on a single dimensional media like a tape. We were able to do a very good job of minimizing the long seeks on the tape by storing the map database in a hierarchical way, and using the inherent topology of the map itself to structure the data.
Map Topology and Data Storage
The need to store map data efficiently on a tape triggered us to develop one of the key technologies that ETAK had: the extremely efficient hierarchical storage of map data. This efficient storage system was essential for maps stored on tape, but when we used this topologically structured map storage structure on a disk drive on a conventional computer, the ETAK map retrieval and geocoding software was able to retrieve map data and geocode addresses many times faster than the other existing approaches prevalent at the time. That was one of the reasons why ETAK did well in commercial applications for delivery and public safety fleets. When we started doing geocoding of addresses, we found that we could match addresses 20 times faster on a PC, than delivery companies were accustomed to doing on a mainframe.
Marv White was the key guy in developing this approach. The key was to apply topology to the inherent hierarchy in the map itself. I learned about it by reading papers in the field, many of them written by mathematicians at the US Census Bureau like Jim Corbett and Marv White, who worked on map storage structures as part of the work on the DIME file, which was a digital map that used to manage the census. Marv and his boss Corbett wrote what I thought were the most insightful papers about the topological structure of maps and how to use topology to structure a map database. So I tracked Marv down and hired him to join ETAK and to lead the development of the digital mapping technology. In my view Marv was the most expert guy in the country in the use of mathematics to intelligently store maps.
The other bit was we needed to come up with an efficient way of developing the digital map data. We could get some useful data from the Census Bureau––street names, address fields, but the Census Bureau coordinates weren’t accurate enough. So we had to come up with an efficient way of digitizing maps. We did that by scanning USGS quad maps and aerial photographs, and we came up with a very efficient way of improving the coordinates of a digital map database through comparison to those scanned images. Digitizing started in 1983. Digitizing maps was very labor intensive. Although the scheme that we came up with was still labor intensive, it was much faster and much more efficient than any other schemes that were used at the time, which were mostly based on big digitizing tables. What we would do is scan the imagery with a scanning microdensitometer. The imagery often had substantial distortion, as did all affordable, non-orthofied aerial photographs. Then we would identify key recognizable points for which we had good coordinates, measure the distortion, and then pre-distort our database to that same distortion, line everything up, do an “overlay” on the computer display, and update the coordinates in our database to the image. We’d then convert the measurements back to the coordinates of latitude and longitude. It was a very efficient way to do the digitizing.
Prioritizing the roads was critical to map storage and for routing. We used the priority of the roads themselves to divide the map into a hierarchy. In topological terms, we had zero-cells, one-cells and two-cells. Zero-cells would be the intersections. The one-cells were the road segments in between intersections which are bounded by the zero-cells and co-bounded by two-cells, and then the two-cells were the areas. The two-cell areas have attributes such as city, county, park, water. The one-cells carry attributes such as the road name, address ranges, priority of the road and the direction of travel. Typically, we would use the high priority roads to divide the map into lower priority, smaller, sub-maps. Every element of this topology has pointers to its co-bounding and bounding elements. So wherever you were on the map, you could find out what was next to you and you could go to a higher priority map or you could go to a lower priority map, all by following pointers that you had handy.
The First Heads-up Display
Our plan was to sell the ETAK car navigation system as an after-market product for use in automobiles. We used a CRT-based, vector display mounted in the front of the car. It was a heading-up display in the sense that the map was automatically rotated to orient it so that the direction in which the car was heading was always at the top of the display. The heading-up display was one of ETAK’s most valuable innovations, and the source of the name “ETAK.” It turns out that the Polynesians and Micronesian navigators used a similar cognitive-mapping approach. They imagined their canoes to be at the center of their cognitive “map” and as they sailed they kept track of the movement of the islands moving past them. Because of the similarities of the cognitive approach, we named the company ETAK.
It sounds odd now because everybody now thinks of in-car map displays as being heading up, but at the time we started ETAK, that wasn’t known. That was one of our original innovations. It was one of the most valuable patents that ETAK had of the 30 or so total patents. Map matching
Another valuable patent was map matching, removing the uncertainty and error in position through cross correlation between the measured movement of the car and the roads themselves. Interestingly, even when GPS later became available and it was easy to know where you were within several meters, people continued to use map matching because the systems that used map matching looked much more precise on the map display. They would show the car on roads, exactly at the correct intersection. Once GPS was introduced, the map matching was easier because GPS could get you in the right vicinity so you could never be miles off, and then the map matching could do the fine positioning on the road more accurately than the GPS. Map matching continues today to be a very important technology because it makes the in-car navigation system look crisp and accurate. Most in-car navigation systems today still use map matching in addition to GPS. The early patents that we applied for at ETAK in rotating maps and map-matching turned out to be more important than we could have imagined and companies are still fighting over them.
Hardware
The hardware components of the system consisted of a processor, which was about the size of a shoebox and was typically kept in the trunk of the vehicle; that contained the 8088 and 128kb of memory. There was the tape drive, which was mounted in the passenger compartment of the car because you needed to change tapes. Three tapes would cover the whole San Francisco Bay area. So you didn’t have to change tapes a lot, but if you wanted to drive to Sacramento, you had to change tapes. Then there was the compass, which was typically mounted in the rear window. It was about half the size of a deck of cards. There were the wheel sensors which were mounted on the two non-driven wheels.
Calibrating the system
We had a very powerful algorithm to calibrate the compass. The calibration ritual basically was as follows: install everything in the car; drive the car to an intersection; tell the system where it was; drive to some other intersection and tell it where it was; and then you’d drive the car in a few circles. The system would use the circles to calibrate the compass, and use the known distance and known heading between the two intersections to calibrate the wheel sensors and the rotation term of the compass. That was good enough for it to start navigating, and from then on, it would automatically improve its own calibration, both of the wheel sensors and of the compass. The longer the system was in the car, the better the calibration would become because it’s using map matching, the cross correlation between the measurements of car movement and the roads on the map, not only to figure out where it is on the map but also to fine tune the calibration.
If you had radial tires, the distance calibration would get extraordinarily accurate to the point where we couldn’t use the spherical earth approximation for our navigation calculations. We had to calculate distances on the geode in order to reduce the noise in our distance calibration as drivers variously drove N-S, and E-W. The heading sensor would get extraordinarily accurate due to this continuous calibration. In fact, there was one experiment where the military was testing different vehicle dead-reckoning systems. They installed an ETAK system in a military vehicle, drove it around, and then compared it to much more expensive dead reckoning systems that were based on inertial navigation. They discovered to their astonishment that even off road when it was only dead-reckoning, the ETAK system outperformed very expensive inertial systems. So they came to us and asked how can it possibly work so well? The answer was that they had driven the ETAK system around enough on roads on the base and in the adjoining cities so that it had become extraordinarily well calibrated. When they were off road, the fact that it was a four-wheel drive vehicle meant that there wasn’t that much tire slip. There was a little bit more on dirt roads but if you’re driving all four wheels, there’s not that much more, and so the system out-performed the more expensive systems not because it had better sensors but because the simple sensors it had were extraordinarily well calibrated.
The calibration algorithm that we developed for the compass used a discrete Fourier transform on the error data that we captured. Prior to applying for a patent we discovered that Lord Kelvin had come up with a similar scheme. It looked to us like Lord Kelvin actually was using the discrete Fourier transform in his calibration of compasses. This is prior to the discovery of the Fourier transform. If you measure the compass heading error (deviation), as a function of measured heading, and then do a DFT for the first three terms, the first or DC term describes the rotation of the compass in the car, the second (single sinusoid term) describes the error due to hard magnetism in the car, and the third (two sinusoid term) describes the error due to flux focusing due to soft iron in the car. It turns out that Kelvin had figured that out, and basically was doing a DFT in his method to calibrate compasses. He didn’t describe it that way but it appears that he was doing it.
The Building a Business
The business part of ETAK was frustrating because we were very far ahead of our time. Back then if you told somebody that you’ve developed a vehicle navigation system, they had no idea what you were talking about except for possibly a vague recollection of a James Bond movie. At the time, nobody understood the product that we were selling. Telling somebody that we had a “vehicle navigation system” was very different than telling them about a portable telephone. They knew what a phone was and they knew what the term portable meant so they could understand a portable phone. Even sending a business plan, a complete description of the product, and details about our company did not always make our product clear to the investors that we were approaching. These were smart guys. They would read our material and discuss it with us. Then we’d go to take them on a test drive and as soon as we backed out, they’d look at the map and say, “it moved.” They were genuinely surprised that the ETAK system showed the location of the car on a map. As soon as we started to drive, potential investors would be amazed, even though they read the business plan and they had read about the technology. They were astonished that the map was scrolling and rotating as we drove. Only during an actual drive would they appreciate the fact that the map scrolling under and rotating around the car symbol showed surrounding roads that corresponded to what they saw looking out their window. That just illustrated to us how difficult it was going to be for us to find a market because when smart people who have read the business plan and read about the technology still don’t know what to expect when they got in the car––how difficult was it then going to be to sell this? We had to give everyone an extensive test drive in order to get past that incredulous reaction of, “how does it know where I am?”
Today nobody ever asks the question, “How does something know where I am?” Everybody just assumes that everything knows where it is ––your phone, your car, your boat, your camera etc. Nowadays, awareness of location is considered to be a utility of nature with GPS. But back then, people thought about things differently and people were aware that you could be lost, just simply not know where you were. In fact, that was a normal state then. People were just astonished that this device could know where they were. They were incredulous.
The business breakthrough for ETAK came when we sold a map license to UPS. Our original goal was to go after the consumer market. But breaking into the consumer market proved to be too difficult, particularly when no one knew what vehicle navigation was. Although not a mass market, the commercial market, on the other hand, offered us some good business opportunities. These were applications involving the routing and scheduling of commercial fleets like fire fleets, ambulance fleets and delivery fleets, and some of them just wanted to match addresses. We did a deal with Coca Cola where they principally used the system just to geocode where all the stops were so they could cluster them and sequence them for the trucks. Just geocoding the stops so that they could do a very simple heuristic clustering and sequencing for the trucks––not solving the traveling salesman problem per se, but just doing a first order cluster and sequence. They found that they could meet their deliveries with 20% fewer trucks than the way they had been doing it.
Our initial business plan for ETAK was to build vehicle navigation systems and sell them to consumers, and we did start selling ETAK vehicle navigation systems to consumers in the fall of 1985. But, as it turned out, that market would have to wait for 20 years to mature. In 1989, News Corporation acquired ETAK. Rupert Murdoch wanted ETAK because it had the highest quality digital roadmap database, and that database would be useful for people asking the question where is the nearest and how do I get to it? Rupert Murdoch figured that this would be a great way to make that kind of media more personal, to allow people to ask, “where is the nearest, and how do I get there” when they used the classified ads or yellow pages. It was a stunning leap then, which only seems obvious today now that we all use Google maps. In 1996, NewsCorp sold ETAK to Sony. Sony’s interest was more in the vehicle navigation system. Then ETAK merged into TeleAtlas, and then TeleAtlas was acquired by TomTom.
