US005933100A
`P
`Numb
`[11]
`atent Number:
`
`
`
`
`
`
`[45] Date of Patent:
`
`
`
`5,933,100
`
`
`
`Aug. 3, 1999
`
` I
`
`United States Patent
`
`
`
`
`Golding
`
`[19]
`
`
`
`[54] AUTOMOBILE NAVIGATION SYSTEM WITH
`
`
`
`
`DYNAMIC TRAFFIC DATA
`
`
`
`
`
`
`[75]
`
`
`
`[73]
`
`
`Inventor: Andrew R. Golding, Cambridge, Mass.
`
`
`
`
`
`
`
`Assignee: Mitsubishi Electric Information
`
`
`
`
`Technology Center America, Inc.,
`
`
`
`Cambridge, Mass.
`
`
`
`
`
`5,689,252 11/1997 Ayanoglu el ale ooeeecccccecee 340/905
`
`
`
`
`
`Primary Examiner—Thomas Mullen
`
`
`
`Assistant Examiner—Anh La
`
`
`
`
`
`Attorney, Agent, or Firm—Dirk Brinkman
`
`
`
`
`
`
`
`[57]
`
`ABSTRACT
`
`
`
`
`
`
`[21]
`[22]
`
`
`[51]
`[52]
`
`
`[58]
`
`
`
`
`[56]
`
`
`
`
`Appl. No.: 08/579,003
`
`Filed:
`Dec. 27, 1995
`
`
`
`
`
`
`
`
`
`Unt, C18 ieee eecceccecceesseeteeteececessesneseess GO8G 1/123
`
`
`
`US. Cheeee 340/995; 340/990; 340/988;
`
`
`
`701/208; 701/213
`
`
`
`
`
`
`Field of Search.
`.. 340/995, 990,
`.....
`
`
`
`
`
`340/989, 988, 994, 905; 364/449.1, 449.2,
`
`
`
`
`
`
`449.5, 449.4; 701/207, 208, 211, 213
`
`
`
`
`
`
`
`
`References Cited
`
`
`U.S. PATENT DOCUMENTS
`
`
`
`5,089,826
`2/1992 Yano et al. ccsceresees 340/995 K&
`
`
`tees 364/449.5
`6/1993 Kirson oe
`5,220,507
`
`s. 340/905
`5/1994 Martell et al.
`5,317,311
`
`
`
`
`
`
`. 340/995 X
`.
`11/1994 Kashiwazaki
`5,365,449
`
`
`
`
`
`
`. 340/995
`5,371,678 12/1994 Nomura ....
`
`
`
`
`
`
`. 340/905
`§,402,117
`3/1995 Zijerhand ..
`
`
`
`
`
`9/1995 Yurimotoet al
`340/995 &
`5,450,343
`
`
`
`
`
`
`5,452,217
`9/1995 Kishi et al.
`...
`340/095 X&
`
`
`
`
`
`
`
`
`5,473,324 12/1995 Ueno......
`. 340/990
`
`
`
`6/1996 Peterson .
`. 340/005
`5,523,950
`
`
`
`
`..
`5,539,398
`7/1996 Hall et al.
`. 340/907
`
`
`340/995 X
`7/1996 Mandhyanctal.
`5,539,645
`. 340/995
`8/1996 Behretal. .
`5,543,789
`
`
`
`
`
`
`
`340/095 X
`3/1997 Gaziset al.
`5,610,821
`
`
`
`
`
`
`5,648,768—7/1997 Bouve wecccccscsscsccnseeesenecseneees 340/988
`32 Claims, 2 Drawing Sheets
`
`
`
`
`
`
`
`
`
`
`A system located in an automobile provides personalized
`
`
`
`
`
`
`
`traffic information and route planning capabilities. This
`
`
`
`
`
`
`
`system uses equipment which is becoming standard in
`
`
`
`
`
`
`
`
`automobiles, such as on-board navigation systems and cel-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`lular telephones. On-board navigation systems use global
`positioning system (GPS)satellites to position the automo-
`
`
`
`
`
`
`
`
`bile with respect
`to sireels in a map database. As the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`automobile moves, the navigation system updates the loca-
`tion. A central database includestravel time information for
`
`
`
`
`
`
`
`
`eachstreet segment and transition between street segments
`
`
`
`
`
`
`
`
`in the map databasc. Based uponthe travel time information
`
`
`
`
`
`
`
`
`
`in the database, a route from a current location to a desired
`
`
`
`
`
`
`
`
`destination, or series of destinations, can be planned in order
`
`
`
`
`
`
`to have a minimum travel time. The route can be provided
`
`
`
`
`
`
`
`
`
`to the on-board navigation system, which then directs the
`
`
`
`
`
`
`
`
`
`driver in traveling the route. The cellular telephone in the
`
`
`
`
`
`
`
`
`automobile can be used for communicating with the central
`
`
`
`
`
`
`
`
`database to obtain travel times for route planning. In order
`
`
`
`
`
`
`
`to provide dynamic travel time information to the central
`
`
`
`
`
`
`
`database, each automobile in the system operates as a data
`
`
`
`
`
`
`
`collector. As various street segmentsare traversed, the travel
`
`
`
`
`
`
`
`
`time for each segmentis recorded. The travel time andstreet
`
`
`
`
`
`
`
`
`
`
`segment informationis periodicallytransferred to the central
`
`
`
`
`
`
`database through the cellular telephone connection. The
`
`
`
`
`
`
`
`central database then combines the travel time data from
`
`
`
`
`
`
`
`
`
`each automobile to create accurate travel time data for each
`
`
`
`
`
`
`
`
`
`street segment.
`
`
`
`
`
`
`INFORMATION
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`LOCATION
`
`
`
`
`
`
`
`
`ON-BOARD
`
`
`NAVIGATION
`
`
`
`
`SYSTEM
`
`
`
`
`
`
`
`
`, ROUTE SEGMENT,
`
`TP
`TRAVEL TIME
`
`
`
`
`
`
`| BEST ROUTE INFO/
`O-
`
`| TRAFFIC WARNINGS
`NS
`
`
`
`
`
`
`
`
`
`
`AB
`
`
`ROUTE
`
`ADVISOR
`TRAVEL
`TIME INFO
`
`
`
`
`
`
`
`
`'
`
`
`
`.
`
`
`
`
`WIRELESS
`DEVICE
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` . COMMUNICATION
`
`
`
`
`
`
`
`
`
`Page 1 of 8
`
`Unified Patents Exhibit 1006
`
`Page 1 of 8
`
`Unified Patents Exhibit 1006
`
`

