(12) United States Patent
`Khavakh et al.
`
`USOO619231.4B1
`(10) Patent No.:
`US 6, 192,314 B1
`(45) Date of Patent:
`Feb. 20, 2001
`
`(54) METHOD AND SYSTEM FOR ROUTE
`CALCULATION IN A NAVIGATION
`APPLICATION
`
`i.
`-
`(75) Inventors: S5 Shyba,. William
`Unough, enten; leg
`Voloshin, Deerfield; Yaoguang Wang,
`Rosemont, all of IL (US)
`(73) Assignee: Navigation Technologies Corp.,
`Rosemont, IL (US)
`Under 35 U.S.C. 154(b), the term of this
`patent shall be extended for 0 days.
`
`(*) Notice:
`
`21) Appl. No.: 09/047,698
`(21) Appl. No.: 09/047,
`(22) Filed:
`Mar. 25, 1998
`7
`(51) Int. Cl." ..................................................... GO1C 21/00
`(52) U.S. Cl. .............................................................. 701/209
`(58) Field of Search ..................................... 701/209, 202,
`701/208
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`2/1986 Tachi et al. .......................... 364/444
`4,570.227
`8/1988 Itoh et al. ...
`. 364/449
`4,763,270
`11/1988 Ueno et al. .
`. 364/449
`4,782,447
`4,794,528 * 12/1988 Hirose et al. ..
`707/101
`4,796,189
`1/1989 Nakayama et al.
`. 364/449
`4,812,990
`3/1989 Adams et al. ....................... 701/202
`4,926,336
`5/1990 Yamada ................................ 364/444
`4,937,753
`6/1990 Yamada ...
`. 364/449
`5,031,104
`7/1991 Ikeda et al. ....
`. 364/449
`5,041,983
`8/1991 Nakahara et al. .
`. 364/449
`5,103,400
`4/1992 Yamada et al.
`. 364/444
`5,184,303
`2/1993 Link ............
`. 364/449
`5,187,667
`2/1993 Short .................................... 701/202
`5,204.817
`4/1993 Yoshida ................................ 364/449
`5,262,775
`11/1993 Tamai et al.
`340/995
`5,272.638
`12/1993 Martin et al. ........................ 364/444
`5,291,412
`3/1994 Tamai et al. ......................... 364/449
`5,291,413
`3/1994 Tamai et al.
`. 364/449
`5,291,414
`3/1994 Tamai et al.
`. 364/449
`5,303,159
`4/1994 Tamai et al.
`. 364/449
`
`5,311,434
`5,369,588
`5,371,678
`5,410,485
`5,428,545
`5,442,349
`5,459,667
`5,467,276
`5,475,387
`5,502,640
`
`5/1994 Tamai ................................... 364/449
`11/1994 Hayami et al.
`... 364/449
`12/1994 Nomura - - - -
`... 364/444
`4/1995 Ichikawa ......
`... 364/444
`6/1995 Maegawa et al.
`... 364/444
`8/1995 Inoue et al. .......................... 340/995
`10/1995 Odagaki et al. ..................... 364/444
`11/1995 Tsuyuki ........
`... 364/449
`12/1995 Matsumoto .......................... 340/990
`3/1996 Yagyu et al. ........................ 364/443
`(List continued on next page.)
`Primary Examiner Gregory C. Issing
`(74) Attorney, Agent, or Firm-Frank J. Kozak; Lawrence
`M. Kaplan
`(57)
`
`ABSTRACT
`
`A program and method for route calculation for use with a
`navigation System and used with a map database that rep
`resents a road network in a geographic region. A route
`calculation program is adapted to find at least one Solution
`route between a first location on a road network and a Second
`location on the road network. The route calculation program
`includes a first Search tree associated with the first location
`and a Second Search tree associated with the Second location.
`Each Search tree is adapted to hold gates. Each of the gates
`represents a physical position on the road network and a
`direction from the position to another location along a path
`on the road network. The route calculation program also
`includes at least one priority queue associated with one of
`the Search trees. The priority queue assigns a priority to one
`of the gates in the associated Search tree based upon an
`evaluation using a Search algorithm. The gate identified as
`having a higher priority than any other gate in its respective
`Search tree is expanded to determine one or more Successor
`gates thereof. Each of these Successor gates So formed is
`compared to the gates in the other Search tree. The process
`of growing at least one of the Search trees by expanding the
`gate in the Search tree that has a higher priority than any
`other gate in the Search tree is continued until a gate in one
`Search tree corresponds to at least one gate in the other
`Search tree.
`
`18 Claims, 13 Drawing Sheets
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`represented by
`"PORTAL"
`
`represented by
`SEGSMENENTY
`W
`represented by
`\s. < 2.
`"PORTAL"
`
`represented by
`NODENTY
`
`SEED \, 'SEED w
`GATE"
`GATE GATE"
`-
`
`SEED
`
`represented by
`SEGMNTENTITY
`
`ARKING
`GARAGE
`
`represented by
`"WAYOINT"
`
`
`
`
`
`represented by
`"PORTAL
`
`Apple Exhibit 1010
`Page 1 of 35
`
`

