(12) United States Patent
`Myr
`
`111111
`
`1111111111111111111111111111111111111111111111111111111111111
`US006480783Bl
`US 6,480, 783 Bl
`Nov. 12, 2002
`
`(10) Patent No.:
`(45) Date of Patent:
`
`(54) REAL TIME VEHICLE GUIDANCE AND
`FORECASTING SYSTEM UNDER TRAFFIC
`JAM CONDITIONS
`
`(75)
`
`Inventor: David Myr, Jerusalem (IL)
`
`(73) Assignee: Makor Issues and Rights Ltd.,
`Jerusalem (IL)
`
`( *) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(21) Appl. No.: 09/528,134
`Mar. 17, 2000
`
`(22) Filed:
`
`(51)
`
`Int. Cl? ......................... G06F 165/00; GOSG 1!09;
`H04Q 7/00
`
`(52) U.S. Cl. ....................... 701!117; 701!118; 340/995;
`340/990
`
`(58) Field of Search ................................. 701!117, 118,
`701/119, 213, 200, 201, 210, 211, 209,
`207, 208; 340/995, 905, 989, 990, 991,
`993, 994; 455/507, 509, 457
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`.............. 364/444
`9/1990 Savage et a!.
`4,954,958 A
`5,058,201 A * 10/1991 Ishii et a!.
`.................... 455/33
`
`(List continued on next page.)
`
`FOREIGN PATENT DOCUMENTS
`
`10/1996
`3/1999
`11/1998
`8/1995
`6/1998
`
`DE
`195 47 574 A1
`EP
`0 903 916 A2
`FR
`2 762 906
`wo 95/21435
`wo
`wo 98/27525
`wo
`Primary Examiner-Tan Nguyen
`Assistant Examiner---Dalena Tran
`(74) Attorney, Agent, or Firm-Stanley N. Protigal; Elman
`& Associates
`
`(57)
`
`ABSTRACT
`
`A system and method for real time vehicle guidance by
`Central Traffic Unit are presented. The proposed vehicle
`Guidance System includes a plurality of vehicles equipped
`with Individual Mobile Units including GPS units (position
`determining systems adapted to determine their present
`position) and communicatively linked to the Central Traffic
`Unit computer server. The Central Traffic Unit broadcasts
`the updated traffic patterns in real time thereby enabling the
`Individual Mobile Units to dynamically calculate the desired
`optimal travel paths. In response to a request from a driver
`for a route update from his present position to a desired
`destination, the Individual Mobile Unit searches for an
`optimal (usually fastest) route and shows it to the driver. In
`route searching by the minimal time criterion, the Individual
`Mobile Unit relies on estimated travel times stored in its
`database, and may also use current real time information on
`bottleneck situations received from Central Traffic Unit. The
`forecasting system allows the driver to enter alternative time
`schedules for the same destination and receive alternative
`travel time estimates for the same destination depending on
`the estimated traffic volumes on the roads at that particular
`time. The backbone of the system is a group of Sample
`Mobile Units equipped with RF transmitters that commu(cid:173)
`nicate their present position to the Central Traffic Unit at
`predetermined time intervals. The Central Traffic Unit uses
`those sample vehicles as antennas by tracking their positions
`for creating and maintaining a network of real time traffic
`load disposition in various geographical areas. To be able to
`detect a bottleneck situation when it arises and to estimate a
`current travel time for a corresponding section of road, the
`Central Traffic Unit maintains a list of sample vehicles that
`recently exited that section. If the times those vehicles have
`spent on the section differ considerably from a regular time
`stored in the database, Central Traffic Unit uses statistical
`tools for forecasting the future travel time along this section.
`Simultaneously, the Central Traffic Unit broadcasts updated
`travel times and any new information on current traffic jams
`and slow-down bottleneck situations in a given geographical
`location.
`
`23 Claims, 29 Drawing Sheets
`
`CMU
`Client Vehicles
`
`IP
`Multicasting
`
`

`

`US 6,480, 783 Bl
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`5,187,810 A * 2/1993 Yoneyama eta!. ........ 455/34.1
`5,420,794 A * 5/1995 James
`........................ 364/436
`5,539,645 A * 7/1996 Mandhyan eta!. ......... 364/438
`5,543,789 A
`8/1996 Behr et a!. .................. 340/995
`5,610,821 A * 3/1997 Gazis et a!.
`............. 364/444.2
`5,699,056 A * 12/1997 Yoshida ...................... 340/905
`
`5,797,330 A * 8/1998 Li ............................... 104/28
`5,822,712 A * 10/1998 Olsson ....................... 701!117
`5,911,773 A * 6/1999 Mutsuga eta!. ............ 701!200
`7/1999 Waizmann eta!. ......... 701!209
`5,919,246 A
`5,928,294 A * 7/1999 Zelinkovsky ............... 701!204
`6,150,961 A * 11/2000 Alewine et a!.
`............ 340/995
`6,163,751 A * 12/2000 Van Roekel ................ 701!210
`6,216,088 B1 * 4/2001 Schulz et a!. ............... 701!209
`
`

