MAP MATCHING AUGMENTED DEAD RECKONING
`
`Walter B. Zavoli
`Stanley K. Honey
`
`Etak, Incorporated
`
`Menlo Park, California
`
`DESCRIPTION
`
`an
`The Etak Navigator provides
`electronic road map as shown in Figure 1.
`The arrowhead car symbol is positioned
`on
`the screen to indicate the precise
`location of the vehicle. As the vehicle
`moves, the map shifts and rotates "under"
`the car symbol to maintain accurate
`position and orientation. With this
`heading-up moving-map display, the driver
`assimilates navigation information at a
`glance. The driver can select different
`map scales, ranging from a detailed view
`of the residential streets around him
`(Figure 2 1 , to a region-wide overview
`of
`the freeway system (Figure
`3 ) . Roads are
`prioritized in categories from residential
`streets to interstates. To limit map
`complexity, the display shows only major
`highways in the region-wide scale and adds
`more detail at larger scales. In this way
`the display is not cluttered with
`Similarly, a dynamic
`extraneous data.
`labeling algorithm labels those streets
`most likely
`to be of interest to the
`driver. As the car changes direction
`and
`the map rotates, the labels are reoriented
`for easy reading and are always written in
`a readable font size.
`
`Figure 1
`
`ABSTRACT
`
`my destination?
`Where am I? Where is
`How do I get there? These are questions
`commonly asked by all drivers. The Etak
`Navigator is an accurate, low cost
`informative vehicle navigation system
`designed to answer these questions.
`
`and
`
`The Navigator operates on a
`combination of dead reckoning
`matching. map matching eliminates the
`accumulation of error attendant in all
`dead reckoning systems.
`
`The Navigator utilizes an on-board
`digital map data base which serves as
`input for the map matching process for
`finding the location
`of selected street
`addresses and for display.
`
`Key to the Navigator's utility is its
`
`
`
`
`
` ability to conveniently locate
`
`and map-
`destinations.
`desired destination may
`A
`be specified by the intersection
`of two
`streets, a street and house address,
`o r a
`point on a single street. A street name
`index is used by the driver to select the
`desired street. Multiple choices having
`different street suffixes
`(e.g. street,
`avenue) and city abbreviations are
`presented when needed to resolve
`the map
`ambiguities. The Navigator uses
`and
`data base to locate the destination
`display it as a flashing star along with
`the current vehicle position o n a suitably
`scaled map.
`Distance and direction-to-go
`information are also constantly maintained
`moves. In
`on the screen as the vehicle
`this way,
`if
`the driver subsequently
`selects a map scale which does not contain
`the destination, range
`and
`bearing
`information is still available.
`
`o f navigation and
`
`The combination
`digital map technology opens new
`and
`opportunities for useful products
`services. Future special maps with Yellow
`Page information and routing will help
`individual drivers.
`An office-based map
`workstation can solve fleet routing
`problems or serve as the control center
`for real-time monitoring and dispatching
`of delivery o r emergency service vehicles.
`
`359
`
`Google Ex. 1023
`
`

`

`Figure 2
`
`Figure 3
`
`be entered,
`Multiple locations may
`by city or
`permanently stored and sorted
`distance. With this feature a driver may
`initially enter all appointments for the
`day and proceed to them in an orderly
`fashion.
`
`The Navigator shows the driver the
`relevant road network between current
`position and destination. The prioritized
`to
`road structure enables the operator
`select an efficient route
`and unexpected
`detours or traffic situations can
`be
`easily accommodated.
`
`The Navigator was designed with the
`multi-task driving function
`in mind. The
`high contrast screen provides all
`pertinent information in one easy-to-view
`location. The heading-up presentation
`compliments the driver’s intuitive sense
`of orientation. The prioritized map and
`dynamic labeling algorithm minimize
`display complexity enabling the driver to
`extract pertinent information at a glance.
`The information is available earlier and
`more continuously than when relying on
`passing road signs; giving the driver
`
`
`
`
`
`
`added flexibility in performing
`tasks.
`navigational
`combined with the clear graphical
`destination, enable
`presentation of the
`the driver to proceed to an unfamiliar
`destination
`wi th efficiency and
`confidence.
`
`These factors
`
`HARDWARE
`
`roof and headliner or is mounted
`rear window.
`
`on the
`
`Wheel sensors comprise str
`rubberized magnetic tape adhered
`inside of two wheels. and small f
`cored coils clamped to the suspension.
`The non-driven wheels are used to avoid
`slip errors caused
`by poor traction or
`high speed driving.
`
`ips of
`t o the
`errous-
`
`The tape drive is placed within
`convenient reach of the driver. Program
`and map data base are stored on specially
`manufactured cassettes similar to audio
`3.5 MBytes
`cassettes. A
`cassette stores
`and reads data at 200 kilobits per second.
`Each cassette covers an area comparable to
`that covered by two typical paper street
`maps. For example, three cassettes cover
`the greater San Francisco, Oakland, San
`Jose area.
`Highways over a larger area
`are included on each cassette.
`
`7 7 0 by 1000
`A vector
`
`vector display of
`A
`equivalent resolution is presented on
`either a 4 . 5
`inch CRT.
`or 7
`display is used rather than raster
`scanning the entire display surface,
`because the vector display does not
`
`
`
`
`
`exhibit aliasing, offers greater
`
`brightness for similar phosphors and
`excitation voltages and eliminates the
`requirement for a large bit-mapped memory
`and a high-speed graphics processor. The
`CRT housing contains 1 2 buttons which are
`soft-labeled for ease of use.
`
`The hardware includes a compass, wheel
`sensors, a cassette transport, an
`electronic display and a processor. The
`compass is a two-axis flux-gate
`
`
`
`
`
`magnetometer which is digitally
`
`compensated during initial calibration.
`This solid state compass
`is small, about
`the size of a pill box, and slips between
`
`The above components are connected to
`a trunk mounted processor unit, about the
`size of a small shoe box and made from a
`rugged aluminum extrusion. The processor
`unit houses three boards containing an
`8 0 8 8 CPU, 2563 DRAM, 16K EPROM, 2K CMOS
`static RAM, power supply and supporting
`digital and analog circuitry. The
`
`360
`
`Google Ex. 1023
`
`

`

`of the
`Navigator is connected to the vehicle's optionsy and accuracy estimates
`30 watts with ignition current DR
`battery and draws
`position.
`The key to system
`on and 0.12 watts under standby.
`performance is proper updating.
`
`of
`
`The Navigator hardware is capable
`near instant-on operation. While the
`display and program take about one minute
`to be fully operational, navigation starts
`within five seconds of vehicle ignition.
`Current position and calibration constants
`are stored in non-volatile memory. The
`program stored in ROM is used to boot in
`the program from cassette and to navigate
`in the interim. By storing the program
`along with the map
`on cassette, future
`enhancements in navigation and added
`features can be easily made available.
`
`Erroneous updates destroy the
`positional accuracy and may cause the
`system to become lost
`(i.e., consistently
`showing the vehicle on the wrong street).
`By executing map matching every few
`seconds, significant DR errors are not
`In addition, the
`allowed to accumulate.
`algorithm is designed only to perform map
`updates when reasonably certain the update
`will be correct. This enables the system
`to work well even when the vehicle is
`driven off the mapped roads, for example
`in parking lots, driveways
`o r o n new
`streets.
`
`NAVIGATION
`
`Performance
`
`The system navigates by a combination
`of dead reckoning and map matching.
`
`Dead Reckoning
`
`The compass measures heading and the
`wheel sensors are used to measure both
`distance and relative heading. This
`relative heading information is combined
`with the absolute heading information from
`the compass. Use
`of two independent
`of
`heading sources allows the effects
`be
`magnetic anomalies and wheel skids to
`A new dead reckoned
`minimized.
`(DR)
`position is thus computed each second from
`the previous position and the new distance
`and heading information. As with any dead
`reckoning system, errors in position
`accumulate in proportion to sensor
`inaccuracies and distance travelled.
`
`Map Matching
`
`By comparing the vehicle's track to
`the digital map, the Navigator eliminates
`the accumulated error that results from
`dead reckoning.
`For example, if the
`vehicle is driving in a straight path and
`the map contains a nearby straight road
`with a corresponding heading, the
`Navigator updates the DR position to a new
`estimated position along the
`road. The
`new position is more accurate than the
`DR
`position only
`the direction
`i n
`perpendicular to the road.
`When the
`vehicle subsequently turns a corner,
`drives around a curve, and the Navigator
`makes a new update, errors are eliminated
`in the remaining direction.
`
`or
`
`The example above provides a
`simplified description of some aspects of
`the navigation algorithms
`used.
`The
`Navigator uses other parameters in making
`decisions to update to the road network
`stored on the map.
`These parameters
`include the connectivity
`of the road
`network, analysis
`of ambiguous update
`
`Navigator performance was evaluated
`quantitatively on over 40,000 miles of
`vehicles and
`test
`driving in
`1 5
`qualitatively in over 4 0 0 , 0 0 0 miles in 5 0
`vehicles.
`Samples collected at random
`intersections showed an average
`50 foot
`accuracy while the Navigator was matched
`A more significant
`to the road network.
`measure is a demonstrated average in
`excess of 1 2 0 miles between map matching
`mistakes requiring manual
`reset.
`Once
`lost, the Navigator can be reset in under
`2 0 seconds. Keeping the Navigator
`on-
`track is thus less time consuming than
`operating a car radio.
`
`Calibration
`
`The Navigator is initially calibrated
`during installation. The installer is
`instructed to perform simple driving
`maneuvers during which sensor measurements
`are processed to compute compass
`compensations for the vehicle's magnetic
`effects and distance coefficients for each
`wheel.
`
`The Navigator uses comparisons between
`the map and the DR track to continually
`improve the calibrations during routine
`driving.
`F o r example if the DR track
`generally is "long" compared to the map,
`is corrected. This
`the wheel calibration
`compensates for tire diameter changes due
`to tread wear.
`The compass is likewise
`continually corrected through comparisons
`with known headings from the map data
`base.
`
`DIGITAL MAP DATA BASE
`
`The Navigator requires map information
`to update its dead reckoning display, to
`compute destination positions
`and for
`display. In order to meet
`the many map
`requirements, a topologically structured
`
`361
`
`Google Ex. 1023
`
`

`

`SUMMARY
`
`The Etak Navigator has been described
`with emphasis placed on its accurate
`navigation, low cost design achieved
`of digital maps,
`through innovative use
`and its informative display approach. The
`Navigator is indicative of taking the
`technology and information explosion onto
`the nation's roads. Future applications
`are many and varied; each in part will
`I? Where
`answer the questions; Where am
`i s my destination? How do I get there?
`
`a
`
`digital map data base is used. Such
`system defines significant points, lines
`and areas, along with their incidence
`relations. Unlike
`a digital map image,
`this map structure can be compactly stored
`and easily searched, modified, and
`manipulated. Cultural and geographic
`features can be associated to any data
`item. Examples include elevations linked
`to points, street names linked to lines,
`and terrain features or city names linked
`to areas.
`
`is
`
`To support the Navigator, Etak
`developing a
`digital map data base
`covering the
`USA.
`The Census Bureau's
`is used as the primary
`digital map file
`street name and address
`source
`of
`information. Coordinates are obtained
`from either United States Geological
`Survey topographical maps, or from aerial
`photographs. Approximately one half of
`in US metropolitan areas have
`the roads
`been digitized using
`a mapping process
`which provides approximately
`a three fold
`
`
`
`
`
`
`improvement in productivity over
`conventional techniques.
`
`An accurate and up-to-date nationwide
`digital map data base has many
`applications beyond in-vehicle navigation.
`Applications include routing, paper map
`publishing, matching address fields to
`coordinates, enhanced Yellow Pages and
`aids t o marketing, billing, field asset
`management and travel itinerary functions.
`
`AUTOHATIC VEHICLE LOCATION
`
`Perhaps the most direct application of
`the data base
`a fleet of
`is in linking
`Navigator equipped vehicles to
`a central
`control or dispatch center. By connecting
`the Navigator's optional RS232C interface
`to a digital radio, position and status
`messages can be automatically radioed to
`map
`headquarters. There with
`a
`workstation, the dispatcher can monitor in
`real time the whereabouts of the fleet,
`take new calls and quickly and reliably
`dispatch the closest vehicle. The
`by
`dispatch instructions can be conveyed
`radio back to the vehicle
`to appear
`unambiguously on its screen - again aiding
`response time.
`
`In non-real time applications
`a map
`workstation can be used to input a fleet's
`daily deliveries. Clustering and routing
`algorithms can aid the dispatcher in
`efficient utilization of the fleet. Once
`a vehicle's route is established it may be
`down-loaded to
`a memory cartridge, given
`to the driver and plugged into the
`vPhicle's Navigator for efficient, hastle
`free deliveries.
`
`362
`
`Google Ex. 1023
`
`

`

`
`
`Figure 1
`
`Google EX. 1023
`
`Google Ex. 1023
`
`

`

`Figure 3
`
`Google Ex. 1023
`
`Google Ex. 1023
`
`