`

`US 6,192,314 B1
`Page 2
`
`U.S. PATENT DOCUMENTS
`4/1996 Nobe et al. .......... 364/424.05
`4/1996 Kanki ................................ 364/449
`4/1996 Smith, Jr.
`... 364/444
`4/1996 Fujita et al.
`... 364/449
`
`5/1996 Seda ............
`
`... 364/444
`
`2- - -2 4 -
`
`9/1996 Nakayama et al. ............. 364/424.02
`5,557.522
`9/1996 Ito et al. .....
`... 340/995
`5,559,511
`3/1997 Tamai .......
`... 364/449.3
`5,608,635
`3/1997 Moroto et al. .................... 364/449.3
`5,612,881
`6/1997 Nishimura et al. .............. 364/449 B
`5,638,280
`5,938,720 * 8/1999 Tamai
`701/209
`
`
`
`1
`
`- - - -
`
`a stillwk - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
`
`... 364/449
`5/1996 Matsumoto .
`8/1996 Fujii et al. ........................... 340/995
`
`* cited by examiner
`
`5,506.774
`5,506.779
`5,508930
`5,513,110
`
`5,519,619
`
`5,521,826
`5,550,538
`
`Apple Exhibit 1010
`Page 2 of 35
`
`

`

`U.S. Patent
`
`US 6, 192,314 B1
`
`
`
`ZZ AVTCHSIC]
`
`5? SHEXVEdS
`
`Apple Exhibit 1010
`Page 3 of 35
`
`

`

`U.S. Patent
`
`Feb. 20, 2001
`
`Sheet 2 of 13
`
`US 6,192,314 B1
`
`
`
`|----
`
`//
`
`Apple Exhibit 1010
`Page 4 of 35
`
`

`

`U.S. Patent
`
`Feb. 20, 2001
`
`Sheet 3 of 13
`
`US 6,192,314 B1
`
`
`
`GEOGRAPHICDATABASE 30
`
`SEGMENT
`
`NODE
`
`LAYER 1
`
`SEGMENT
`
`NODE
`
`LAYERO
`
`SEGMENT
`
`NODE
`
`FIG. 3
`
`Apple Exhibit 1010
`Page 5 of 35
`
`

`

`U.S. Patent
`
`Feb. 20, 2001
`
`Sheet 4 of 13
`
`US 6,192,314 B1
`
`
`
`POSITIONING
`SYSTEM 14
`
`NAVGATION
`PROGRAM 18
`
`ROUTE
`GUIDANCE
`TOOL-91
`
`S59DING
`
`NAV. POS.
`OBJECTS 56
`
`NAVIGATION
`APPLICATION 47
`
`ROUTE CALCULATION
`TOOL 40
`
`wront.
`
`WAYPOINT
`OBJECTS 100
`
`ROUTE
`OBJECT
`(INPUT)
`72
`--a
`
`ROUTE
`OBJECT
`(OUTPUT)
`60
`
`TIME
`OBJECT
`
`69
`
`CONFIG
`OBJECT
`64
`
`VEHICLE
`OBJECT
`68
`
`Apple Exhibit 1010
`Page 6 of 35
`
`

`

