`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` (cid:9)
`
`
`
`
`
`
`
`
`
`
` (cid:9)
`
`
`
`
`
`
`
` (cid:9)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` (cid:9)
` (cid:9)
` (cid:9)
` (cid:9)
`
`
` (cid:9)
` (cid:9)
` (cid:9)
` (cid:9)
` (cid:9)
` (cid:9)
` (cid:9)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` (cid:9)
` (cid:9)
`
`
`
` (cid:9)
`
` (cid:9)
`
`
`
`
`
`
`
` (cid:9)
`
`
`
`
`
` (cid:9)
`
`
`
`
`
` (cid:9)
`
`
`
`
`
`
`
` (cid:9)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` (cid:9)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` (cid:9)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` (cid:9)
`
`
`
`
`
`
`
`
`
`
`
`
`
` (cid:9)
`
`
`
`
`
`
`
`
`
`
`
`
`
` (cid:9)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` (cid:9)
`
`
` (cid:9)
`
` (cid:9)
` (cid:9)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` (cid:9)
`
`
`
`
` (cid:9)
` (cid:9)
`
`
`
` (cid:9)
`
`
`
`
`
` (cid:9)
`
`
`
` (cid:9)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` (cid:9)
`
` (cid:9)
`
` (cid:9)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` (cid:9)
`
` (cid:9)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` (cid:9)
`
`Page 1 of 18
`
`Unified Patents Exhibit 1004
`
`

`

`
`
` (cid:9)
`
`
`
`
`
` (cid:9)
`
`
`
`
`
`
`
` (cid:9)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` (cid:9)
`
`
`
`Page 2 of 18
`
`Unified Patents Exhibit 1004
`
`

`

`
`
` (cid:9)
`
`
`
`
`
` (cid:9)
`
`
`
`
`
`
`
` (cid:9)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` (cid:9)
`
` (cid:9)
`
` (cid:9)
`
` (cid:9)
`
` (cid:9)
` (cid:9)
`
`
`
`
`
`
`
`
`
` (cid:9)
`
` (cid:9)
`
` (cid:9)
`
` (cid:9)
`
`
`
`
`
`
`
` (cid:9)
`
` (cid:9)
`
` (cid:9)
`
` (cid:9)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Page 3 of 18
`
`Unified Patents Exhibit 1004
`
`

`

`
`
` (cid:9)
`
`
`
`
`
` (cid:9)
`
`
`
` (cid:9)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Page 4 of 18
`
`Unified Patents Exhibit 1004
`
`

`

`
`
` (cid:9)
`
`
`
`
`
` (cid:9)
`
`
`
`
`
`
`
` (cid:9)
`
`
`
`
`
`
`
`
`
`
`
`Page 5 of 18
`
`Unified Patents Exhibit 1004
`
`

`

`
`
` (cid:9)
`
`
`
`
`
` (cid:9)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Page 6 of 18
`
`Unified Patents Exhibit 1004
`
`(cid:9)
`

`

`
`
` (cid:9)
`
` (cid:9)
`
` (cid:9)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` (cid:9)
`
` (cid:9)
`
` (cid:9)
`
` (cid:9)
`
`
`
` (cid:9)
`
` (cid:9)
`
` (cid:9)
`
`
`
` (cid:9)
`
` (cid:9)
`
` (cid:9)
`
` (cid:9)
`
` (cid:9)
`
` (cid:9)
`
` (cid:9)
`
`
`
`
`
`Page 7 of 18
`
`Unified Patents Exhibit 1004
`
`(cid:9)
`