`

`U.S. Patent
`
`Nov. 12,2002
`
`Sheet 1 of 29
`
`US 6,480,783 Bl
`
`Fig. 1
`
`CMU
`Client Vehicles
`
`IP
`Multicasting
`
`~
`
`Traffic
`Congestion~
`Data
`
`0
`0
`0
`
`SMU
`Sample Vehicles
`
`CTU
`
`---GPs
`Data- -)
`
`41~ I
`0
`
`r;g=t~l@
`
`I
`
`0
`0
`
`\(
`~
`
`/
`
`/
`
`/
`
`/
`
`/
`
`/
`
`~- ~-~)
`
`~
`~
`
`~
`
`7\
`0//
`~/~1>
`//~'l')
`
`

`

`U.S. Patent
`
`Nov. 12, 2002
`
`Sheet 2 of 29
`
`US 6,480, 783 Bl
`
`Fig. 2
`
`Satellite
`
`IP Multicaster
`
`-=-t~---
`
`SMU Transmitter
`Modem
`
`GPS Unit
`
`Traffic
`Update
`
`CTU
`
`IMU Receiver
`
`

`

`U.S. Patent
`
`Nov. 12, 2002
`
`Sheet 3 of 29
`
`US 6,480, 783 Bl
`
`Fig. 3
`
`301
`
`I
`I
`I
`I
`\
`I
`I
`~
`
`SMU
`
`305
`
`302
`
`303
`Transmission
`t Modem
`
`~--------~
`
`304
`RF
`Transmission
`
`CTU
`
`

`

`U.S. Patent
`
`Nov. 12, 2002
`
`Sheet 4 of 29
`
`US 6,480, 783 Bl
`
`Fig. 4
`
`IMU
`
`410
`
`401
`
`I
`I
`I
`I
`I
`
`404
`Display
`
`~
`402
`GPS
`Unit
`
`411
`
`~ Modem
`
`RF 412,
`
`Transmission'
`
`:og IP-
`
`~ Multicast
`
`CTU
`
`405
`User
`Input
`
`403
`408
`r-. Processor._ Receiver
`
`406
`Map
`Map
`Database Updates
`
`407
`
`

`

`U.S. Patent
`
`Nov. 12,2002
`
`Sheet 5 of 29
`
`US 6,480,783 Bl
`
`Fig. Sa
`CMU Client 501
`GPS
`
`502 Client Input
`SP
`Start Pt
`
`50 3r-~-,.1ta---.-,-n­
`SP Zone
`Data
`
`Client Input 504
`DP
`End Pt
`
`tain 505
`DP Zone
`Data
`
`506
`
`To
`Fig. Sb
`Is
`SP Zone-r-Y_e_s~_S_l_O~
`P Zone
`?
`
`No
`507
`Algorithm
`z
`
`508
`
`Does
`No Route need
`Updating
`?
`
`Display
`heoretical Time-
`Route
`
`

`

`U.S. Patent
`
`Nov.12, 2002
`
`Sheet 6 of 29
`
`US 6,480, 783 Bl
`
`Fig. Sb
`
`CTU
`
`Obtain
`Road 'A'
`Data
`
`512
`Algorithm
`z
`
`No
`
`Does
`oute nee
`Updating
`?
`
`Obtai
`Road 'B
`Data
`
`516
`Algorithm
`z
`
`51"Z
`Does
`oute nee
`Updatin
`? .
`
`Display
`Yes
`'-----~Theoretical Tim
`Route
`
`

`

`U.S. Patent
`
`Nov.12, 2002
`
`Sheet 7 of 29
`
`US 6,480, 783 Bl
`
`Fig. 6
`
`602
`
`601
`
`GPS
`Position
`
`Request
`From User
`
`603
`"---
`Data Update
`From CTU
`
`605 Yes
`~
`Set Origin To
`User's Input
`
`Set Origin To
`GPS Position
`
`607
`608
`.-------___,;1__--~---,
`M u lti level
`r---'---=-'~-___,
`Map
`Planning
`AI orithm
`Database
`
`609
`
`Section Travel
`Time Managing
`Algorithm
`
`610
`
`Transform
`Solution Into
`Required Form
`
`

`

`U.S. Patent
`
`Nov.12, 2002
`
`Sheet 8 of 29
`
`US 6,480, 783 Bl
`
`Fig. 7
`
`701
`~
`Get Section S
`
`702
`,r--./
`
`703
`
`Put Long No
`Travel
`Time on S
`
`705
`
`Yes
`
`Culculate
`Travel Time
`For S
`
`Put
`Regular
`Time On S
`
`707
`To Route-
`~ Planning
`Algorithm
`
`

`

`U.S. Patent
`
`Nov. 12,2002
`
`Sheet 9 of 29
`
`US 6,480,783 Bl
`
`Fig. 8
`
`803
`
`CTU
`Server
`
`DataGram
`To
`Database
`
`801
`
`,-------=.__----,
`
`804
`Hand-held
`GPS
`Modem lf------tl Unit
`HDD
`A/V Display
`Modem
`
`IMU
`
`

`

`U.S. Patent
`
`Nov. 12,2002
`
`Sheet 10 of 29
`
`US 6,480,783 Bl
`
`Fig. 9
`
`901
`
`Travel Info:~
`I 907
`User Input
`I 908
`User Query
`
`l
`
`I Accidents
`1909
`Lower Str
`.
`+------' . - - - -1 I Accidents Query! 910
`I Road Closures 1911
`[ A/V Display:
`]
`JVoice Command~ 912
`.____ ___ ---..:::..~_____, I Channel Se I ect 1913
`
`

`

`U.S. Patent
`
`Nov. 12,2002
`
`Sheet 11 of 29
`
`US 6,480, 783 Bl
`
`Fig. 10
`
`Interstate
`Highway
`Type 1
`
`State
`Highway
`Type 2
`
`National
`Highway
`Type 3
`
`Major
`Street
`Type 4
`
`Local
`Street
`Type 5
`
`Category A
`
`Category B
`
`

`

`U.S. Patent
`
`Nov. 12,2002
`
`Sheet 12 of 29
`
`US 6,480, 783 Bl
`
`Fig. 11 a
`
`Obtain Map Data
`From CTU Database
`
`Identify Road Code
`
`Yes Place On Interstate
`Road List
`
`Yes
`
`Place On State
`Road List
`
`Yes Place On National
`Road List
`
`

`

`U.S. Patent
`
`Nov. 12,2002
`
`Sheet 13 of 29
`
`US 6,480,783 Bl
`
`Fig. 11 b
`
`Yes Place On Major
`Road List
`
`Yes r - - - - - - - - - - .
`Place Into
`Category A
`
`No
`
`Place Into
`Category 8
`
`

`

`U.S. Patent
`U.S. Patent
`
`Nov. 12, 2002
`Nov. 12, 2002
`
`Sheet 14 of 29
`Sheet 14 of 29
`
`US 6,480,783 B1
`US 6,480, 783 Bl
`
`Fig. 12
`Fig. 12
`
`,------------------------------,
`
`1
`
`/
`
`/
`
`/
`
`/
`
`11
`
`Google Exhibit 1007, Page 16 of 43
`
`
`
`5
`
`9
`
`6
`
`/
`
`t(J
`
`/
`
`'
`'
`'
`'
`'
`7~
`'
`'
`/
`'
`/
`~
`~
`L------------------------------~
`
`

`

`U.S. Patent
`
`Nov. 12, 2002
`
`Sheet 15 of 29
`
`US 6,480, 783 Bl
`
`Fig. 13
`
`1301
`~~------,
`Get Section S
`
`1303
`~
`
`1~ Yes
`Estimate CTT By
`Linear Regression
`1306
`~
`
`Put
`Individual
`RTT on S
`
`1308
`
`1307
`~Yes
`
`Put CTT on S
`
`Put MinTime
`on S
`
`To Route-Planning
`Algorithm
`
`1+ - - - - - - _ _ _ _ . l
`
`

`

`U.S. Patent
`
`Nov. 12, 2002
`
`Sheet 16 of 29
`
`US 6,480, 783 Bl
`
`Fig. 14a
`
`1401
`Receive GPS
`Info
`
`1402
`Statistical Times
`Processing
`
`1403
`Current Times
`Processing
`
`1404
`General Info
`
`Zone Info
`
`1406
`Map Info
`
`1407
`Administrator
`(Human Operator
`
`To Fig. 14b
`
`

`

`U.S. Patent
`
`Nov.12, 2002
`
`Sheet 17 of 29
`
`US 6,480, 783 Bl
`
`Fig. 14b
`
`From Fig. 14a
`I
`I
`
`+
`
`~
`Theoretical
`Times
`
`140 8 Theoretical
`Times
`
`140 9
`
`Statistica I
`Times
`I A I Roads
`I B I Roads
`Current
`Times
`I A' Roads
`141 1 Accident
`Reports
`
`141
`0
`
`141 2 Weather
`Reports
`
`..-I
`
`(])
`c
`0
`N
`
`-
`z
`-
`(])
`c
`0
`N
`
`Statistical
`Times
`1 A I Roads
`1 B 1 Roads
`Current
`Times
`I A I Roads
`Accident
`Reports
`
`Weather
`Reports
`
`I
`
`1413 + +
`
`I
`
`Prepare Zone
`Data Updates
`~
`I P-M ulticast
`Updates to IMU
`"0111 ,..
`"0111 ,..
`
`1414
`
`+
`
`

`

`U.S. Patent
`
`Sheet 18 of 29
`Nov. 12,2002
`Fig. 15
`
`US 6,480,783 Bl
`
`I
`
`0.8
`
`Time Zones
`o \ o'_;:
`... ~ R~ (/)
`_/"
`_____.
`_____.
`_____.
`~ 0~ ...-
`---- '\...J~
`__...,.
`>-
`----
`----
`---
`~ __,.... --- ~ ---/ ~~ /
`co
`R2·RA-,~~·RA- ,tt8J- ,M_·RJ- ~£-RA- ~v ~--- o
`(/)
`~SUN 0.7
`------c~ ~
`0.5 0.2
`0.8 0.2 0.2 -------Vl...-- 0 :::J
`0 MON
`0.5 0.2 ...------Vv ~Ul
`~>- TUE
`0.7
`B -g WED 0.2 0.5 0.2 0.5 0.8 ---------- ~ ... J----
`SU) THu
`----------v~
`o.5 o.8
`0.2 0.2 0.5 0.2 0.7 ~V/ ~
`FRI
`:sA1 o.3 o.8
`o.8 o.7
`o.5 ~ ~1.-----
`::J
`----------VV ~
`>-SUN
`0. 7
`0.5 0.2
`---------vv 0
`"'0 MON
`0.2 0.5 0.8
`___...--V[._...-- S~
`~.a TUE
`0.3 0.8 0.5
`0l{l WED
`0.5 0.2 0.2 0.5 0.7 ------=:v~ (/)
`----------VV
`0.8 0. 7
`0.5 0. 7
`S~ THU
`0.8 0.2 ~ //.........._>-
`FRI
`~ ~-------c~
`(!) ISAT 0.2 0.2 0.5
`--------- ~------ ~ ~
`.........._>-SUN
`0.2 0.2 0.5 0.2 0. 7
`___. .. ...-- > '""'
`.::::t. ro M 0 N 0 . 5 0 . 2
`---------- 1
`0 . 5
`0 . 2
`0 . 5
`l.. 0 i-=--=--=~--=--=+--=--:::-+-~r--+----+--V
`v-
`0.5 0.8 ...------1 ___......V 0 ::J
`0.5 0.8 0. 7
`0
`TUE
`~>-
`ZU)~
`v
`1.8 0.8 0.5 ----------V v
`>"'0 WED 0.8 0.5
`1.8 0.5 0.8 ---------yH
`0 ::J THU
`-u.7
`0.5
`zU) FRI
`o.2 o.2 o.5 o.9 o.5 ~vv
`0.5 0.2 .../~_ ........ J . .----~
`:sAT 0.2 0.5 0.7
`0.8 0.2 0.2 ----------~V 0 :::J
`SUN
`0.2 0.7
`~>- MON 0.2 0.5 0. 7
`0.5 0.2 --------- ~[._..---- ~Ul
`5 -g TuE
`o.5 o.8 o.2 o.5 o.8 ---------~v 0 1
`Stn WED 0.8 0.5
`0.3 0.8 0.5 ---------~[..-.---- Z~
`o.5 ...-----vH
`1 THu
`o.5 ~ o.8 o.7
`0
`z~ FRI
`o.5 o.2 o.2 ~vv
`o.9
`c .5
`:sAT 0.5 U .2
`0.3 0.8 0.5
`Vehicle Speed
`Coefficient
`
`

`

`U.S. Patent
`
`Nov. 12, 2002
`
`Sheet 19 of 29
`
`US 6,480, 783 Bl
`
`Fig. 16
`
`I
`
`ofi:..
`Time Zones
`~es 0s
`~~~oaT~ ~ ~ ~ ~ ~ ~ ~
`I_......
`__.----
`_.......
`....------
`__.----
`....------
`__.----
`.--- ~ >-
`~ ~ ~ ~ ~ ~ ~ /~ co
`(/)
`RU:RJ-~?g_·RJ- ~t~_.gJ- fg·RJ- J1·RJ- ~ ---~ 0
`~SUN 0.3 0.8 0.5
`0.5 0.8 ~ __-/_....-- ~
`0.8 0.2 0.2 ~ ---~_....-- o :::J
`0 MON 0.2 0.7
`~>- TUE
`0.5 0.2 ~VV$U)
`0.2 0.5
`0.7
`l -"'0 WED
`0.2 0.2 0.5 0.2 0. 7 ~1
`___......f-.-_......
`0 :::J !--=-=-===--ll---::--=-+--::---,-+---+---::--:::c-+--:--:-:--v
`v
`$U) THU
`0.5 0.2 0.5 0.2 0.5 ~VM
`0.8 0.5 ~/V £
`FRI
`0.5 _,/ __-l--___.--- ........... :::J
`:sAT 0.3 0.8
`0.8 0.7
`~ ---~ tU1
`>-SUN
`0. 7
`0.5 0.2
`0.2 0.5 0.8 0.2 0.2 ~ ---~ 0
`"'0 MON
`0.2 ~ __----___....-- $~
`~.a TUE
`0.3 0.8 0.5 0.5
`0<f WED 0.8 0. 7
`0.8 ~ ---~___....-­
`0.5 0. 7
`0.5 0.2 0.2 0.5 0.7 ~ /H Ul
`$~ THU
`0.8 0.2 ~VV ........... >-
`FRI
`Ul I SAT 0.2 0.2 0.5
`~ V~___...... t~
`.....__ >-SUN
`0.2 0.2 0.5 0.2 0.7 ~1
`___......~/ 0
`>~
`_.-/~___....-- > _
`--
`v
`~CO MON
`0.5 0.2 0.5 0.2 0.5 ~1
`L 0 1-----il----::--=-+----+---+---+---+-'"
`V
`0.5 0.8 ~1 _......V 0 :::J
`TUE
`0.5
`O
`> >-
`v
`Z(J)...a...J
`0.8 0.5 ~ V /
`>"'0 WED 0.8
`o :::J THU
`0.5 1.8 0.5 0.8 ~ ~~
`0.7
`zU) FRI
`0.2 0.2 0.5 0.9 0.5 ~ --&""/
`~ _.-/ ~>­
`"t:"'C
`:sAT 0.2 0.5 0.7
`0.5
`0.2 __/ __------
`0.5 0.2 0.5 0.2 0.5 ~ ---~ 0 ::J
`SUN
`0.5 0.8 ~ __-V$U)
`~>-MON 0.5 0.8 0.7
`0 -g TUE
`0.8 0.5 1.8 0.8 0.5 ~ vv 0
`$U) WED 0.8 @1> 0.3 0.8 0.5 ~ Vl---_.-/ Z~
`o I THu
`a.5 ~vH
`o.5 w.5
`o.8 o.7
`z~ FRI
`(~.5 o.5 o.2 o.2 ~vl---_)
`o.9
`:sAT 0.5
`( .2
`0.3 0.8 0.5
`Vehicle Speed
`Coefficient
`
`I
`
`

`

`U.S. Patent
`
`Sheet 20 of 29
`Nov. 12,2002
`Fig. 17
`
`US 6,480,783 Bl
`
`Road Type 'A'
`
`'B'
`
`'C'
`
`'D'
`
`Vehicle Speed
`Coefficient
`
`(/)
`~·F-s~U~N~~~~~~~~~~~
`0 MON
`~~~T~U~E~~~~~~~~~~v
`1.... "'0 WED
`0.2
`0.5
`~.a THU
`0.2
`0.5 0.2 0.5
`U)~F~R~I1r~0.~7~-0.-5+--0.~8+---~--v
`0.5
`0.8 0.7
`0.3 0.8
`SA
`~SUN 0.7
`0.5 0.2
`"0 MON
`0.2 0.5 0.8
`~ TUE
`0.3 0.8 0.5
`1....lQ~w~E~D~~o~.8~0~.~7+-o~.~5+---~--v
`0.7
`0.8
`~ 0 THU
`0.5 0.2 0.2 0.5 0.7
`>z FRI
`0.8
`0.5
`SA
`
`0.2 0.2
`
`0.2
`
`

`