`

`U.S. Patent
`
`Aug. 3, 1999
`
`Sheet 1 of 2
`
`5,933,100
`
`
`
`
`
` ILVadN3IsVvaVLVaSsa13aIM7avl
`
`poo-eeeeeeeeeeeeeeee
`
`ISVaVLVd
`
`WALI
`
`JINdIDOdd
`
`
`
`JINGIDOUdNOLLVOINNWWOD
`
`JDIAI
`
`TAVaL
`
`
`
`OJNISWIL
`
`
`
`
`
`/OANIILNOS1S39
`
`
`
`SONINAVMSiddval
`
`
`
`"INJWO4SALNOY
`
`
`
`IWILTSAVaL
`
`SalVd
`
`Viva
`
`YOLOINOD
`
`
`
`LNIW9ISINOS
`
`NOLLVWaOJNI
`
`NOILV901
`
`davOg-NO
`
`NOILVOIAVN
`
`W3LSAS
`
`Page 2 of 8
`
`Unified Patents Exhibit 1006
`
`Page 2 of 8
`
`Unified Patents Exhibit 1006
`
`
`
`
`
`
`
`
`

`

`
`U.S. Patent
`
`
`
`
`
`Aug. 3, 1999
`
`
`Sheet 2 of 2
`
`5,933,100
`
`
`
`OSL
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ZBld
`
`
`WNS
`
`
`
`JIVNOS
`Viva
`
`vivd
`
`wns
`dIgWNN
`
`
`StlOrlc}02
`
`SINIOdViva|13aN10D|193T10D|GYVGNVIS|T3AVUL|LNIWDIS1439a1S
`
`
`SELoflS2lOZlSLLoll
`
`IMAJdAL|NOILLVIAIQ|aWILSSHILNaG!
`
`
`
`
`
`
`
`
`
`roo|ool
`|001|oot
`
`Page 3 of 8
`
`Unified Patents Exhibit 1006
`
`Page 3 of 8
`
`Unified Patents Exhibit 1006
`
`

`