`U.S. Patent
`
`Feb. 20, 2001
`
`Sheet S of 13
`
`US 6,192,314 B1
`
`CONFIGURATION
`OBJECT 64
`parameters 64(1)
`
`parameters 64(n)
`
`TIME OBJECT 69
`START TIME 69(1)
`
`other 69(n)
`
`FIG. 8
`
`
`
`ROUTE OBJECT 60
`
`LIST OF
`SEGMENTS
`60(1)
`SEG
`
`LIST 60(2) OF WAYPOINT
`DATA STRUCTURES
`
`WAYPOINT 400
`
`SEG
`
`WAYPOINT 400
`
`WAYPOINT 400
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`VEHICLE OBJECT 68
`TYPE 68(1)
`
`HEIGHT 68(2)
`
`WEIGHT 68(3
`
`LENGTH 68(4
`
`NO OF AXLES 685
`
`NO. OF PEOPL
`E 68(6
`
`OTHER 68(n)
`
`F.G. 6
`
`FIG. 7
`
`START DATE/TIME 60(3)
`
`RT. GENERATION
`DATE/TIME 6O(4
`(4)
`
`EHICLE OBJ. 68
`
`GEODB VER. 60(5)
`S-FLAG 60(6)
`
`OTHER 60(n)
`
`Apple Exhibit 1010
`Page 7 of 35
`
`

`

`U.S. Patent
`
`Feb. 20, 2001
`
`Sheet 6 of 13
`
`US 6,192,314 B1
`
`FIG. 9
`NAVIGATION POSITION
`OBJECT 56
`
`
`
`
`
`
`
`LOCUS 92
`
`GEOGRAPHIC
`POSITION 93
`
`OTHER 56(n)
`
`FIG 10
`LOCUS 92
`SEGMENT 94
`
`SPOT 95
`
`SIDE 96
`
`FIG 11
`
`WAYPOINT OBJECT 100
`POSITION 102
`DESCRIPTION104
`
`DELAY 1 12
`
`
`
`PORTAL 106 6
`
`LOCUS 92
`
`DIRECTIONS 107
`
`ENFORCE SIDE FLAG 109
`
`PORTAL 106
`
`LOCUS 92
`
`
`
`DIRECTIONS 107
`
`ENFORCE SIDE FLAG 109
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Apple Exhibit 1010
`Page 8 of 35
`
`

`

`U.S. Patent
`
`Feb. 20, 2001
`
`Sheet 7 of 13
`
`US 6,192,314 BI
`
`
`
`ALILNALNSAWS3S
`
`Aqpejueseidal
`
`ALINCONqpejusseldel«WLYOd,«WLYOd,,—2>>AqpejusseidasAqpajuesaida
`
`
`
`ALILNALNAWS3AS
`
`Aqpajuesaidas
`
`
`
`qaajas,44s:gqaas.
`
`
`LDLO12/
`
`LV«LVSWALVD
`
`|(aouel}Ua)
`
`ONIMYVd
`
`dSVeVS
`
`(a0ues}Uua)
`
`élOla
`
`Aqpeyuesaidas
`
`«LNIOdAVM,
`
`«SILV9S,
`
`Aqpajueseaidas
`
`«WLYOd.
`
`Apple Exhibit 1010
`Page 9 of 35
`
`Apple Exhibit 1010
`Page 9 of 35
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Feb. 20, 2001
`
`Sheet 8 of 13
`
`US 6,192,314 BI
`
`LNIOGAWM
`
`1oargo
`
`
`
`OOF(LS3q)
`
`
`
`CISSQ)0S¢SYNLONYLS
`
`‘fdODIVOALY
`
`
`
`VIVdLINIOdAVM
`
`
`
`(NIDTHO)OSPANNLONYLS
`
`
`
`VLVdLNIOdAVM
`
`EO“OTWO
`
`
`
`(NOPELOarao
`
`
`
`(INO)OFTLoarao
`
`dauHOYVAS
`
`ALIMOdd
`
`anand
`
`(LINO)OST
`
`“ALY
`
`
`
`0SLOArONOILV1INOV93LNOY
`
`Apple Exhibit 1010
`Page 10 of 35
`
`Apple Exhibit 1010
`Page 10 of 35
`
`

`

`U.S. Patent
`
`Feb. 20, 2001
`
`Sheet 9 of 13
`
`US 6,192,314 BI
`
`
`(NDOPELoargo
`(NDOSFANAND
`
`JaylHOYVAS
`ALIMO!Yd
`PelSALVO
`
`velALVOD
`
`
`
`
`
`WLIVGLNIOdAVMdO‘O1V9“SLY
`
`
`
`CISSQ)0SPSYNLONYLS
`
`
`
`0SLOAraONOILV1ND1V93LNOY
`
`
`
`“ALY
`
`VlOla
`
`
`
`VIVdLNIOdAVMEO‘O1V9
`
`
`
`(NISTHO)OSPAUNLONYLS
`
`
`
`
`
`(INO)0SFANANDALIMOId
`
`belLVSretALW9
`velS1LV
`
`velALV
`
`(inO)OFTLoargdo
`
`dau.HOYXVsAS
`
`LAO)&rb
`
`SNOO4
`
`
`
`relSLWOM-PelALY
`
`Apple Exhibit 1010
`Page 11 of 35
`
`Apple Exhibit 1010
`Page 11 of 35
`
`
`
`

`

`US 6,192,314 B1
`
`OG Loarao Noi LwT no Two = Lnow
`
`U.S. Patent
`
`
`
`
`
`
`
`(NIJ?GT EnEnoOT\/O ELTON
`
`Apple Exhibit 1010
`Page 12 of 35
`
`

`

`U.S. Patent
`
`Feb. 20, 2001
`
`Sheet 11 of 13
`
`US 6,192,314 B1
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`FIG. 16
`ROUTE OBJECT WAYPOINT
`DATA STRUCTURE 400
`
`DESCRIPTION 404
`POSITION (LAT, LONG) 402
`2 LOC (ENTRANCE/EXIT) 422
`
`DSTANCE 41
`
`TIME 41
`
`TIME 416
`
`T 414
`C O S 4.
`
`INDEX TO
`SEGMENT LIST 424
`
`TYPE (ORIGIN/
`DESTINATION/
`INTERMEDIATE) 420
`
`GATE 124
`ASSOCATED NODE 125
`
`TARGET NODE 127
`
`PREDECESSOR 131
`
`SEGMENT 12
`
`TIME 13
`
`COST 13
`
`DISTANCE 13
`
`FIG. 17
`
`FIG. 20
`ROUTE CALCULATION OBJECT
`WAYPOINT DATASTRUCTURE 450
`
`DESCRIPTION 404
`
`POSITION (LAT, LONG) 402
`2 LOC (ENTRANCE/EXIT) 422
`
`PORTAL 106
`
`LOCUS
`
`DIRECTIONS 107
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ENFORCE SIDE FLAG 1
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`PORTAL 106
`
`LOCUS
`
`DIRECTIONS 107
`
`ENFORCE SIDE FLAG 109
`
`DELAY 421
`
`COST 414
`
`416 6
`TIME 41
`
`418
`DISTANCE 41
`
`
`
`
`
`
`
`Apple Exhibit 1010
`Page 13 of 35
`
`

`

`U.S. Patent
`
`Feb. 20, 2001
`
`Sheet 12 of 13
`
`US 6,192,314 B1
`
`
`
`SEED GATE 108
`
`POSITION 125
`LOCUS FROM
`PORTAL
`
`TARGET NODE 127
`
`SEGMENT 129
`SEGMENT FROM
`LOCUS
`
`LIST OF SEGMENTS 50
`
`
`
`FIG. 18
`
`FIG. 19
`
`SEGMENT
`
`Apple Exhibit 1010
`Page 14 of 35
`
`

`

`U.S. Patent
`
`Feb. 20, 2001
`
`Sheet 13 of 13
`
`US 6,192,314 BI
`
`leOld
`
`QS31N3S3ed3y
`
`NISALVSAd—S
`
`aad
`
`QNNOGNI~~
`
`~
`
`eu
`
`HLOIM/ONINSNOO4/;
`/HLOIMONITY
`
`}I
`
`—ft|cui
`{PT
`!SSMLNI
`/SNOOJOL|1S3S010!
`
`1“daNsSSNdO4
`
`bu
`
`LNIOGAVM
`
`LZ
`
`YANNI
`
`-_——
`
`||
`
`dV9SNOOSA
`
`Snood
`
`Apple Exhibit 1010
`Page 15 of 35
`
`Apple Exhibit 1010
`Page 15 of 35
`
`
`
`
`
`

`

`1
`METHOD AND SYSTEM FOR ROUTE
`CALCULATION IN ANAVIGATION
`APPLICATION
`
`BACKGROUND OF THE INVENTION
`The present invention relates to a System and method for
`route calculation in a navigation application program.
`Computer-based navigation Systems are able to provide
`end-users, Such as vehicle drivers and as well as others, with
`various navigating functions and features. For example,
`Some navigation Systems are able to determine an optimum
`route to travel by roads between locations in a geographic
`region. Using input from the end-user, and optionally from
`equipment that can determine the end-user's physical loca
`tion (Such as a GPS System), a navigation System can
`examine various routes between two locations to determine
`an optimum route to travel from a starting location to a
`destination location in the geographic region. The naviga
`tion System may then provide the end-user with information
`about the optimum route in the form of instructions that
`identify the maneuverS required to be taken by the end-user
`to travel from the Starting location to the destination loca
`tion. The navigation System may be located in an automobile
`and the instructions may take the form of audio instructions
`that are provided as the end-user is driving the route. Some
`navigation Systems are able to Show detailed maps on
`computer displays that outline routes to destinations, the
`types of maneuvers to be taken at various locations along the
`routes, locations of certain types of features, and So on.
`In order to provide these and other navigating functions,
`present navigation Systems include navigation application
`Software programs and use one or more detailed databases
`that include data which represent physical features in geo
`graphic regions. The detailed database(s) includes data
`which represent the road network in a region, including the
`roads and interSections in the region and information about
`the roads and interSections, Such as turn restrictions at
`interSections, Speed limits along the roads, Street names of
`the various roads, address ranges along the various roads,
`and So on. Further, the data may include information about
`points-of-interest. Presently, the collection of Such geo
`graphic data and the provision of Such data in a computer
`usable database format are provided by Navigation Tech
`nologies of Rosemont, Ill.
`Present navigation application programs and navigation
`Systems are able to provide many advantages and many
`useful features. However, there continues to be a need for
`improvement. One area in which there is need for improve
`ment relates to providing the end-user with better and more
`detailed navigation instructions at an initial Stage of a route.
`Another area in which there is need for improvement relates
`to providing the end-user with better instructions as the
`desired destination is approached. Still another area in which
`navigation Systems can be improved relates to providing the
`end-user with better instructions as to how to get back on a
`route to a desired destination when the end-user either
`accidentally or deliberately deviates from a previously cal
`culated route. Still another area in which there is a need for
`improvement relates to handling of intermediate stops along
`a route. For example, an end-user will often want to make
`one or more intermediate Stops between a starting location
`and a final destination. Thus, there is a need for a navigation
`System application that can not only calculate a route
`between two locations, but also that can calculate quickly
`and effectively a route that includes Stops at one or more
`intermediate locations along the way between a starting
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 6,192,314 B1
`
`2
`location and a destination. A further area in which there is
`need for improvement relates to provision of a universal
`route calculation module or tool that can be readily used in
`a variety of different software and hardware environments
`without the need for extensive revisions and customizations
`to the tool.
`Accordingly, it is an objective to provide a navigation
`application that provides improved route calculation fea
`tures to an end-user.
`
`SUMMARY OF THE INVENTION
`To address the above concerns, according to one aspect of
`the present invention, there is provided a program and
`method for a route calculation tool for use with a navigation
`System and used with a map database. The route calculation
`tool is adapted to find at least one Solution route between a
`first location on a road network in a geographic region and
`a Second location on the road network in the geographic
`region. The route calculation tool includes a first Search tree
`asSociated with the first location and a Second Search tree
`asSociated with the Second location. Each of the Search trees
`is adapted to hold gates. Each of the gates represents a
`physical position on the road network and a direction from
`the position to another location along a path on the repre
`Sented road network. The route calculation tool also includes
`a priority queue associated with each of the Search trees.
`Starting with one of the Search trees, the priority queue
`assigns a priority to each of the gates based upon an
`evaluation by a Search algorithm. A Search engine expands
`the gate that has the highest priority to determine one or
`more Successor gates thereof and compares the one or more
`Successor gates So formed to one or more gates in the other
`Search tree. The process of growing either or both Search
`trees by expanding the gate that has the highest priority in its
`respective Search tree is continued until a gate in the Search
`tree corresponds to at least one of the one or more gates in
`the other Search tree.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`FIG. 1 is a block diagram of an exemplary navigation
`System.
`FIG. 2 is a map illustrating physical geographic features
`in a portion of a geographic region represented by the
`geographic database in FIG. 1.
`FIG. 3 is a block diagram illustrating the organization of
`the geographic database in FIG. 1.
`FIG. 4 is a block diagram showing components of the
`navigation application of FIG. 1.
`FIG. 5 is a diagram illustrating the components of the
`configuration object of FIG. 4.
`FIG. 6 is a diagram illustrating the components of the
`vehicle object of FIG. 4.
`FIG. 7 is a diagram illustrating the components of the
`output route object of FIG. 4.
`FIG. 8 is a diagram illustrating the components of the time
`object of FIG. 4.
`FIG. 9 is a diagram illustrating the components of the
`navigation position object of FIG. 4.
`FIG. 10 is a diagram illustrating the components of the
`locus structure of FIG. 9.
`FIG. 11 is a diagram illustrating the components of the
`waypoint object of FIG. 4.
`FIG. 12 is a diagram illustrating the geographic features
`represented by the waypoint object of FIG. 11.
`
`Apple Exhibit 1010
`Page 16 of 35
`
`

`

`3
`FIG. 13 is a diagram of the components in the route
`calculation object of FIG. 4 in one Stage of operation.
`FIG. 14 is a diagram of the components in the route
`calculation object of FIG. 4 in another Stage of operation.
`FIG. 15 is a diagram of the components in the route
`calculation object of FIG. 4 in yet another Stage of operation.
`FIG. 16 is a diagram illustrating the components of the
`waypoint structure which is stored in the route object of FIG.
`7.
`FIG. 17 is a diagram illustrating the components of the
`gate data structure of FIGS. 13-15.
`FIG. 18 is a diagram illustrating the components of the
`gate data Structure of FIGS. 17 when used as a Seed gate.
`FIG. 19 is a diagram illustrating the list of solution routes
`in FIG. 15.
`FIG. 20 is a diagram illustrating the components of the
`Waypoint data structure which is used in route calculation
`object of FIGS. 13–15.
`FIG. 21 is a map illustrating the concepts associated with
`a rank Suppression feature according to one alternative
`embodiment of the route calculation program.
`DETAILED DESCRIPTION OF THE
`PRESENTLY PREFERRED EMBODIMENTS
`I. Navigation System Overview
`Referring to FIG. 1, there is a block diagram of a
`navigation system 10. The navigation system 10 is installed
`in a vehicle 11, Such as a car or truck, although in alternative
`embodiments, the navigation System 10 may be located
`outside of a vehicle or may be implemented in various other
`platforms. For example, the navigation System may be
`implemented as a hand-held portable system, or may be
`implemented on a personal computer (Such as a desktop or
`portable notebook) or a personal digital assistant. The navi
`gation System may also be implemented in a networked
`environment or on a client-Server platform.
`Referring to the embodiment illustrated in FIG. 1, the
`navigation System 10 is a combination of hardware and
`Software components. In one embodiment, the navigation
`System 10 includes a processor 12, a drive 14 connected to
`the processor 12, and a non-volatile memory Storage device
`16 for Storing a navigation Software program 18, as well as
`other information, Such as configuration parameters 19. The
`processor 12 may be of any type used in navigation Systems,
`Such as 32-bit processors using a flat address Space, Such as
`a Hitachi SHI, an Intel 80386, an Intel 960, a Motorola
`68020 (or other processors having Similar or greater address
`ing space). Processor types other than these, as well as
`processors that may be developed in the future, are also
`Suitable.
`The navigation System 10 may also include a positioning
`system 24. The positioning system 24 may utilize GPS-type
`technology, a dead reckoning-type System, or combinations
`of these, or other Systems, all of which are known in the art.
`The positioning System 24 may include Suitable Sensing
`devices 25 that measure the Speed, direction, and So on, of
`the vehicle. The positioning System 24 may also include
`appropriate wireleSS communication technology to obtain a
`GPS signal, in a manner which is known in the art. The
`positioning System 24 outputs a signal 26 to the processor
`12. The signal 26 may be used by the navigation software
`program 18 that is run on the processor 12 to determine the
`location, direction, Speed, etc., of the navigation System 10.
`The navigation System 10 also includes a user interface
`31. The user interface 31 includes appropriate equipment
`that allows the end-user to input information into the navi
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 6,192,314 B1
`
`4
`gation System. This input information may include a request
`to use the navigation features of the navigation System. For
`example, the input information may include a request for a
`route to a desired destination. The input information may
`also include other kinds of information, Such as configura
`tion information or vehicle information, as explained further
`below. The equipment used to input information into the
`navigation System may include a keypad, a keyboard, a
`microphone, etc., as well as appropriate Software, Such as a
`Voice recognition program. The user interface 31 also
`includes Suitable equipment that provides information back
`to the end-user. This equipment may include a display 27,
`Speakers 29, or other means.
`The navigation system 10 uses a map database 30 stored
`on a storage medium 32. The Storage medium 32 is installed
`in the drive 14 so that the map database 30 can be read and
`used by the navigation System. The Storage medium 32 may
`be removable and replaceable So that a storage medium with
`an appropriate map database for the geographic region in
`which the vehicle is traveling can be used. In addition, the
`Storage medium 32 may be replaceable So that the map
`database 32 on it can be updated easily.
`In one embodiment, the storage medium 32 is a CD-ROM
`disc. In an alternative embodiment, the Storage medium 32
`may be a PCMCIA card in which case the drive 14 would be
`substituted with a PCMCIA slot. Various other storage
`media may be used, including fixed or hard disks, DVD
`(digital video disks) or other currently available storage
`media, as well as Storage media that may be developed in the
`future.
`The map database 30 contains information about the
`roadway network in the geographic region. FIG. 2 shows a
`map illustrating physical geographic features in a portion of
`a geographic region. FIG. 3 is a block diagram illustrating
`the data entities that represent the geographic features in
`FIG. 2. In one embodiment, the map database 30 includes
`node data and Segment data. Node data represent physical
`locations in the geographic region (Such as roadway inter
`Sections and other positions) and segment data represent
`portions of roadways between the physical locations repre
`Sented by nodes. Each road Segment in the geographic
`region is represented by a road segment data entity (i.e., a
`record) in the map database 30. Each road segment data
`record in the map database has two nodes which represent
`the coordinate positions at each end of the road Segment
`represented by the road Segment data record. The data
`records include information that can be used during route
`calculation, Such as turn restrictions, vehicle access,
`restricted driving conditions, etc. (The terms "nodes' and
`"Segments' represent only one terminology for describing
`these physical geographic features and other terminology for
`these feature is intended to be encompassed within the Scope
`of these concepts.)
`In one embodiment of the map database 30, the roadways
`are classified by rank in accordance with the importance or
`Significance of the roadway for vehicle travel. For example,
`roadways of rank “0” may be alleyways and side streets,
`roadways of rank “1” may be primary city Streets, roadways
`of rank "2" may be highways, and So on. Each road Segment
`data record in the map database 30 also identifies the rank of
`the corresponding portion of the roadway that it represents.
`As illustrated in FIG. 3, the map database 30 for a geo
`graphical area may be Stored in layers. The lowest layer
`(“0”) contains records that represent roadways of all ranks,
`the next higher layer (“1”) contains roadways of rank “1”
`and higher, the next higher layer ("2") contains roadways of
`rank "2" and higher, and So on. The road Segment records
`
`Apple Exhibit 1010
`Page 17 of 35
`
`

`

`S
`may include additional information about the represented
`road Segments, Such as the Speeds along the represented road
`Segments, turn restrictions, weight restrictions, the names of
`the roads that the Segments are parts of, address ranges along
`the road Segments, and So on. In an alternative embodiment,
`the geographic database 30 may include more than one rank
`of road in a single layer. The map database 30 may include
`additional information as well.
`Referring again to FIG. 1, the navigation application
`Software program 18 is loaded from the non-volatile
`memory 16 into a RAM 20 associated with the processor 12
`in order to operate the navigation System. The navigation
`system 10 uses the map database 30 stored on the storage
`medium 32, possibly in conjunction with the output 26 from
`the positioning System 24, to provide various navigation
`features and functions. The navigation Software program 18
`may include separate applications (or Subprograms) that
`provide these various navigation features and functions.
`These functions and features may include route calculation,
`map display, vehicle positioning (e.g., map matching), route
`guidance (wherein detailed directions are provided for
`reaching a desired destination), destination resolution
`capabilities, and other functions.
`II. The Route Calculation Tool Program
`A. Overview
`Referring to FIG. 4, in the navigation Software program
`18 the route calculation features are provided by a route
`calculation tool 40. The route calculation tool 40 is a
`computer program that may be used as part of the navigation
`Software program 18. The route calculation tool 40 deter
`mines routes between Specified locations. If used with a
`navigation Software program 18 in a navigation System
`installed in a vehicle, the route calculation tool 40 deter
`mines routes for the vehicle to travel. The route calculation
`tool 40 may be used in combination with the map database
`30 and other programs or Subprograms within the navigation
`program 18, or even with other programs outside the navi
`gation program 18 or navigation System 10. Specifically, in
`the navigation Software program 18, the route calculation
`tool 40 interfaces with a navigation application 47. The
`navigation application 47 may include appropriate programs
`that provide the remainder of the navigating functions
`provided by the navigation System 10, Such as route
`guidance, vehicle positioning, the user interface, and So on.
`Alternatively, the navigation application 47 may operate as
`a manager that uses other tool programs, Such as a geo
`coding tool 90, a route guidance tool 91, a map display tool,
`and So on, to implement one or more of the other various
`navigation functions.
`In a preferred embodiment, the route calculation tool 40
`is provided as a module that is relatively portable and that
`can be incorporated into different kinds of systems. The
`route calculation tool may be compiled into an executable
`module with the navigation application or may be used as a
`Standalone program. In a preferred embodiment, the route
`calculation tool 40 employs an object oriented approach to
`both its programming, its use of data, and its relationship to
`the navigation application 47. Each object that forms the
`route calculation tool receives input data and generates
`output data according to a predefined function and may
`invoke methods on other objects. In one present
`embodiment, each object has its own private memory which
`is opaque to other objects. In the disclosed embodiment, an
`object may be used to convey data from one object to
`another object or may be used to transform data received as
`input. The route calculation tool 40 is written in the C
`programming language although in alternative embodiments
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 6,192,314 B1
`
`6
`other programming languages may be used, Such as C++ or
`Java. In general, programming languages that Support object
`oriented programming are preferred.
`B. Objects input to and output from the Route Calculation
`Tool Program
`In one embodiment, the route calculation tool 40 com
`prises a route calculation object 50. This route calculation
`object 50 receives as input as least two waypoint objects 100
`and provides an output in the form of a route object 60. In
`a present embodiment, the route calculation object 50 may
`also use as input a configuration object 64, a vehicle object
`68, a time object 69, and an input route object 72. (There
`may be additional objects in addition to these. For example,
`there may be an object that defines Specific application
`defined callbacks, i.e., wherein the application may want
`partial Solutions, as described below.)
`(1). The configuration object
`Referring to FIG. 5, the configuration object 64 is a data
`structure that holds parameters 64(1) . . . 64(n), which are
`used to control the route calculation object 50. Some or all
`of these parameters may be configurable by the end-user.
`Some of these parameters may include items, Such as
`weighting factors, that may be used in route calculation. For
`example, these parameters may include "avoid highways,'
`"avoid U-turns,” “determine shortest route,” “determine
`quickest route,” etc. These parameters may also include the
`maximum layer of map data (as represented in FIG. 3) at
`which route Searching is to be performed and whether the
`route Searching Should use logical or physical Suppression to
`enforce the maximum layer. Some configurable parameters
`in the configuration object 64 may be selected by the
`navigation System manufacturer or by a Service technician
`and thus may not be configurable by the end-user. The data
`included in the configuration object 64 is Stored in a
`re-writable and non-volatile memory of the navigation
`system, such as the non-volatile memory 16 (in FIG. 1).
`(2). The vehicle object
`Referring to FIG. 6, the vehicle object 68 is a data
`structure that includes data 68(1) . . . 68(n) that provide the
`characteristics of the vehicle for which the route will be
`calculated by the route calculation tool 40. Under some
`circumstances, characteristics of the vehicle may affect
`generation of the route. For example, the vehicle object 68
`may include data that indicates that the vehicle is a truck
`having a given weight and number of axles. In Such a case,
`the route Searching tool 40 ensures that the calculated route
`include only roadways with weight limits that allow Such a
`vehicle. In another example, the vehicle object 68 may
`include information indicating that the vehicle is a passenger
`vehicle having more than one perSon on board. The route
`Searching tool 40 can then include lanes restricted to mul
`tiple passenger vehicles. The data included in the vehicle
`object 68 is stored in a re-writable and non-volatile memory
`of the navigation System, Such as the non-volatile memory
`16 (in FIG. 1). Some or all of the data in the vehicle object
`68 may be configurable by the end-user. Alternatively, some
`or all may be determined by the navigation System manu
`facturer or a technician.
`(3). The (output) route object
`Referring to FIG. 7, the output route object 60 is illus
`trated. The route object 60 is a data structure generated by
`the route calculation object 50. The output route object 60
`includes a Single route determined by the route calculation
`object 50. The route is comprised of a list 60(1) of road
`Segment data records (Such as the segment data records
`described in connection with FIG. 3) that represent portions
`of roadways that together comprise the calculated route. The
`
`Apple Exhibit 1010
`Page 18 of 35
`
`

`

`US 6,192,314 B1
`
`15
`
`25
`
`35
`
`40
`
`7
`route object 60 also contains waypoint information 60(2)
`describing the origin, destination, and intermediate way
`points and indicating where they are located relat