`U.S. Patent
`
`Nov. 12,2002
`
`Sheet 21 of 29
`
`US 6,480,783 Bl
`
`Fig. 18
`
`J
`
`Entry List
`
`s
`
`0
`0
`0
`0
`0
`0
`0
`-~
`
`Vm 1'- /
`
`Exit List
`
`0
`0
`0
`Cj)
`
`Vn
`
`" v
`
`

`

`U.S. Patent
`
`Nov. 12,2002
`
`Sheet 22 of 29
`
`US 6,480,783 Bl
`
`1901~
`
`Receive Signal
`From Vehicle V
`
`1905
`~
`
`No
`
`Put Von
`EL of S
`
`Yes
`
`Yes
`
`Fig. 19
`
`1903
`~
`
`1904
`
`Remove V From
`EL Of S'
`Put V On EXL Of S'
`
`No
`
`1908
`~
`
`Put V On EL Of S
`Remove V from EL Of S'
`Put V On EXL Of S'
`
`1909
`,r---/
`End
`
`

`

`U.S. Patent
`
`Nov. 12,2002
`
`Sheet 23 of 29
`
`US 6,480,783 Bl
`
`Fig. 20
`
`(/)
`ClJ
`
`E ·-1-
`> ro
`L. r-
`
`ClJ
`
`------~t2 ______ ~
`
`I
`-----------------~-
`
`---· Dt3:
`
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`
`L - _ _ _ _ _ _L . _ _ _ _
`
`tl
`
`__L______ I I _
`
`__L___~
`t
`t3
`t2
`Entry Times
`
`

`