`
`
`2
`1
`travel destination and the travel times stored in the database.
`AUTOMOBILE NAVIGATION SYSTEM WITH
`
`
`
`
`
`
`
`
`
`
`
`
`DYNAMIC TRAFFIC DATA
`
`
`
`
`
`
`
`
`However, the patent does not describe how the information
`
`
`
`
`
`
`
`
`
`
`
`in the database can be obtained. It suggests that dynamic
`FIELD OF THE INVENTION
`
`
`
`
`
`
`
`
`
`
`traffic information can be obtained throughatraffic inter-
`
`
`
`
`
`
`
`
`face. A traffic interface may receive digital broadcast over
`
`
`
`
`
`
`
`radio sidebands, or from centralized cellular phone systems
`
`
`
`
`
`
`containing information ontraffic obstacles such as accidents
`
`
`
`
`
`
`
`and amountsofthe resulting delays. However, no suggestion
`
`
`
`
`
`
`
`is made as to how such dynamic information is collected or
`
`
`
`
`
`
`
`
`
`organized for
`transfer to the system in the vehicle.
`
`
`
`
`
`
`
`
`Therefore, a need exists for a system which provides for
`
`
`
`
`
`
`
`collection, organization and dissemination oftraffic infor-
`
`
`
`
`
`
`
`
`mation which can be used in a route planning and navigation
`
`system.
`
`
`
`
`
`
`
`U.S. Pat. No. 5,459,667, assigned to Sumitomo Electric
`
`
`
`
`
`
`Industries, Ltd., is another example of a vehicle navigation
`
`
`
`
`
`
`
`
`
`system. The system disclosed in this patent provides for
`more accurate vehicle location determinations and a capa-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`bility to determine whether the vehicle is traveling on an
`
`
`
`
`
`
`
`
`optimum route between starting and ending locations. As
`
`
`
`
`
`
`
`with the previously-described system, this system uses a
`
`
`
`
`
`
`
`database having information relating to street segments and
`
`
`
`
`
`
`
`
`
`times in order
`to estimate the optimum route.
`travel
`
`
`
`
`
`
`
`Preferably, the travel information is stored in a CD ROM.
`
`
`
`
`
`
`
`Since the information is stored in a CD ROM, itis not easily
`
`
`
`
`
`
`
`
`changeable and cannot be adjusted for changes in travel
`
`
`
`
`
`
`
`
`times resulting from changes in road conditions. Again,this
`system does not determine how to create the database, to
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`determinetravel time, or how to adjusttravel time to account
`for traffic conditions.
`
`
`
`
`
`
`
`
`The Illinois Department of Transportation is developing a
`
`
`
`
`
`
`
`system, called ADVANCE (Advanced Driver and Vehicle
`
`
`
`
`
`
`Advisory Navigation ConcEpt). The ADVANCEsystem is
`
`
`
`
`
`
`
`described in several articles including “Operation of the
`
`
`
`
`
`
`
`ADVANCETraffic Information Center” by Jeffrey Hoch-
`
`
`
`
`
`
`
`muth (Jan. 25, 1995) and “ADVANCE-Initial Deployment”
`
`
`
`
`
`
`
`
`
`by Joseph S. Ligas and Syde Bowott, ITS America, 1995
`
`
`
`
`
`
`Annual Conference (March, 1995). A traffic information
`
`
`
`
`
`
`
`
`
`center collects and organizes traffic data from a variety of
`sources. These sources include a closed looptraffic signal
`
`
`
`
`
`
`
`
`system, a cellular based motorist call-in system, a motorist
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`assistance system, and emergency dispatch systems. The
`information is used to create historical databases and a CD
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ROMoftravel data. Each vehicle is provided with a mobile
`
`
`
`
`
`
`
`navigation assistant, which provides route planning using
`
`
`
`
`
`
`
`
`
`
`both static and dynamic travel time data. Static data are
`
`
`
`
`
`
`
`
`provided by the CD ROM. The mobile navigation system
`
`
`
`
`
`
`
`provides route planning and navigational information simi-
`lar to the systems described above. In addition to static
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`information, the mobile navigation assistance communicates
`
`
`
`
`
`
`
`
`with the traffic information center through a radio frequency
`
`
`
`
`
`
`communications network to obtain dynamictraffic informa-
`tion data. The dynamictraffic data can be used for more
`
`
`
`
`
`
`
`
`
`
`
`accurate route planning, or for rerouting based upon new
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`information. The ADVANCEsystem also anticipates using
`
`
`
`
`
`
`
`
`vehicles as traffic probes to provide real time traffic infor-
`mation. The vehicles would transmit data to the traffic
`
`
`
`
`
`
`
`
`
`information center over the radio frequency communica-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`tions network on recently traversed streets in the system.
`Thetraffic information center would combine this informa-
`
`
`
`
`
`
`
`
`tion with the traffic information from other sources in
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`creating its dynamic traffic data. Although the ADVANCE
`
`
`
`
`
`
`
`
`system is still being developed and the descriptions are
`
`
`
`
`
`
`
`incomplete, several disadvantages are apparent in the sys-
`
`
`
`
`
`
`
`tem. Significant additional equipment
`is needed in the
`
`
`
`
`
`
`
`vehicle to operate the system. Much of this equipment is
`
`
`
`
`
`
`
`duplicative of functions performed by other equipment
`
`10
`
`
`
`15
`
`
`
`20
`
`25
`
`
`
`30
`
`35
`
`
`
`40
`
`45
`
`
`
`50
`
`55
`
`
`
`60
`
`65
`
`
`
`5,933,100
`
`
`
`
`
`
`
`
`
`
`
`
`
`The present invention relates to a system for providing
`
`
`
`
`
`
`
`traffic report
`information, route planning assistance, and
`
`
`
`
`
`navigational assistance to automobiles. Moreparticularly,it
`
`
`
`
`
`
`
`relates to a system having a central database in which travel
`
`
`
`
`
`
`time information is updated periodically from automobiles
`
`
`
`traveling in the system.
`BACKGROUND OF THE INVENTION
`
`
`
`
`
`
`
`
`
`
`
`
`
`Traffic reports on the radio or television provide useful
`
`
`
`
`
`
`
`information to travelers about accidents, heavy traffic,
`construction, and other conditions which can cause increases
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`in expected travel
`times. This information is broadcast
`
`
`
`
`
`
`
`periodically, but may not be readily available when a person
`
`
`
`
`
`
`
`
`actually needs a report. Additionally, such reports only cover
`
`
`
`
`
`
`
`
`major highways and commuting routes. Often, drivers expe-
`
`
`
`
`
`
`
`
`rience significant delays on routes which are not reported in
`
`
`
`
`
`
`
`
`any traffic reports. Therefore, it would be useful for drivers
`
`
`
`
`
`
`
`
`
`to be able to obtain accuratetraffic reports covering the roads
`
`
`
`they intendto travel.
`
`
`
`
`
`
`
`In addition to difficulties in providing useful reports, news
`
`
`
`
`
`
`
`agencies have difficulty in acquiring relevant traffic infor-
`
`
`
`
`
`
`
`
`
`
`mation for the roads which they do cover. Often,
`traffic
`
`
`
`
`
`
`information is based upon personal observations
`report
`
`
`
`
`
`
`
`
`provided to a news agency. News agencies have been using
`
`
`
`
`
`
`
`
`
`helicopters in order to monitor the major highways for
`
`
`
`
`
`
`
`
`significant backups and delays. They also use information
`
`
`
`
`
`
`
`
`
`provided to them from actual drivers as to delays, traffic
`
`
`
`
`
`
`
`
`conditions and travel times. Such sources cannot provide
`particularly useful information or objective data as to the
`
`
`
`
`
`
`
`
`
`
`
`likely extent of delays intraffic.
`Various attempts have been made to create automated
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`systems for determining traffic information, and to provide
`
`
`
`
`
`
`
`
`more objective estimates of traffic flow. For example, U.S.
`Pat. No. 5,465,289 discloses a method and apparatus for
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`determining vehiculartraffic information using existing cel-
`
`
`
`
`
`
`
`lular telephone technology. Sensors are used to monitor
`
`
`
`
`
`
`cellular telephone communication information. Data from
`the cellular communications are extracted and analyzed to
`
`
`
`
`
`
`
`determine vehicle locations and travel
`information. The
`
`
`
`
`
`
`
`
`
`
`
`
`
`system requires a statistical model for determining location
`
`
`
`
`
`
`
`
`
`of automobiles within each cell of the cellular system. As
`
`
`
`
`
`
`
`
`with news reports, this system only provides information
`
`
`
`
`
`
`
`relating to major thoroughfares, and cannot provide infor-
`
`
`
`
`
`mation relating to individual street segments.
`
`
`
`
`
`
`
`
`In addition to traffic report information, systems have
`
`
`
`
`
`
`
`
`
`been and are being developed for providing route planning
`
`
`
`
`
`
`
`information and navigational assistance to drivers. One such
`
`
`
`
`
`
`
`system is illustrated in U.S. Pat. No. 5,272,638, assigned to
`
`
`
`
`
`
`Texas Instruments Incorporated. This system includes a
`
`
`
`
`
`
`
`
`digital road map database providing information about road
`
`
`
`
`
`
`
`
`segments, intersections, and travel times for road segments.
`
`
`
`
`
`
`
`Information in the database is used to plan routes having
`minimal travel time from one location to another. More
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`efficient route planning is obtained by using a route hierar-
`
`
`
`
`
`
`
`
`
`chy of local areas around the starting and ending locations,
`
`
`
`
`
`
`
`
`major thoroughfares between local areas, and major free-
`
`
`
`
`
`
`
`waysfor longertravel distances. Preferably, vehicle location
`information can be determined using satellite systems or
`
`
`
`
`
`
`
`some other positioning method. Instructions can then be
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`provided audibly or visually to the driver when turns are
`
`
`
`
`
`
`
`
`necessary in the travel plan. This patent provides sugges-
`tions for a process for determining a route based upon the
`
`
`
`
`
`
`
`
`
`
`Page 4 of 8
`
`Unified Patents Exhibit 1006
`
`Page 4 of 8
`
`Unified Patents Exhibit 1006
`
`