`

`
`
`US 6,401,027 B1
`
`
`
`
`
`1
`REMOTE ROAD TRAFFIC DATA
`
`
`
`
`COLLECTION AND INTELLIGENT
`
`
`VEHICLE HIGHWAY SYSTEM
`
`
`
`TECHNICAL FIELD
`
`
`This invention relates to traffic data collection and intel-
`
`
`
`
`
`
`
`
`in
`ligent routing systems for highway vehicles and,
`
`
`
`
`
`
`
`particular, to a system and method for remotely collecting
`
`
`
`
`
`
`
`real-time traffic data and providing traffic forecasts and
`
`
`
`
`
`
`
`travel guidance for drivers of vehicles equipped to utilize the
`
`
`
`
`
`
`
`
`
`system.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`BACKGROUND OF THE INVENTION
`
`
`
`
`Modern automobile travel is plagued by excessive traffic
`
`
`
`
`
`
`
`congestion due to continuously increasing automobile use.
`
`
`
`
`
`
`Drivers constantly seek optimum travel routes to minimize
`
`
`
`
`
`
`
`driving time. Local area radio and television stations trans-
`
`
`
`
`
`
`
`
`mit traffic alerts to inform drivers of blocked or congested
`
`
`
`
`
`
`
`
`
`traffic routes so that drivers familiar with alternate routes to
`
`
`
`
`
`
`
`
`
`their respective destinations can alter their planned route to
`
`
`
`
`
`
`
`
`minimize driving time. This, however, is often unproductive
`
`
`
`
`
`
`
`and results in increased travel
`time. Such traffic alerts
`
`
`
`
`
`
`
`
`disadvantageously require real-time reception by drivers
`
`
`
`
`
`prior to entering a congested traffic area. Traffic alerts are
`
`
`
`
`
`
`
`
`often missed because drivers are not
`tuned to the right
`
`
`
`
`
`
`
`
`
`station at the proper time. Besides, drivers tend to learn and
`
`
`
`
`
`
`
`
`
`
`routinely follow the same route day after day without
`
`
`
`
`
`
`
`
`becoming familiar with alternate routes even when they
`
`
`
`
`
`
`
`encounter heavy recurring congestion.
`
`
`
`
`Roadside signs are also used to warn drivers and re-direct
`
`
`
`
`
`
`
`
`
`
`traffic during road construction or traffic congestion. For
`
`
`
`
`
`
`
`
`example, detour signs and electronic roadside billboards are
`
`
`
`
`
`
`
`
`used to suggest or require alternate routes. Some electronic
`
`
`
`
`
`
`
`
`
`billboards are located on main traffic arteries, warning of a
`
`
`
`
`
`
`
`
`
`pending traffic blockage or congestion. However, signs and
`
`
`
`
`
`
`
`
`billboards are usually too near the point of congestion or
`
`
`
`
`
`
`
`
`
`
`blockage to enable meaningful re-evaluation of a planned
`
`
`
`
`
`
`
`route, primarily because of the required close proximal
`
`
`
`
`
`
`
`
`relationship between the location of the sign and the point of
`
`
`
`
`
`
`
`
`
`
`
`congestion or blockage. There exists a continuing need to
`
`
`
`
`
`
`
`
`improve the collection of accurate traffic congestion data in
`
`
`
`
`
`
`
`
`
`order to provide accurate route planning information.
`
`
`
`
`
`
`
`Governmental agencies provide emergency care service
`
`
`
`
`
`in response to roadside vehicle accidents, as is well known.
`
`
`
`
`
`
`
`
`
`Governmental agencies in North America have adopted the
`
`
`
`
`
`
`
`well-known “911” emergency call system through which
`
`
`
`
`
`
`road accidents are reported to enable emergency care ser-
`
`
`
`
`
`
`
`
`vices including police,
`fire and paramedic services to
`
`
`
`
`
`
`
`respond. The 911 emergency system relies on the reporting
`
`
`
`
`
`
`
`
`of accidents by private citizens who are typically either
`
`
`
`
`
`
`
`
`witnesses to an accident or are involved in the accident.
`
`
`
`
`
`
`
`
`
`However, when victims are incapacitated by injury, or when
`
`
`
`
`
`
`
`
`witnesses are unable to quickly locate a telephone, the 911
`
`
`
`
`
`
`
`
`system fails. Moreover, critical
`time is often lost while
`
`
`
`
`
`
`
`
`searching for a telephone to place the 911 call. In addition,
`
`
`
`
`
`
`
`
`
`misinformation may be inadvertently given by victims or
`
`
`
`
`
`
`
`witnesses unfamiliar with the location of an accident,
`
`
`
`
`
`
`
`thereby directing the emergency care providers to a wrong
`
`
`
`
`
`
`
`location. There therefore exists a need for a system to more
`
`
`
`
`
`
`
`
`expeditiously provide accurate vehicle traffic accident infor-
`
`
`
`
`
`
`mation to emergency care providers.
`
`
`
`
`
`Automobiles have also been equipped with experimental
`
`
`
`
`
`
`
`local area road-map systems which display a portion of a
`
`
`
`
`
`
`
`
`map of interest but do not use a global positioning system
`
`
`
`
`
`
`
`
`
`
`(GPS) to determine a vehicle position on the map. The driver
`
`
`
`
`
`
`
`
`
`
`is enabled to locate departure and destination points on the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`10
`
`
`
`15
`
`
`
`20
`
`
`
`25
`
`
`
`30
`
`
`
`35
`
`
`
`40
`
`
`
`45
`
`
`
`50
`
`
`
`55
`
`
`
`60
`
`
`
`65
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`2
`map, and then visually refers to the displayed map to see the
`
`
`
`
`
`
`
`
`
`
`
`current position of the vehicle as the driver travels toward
`
`
`
`
`
`
`
`
`
`the destination point. The map system displays a cursor to
`
`
`
`
`
`
`
`
`indicate the current position of a moving vehicle on the
`
`
`
`
`
`
`
`
`display map. The portion of the map that is displayed is
`
`
`
`
`
`
`
`
`
`
`periodically adjusted to keep the current position cursor in
`
`
`
`
`
`
`
`
`the center of the displayed map. The system uses a compass
`
`
`
`
`
`
`
`
`
`and a wheel sensor odometer to determine the current
`
`
`
`
`
`
`
`position as the vehicle travels on the road. The use of this
`
`
`
`
`
`
`
`
`
`
`
`map display system requires the driver to repetitively study
`
`
`
`
`
`
`
`
`the map and then mentally determine and select
`travel
`
`
`
`
`
`
`
`
`routes, directing attention away from the safe operation of
`
`
`
`
`
`
`
`
`the vehicle. This does not promote safe vehicle operation.
`
`
`
`
`
`
`
`
`Besides,
`the compass and wheel odometer technology
`
`
`
`
`
`
`causes map position error drifts, requiring re-calibration
`
`
`
`
`
`
`after travelling only a few miles. Moreover, the use of such
`
`
`
`
`
`
`
`
`
`a map system disadvantageously requires the entry of the
`
`
`
`
`
`
`
`
`departure point each time the driver begins a new route.
`
`
`
`
`
`
`
`
`Additionally, this map system does not perform route guid-
`
`
`
`
`
`
`
`
`ance and is not dynamically updated with current traffic
`
`
`
`
`
`
`
`
`information. There therefore exists a need to improve map
`
`
`
`
`
`
`
`systems with a driver friendly interface which reduces
`
`
`
`
`
`
`diversion away from the safe operation of the vehicle.
`
`
`
`
`
`
`
`
`
`Certain experimental integrated dynamic vehicle guid-
`
`
`
`
`
`ance systems have been proposed. For example, Motorola
`
`
`
`
`
`
`
`has disclosed an intelligent vehicle highway system in block
`
`
`
`
`
`
`
`
`diagram form in a 1993 brochure, and DELCO Electronics
`
`
`
`
`
`
`
`has disclosed another intelligent vehicle highway system,
`
`
`
`
`
`
`also in block diagram form, in Automotive News published
`
`
`
`
`
`
`
`
`on Apr. 12, 1993. These systems use compass technology for
`
`
`
`
`
`
`
`
`vehicle positioning. However, displacement wheel sensors
`
`
`
`
`
`are plagued by tire slippage, tire wear and are relatively
`
`
`
`
`
`
`
`
`
`inaccurate, requiring re-calibration of a current vehicle posi-
`
`
`
`
`
`
`tion. Compasses suffer from drift, particularly when driving
`
`
`
`
`
`
`
`on a straight road for an extended period of time. These
`
`
`
`
`
`
`
`
`
`intelligent vehicle highway systems appear to use GPS
`
`
`
`
`
`
`
`satellite reception to enhance vehicle tracking on road-maps
`
`
`
`
`
`
`
`as part of a guidance and control system. GPS data is used
`
`
`
`
`
`
`
`
`
`
`to determine when drift errors become excessive and to
`
`
`
`
`
`
`
`
`indicate that re-calibration is necessary. However, the GPS
`
`
`
`
`
`
`
`data is not used for automatic re-calibration of a current
`
`
`
`
`
`
`
`
`vehicle position. These intelligent vehicle highway systems
`
`
`
`
`
`
`also use RF receivers to receive dynamic road condition
`
`
`
`
`
`
`
`
`information for dynamic route guidance, and contemplate
`
`
`
`
`
`
`infrastructure traffic monitoring, for example, a network of
`
`
`
`
`
`
`road magnetic sensing loops, and contemplate the RF broad-
`
`
`
`
`
`
`
`
`casting of dynamic traffic conditions for route guidance. The
`
`
`
`
`
`
`
`
`
`disclosed two-way RF communication through the use of a
`
`
`
`
`
`
`
`
`transceiver suggests a dedicated two-way RF radio data
`
`
`
`
`
`
`
`system. While two-way RF communication is possible, the
`
`
`
`
`
`
`
`
`flow of information between the vehicles and central sys-
`
`
`
`
`
`
`
`
`tems appears to be exceedingly lopsided. It appears that the
`
`
`
`
`
`
`
`
`
`amount of the broadcast dynamic traffic flow information
`
`
`
`
`
`
`
`from a central
`traffic radio data control system to the
`
`
`
`
`
`
`
`
`vehicles would be far greater than the information transmit-
`
`
`
`
`
`
`
`
`ted from the vehicles to the central traffic control center,
`
`
`
`
`
`
`
`
`
`since the system is only used to report roadside incidents or
`
`
`
`
`
`
`
`
`
`
`accident emergency messages to the control center.
`
`
`
`
`
`
`
`To overcome the above disadvantages, US. Pat. No.
`
`
`
`
`
`
`
`5,504,482 entitled AUTOMOBILE NAVIGATION
`
`
`
`GUIDANCE, CONTROL AND SAFETY SYSTEM, which
`
`
`
`
`
`issued to K. D. Schreder on Apr. 2, 1996, discloses an
`
`
`
`
`
`
`
`
`
`
`automobile route guidance system. In this system, an auto-
`
`
`
`
`
`
`
`
`mobile is equipped with an inertial measuring unit and GPS
`
`
`
`
`
`
`
`
`
`satellite navigational unit and a local area digitized street
`
`
`
`
`
`
`
`map system for precise electronic positioning and route
`
`
`
`
`
`
`
`guidance between departures and arrivals. The system is
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Page 8 of 18
`
`Unified Patents Exhibit 1004
`
`Page 8 of 18
`
`Unified Patents Exhibit 1004
`
`

`