`U.S. Patent
`
`Nov. 12,2002
`
`Sheet 24 of 29
`
`US 6,480,783 Bl
`
`Fig. 21
`
`r8
`
`r9
`
`Exit List-r7
`
`Exit List-r8
`
`Exit
`Current
`Current
`Exit
`ID.
`ID.
`Queque Travel
`Travel
`Queque
`Times
`Times
`Times
`Times
`V1 8:15-8:30 15
`V1 7:15-7:22 7
`V2 8:20-8:45 25
`~2 7:28-7:45 17
`V3 8:40-9:10 30
`~3 7:50-8:15 25
`~n Predicted time tn ~n Predicted time tn
`
`

`

`U.S. Patent
`U.S. Patent
`
`Nov.12, 2002
`Nov. 12, 2002
`
`Sheet 25 of 29
`Sheet 25 of 29
`
`US 6,480,783 B1
`US 6,480, 783 Bl
`
`Fig. 22
`Fig. 22
`
`}
`
`SP1
`SP1
`
`Google Exhibit 1007, Page 27 of 43
`
`

`

`U.S. Patent
`U.S. Patent
`
`Nov.12, 2002
`Nov. 12, 2002
`
`Sheet 26 of 29
`Sheet 26 of 29
`
`US 6,480,783 B1
`US 6,480, 783 Bl
`
`Fig. 23
`Fig. 23
`
`DP
`
`N3
`N3
`
`N4
`
`SP 1
`
`Google Exhibit 1007, Page 28 of 43
`
`