`

`5,933,100
`
`
`
`
`4
`
`
`
`
`
`
`
`
`In a preferred embodiment the central database can then
`
`
`
`
`
`
`
`
`be updated using information received from the automobile
`
`
`
`
`
`
`
`
`data collection. Preferably, the travel time in the database
`
`
`
`
`
`
`
`would include a moving average having a certain numberof
`
`
`
`
`
`
`
`
`data points or a specific time period. As traffic becomes more
`
`
`
`
`
`
`
`
`congested,
`the travel
`times reported by the automobiles
`
`
`
`
`
`
`
`
`would increase, and the moving average would become
`
`
`
`
`
`
`
`
`greater. As traffic became less congested, the reported times
`
`
`
`
`
`
`
`
`would decrease and the moving average would similarly be
`
`
`
`
`
`
`
`
`reduced. The numberof data points or time period used in
`
`
`
`
`
`
`
`
`
`producing the moving average could be varied by street
`
`
`
`
`
`
`
`segments depending upon the frequency of use of the street
`segment. In addition, the central database can determine a
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`standard deviation for travel times on the street segments.
`The standard deviation information can be used to omit data
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`points which appear erroneous. Data points caused by brief
`delays on a travel segment can also be omitted to prevent
`
`
`
`
`
`
`
`
`
`
`
`skewing of the data.
`BRIEF DESCRIPTION OF THE DRAWING
`
`
`
`
`
`
`
`3
`
`
`
`
`
`
`
`already present in many vehicles. The radio communications
`
`
`
`
`
`
`
`
`equipment would need specific frequencies and may inter-
`
`
`
`
`
`
`
`fere with other radio communications. Additionally, no
`
`
`
`
`
`
`
`method for combining dynamic data from automobiles with
`
`
`
`
`
`
`
`other information relating to potentialtraffic delays is indi-
`cated. The use of additional information may cause distor-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`tion of the dynamictraffic data unless the effect of the traffic
`
`
`
`
`
`
`
`
`conditions from the outside sources can be accurately
`
`
`
`
`
`
`
`
`reflected in the travel times used for route planning.
`
`
`
`
`
`
`Furthermore, each of the navigation systems described
`
`
`
`
`
`
`
`
`
`above include only travel times for various street segments.
`
`
`
`
`
`
`
`
`Often, delays are caused by transitions betweenstreet seg-
`ments.
`
`
`SUMMARYOF THE INVENTION
`
`
`
`
`
`
`
`
`
`
`The present invention provides a system for personalized
`
`
`
`
`
`
`
`
`traffic reports and route planning using dynamically updated
`
`
`
`
`
`
`travel information in conjunction with equipment currently
`
`
`
`
`
`
`
`found in automobiles. Many new automobiles include as
`
`
`
`
`
`
`standard equipment an on-board navigation system. Such a
`
`
`
`
`
`
`
`
`
`system usesstatic travel time data in connection with street
`
`
`
`
`
`
`data to provide navigational information to the operator of
`
`
`
`
`
`
`
`
`the automobile. Typically, GPS satellites are used to locate
`
`
`
`
`
`
`
`
`the automobile within the street system of the navigation
`
`
`
`
`
`
`
`system. A map of the surrounding streets can then be
`
`
`
`
`
`
`
`displayed to the operator. Sometimes, such systems also
`
`
`
`
`
`
`
`include route planning information. If not already included
`
`
`
`
`
`
`
`
`in the on-board navigation system, in one embodiment, the
`
`
`
`
`
`
`
`present invention would include a route planning system
`which uses the travel time information to determine a route
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`having minimum travel time, or meeting othercriteria.
`
`
`
`
`
`
`
`
`In conjunction with the navigation system in the
`automobile, in one embodiment, a central database would
`
`
`
`
`
`
`collect and store travel time information for the various
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`street segments. When updated, the travel time information
`can be transferred from a central database to the individual
`
`
`
`
`
`
`
`
`
`
`
`
`automobiles. Preferably,
`the information is transferred
`through a wireless communication device, such as a cellular
`
`
`
`
`
`
`
`
`
`
`
`
`
`telephone. Since automobiles often include a cellular tele-
`phone as standard or add-on equipment, and a cellular
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`network is already in place in most cities,
`the present
`
`
`
`
`
`
`
`
`
`invention can make use of this existing equipment. The
`
`
`
`
`
`
`
`automobile would merely require a modem in order to
`receive data from the central database. In addition to includ-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ing time for traversing street segments, the database would
`
`
`
`
`
`
`
`
`also include times for transitions between segments. The
`
`
`
`
`
`
`
`transition times between segments would include different
`
`
`
`
`
`
`
`
`times for people proceeding through an intersection to a
`
`
`
`
`
`
`
`following street segment or turning onto adjoining street
`segments. The use of transition times can assist in more
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`accurately reflecting travel time and determining optimum
`routes. Alternatively,
`the street segments can be defined
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`between midpoints of blocks, which can include turns.
`In addition to providing navigation assistance, in a pre-
`
`
`
`
`
`
`
`ferred embodiment, the navigation system can be used to
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`determine travel time data for adjusting the travel times in
`
`
`
`
`
`
`
`
`the central database. Since the navigation system determines
`the location of the automobile with respect to street seg-
`
`
`
`
`
`
`
`
`
`ments of a map database, the movement of the automobile
`
`
`
`
`
`
`
`on various street segments can be collected. A timer, which
`
`
`
`
`
`
`
`
`can include the existing clock in the automobile, can be used
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`for determining timesfor traversing the street segments. The
`times for transitions between street segments can also be
`
`
`
`
`
`
`
`
`
`determined. Oncethe data are collected,it can be transferred
`
`
`
`
`
`
`
`to the central database through the same wireless commu-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`nication device, 1.e., the cellular telephone. The data can be
`
`
`
`
`
`
`collected and then transferred at periodic intervals.
`
`10
`
`
`
`15
`
`
`
`20
`
`25
`
`
`
`30
`
`35
`
`
`
`40
`
`45
`
`
`
`50
`
`55
`
`
`
`60
`
`65
`
`
`
`
`
`
`
`
`
`
`
`These and other features of the Subject Invention will be
`
`
`
`
`
`
`
`better understood in connection with the Detailed Descrip-
`
`
`
`
`
`
`
`tion taken in conjunction with the Drawings of which:
`
`
`
`
`
`
`FIG. 1 illustrates an embodiment of the route planning
`
`
`
`
`
`
`and navigation system of the present invention.
`
`
`
`
`
`
`FIG. 2 represents storage of travel time information in a
`
`
`
`
`
`
`
`central database in conjunction with the system of FIG. 1.
`DETAILED DESCRIPTION
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`As illustrated in FIG. 1, the route planning and navigation
`
`
`
`
`
`
`
`system of the present invention includes a vehicle navigation
`
`
`
`
`
`
`
`system 1 and a central database 2. The vehicle navigation
`
`
`
`
`
`
`
`system 1 is located on each automobile within the system.
`
`
`
`
`
`
`
`The vehicle navigation system 1 includes an on-board
`
`
`
`
`
`
`
`
`navigation system 10, which can include a standard system
`currently found on some automobiles. The on-board navi-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`gation system 10,
`includes a map database having data
`
`
`
`
`
`
`
`relating to street segments and intersections between street
`
`
`
`
`
`
`
`segments. The on-board navigation system 10 also includes
`
`
`
`
`
`
`
`
`sensors for receiving transmissions from GPSsatellites 3.
`
`
`
`
`
`
`
`An appropriately designed processor locates the automobile,
`using the satellite information, on the street segments in the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`map database. The on-board navigation system 10 can
`
`
`
`
`
`
`
`
`provide information to the operator relating to the current
`
`
`
`
`
`
`
`position and a map of surrounding streets. The navigation
`system can also indicate when turns are to be made in
`
`
`
`
`
`
`
`
`
`
`accordance with a particular route.
`
`
`
`
`to a destination
`The best route from a starting point
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`location can be determined by the route advisor 13. The
`route advisor would include a database of travel
`time
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`information correspondingto the street segments in the map
`
`
`
`
`
`
`
`database. Alternative, in order to limit the required memory,
`
`
`
`
`
`
`
`
`
`
`the route advisor can have travel time information for only
`
`
`
`
`
`
`
`
`
`a portion of the map database in which the automobile is
`
`
`
`
`
`
`
`
`
`presently located. The route advisor could then obtain any
`additional travel time information from the central database,
`
`
`
`
`
`
`
`
`as needed. The route advisor can process the information in
`
`
`
`
`
`
`
`
`
`the database according to one of several known processesto
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`determine an optimal travel route from the starting to ending
`locations.
`
`
`
`
`
`
`
`
`As the on-board navigation system 10 monitors the loca-
`
`
`
`
`
`
`
`
`tion of the automobile, it outputs route segments which have
`been traversed. A timer 11 is used to determine a travel time
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`for each route segment. The clock in the automobile may be
`used as the timer 11. In addition to street segments, the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`system can include representations of transitions between
`
`Page 5 of 8
`
`Unified Patents Exhibit 1006
`
`Page 5 of 8
`
`Unified Patents Exhibit 1006
`
`

`