`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` (cid:9)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` (cid:9)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Page 9 of 18
`
`Unified Patents Exhibit 1004
`
`(cid:9)
`

`

`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` (cid:9)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` (cid:9)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Page 10 of 18
`
`Unified Patents Exhibit 1004
`
`

`

`
`
`US 6,401,027 B1
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`7
`
`three satellites in the field of view of any pertinent place on
`
`
`
`
`
`
`
`
`
`
`
`
`the earth. The precise position of a point can be determined
`
`
`
`
`
`
`
`
`
`
`by measuring the time required for the positioning signals of
`
`
`
`
`
`
`
`
`
`
`at least three satellites to reach that point. The GPS satellites
`
`
`
`
`
`
`
`
`
`
`
`42 transmit global positioning information to the GPS
`
`
`
`
`
`
`
`
`receivers 22 installed in the vehicles 20. Each receiver 22
`
`
`
`
`
`
`
`
`
`
`interprets the signals from three or more satellites 42 and
`
`
`
`
`
`
`
`
`
`
`determines a geographical position with an accuracy within
`
`
`
`
`
`
`
`an average of 20 meters, which is considered to be a
`
`
`
`
`
`
`
`
`
`
`positioning error. Differential GPS systems may provide
`
`
`
`
`
`
`
`even greater accuracy using geographic benchmark correc-
`
`
`
`
`
`
`tion.
`
`The existence of this error means that a geographical
`
`
`
`
`
`
`
`position of a vehicle moving on a road derived using the
`
`
`
`
`
`
`
`
`GPS information may appear to be located, for example, in
`
`
`
`
`
`
`
`
`
`a ditch or even within a roadside building. To correct the
`
`
`
`
`
`
`
`
`
`vehicle position, a method of converting this geographical
`
`
`
`
`
`
`position to a location on a corresponding digitized road
`
`
`
`
`
`
`network map has been developed and will be described
`
`
`
`
`
`
`
`
`below.
`
`A vehicle support sub-system 30 is provided in the
`
`
`
`
`
`
`
`
`in-vehicle device 21. It includes a road network locator 32
`
`
`
`
`
`
`
`
`(hereinafter locator 32) and a road explorer 34. A mobile
`
`
`
`
`
`
`
`
`radio sub-system 24 is provided for exchanging radio fre-
`
`
`
`
`
`
`
`
`quency data with the traffic service center 60 via the com-
`
`
`
`
`
`
`
`
`
`
`munication station 50. Also included in the in-vehicle device
`
`
`
`
`
`
`
`
`21 are a computer system 26 for operating the sub-systems
`
`
`
`
`
`
`
`
`and storing the digitized road network map. A driver inter-
`
`
`
`
`
`
`
`
`
`face 28 includes a microphone, data entry pad, screen
`
`
`
`
`
`
`
`display and loud-speaker to permit drivers to interact with
`
`
`
`
`
`
`
`
`the in-vehicle device 21.
`
`
`
`
`The locator 32 computes the geographical location of the
`
`
`
`
`
`
`
`
`vehicle, using data received from the GPS receiver 22, and
`
`
`
`
`
`
`
`
`
`converts it to a position on the digitized road network map,
`
`
`
`
`
`
`
`
`
`which is broadcast from the traffic service center 60 via the
`
`
`
`
`
`
`
`
`
`
`communication station 50 and stored in the computer system
`
`
`
`
`
`
`
`
`26. From time to time,
`the mobile radio sub-system 24
`
`
`
`
`
`
`
`
`
`transmits vehicle position data processed by the locator 32
`
`
`
`
`
`
`
`
`to the communication station 50 which forwards road traffic
`
`
`
`
`
`
`
`
`data reported from all vehicles 20 travelling the roadway
`
`
`
`
`
`
`
`
`system 10 to the traffic service center 60 for further pro-
`
`
`
`
`
`
`
`
`
`
`cessing. The processed data is used for forecasting road
`
`
`
`
`
`
`
`
`traffic conditions. The mobile radio system 24 in the vehicle
`
`
`
`
`
`
`
`
`
`20 also receives data broadcast by the communication
`
`
`
`
`
`
`
`station 50. The broadcast data includes digitized road net-
`
`
`
`
`
`
`
`
`work map and traffic forecasts. The data received by the
`
`
`
`
`
`
`
`
`
`mobile radio sub-system 24 is stored by the computer
`
`
`
`
`
`
`
`
`system 26 and the road network explorer 34 uses the data in
`
`
`
`
`
`
`
`
`
`
`
`conjunction with driver’s instructions received from the
`
`
`
`
`
`
`driver interface 28 to provide intelligent route guidance. The
`
`
`
`
`
`
`
`
`intelligent route guidance, such as an optimum travel route
`
`
`
`
`
`
`
`
`based on real-time traffic conditions, is displayed on the
`
`
`
`
`
`
`
`
`screen display (not shown) of the driver interface 28.
`
`
`
`
`
`
`
`
`
`For the purpose of location reports and route guidance, the
`
`
`
`
`
`
`
`
`
`digital road network map includes only intersections and
`
`
`
`
`
`
`
`road segments, each road segment having an indicated traffic
`
`
`
`
`
`
`
`
`direction. The size of a digitized road network map is
`
`
`
`
`
`
`
`
`proportional to the size of the area it represents, densely
`
`
`
`
`
`
`
`
`
`populated areas having more roads. To map an area, for
`
`
`
`
`
`
`
`
`
`example, with a population of around one million, a road
`
`
`
`
`
`
`
`network of about 10,000 intersections and 40,000 one-way
`
`
`
`
`
`
`
`traffic road segments is required. It is assumed that about 20
`
`
`
`
`
`
`
`
`
`
`bytes are required to map each intersection, and each road
`
`
`
`
`
`
`
`
`
`segment in each traffic direction. Therefore, one megabyte is
`
`
`
`
`
`
`
`
`required to digitize the road network of a metropolitan area
`
`
`
`
`
`
`
`
`of that size. It is not necessary to store a map of the entire
`
`
`
`
`
`
`
`
`
`
`
`
`continental roadway system in vehicles because metropoli-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`8
`tan areas are separated from one another and are connected
`
`
`
`
`
`
`
`
`
`by the continental expressway system. Digitized road net-
`
`
`
`
`
`
`
`work maps may therefore broadcast on a regional basis and
`
`
`
`
`
`
`
`
`each vehicle keeps only two digitized road network maps at
`
`
`
`
`
`
`
`
`
`any time. One is the continental expressway network map
`
`
`
`
`
`
`
`
`and the other is a local regional/metropolitan roadway
`
`
`
`
`
`
`network map. As a vehicle travels from one region to
`
`
`
`
`
`
`
`
`another, it moves away from a previous roadway network
`
`
`
`
`
`
`
`using the continental expressway network map. Meanwhile,
`
`
`
`
`
`
`it receives a new roadway network map of the upcoming
`
`
`
`
`
`
`
`
`region.
`
`The in-vehicle device also includes a means that allows
`
`
`
`
`
`
`
`the driver to report an emergency. The driver may simply
`
`
`
`
`
`
`
`
`
`press an emergency button if an emergency arises. When the
`
`
`
`
`
`
`
`
`
`emergency button is pressed, the in-vehicle device automati-
`
`
`
`
`
`
`
`cally sends an emergency report to the traffic service center
`
`
`
`
`
`
`
`
`
`with the vehicle’s current position.
`
`
`
`
`
`FIG. 3 illustrates the configuration of the traffic service
`
`
`
`
`
`
`
`center 60. A data exchange interface 62 is provided for
`
`
`
`
`
`
`
`
`
`connection of the communication station 50 for receiving
`
`
`
`
`
`
`
`the vehicle position data and sending data respecting the
`
`
`
`
`
`
`
`
`digitized road network maps and real-time traffic forecast
`
`
`
`
`
`
`
`data which are to be broadcast. An external party interface
`
`
`
`
`
`
`
`
`
`64 is provided to connect the external party data sources 70
`
`
`
`
`
`
`
`
`
`
`to receive real-time information about weather or road
`
`
`
`
`
`
`
`conditions. The real-time information is processed by an
`
`
`
`
`
`
`
`external party data integrator 65 for
`incorporation into
`
`
`
`
`
`
`
`real-time traffic forecasts. The traflic forecasts are computed
`
`
`
`
`
`
`
`by a traffic forecaster 68 using the collected vehicle position
`
`
`
`
`
`
`
`
`data for normal road conditions. The collected vehicle
`
`
`
`
`
`
`
`position data received from the data exchange interface 62
`
`
`
`
`
`
`
`
`is stored in a database 66 to be processed by the traffic
`
`
`
`
`
`
`
`
`
`
`forecaster 68. Atraffic service center (TSC) server 67 is also
`
`
`
`
`
`
`
`
`
`
`provided for running the traffic forecaster 68 as well as
`
`
`
`
`
`
`
`
`
`storing the digitized road network maps and temporarily
`
`
`
`
`
`
`
`storing the real-time traffic forecasts. An operator interface
`
`
`
`
`
`
`
`including hardware and software for map entry and
`69,
`
`
`
`
`
`
`
`
`maintenance, system supervision, etc. permits operators to
`
`
`
`
`
`
`interact with the system 8.
`
`
`
`
`
`Aroadway system 10 is illustrated in FIG. 4. The roadway
`
`
`
`
`
`
`
`
`
`
`system 10 includes a plurality of roads indicated by refer-
`
`
`
`
`
`
`
`
`ence numeral 11. Generally, cach road 11 supports two-way
`
`
`
`
`
`
`
`
`traffic, permitting vehicles to travel in opposite directions.
`
`
`
`
`
`
`
`Each one-way road, indicated by reference 12, illustrates the
`
`
`
`
`
`
`
`
`traffic direction allowed on the road. As described above, the
`
`
`
`
`
`
`
`
`
`roadway system 10 is digitized to form a map. The digital
`
`
`
`
`
`
`
`
`
`map includes only intersections and road segments oriented
`
`
`
`
`
`
`
`in the traffic direction in order to maintain a data size
`
`
`
`
`
`
`
`
`
`appropriate for broadcast and storage by the computer
`
`
`
`
`
`
`
`system 26 of an in-vehicle device 21. A digitized road
`
`
`
`
`
`
`
`
`
`network map 13 representing the roadway system 10 of FIG.
`
`
`
`
`
`
`
`
`
`4 is illustrated in FIG. 5. The digitized road network map 13
`
`
`
`
`
`
`
`
`
`
`
`is an abstract representation of a roadway system which
`
`
`
`
`
`
`
`includes intersections, road segments, parking lots, ramps,
`
`
`
`
`
`
`bridges, overpasses, tunnels, highways and special points.
`
`
`
`
`
`
`Although there are many physical elements in a roadway
`
`
`
`
`
`
`
`system, there are only two classes of elements represented in
`
`
`
`
`
`
`
`
`
`the digital road network map 13: nodes 14 and links 16
`
`
`
`
`
`
`
`
`
`
`indicating a traffic direction. The node 14 may represent an
`
`
`
`
`
`
`
`
`intersection of two or more roads, an entry to a parking lot,
`
`
`
`
`
`
`
`
`
`
`a junction of a highway with an entry or exit ramp, a starting
`
`
`
`
`
`
`
`
`
`
`or an endpoint of a bridge, a tunnel, an overpass or an
`
`
`
`
`
`
`
`
`
`arbitrary location on a road. A link 16 represents a road
`
`
`
`
`
`
`
`
`segment with an orientation indication, which connects two
`
`
`
`
`
`
`
`nodes 14 of the road network. A node from which a link
`
`
`
`
`
`
`
`
`
`
`originates is called a source node of the link and a node at
`
`
`
`
`
`
`
`
`
`
`which a link terminates is called a sink node. Further, the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`10
`
`
`
`15
`
`
`
`20
`
`
`
`25
`
`
`
`30
`
`
`
`35
`
`
`
`40
`
` (cid:9)
`
`45
`
`
`
`50
`
`
`
`55
`
`
`
`60
`
`
`
`65
`
`
`
`Page11of18
`
`Unified Patents Exhibit 1004
`
`Page 11 of 18
`
`Unified Patents Exhibit 1004
`
`

`