`

`U.S. Patent
`U.S. Patent
`
`Nov.12, 2002
`Nov. 12, 2002
`
`Sheet 27 of 29
`Sheet 27 of 29
`
`US 6,480,783 B1
`US 6,480, 783 Bl
`
`Fig. 24
`Fig. 24
`
`N3
`
`N2
`
`DP
`DP
`
`A
`
`SP2
`
`N14
`
`SP1
`SP1
`
`Google Exhibit 1007, Page 29 of 43
`
`

`

`U.S. Patent
`
`Nov. 12, 2002
`
`Sheet 28 of 29
`
`US 6,480, 783 Bl
`
`Fig. 25
`
`2501
`
`2502
`
`Get Request For Route
`From SP To DP
`
`Construct Neighbors
`Of SP And DP
`
`2503~
`
`Calculate Route
`From SP To DP
`'
`On Extended Network ~
`25~
`~ ~05
`Calculate Route from SP
`Multilevel Map
`To Its Neighbor
`Database
`
`~--------L..---------,
`
`25Q§_~
`Calculate Route From
`DP's Neighbor To DP
`
`2507
`~
`Combine Routes Into
`Final Route
`
`~---~--------,
`
`2508 _____
`
`Display Unit
`
`

`

`U.S. Patent
`
`Nov.12, 2002
`
`Sheet 29 of 29
`
`US 6,480, 783 Bl
`
`Fig. 26
`
`Internet
`·~~~'---+Digital
`Server
`
`~~
`
`~
`
`. - - - - - - -1
`
`<=:><=:><=:>
`0 0 0 0
`0 0 0 0
`0 0 0 0
`0 0 0 0
`0 0 0 0
`0 0 0 0
`
`On Vehicle
`Display
`A/V
`Monitor
`
`IMU
`
`Map
`Data(cid:173)
`base
`
`Real
`Time
`Data
`
`Route
`Calcula(cid:173)
`tions
`
`