`
`
`6
`5
`
`
`
`
`
`
`
`Additionally, standard deviations for each route segment
`street segments. Transitions can also be timed to represent
`
`
`
`
`
`
`
`
`can also be determined. Standard deviations can be used for
`
`
`
`
`
`
`
`
`times for crossing intersections or making turns. The route
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`eliminating spurious data. Such data may be caused by a
`segments and travel timesare stored in the data collector 12,
`
`
`
`
`
`
`
`
`person stopping for a short period of time on a street
`to be used to update the travel time database.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`segmentora brief blockageofthe street segment. Individual
`
`
`
`
`
`
`
`The central database 2 is used for dynamically updating
`
`
`
`
`
`
`
`
`data which is significantly different from the stored travel
`
`
`
`
`
`
`
`
`travel time data based upon information collected from all of
`
`
`
`
`
`
`
`
`times may be discarded as being erroneous. If standard
`
`
`
`
`
`
`
`the vehicles in the navigation system. A wireless commu-
`nication device 14 is used to communicate between the
`
`
`
`
`
`
`
`deviations are being determinedbythe central database, then
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`each data point becomesrelevant, and the data collector in
`
`
`
`
`
`
`
`
`automobiles and the central database. Preferably, the wire-
`the automobiles should notfilter the data.
`less communications device 14 would be a cellular tele-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`FIG. 2 illustrates a potential format for the travel time data
`
`
`
`
`
`
`
`phone. Such devices are becoming standard in automobiles,
`
`
`
`
`
`
`
`
`
`20 in the central database 2. Each street segment 100 would
`
`
`
`
`
`
`and a cellular communication system is already in place in
`most cities. The wireless communication device 14 would
`
`
`
`
`
`
`
`include a unique street segment identifier 110 as discussed
`
`
`
`
`
`
`
`
`include a modem connectedto the data collector 12 and the
`
`
`
`
`
`
`
`
`
`above. The travel
`time 115 corresponding to the street
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`segment would be the mean or moving average of the
`
`
`
`
`
`
`
`
`route advisor 13 for transferring travel time information into
`
`
`
`
`
`
`
`
`
`received data. The standard deviation 120 may also be
`
`
`
`
`
`
`
`
`
`and out of the automobile. The modem will periodically call
`
`
`
`
`
`
`
`
`calculated and stored. Since different processed could be
`
`
`
`
`
`
`
`
`
`up the central database 2 and transfer information from the
`
`
`
`
`
`
`
`
`
`used to maintain data and determine the averagetravel time,
`data collector 12. In order to limit communication time, the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`the type of collection 125 (whether by time or number of
`
`
`
`
`
`
`
`
`data collector 12 will only provide the informationat certain
`
`
`
`
`
`
`
`
`
`data points), and the amountor value of the data collection
`
`
`
`
`
`
`
`
`time intervals, such as every five minutes. Additionally, the
`130 (minutes of duration or numberor data points) would be
`
`
`
`
`
`
`
`data collector 12 can compare the actual travel time to the
`
`
`
`
`
`
`
`
`
`
`estimated travel time in the route advisor 13 database. If the
`stored for each street segment. In order to determine a
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`measured travel time is within a certain threshold of the
`
`
`
`
`
`
`
`
`
`moving average, a buffer with a set of data points 135 is
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`maintained.
`In order to simplify the calculation of the
`
`
`
`
`
`
`
`
`currently estimated travel time, then the central database
`
`
`
`
`
`
`
`
`average and standard deviation, the number of data points
`may not need to be updated, and no call will be made or data
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`140, sum of the data points 145, and sum of the squares of
`
`
`
`
`
`
`transferred. If the cellular telephone is otherwise in use, or
`
`
`
`
`
`
`
`
`
`
`the data points 150 can also be determined and stored.
`
`
`
`
`
`
`
`
`
`the central database is busy, the data collector will refrain
`
`
`
`
`
`
`The database retrieval procedure 22 communicates with
`
`
`
`
`
`
`from sending a message at that time interval.
`
`
`
`
`
`
`
`the route advisor 13 in each of the automobiles to provide
`The central database 2 includes travel time data 20, a
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`updated travel time information for each route segment.
`
`
`
`
`
`
`
`database update procedure 21 and a databaseretrieval pro-
`
`
`
`
`
`
`
`
`Various alternatives can be used for updating travel times.
`
`
`
`
`
`
`
`
`
`
`cedure 22. The travel time data is illustrated more fully in
`When planning a route, the route advisor 13 can contact the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`FIG. 2. Since the map information is included in the
`
`
`
`
`
`
`
`central database 2 to obtain updated information for the
`
`
`
`
`
`
`on-board navigation system 10 of each automobile, it does
`
`
`
`
`
`
`
`locations of interest. Alternatively, the central database 2
`not need to be included in the central database 2. The central
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`may periodically dial up the automobile navigation system
`
`
`
`
`
`
`
`database merely includes street or
`transition segment
`1 to transfer travel time information. The travel time data-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`identifiers, and travel
`times. Alternatively, different map
`
`
`
`
`
`
`
`
`base mayalso be continuously broadcast through some type
`
`
`
`
`
`
`
`databases from different companies may be used in each
`of radio network to all
`the vehicles on the system.
`
`
`
`
`
`
`
`
`
`automobile. In such a situation, the central database may
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Additionally, the route advisor 13 can provide a proposed
`need a map database which will permit conversion to each
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`route to the central database, which will then update the
`
`
`
`
`
`
`
`
`of the different databases in automobiles. Each street seg-
`
`
`
`
`
`
`
`
`route advisor if significant changes occurin travel times for
`
`
`
`
`
`
`
`ment has a unique identifier, which corresponds to the
`
`
`
`
`
`
`
`street segments in the planned route. If significant changes
`
`
`
`
`
`
`
`
`identifier in the map database of the on-board navigation
`occur in travel times, the route advisor may chooseto replan
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`system 10. Associated with each street segment identifier is
`a new route from the current location to the destination in
`
`
`
`
`
`
`
`
`
`a determinedtravel time. Since travel times maybedifferent
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`order to avoid anytraffic tie-ups. A threshold for improve-
`in each direction, each direction of the street is considered
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`mentin estimated times should be used in determining when
`a separate identifier. Transition segments, such asaleft turn
`
`
`
`
`
`
`
`
`to make changes in a route. Otherwise, changes in routes
`
`
`
`
`
`
`
`from one segmentto another, is also provided with a travel
`
`
`
`
`
`
`
`
`
`
`
`
`
`could become confusing to the operator.
`
`
`
`
`
`
`
`
`time. The database update procedure 21 determines the
`Alternatively,
`the route advisor 13 can be located in
`
`
`
`
`
`
`
`
`
`travel times based upon travel data received from automo-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`conjunction with this central database 2. Each of the routes
`
`
`
`
`
`
`
`
`biles. Preferably, the travel times in the central database 2
`
`
`
`
`
`
`
`for the automobiles would be centrally determined. The
`
`
`
`
`
`
`would be moving averages, covering a predefined time
`route advisor 13 would then communicate with the cellular
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`period or numberof data points. Upon receiving information
`
`
`
`
`
`
`
`
`telephone 14 in the automobile to provide the route to the
`
`
`
`
`
`
`
`
`from a data collector 12, the database update procedure 21
`
`
`
`
`
`
`
`
`the
`on-board navigation system 10. For route planning,
`
`
`
`
`
`
`
`
`
`
`would eliminate the oldest data point for the identified route
`central database 2 would require a map database, as well as
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`segment, add the new data point, and redetermine the
`
`
`
`
`
`
`
`
`the time