`
`
`US 6,401,027 B1
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`9
`link is said to be an outgoing link of the source node and an
`
`
`
`
`
`
`
`
`
`
`
`
`
`incoming link of the sink node.
`
`
`
`
`
`
`When a road segment supports only one-way traffic, the
`
`
`
`
`
`
`
`road segment may be represented by one link having an
`
`
`
`
`
`
`
`
`
`orientation that is the same as the traffic direction on the road
`
`
`
`
`
`
`
`
`
`
`
`segment. When a road segment supports two-way traffic, this
`
`
`
`
`
`
`
`road segment
`is represented by two oppositely oriented
`
`
`
`
`
`
`
`links.
`
`A road segment may be either straight or curved. In the
`
`
`
`
`
`
`
`
`
`
`digitized road network representation, however, all links are
`
`
`
`
`
`
`
`straight. Therefore, necessary adjustments are required to
`
`
`
`
`
`
`make the digitized road network map more meaningful.
`
`
`
`
`
`
`
`When a road segment is curved, arbitrary nodes may be
`
`
`
`
`
`
`
`
`inserted to create several shorter straight links. Criteria may
`
`
`
`
`
`
`
`
`be established for determining which curves may be repre-
`
`
`
`
`
`
`
`
`sented as a straight link, and which ones must be segmented
`
`
`
`
`
`
`
`
`
`into a plurality of straight links. For example, a straight line
`
`
`
`
`
`
`
`
`may be used to represent a curve C if Ls/Lc is sufficiently
`
`
`
`
`
`
`
`
`
`
`close to 1, wherein Lc is the length of the curve C and Ls is
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`the length of a straight line connecting end points of the
`
`
`
`
`
`
`
`
`
`curve C. A predetermined ratio, such as 0.97, for example,
`
`
`
`
`
`
`
`
`
`may be used. If 0.97<Ls/Lc<1, the curve C may be repre-
`
`
`
`
`
`
`
`
`
`
`sented as one straight link.
`
`
`
`
`
`FIG. 6 illustrates a slope angle, (X, of each link used in
`
`
`
`
`
`
`
`
`
`vehicle location calculations. Each link 16 has a source node
`
`
`
`
`
`
`
`
`NA and a sink node NB in the digitized road network map
`
`
`
`
`
`
`
`
`
`
`13. An imaginary link 15 is created in a due east orientation.
`
`
`
`
`
`
`
`
`
`
`The slope angle (X of the link 16 is determined by computing
`
`
`
`
`
`
`
`
`
`
`the angle of rotation between the link 16 and the imaginary
`
`
`
`
`
`
`
`
`
`
`link 15. The slope angle (X of the link 16 is between 0° and
`
`
`
`
`
`
`
`
`
`
`
`
`=180°. It is represented as a positive angle if the link 16 is
`
`
`
`
`
`
`
`
`
`
`
`in an upper quadrant with respect to the imaginary link 15,
`
`
`
`
`
`
`
`
`
`
`and as a negative angle if the link 16 is in a lower quadrant
`
`
`
`
`
`
`
`
`
`
`
`with respect to the imaginary link 15. The slope angle of
`
`
`
`
`
`
`
`
`
`
`each link provides a basis for correctly locating a vehicle on
`
`
`
`
`
`
`
`
`the digitized road network map 13.
`
`
`
`
`
`
`In FIG. 7, node 14 represents an intersection of two roads
`
`
`
`
`
`
`
`
`
`
`
`that are represented by four links 16, A1 to A4. Point P
`
`
`
`
`
`
`
`
`
`
`
`
`represents a current geographical position derived from GPS
`
`
`
`
`
`
`
`information and the node 14 is a last known node that the
`
`
`
`
`
`
`
`
`
`
`
`vehicle passed, as determined from previous steps of the
`
`
`
`
`
`
`
`
`
`vehicle locating process. An imaginary position link 17 is
`
`
`
`
`
`
`
`
`
`created from the last known node 14 to the current position
`
`
`
`
`
`
`
`
`
`
`
`P. Slope angles of the position link 17 and each of links A1
`
`
`
`
`
`
`
`
`
`
`
`
`
`to A4 are calculated using the method described above. In
`
`
`
`
`
`
`
`
`
`
`this example, the slope angle of a position link 17 is [3, the
`
`
`
`
`
`
`
`
`
`
`
`
`slope angles of links A1 to A4 are 0°, 90°, 180° and —90°,
`
`
`
`
`
`
`
`
`
`
`
`
`
`respectivel