`

`US 6,480,783 Bl
`
`1
`REAL TIME VEHICLE GUIDANCE AND
`FORECASTING SYSTEM UNDER TRAFFIC
`JAM CONDITIONS
`
`BACKGROUND OF THE INVENTION
`
`2
`many if not all speed measurements may return zero values.
`In other words, speed as a function of time may be wildly
`discontinuous and measuring it on time grid of a minute may
`prove highly inaccurate. Consider a case of growing jam.
`5 Average speeds will in this case give no indication of this
`dynamic change, the same being true of a dissipating jam.
`Averaging is a static operation incapable of catching a trend.
`Average speed is compared with a fixed constant while it
`might be better to compare it to "usual" speed empirically
`10 determined previously and stored in the database.
`
`BRIEF DESCRIPTION OF THE INVENTION
`This invention provides real time traffic Guidance
`System, which is capable of providing optimal route from
`15 the present position of a vehicle to a desired target destin a(cid:173)
`tion when traffic jams may be present, thereby reducing the
`burden upon the driver when the vehicle is traveling at high
`speeds on unfamiliar roads. Thereafter the optimal route
`found is communicated to the driver and displayed on the
`20 vehicle's computer screen featuring the digital map of the
`relevant region and/or via audio instructions.
`The travel time between two road intersections A and B is
`the sum of travel times for all sections of roads connecting
`A and B on the shortest route either by the minimal time
`25 criterion, or by some other criterion. Then in order to be able
`to compute a travel time between two positions on a map, we
`must be able to determine travel times for all sections of
`roads connecting those positions, or road intersections close
`to them. In the standard solution (an autonomous or stand(cid:173)
`alone on-vehicle application), a route is computed by a
`mathematical optimization algorithm while travel times are
`computed as distances divided by maximal allowed speeds.
`While being simple, such solutions have an obvious short(cid:173)
`coming in that they do not take into account the real
`35 conditions on the roads and therefore can serve only as a
`guidance suggestion. Obviously, a true real time system
`should collect, store and make use of the following kinds of
`data:
`1) Temporary changes in road conditions known in advance
`like closed roads under construction, traffic reroutes, etc.;
`2) Regular predictable changes like everyday slowdowns in
`rush hours;
`3) Sudden unpredictable changes such traffic accidents,
`traffic congestion due to sudden and drastic changes in
`traffic arrangements because of visiting dignitaries, etc.
`The system in the present invention is built around an idea
`of collecting and processing information that describes all
`those changing conditions.
`Overview of the Guidance System
`The Guidance System in the present invention consists of
`CTU and a fleet of IMUs, i.e. traveling vehicles. In order to
`have an updated data on traffic situations, the vehicle fleet is
`divided into two categories: sample vehicles SMU and all
`other client vehicles CMU. In general, CMUs are only
`55 clients that "consume" traffic congestion data provided by
`the CTU. The sample vehicles, on the other hand can be both
`clients and serve also as antennas or tentacles for collecting
`real time data on traffic situations, which can be used by all
`end users for updating their optimal routes. This data col-
`60 lection is performed by permanent monitoring of GPS
`signals obtained from SMUs and by concurrent measuring
`of their current travel times along a broad range of roads.
`FIG. 1 is a schematic representation of the information
`exchange between CTU and IMUs in the Guidance System.
`65 The data transfer from SMUs to CTU is done by wireless RF
`communication, and from CTU to both SMUs and CMUs by
`one-to-many multicasting system. The SMU vehicles com-
`
`1. Field of the Invention
`The present invention describes the vehicle Guidance
`System consisting of a plurality of vehicles equipped with
`IMUs including GPS units and of the CTU computer. The
`CTU broadcasts the updated traffic data collected from a
`number of sample vehicles via Multicast Broadcasting Sys(cid:173)
`tem thereby enabling the IMUs to dynamically update the
`desired optimal travel routes.
`2. Description of the State of Art
`The conventional on-vehicle guidance systems are usu(cid:173)
`ally stand-alone applications wherein the traffic data are
`static and cannot be easily dynamically updated.
`Consequently, the proposed routes are accurate only under
`ideal traffic conditions. The stand-alone versions cannot take
`into account current traffic jam conditions or real time
`emergencies. Hence, even when a so-called 'optimal route'
`is found, it may not be usable solution in real time situations
`and can only be used as a general recommendation.
`Other systems rely on electronic and optical sensors
`situated at various key locations to measure and update the
`current traffic loads. These systems are typically costly to
`install and to maintain and to be effective they must be
`distributed over large sectors of roads. Still other real time 30
`traffic control systems utilize real time field information
`typically gathered from various service vehicle such as
`traffic police, ambulances, road maintenance teams, etc.
`which is usually transmitted by radio to the control center
`and from there broadcasted to the public.
`The present invention eliminates the need for a large
`number of static sensors and relies instead on a number of
`highly mobile GPS carrying sample vehicles. Naturally, the
`reliability of the results will depend on the size of the sample
`vehicle fleet, and the ability of the server to process the 40
`incoming information simultaneously. Similar ideas could
`be found in existing inventions. Of particular relevance is
`U.S. Pat. No. 5,699,056 wherein the problem statement is
`similar to ours. In particular, it formulates the problem of
`dealing with traffic jams and other bottleneck situations. For 45
`detecting traffic jams and representing them in its database,
`this patent uses data obtained from traveling vehicles, in
`particular their IDs, positions, times, and speeds. In Embodi(cid:173)
`ment 2, it divides all the vehicles into blocks (i.e. groups),
`measures average speed in each block, and defines a situa- 50
`tion as a jam if the average speed is less than a predeter(cid:173)
`mined value.
`In our view, the proposed there solution contains a num(cid:173)
`ber of problematic points that require further development
`and which remained unclear in the patent description. 1) The
`definition of blocks is not quite clear. No algorithm is given
`for partitioning the vehicles into blocks; 2) The number of
`roads or more precisely, sections of roads may be very large,
`say, tens of thousands. It may be difficult to cover them all,
`i.e. store all the relevant data, process and update it on-line;
`3) The number of vehicles can also be very large, say, tens
`of thousands, so processing and updating in real time signals
`sent by them at time intervals of, say, a minute might be
`challenging for a server of average capacity; 4) An important
`point in his solution is evaluating vehicle speeds and aver(cid:173)
`aging them over a block. This seemingly innocuous opera(cid:173)
`tion may highly problematic, however, within a traffic jam as
`
`

`

`US 6,480,783 Bl
`
`3
`municate to CTU their GPS data: the present positions, the
`position time, their IDs, and their speed vectors at specific
`time intervals. After processing the information, CTU sends
`to CMUs updated information on traffic bottleneck situa(cid:173)
`tions (i.e. road ID, current time, and travel times of the latest 5
`n vehicles). At any given moment, the CTU also maintains
`the database containing travel times for all sections of roads
`at a particular time of the day, for a particular of day of the
`week, etc.
`Initially, those travel times are theoretical travel times but 10
`as the time goes by and observational data are being col(cid:173)
`lected and processed, they are replaced by empirical travel
`times reflecting realistic travel conditions, and on particular
`occasions by current travel times, which reflect sudden and
`unpredictable changes in traffic conditions. Those travel 15
`times are being measured and periodically broadcasted by
`the CTU via satellite IP Multicasting broadcast to end-users
`where they are entered into the databases of the on-vehicle
`computers for future use.
`On receiving a request from a driver for a shortest route 20
`to a particular destination, the end-user on-vehicle computer
`applies an optimization procedure for computing an optimal
`route while making use of updated by CTU travel times for
`individual sections of roads. Thereafter, the optimal route is
`communicated to the driver either visually on the computer 25
`map, or auditorilly through a sequence of voice instructions.
`Below is the list of the major functions performed by the
`Guidance System.
`
`Major Functions of the Guidance System
`The CTU Functions
`1. Receiving GPS signals from sample vehicles.
`2. Processing those signals and storing the information in
`the central database.
`3. Managing (processing and storing) theoretical travel
`times.
`4. Managing (processing, storing and updating) regular
`(statistical) travel times.
`5. Managing (processing, storing and updating) current
`travel times.
`6. Maintaining and updating digital geographical maps of
`all roads.
`7. Managing zoning information.
`8. IF-Multicasting.
`9. Interaction with Administrator (human operator)
`The IMU Functions
`1. The SMU Functions:
`2. Receiving and Processing GPS Data.
`3. RF Transmitting GPS Data to CTU.
`The CMU Functions
`On-Line Information Processing:
`1. Receiving and Processing GPS Data.
`2. Maintaining Local On-Vehicle Database.
`3. Receiving and Processing IF-Multicast Updates.
`Processing Individual Navigation Requests:
`1. Receiving a Destination Point (and Optionally a Start(cid:173)
`ing Point) from a Client.
`2. Translating Request into Standard Form.
`3. Processing Client's Request, i.e. Calculating the Short(cid:173)
`est Route.
`4. Passing Solution to Display and Audio Unit.
`5. Processing Additional Individual User's Requests.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`FIG. 1 shows Information Exchange in the Guidance
`System;
`
`4
`FIG. 2 shows Information Flow Between Individual Com(cid:173)
`ponents of the Guidance System;
`FIG. 3 shows Information Flow from SMU to CTU;
`FIG. 4 shows Information Exchange Between IMU and
`CTU;
`FIG. 5 shows the Flowchart of the Guidance System with
`Real Time Traffic Volume Updates;
`FIG. 6 shows the Algorithm for Processing User's
`Request;
`FIG. 7 shows the Section Travel Time Managing Algo-
`rithm;
`FIG. 8 shows Vehicle Hardware Configuration;
`FIG. 9 shows Vehicle Display Panel;
`FIG. 10 is the Road Type Classification;
`FIG. 11 is Road Classification Flowchart;
`FIG. 12 is IF-Multicasting to Vehicles Traveling from
`Zone to Zone;
`FIG. 13 shows Calculations of Travel Times in Category
`A Roads;
`FIG. 14 shows the CTU Database;
`FIG. 15 is Table of Administrator for Category A Roads;
`FIG. 16 is Table of Administrator for Category B Roads;
`FIG. 17 shows the Multilevel Road Information Gather(cid:173)
`ing System;
`FIG. 18 shows the Method of Maintaining Two Lists of
`Vehicles;
`FIG. 19 shows the Algorithm for Maintaining Two Lists
`of Vehicles for Category A Sections;
`FIG. 20 illustrates Regression-Based Prediction of Cur(cid:173)
`rent Travel Times;
`FIG. 21 illustrates the Computation of Optimal Routes the
`algorithm A*;
`FIG. 22 shows Algorithm Z for Planning in Two-Layer
`Hierarchical Model;
`FIG. 23 shows the Algorithm Z for Planning at Upper
`40 Layer;
`FIG. 24 shows the Algorithm Z for Planning at the
`Extended Road Network; and
`FIG. 25 shows the Flowchart of Algorithm Z for Route
`45 Planning.
`
`30
`
`35
`
`DETAILED DESCRIPTION OF THE
`INVENTION
`
`The major goal of the invention is to provide a real time
`50 travel Guidance System capable of handling a driver's
`request for a shortest route to any destination. At any point
`of the journey the driver can enter a request for alternative
`route and will receive an updated route reflecting the real
`time traffic situation directly on his display panel. The
`55 information will also be updated by visual and audio
`instructions, and driver's vehicle position will be displayed
`dynamically on the display unit. Another goal is to provide
`the driver with a tool for strategic trip planning. By entering
`alternate times for future trips and comparing their travel
`60 time estimates for the same destination, the driver receives
`an option to select a trip proposal ideally suited for his needs.
`The Guidance System also enables the user to manually, or
`by verbal commands, to update and customize his informa(cid:173)
`tion database and adapt it to his personal needs and require-
`65 ments.
`The subsequent description of the Guidance System is
`divided into the following parts:
`
`

`

`US 6,480,783 Bl
`
`5
`1. Information Flow in the Guidance System
`2. Algorithm for processing user's request
`3. Vehicle's display and hardware
`4. Sample vehicles and client vehicles
`5. Two categories of roads
`6. Information zones: updating on-vehicle databases via
`multicasting
`7. Travel times data
`8. General description of databases
`9. Theoretical travel times
`10. Regular empirical travel times
`11. Current travel times
`12. Computation of optimal route
`Information Flow in the Guidance System
`The Guidance System comprises client vehicles CMU,
`sample vehicles SMU, and the central traffic unit CTU (see
`FIG. 1). The CTU unit is configured to receive GPS data
`obtained from a fleet of sample vehicles SMU that are
`traveling and passively collecting sample traffic congestion
`data along a broad range of road systems. The CTU pro(cid:173)
`cesses the information and passes it along to be multicasted
`to the groups of client vehicles CMU each according to its
`group position.
`FIG. 2 shows information flow between individual com(cid:173)
`ponents of the Guidance System. The GPS data obtained via
`satellite is transmitted by means of on-vehicle modem and
`transmitter to the CTU. CTU uses the map database and
`information obtained from all GPS units for calculation of
`real time information traffic updates that are thereafter 30
`IP-multicasted to IMU receivers and utilized for calculation
`of routes by on-vehicle computers.
`FIG. 3 shows information flow from SMU to CTU for a
`case when SMU is not a client, i.e. is not using the guidance
`services, and therefore is equipped only with GPS unit and
`Unit 1 shows the satellite supplying GPS signals to SMU.
`The only function of such SMUs in the Guidance System is
`providing GPS travel coordinates (Unit 2) along roads and
`transmitting them to CTU (Unit 5) by modem (Unit 3) RF
`transmitter (Unit 4). After the CTU processes the data and
`creates the real time traffic updates, it IP-multicasts them to
`all IMUs.
`FIG. 4 shows the main components of the IMU and
`information exchange between IMUs and CTU. It illustrates
`two cases: when IMU is a client and when it is both a client 45
`and a sample vehicle. When IMU is a client only, consider
`Units 1 to 10. Unit 1 shows the satellite supplying GPS
`signals to IMU. The IMU navigation unit comprises Units 2
`to 8. It consists of the GPS locator unit 2, processor
`(on-vehicle computer) 3 with its map database 6, display
`unit 4, an additional user manual input option 5, the map
`update database 7, and receiver 8. The IP Multicast 9
`accomplishes the communication from CTU 10 to IMU. In
`the future embodiments, when client vehicles will be able to
`function as sample vehicles as well, they will be equipped 55
`with its own transmitter unit 11 for performing RF trans(cid:173)
`missions 12.
`Major part of the Guidance System is illustrated by the
`flowchart in FIG. 5. The client is required to enter the desired
`starting point SP and the destination point DP (Units 2 and 60
`4). In the on-vehicle application, SP may also be obtained
`automatically via GPS (Unit 1). For each SP and DP, specific
`zones are assigned with points SP and DP of sizes according
`to predetermined criteria and called SP zone and DP zone
`respectively (Units 3 and 5).
`In order to determine if the current time information is
`available along the travel route, it is necessary to locate both
`
`6
`SP zone a