(19)
`
`(12)
`
`(cid:6)(cid:27)&(cid:11)(cid:11)(cid:12)(cid:12)(cid:15)(cid:17)(cid:15)(cid:20)(cid:17)(cid:24)(cid:12)(cid:6)
`EP 1 146 496 B1
`
`(11)
`
`(45) Date of publication and mention
`of the grant of the patent:
`22.08.2007 Bulletin 2007/34
`
`EUROPEAN PATENT SPECIFICATION
`(51) Int Cl.:(cid:3)
`G08G1/0968(2006.01) G01C21/26(2006.01)
`
`(21) Application number: 01300305.8
`
`(22) Date of filing: 15.01.2001
`
`(54) Method and system for providing routing guidance
`
`Verfahren und Vorrichtung zur Routenführung
`
`Méthode et système de guidage
`
`(84) Designated Contracting States:
`AT BE CH CY DE DK ES FI FR GB GR IE IT LI LU
`MC NL PT SE TR
`
`(30) Priority: 21.03.2000 US 531574
`
`(43) Date of publication of application:
`17.10.2001 Bulletin 2001/42
`
`(73) Proprietor: Navteq North America, LLC
`Chicago IL 60654 (US)(cid:3)
`
`(72) Inventor: McDonough, William
`Glen Ellyn,(cid:3)
`Illinois 60137 (US)(cid:3)
`
`(74) Representative: McLeish, Nicholas Alistair
`Maxwell et al
`Boult Wade Tennant
`Verulam Gardens
`70 Gray’s Inn Road
`London WC1X 8BT (GB)(cid:3)
`
`(56) References cited:
`EP-(cid:3)A- 0 854 463
`US-(cid:3)A- 6 026 346
`
`US-(cid:3)A- 5 902 349
`US-(cid:3)A- 6 038 509
`
`• PATENT ABSTRACTS OF JAPAN vol. 1999, no.
`08, 30 June 1999 (1999-06-30) & JP 11 072340 A
`(DENSO CORP), 16 March 1999 (1999-03-16)(cid:3)
`
`Note: Within nine months from the publication of the mention of the grant of the European patent, any person may give
`notice to the European Patent Office of opposition to the European patent granted. Notice of opposition shall be filed in
`a written reasoned statement. It shall not be deemed to have been filed until the opposition fee has been paid. (Art.
`99(1) European Patent Convention).
`
`Printed by Jouve, 75001 PARIS (FR)
`
`EP1 146 496B1
`
`Hyundai Exhibit 1017, Page 1 of 19
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00173
`
`

`

`1
`
`EP 1 146 496 B1
`
`2
`
`vided by the navigation system. Intersections that can be
`reached by the vehicle while calculation of a new solution
`route to the destination is being performed are identified.
`For each identified intersection, cost factors associated
`with the possible paths leading from the identified inter-
`section are modified to increase the likelihood that the
`new solution route include those paths with the least cost
`factors.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`(cid:3)[0009]
`
`Figure 1 is a block diagram illustrating a navigation
`system.
`Figure 2 is a block diagram illustrating components
`of a road segment data record included in the geo-
`graphic database of Figure 1.
`Figure 3 is a block diagram illustrating components
`of the navigation programming shown in Figure 1.
`Figure 4 is a flow chart showing steps performed by
`the off-(cid:3)route application of Figure 3.
`Figure 5A depicts the vehicle of Figure 1 approach-
`ing an intersection. Figure 5A is used in a first ex-
`ample describing operation of the off-(cid:3)route applica-
`tion of Figure 4.
`Figure 5B is a graphical representation of the inter-
`section shown in Figure 5A.
`Figure 5C shows how the turn costs of the intersec-
`tion of Figure 5A are represented in the geographic
`database of Figure 2.
`Figure 6A depicts the vehicle of Figure 1 approach-
`ing an exit ramp. Figure 6A is used in a second ex-
`ample describing operation of the off-(cid:3)route applica-
`tion of Figure 4.
`Figure 6B is a graphical representation of the con-
`trolled access road and exit ramp shown in Figure
`6A.
`Figure 6C shows how the turn costs of the controlled
`access road and exit ramp of Figure 6A are repre-
`sented in the geographic database of Figure 2.
`Figure 7A depicts the vehicle of Figure 1 approach-
`ing an intersection. Figure 7A is used in a third ex-
`ample describing operation of the off-(cid:3)route applica-
`tion of Figure 4.
`Figure 7B is a graphical representation of the inter-
`section shown in Figure 7A.
`Figure 7C shows how the turn costs of the intersec-
`tion of Figure 7A are represented in the geographic
`database of Figure 2.
`
`Description
`
`BACKGROUND OF THE INVENTION
`(cid:3)[0001] The present invention relates to navigation sys-
`tems and more particularly the present invention relates
`to providing guidance when a driver deviates from a route
`for which route guidance was previously being provided
`a navigation system.
`(cid:3)[0002] Navigation systems provide useful features,
`such as calculating a route to a desired destination and
`providing guidance for following the route. In order to
`provide these features, navigation systems use geo-
`graphic data that include information about the locations
`of roads and intersections, estimated travel times along
`road segments, the speed limits along roads, etc. Using
`these kinds of geographic data, programming algorithms
`included in navigation systems can find an optimal (e.g,
`fastest or shortest) route to a specified destination.
`(cid:3)[0003] Some navigation systems provide a feature that
`can detect if a vehicle has departed from a route for which
`route guidance was being provided (i.e., when the vehicle
`has gone "off-(cid:3)route"). Upon detecting that the vehicle has
`gone off-(cid:3)route, the navigation system calculates a new
`route to either the destination or back to the original route
`and provides guidance to the vehicle driver for following
`the new route. A factor that can complicate providing this
`feature is that the calculation of the new route may take
`several seconds during which time the vehicle position
`may change. Therefore, the point of origin from which
`the new route was calculated may not be valid several
`seconds later when the guidance for following the new
`route is available for the driver. Worse still, the vehicle
`driver may have encountered an intersection before the
`route guidance for following the new route was available
`and chosen a path leading from the intersection that was
`not part of the new route. If this occurs, the vehicle is off-
`route of the new route when the new route becomes avail-
`able thereby necessitating calculation of another new
`route from the vehicle position to either the destination
`or back to the original route.
`(cid:3)[0004] A navigation system to provide route guidance
`to a user when the vehicle in the navigation system goes
`off-(cid:3)route is known from EP-(cid:3)A-(cid:3)0 854 463.
`
`SUMMARY OF THE INVENTION
`(cid:3)[0005] According to an aspect of the invention, there
`is provided a method according to claim 1.
`(cid:3)[0006] According to an aspect of the invention, there
`is provided a navigation system according to claim 12.
`(cid:3)[0007] According to an aspect of the invention, there
`is provided a computer program according to claim 13.
`(cid:3)[0008] To address these and other objectives, embod-
`iments of the present invention comprise a method per-
`formed by a navigation system to provide guidance to a
`driver of a vehicle when the vehicle departs from a route
`to a destination for which route guidance was being pro-
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`2
`
`Hyundai Exhibit 1017, Page 2 of 19
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00173
`
`

`

`3
`
`EP 1 146 496 B1
`
`4
`
`DETAILED DESCRIPTION OF THE PRESENTLY PRE-
`FERRED EMBODIMENTS
`
`I. EXEMPLARY NAVIGATION SYSTEM PLATFORM
`
`A. Overview
`(cid:3)[0010] Referring to Figure 1, there is a diagram illus-
`trating an exemplary embodiment of a navigation system
`110. In the embodiment shown in Figure 1, the navigation
`system 110 is located in a vehicle 111, such as an auto-
`mobile, truck, or bus. The navigation system 110 is a
`combination of hardware and software components. The
`hardware components of the navigation system 110 may
`include a processor 112, memory 120, and so on. In the
`embodiment of Figure 1, the navigation system 110 also
`includes a positioning system 124 that determines the
`position of the vehicle 111 in which it is installed. The
`positioning system 124 may include sensors 125 or other
`components that sense the speed, orientation, direction,
`angular acceleration, and so on, of the vehicle 111. The
`positioning system 124 may also include a GPS system.
`(cid:3)[0011] The navigation system 110 also includes a user
`interface 131. The user interface 131 includes appropri-
`ate means 127 for receiving instructions and/or input from
`an end user of the navigation system. The instruction
`receiving means 127 may include a keyboard, keypad,
`or other type of input panel 127(cid:3)(P), a microphone 127
`(M), as well as other means for accepting end-(cid:3)user input,
`such as voice recognition software, and so on, through
`which the end user may request navigation information
`and services. The user interface 131 also includes ap-
`propriate means 129 for providing information back to
`the end user. The information providing means 129 may
`include a display 129(cid:3)(D) and speakers 129(cid:3)(S) (including
`speech synthesis hardware and software) through which
`the end user can be provided with information and serv-
`ices from the navigation system 110.
`(cid:3)[0012] All of the components described above may be
`conventional (or other than conventional) and the man-
`ufacture and use of these components are known to
`those of skill in the art
`
`B. The geographic database
`(cid:3)[0013]
`In order to provide navigation features to an end
`user, the navigation system 110 uses geographic data
`140. The geographic data 140 include information about
`one or more geographic regions or coverage areas. The
`geographic data 140 may be stored in the vehicle 11 1
`or alternatively, the geographic data 140 may be stored
`remotely and made available to the navigation system
`110 in the vehicle 111 through a wireless communication
`system which may be part of the navigation system 110.
`In another alternative, a portion of the geographic data
`140 may be stored in the vehicle 111 and a portion of the
`geographic data 140 may be stored in a remote location
`and made available to the navigation system 110 in the
`
`vehicle 111 over a wireless communication system from
`the remote location.
`(cid:3)[0014]
`In the embodiment shown in Figure 1, some or
`all of the geographic data 140 are stored on a medium
`132 which is located in the vehicle 111. Accordingly, the
`navigation system 110 includes a drive 114 (or other suit-
`able peripheral device) into which the medium 132 can
`be installed and accessed. In one embodiment, the stor-
`age medium 132 is a CD-(cid:3)ROM disk. In another alternative
`embodiment, the storage medium 132 may be a PCMCIA
`card in which case the drive 114 would be substituted
`with a PCMCIA slot. Various other storage media may
`be used, including fixed or hard disks, DVD disks or other
`currently available storage media, as well as storage me-
`dia that may be developed in the future.
`(cid:3)[0015] The geographic data 140 include data specify-
`ing the positions of the roads in the covered geographic
`region(cid:3)(s). The geographic data 140 also include data re-
`lating to the roads, such as restrictions on directions of
`travel along the roads (e.g., one-(cid:3)way streets), street ad-
`dresses along the roads, street names, speed limits
`along the roads, turn restrictions at intersections, and so
`on. The geographic data 140 may also include informa-
`tion about points of interest in the geographic area, such
`as hotels, restaurants, museums, stadiums, offices, au-
`tomobile dealerships, auto repair shops, etc. The geo-
`graphic data 140 may also include information about
`places, such as cities, towns, or other communities. The
`geographic data 140 may include other kinds of data
`about the geographic area.
`(cid:3)[0016] The geographic data 140 may take a variety of
`different forms. In one embodiment, the geographic data
`140 are in the form of one or more computer-(cid:3)readable
`data files or databases 141. Methods for forming and
`organizing a geographic database are disclosed in U.S.
`Pat. Nos. 5,953,722 and 5,974,419 and copending patent
`application Ser. No. 08/740,295, the disclosures of which
`are incorporated herein by reference. In one embodi-
`ment, the geographic database 141 contains a plurality
`of road segment data records. Each road segment data
`record represents a portion (or segment) of a navigable
`road in the geographic region. In one type of geographic
`database, there is at least one database entry (also re-
`ferred to as "entity" or "record") for each represented road
`segment in a geographic region. Each physical road seg-
`ment has two nodes associated with it, one at each of
`the endpoints of the road segment. In this embodiment,
`the geographic database also includes a plurality of data
`entities that represent these nodes. (The terms "seg-
`ment" and "node" represent only one terminology for de-
`scribing these physical geographic features and other
`terminology for these features is intended to be encom-
`passed within the scope of these concepts.)
`(cid:3)[0017] Data attributes are associated with each road
`segment data record to describe features or character-
`istics of the represented road segment. The various at-
`tributes associated with a road segment may be included
`in a single road segment record, or may be included in
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`3
`
`Hyundai Exhibit 1017, Page 3 of 19
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00173
`
`

`

`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`EP 1 146 496 B1
`6
`5
`more than one type of record which are cross-(cid:3)referenced
`the common intersection, the turn cost data 222(cid:3)(4) rep-
`to each other.
`resent the cost (e.g., travel time) to cross straight ahead
`(cid:3)[0018] Figure 2 illustrates some of the components of
`across the intersection. The turn cost data 222(cid:3)(4) can
`a road segment data record 222 included in the geo-
`also be used to represent invalid successor segments.
`graphic database 141. The road segment data record
`Invalid successor segments have an infinite (or very high)
`222 includes a segment ID 222(cid:3)(1) by which the record
`travel cost value.
`(cid:3)[0023]
`can be identified in the geographic database. The road
`In one embodiment, the geographic data are
`segment data record 222 includes data fields 222(cid:3)(2) for
`provided by Navigation Technologies Corporation of
`various attributes of the represented road segment.
`Rosemont, Illinois. However it is understood that the in-
`These attributes include the speed limit along the road
`ventive concepts disclosed herein are not restricted to
`(or a speed limit range), the type of road (e.g., controlled
`any particular source of data.
`access, ramp, bridge, tunnel, toll road, ferry, and so on),
`a functional rank, a permitted direction of travel, an ad-
`dress range, a name, a highway designation of the road
`of which the road segment is a part, and so on.
`(cid:3)[0019] The road segment data record 222 includes da-
`ta 222(cid:3)(3) identifying the endpoints of the road segment.
`In one embodiment, these data 222(cid:3)(3) include references
`222(cid:3)(3)(cid:3)(1)(cid:3)(L) and 222(cid:3)(3)(cid:3)(1)(cid:3)(R) to node data records 223
`(1) and 223(cid:3)(2) defined for the nodes corresponding to
`the endpoints of the represented road segment.
`(cid:3)[0020] Also associated with the road segment data
`record 222 are data 222(cid:3)(3)(cid:3)(2)(cid:3)(L) and 222(cid:3)(3)(cid:3)(2)(cid:3)(R) indi-
`cating valid successor segments (if any) at each of the
`endpoints of the represented road segment. A valid suc-
`cessor segment is a road segment to which vehicular
`travel is legally permitted from the represented road seg-
`ment. Also associated with the road segment data record
`222 are data 222(cid:3)(3)(cid:3)(3)(cid:3)(L) and 222(cid:3)(3)(cid:3)(3)(cid:3)(R) indicating
`invalid successor segments (if any) at each of the end-
`points of the represented road segment. An invalid suc-
`cessor segment is a road segment to which vehicular
`travel is not legally permitted from the represented road
`segment.
`(cid:3)[0021] Associated with the data indicating each iden-
`tified successor segment are data 222(cid:3)(4) indicating a turn
`cost. The turn cost data 222(cid:3)(4) indicate a cost associated
`with travel from the represented segment onto the suc-
`cessor segment via the common node (intersection) con-
`necting the represented segment and the successor seg-
`ment. The turn cost data 222(cid:3)(4) are used by functions in
`the navigation system (e.g., the route calculation function
`250 in Figure 3) to evaluate and compare different pos-
`sible travel paths in order to ascertain which travel path
`takes the least time. In the embodiment of Figure 2, the
`turn cost data 222(cid:3)(4) represent an estimate of the actual
`travel time it take to traverse the intersection between a
`represented segment and a successor segment. For ex-
`ample, if the successor segment is reached by a left turn
`from the represented segment at the common node, the
`turn cost data 222(cid:3)(4) represent an estimation of the time
`(in seconds) it takes to make the left turn from the rep-
`resented segment onto to the successor segment.
`(cid:3)[0022] The turn cost data 222(cid:3)(4) are used to represent
`the time it takes to travel onto a successor segment even
`if no turn is required to reach the successor segment.
`For example, if a successor segment is reached from the
`represented segment by traveling straight ahead across
`
`C. The navigation programming.
`(cid:3)[0024] Referring again to Figure 1, in addition to the
`hardware components and geographic database, the
`navigation system 110 includes or uses navigation pro-
`gramming 228. The navigation programming 228 in-
`cludes the software that provides for the functions and/or
`features performed by the navigation system 110. The
`navigation programming 228 uses the geographic data
`140 in conjunction with input from the end user via the
`user interface 131, and possibly in conjunction with out-
`puts from the positioning system 124, to provide various
`navigation-(cid:3)related features and/or functions.
`(cid:3)[0025] The navigation programming 228 may be
`stored in a non-(cid:3)volatile storage medium 229 in the nav-
`igation system 110. Alternatively, the navigation pro-
`gramming 228 and the geographic data 140 may be
`stored together on a single storage device or medium.
`Alternatively, the navigation programming 228 may be
`located at a remote location and may be provided to or
`accessed by the navigation system 110 over a commu-
`nications system.
`(cid:3)[0026]
`In one embodiment, the navigation program-
`ming 228 is written in the C programming language al-
`though in alternative embodiments other programming
`languages may be used, such as C++, Java, Visual Ba-
`sic, and so on.
`(cid:3)[0027] The navigation programming 228 may be
`formed of separate component applications (also re-
`ferred to as programs, subprograms, routines, or tools).
`The component applications of the navigation program-
`ming 228 work together through defined programming
`interfaces. Figure 3 shows a block diagram illustrating
`some of the component applications for one embodiment
`of the navigation programming 228 included in the nav-
`igation system 110 of Figure 1. In addition to the compo-
`nent programs shown in Figure 3, the navigation pro-
`gramming 228 may include other component sub-(cid:3)rou-
`tines or programs.
`(cid:3)[0028]
`In Figure 3, the navigation programming 228 is
`shown to include a navigation application manager 240.
`The navigation application manager 240 is a program or
`routine that provides for overall management of the func-
`tions of the navigation system 110. The navigation ap-
`plication manager 240 may also include support for and
`interfaces to the navigation system hardware, such as
`
`35
`
`40
`
`45
`
`50
`
`55
`
`4
`
`Hyundai Exhibit 1017, Page 4 of 19
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00173
`
`

`

`7
`
`EP 1 146 496 B1
`
`8
`
`the positioning system 124 and the user interface 131.
`The navigation application manager 240 includes user
`interface functions 242 to interface with the user interface
`hardware 131. These user interface functions 242 may
`provide for presenting a menu to the end user on the
`screen display 129(cid:3)(D) of the user interface hardware 131,
`accepting inputs from the end user via the input devices
`127 of the user interface hardware 131, displaying results
`to the end user on the screen display 129(cid:3)(D) of the user
`interface hardware 131, and so on.
`(cid:3)[0029] The navigation programming 228 includes sub-
`programs or routines that interface with the navigation
`application manager 240 and that provide for specific
`navigation-(cid:3)related features or functions to be performed
`by the navigation system. These sub-(cid:3)programs include
`a route calculation application 250, a route guidance ap-
`plication 252, a map display application 253, and a ve-
`hicle positioning application 256. The navigation pro-
`gramming 228 may include other navigation applications
`in addition to these.
`
`Example of operation of the navigation system.
`(cid:3)[0030] The route calculation application 250 receives
`a request to calculate a route to a desired destination.
`The request may originate with the end user. The request
`is received via the user interface 131, the user interface
`functions 242 and the manager application 240. The re-
`quest may be in the form of an identification of a starting
`location and a desired destination location. The identifi-
`cation of these locations may include the geographic co-
`ordinates of these locations. The route calculation appli-
`cation may also be provided with other data or parame-
`ters, such as driving preferences (e.g., avoid toll roads).
`(cid:3)[0031] Given at least the identification of a starting lo-
`cation and a desired destination location, the route cal-
`culation application 250 attempts to determine one or
`more solution routes between the starting location and
`the destination location. A solution route is formed of a
`series of connected road segments over which a vehicle
`can travel from the starting location to the destination
`location. When the route calculation application 250 cal-
`culates a route, it accesses the geographic data 140 and
`obtains road segment data records 222 that represent
`road segments around and between the starting location
`and the destination location. The route calculation appli-
`cation 250 uses the information in the road segment data
`records 222 to attempt to determine at least one valid
`solution route from the starting location to the destination
`location. The route calculation application 250 may use
`various means or algorithms in determining solution
`routes. In determining a valid solution route for a vehicle
`to travel, the route calculation program 250 uses the data
`attributes associated with the road segment data records
`to account for direction of travel restrictions (e.g., one-
`way streets), turn restrictions at intersections (e.g., no
`left turns), and so on. The route calculation application
`250 may attempt to find a solution route that takes the
`
`least time to travel, that covers the least distance, or that
`meets some other specifiable criteria.
`(cid:3)[0032] The route calculation application 250 provides
`an output. In the embodiment of Figure 3, the output of
`the route calculation application 250 is in the form of an
`ordered list 254 identifying a plurality of road segments.
`The plurality of road segments form the continuous nav-
`igable route between the origin and the destination that
`had been calculated by the route calculation application
`250. (The route calculation application 250 may calculate
`more than one solution route.)
`(cid:3)[0033] The list 254 of road segments determined by
`the route calculation application 250 is provided to the
`route guidance application 252. The route guidance ap-
`plication 252 uses the information in the list 254, as well
`as additional information from the geographic database
`141, to provide instructions and advice to the end user
`to travel the route defined by the list 254 output by the
`route calculation application 250. The route guidance ap-
`plication 252 may include functions that identify locations
`along the calculated route at which maneuvering instruc-
`tions may be provided to the end user. The route guid-
`ance application 252 may also include functions that for-
`mulate the maneuvering instructions for visual output
`and/or audio output. The route guidance application 252
`may provide the maneuvering instructions all at once, or
`alternatively, the route guidance application 252 may pro-
`vide the maneuvering instructions one at a time as the
`vehicle is traveling. In one embodiment, each maneuver-
`ing instruction is provided separately (or in small groups
`of combined maneuvering instructions) in advance of
`when the specific maneuver is required to be taken so
`that the end user can prepare to make the required
`maneuver.
`(cid:3)[0034]
`In order to provide maneuvering instructions at
`appropriate times and/or locations, the navigation sys-
`tem 110 uses data from the positioning system 124. The
`positioning system 124 determines the position of the
`vehicle as it is traveling. The vehicle positioning applica-
`tion 256 in the navigation programming 228 compares
`the vehicle position determined by the positioning system
`124 to the positions of the road segments in the solution
`driving route 254. Using this comparison, the maneuver
`instructions, which are related to positions along the so-
`lution route, can be provided at appropriates times as
`these positions are approached.
`(cid:3)[0035] The list 254 of road segments from the route
`calculation application 250 may also be provided to the
`map display application 253. The map display application
`253 uses the information in the list 254, as well as addi-
`tional information from the geographic database 140, to
`provide graphical maps on the display (129(cid:3)(D) in Figure
`1) of the user interface 131. The graphical maps illustrate
`the areas through which the calculated route passes. The
`path of the calculated route may be highlighted on the
`displayed maps. The map display application 253 inter-
`faces with the navigation application manager 240 so
`that the display maps are provided as the vehicle is
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`5
`
`Hyundai Exhibit 1017, Page 5 of 19
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00173
`
`

`

`9
`
`EP 1 146 496 B1
`
`10
`
`traveling the calculated route. The navigation application
`manager 240 and the map display application 253 may
`receive the outputs from the positioning system 124 and
`the map-(cid:3)matching application 256 for this purpose.
`(cid:3)[0036] Methods for route calculation are disclosed in
`Ser. No. 09/047,698, filed March 25, 1998, methods for
`providing route guidance are disclosed in Ser. No.
`08/893,201, filed July 15, 1997 and Ser. No. 09/196,279,
`filed November 19, 1998, methods for providing vehicle
`positioning are disclosed in Ser. No. 09/276,377, filed
`March 25, 1999, and methods for providing map display
`are disclosed in Ser. No. 09/047,141, filed March 24,
`1998 and Ser. No. 09/092,625, filed June 5, 1998. The
`disclosures of these six patent applications are incorpo-
`rated by reference herein. The methods disclosed in
`these patent applications represent only some of the
`ways that these functions can be provided and the subject
`matter claimed herein is not limited to any particular meth-
`od. Any suitable method now known or developed in the
`future may be employed.
`II. OFF-(cid:3)ROUTE DETECTION AND GUIDANCE
`(cid:3)[0037] Despite receiving driving instructions from the
`navigation system for following a calculated route to a
`destination, it sometimes occurs that the vehicle departs
`from the route for which route guidance was being pro-
`vided. When this occurs, the navigation system detects
`that the vehicle has departed from the route and advises
`the driver that the vehicle is no longer following the cal-
`culated route. Also, if desired by the driver, the navigation
`system provides the driver with assistance to get back
`on a route to the destination. In a present embodiment,
`these features are provided by an off-(cid:3)route application
`400. The off-(cid:3)route application 400 is included among the
`applications that are part of the software programming
`228 of the navigation system 110. The off-(cid:3)route applica-
`tion 400 may be included as part of another application,
`such as the vehicle positioning application 256, the route
`calculation application 250, the route guidance applica-
`tion 252, or another application. Alternatively, the off-
`route application 400 may be a separate application.
`(cid:3)[0038] Figure 4 show steps performed by the off-(cid:3)route
`application 400. In an initial step (Step 410), the off-(cid:3)route
`application 400 compares the current vehicle position to
`the route 254 calculated by the route calculation appli-
`cation 250. The current vehicle position is determined
`with respect to a position and direction along a segment
`represented by data 140 in the geographic database 141.
`This information can be obtained from the vehicle posi-
`tioning application 256. The comparison step determines
`whether the vehicle is located on a segment that is part
`of the solution route 254 and whether the vehicle is
`traveling in the proper direction along the segment toward
`the destination. Based upon these determinations, a de-
`cision is made whether the vehicle is on the calculated
`route 254 (Step 420). If the vehicle is on the calculated
`route 254, the driver may be given route guidance, if ap-
`
`propriate, for performing an upcoming maneuver re-
`quired to continue on the calculated route. This guidance
`may be determined by the route guidance application
`244. After the appropriate guidance is provided, the proc-
`ess loops back to the step (Step 410) of comparing the
`current vehicle position to the calculated route 254.
`(cid:3)[0039]
`If the vehicle is determined to be off route at
`step 420, a process of calculating a new route to the
`destination is started. First, the off-(cid:3)route application in-
`cludes a step that determines all the intersections located
`within a threshold distance 434 of the current vehicle po-
`sition (Step 430). The information about the locations of
`intersections is obtained from the geographic database
`141. The threshold distance 434 is determined so as to
`encompass all the intersections that could be reached
`from the current vehicle position during the time it takes
`for the navigation system to calculate a new route to the
`destination from the current vehicle position. The thresh-
`old distance 434 may be specified using a fixed or con-
`figurable distance parameter which is stored as config-
`uration data 436 in the non-(cid:3)volatile memory (229 in Figure
`1) of the navigation system 110. Alternatively, the thresh-
`old distance 434 may be calculated using the current
`vehicle speed and/or the speed limits of the roads located
`around the current vehicle position. If the threshold dis-
`tance is calculated, an estimate of the amount of time
`needed to calculate a new route is used. This time esti-
`mate would vary depending upon the hardware platform
`and resources of the navigation system. This time esti-
`mate may be stored as a parameter in the configuration
`data (436 in Figure 1). Using this time estimate, the dis-
`tance that the vehicle could travel in the estimated
`amount of time given the speed limits of the roads around
`the vehicle is calculated and used as the threshold dis-
`tance.
`(cid:3)[0040] After the intersections located within the thresh-
`old distance 434 of the current vehicle position are de-
`termined, the off-(cid:3)route application 400 applies a weight-
`ing factor 444 to the turn costs at the identified intersec-
`tions (Step 440). As described above, the geographic
`database 141 includes turn cost data 222(cid:3)(4) indicating
`an estimate of the amount of time it take to turn onto each
`successor segment from a represented road segment.
`The weighting factor 444 may be a fixed parameter. In
`one embodiment, the weighting factor is 10, although any
`arbitrarily large number will suffice. The weighting factor
`444 may be stored with the configuration data 436.
`(cid:3)[0041] After the weighting factor 444 is applied to all
`the turn costs of all the intersections located within the
`threshold distance 434 of the current vehicle position, a
`new route is calculated to the destination (Step 450). The
`new route is calculated using the route calculation appli-
`cation 250. The new route is calculated using the current
`vehicle position as the new origin and the prior destination
`as the new destination.
`(cid:3)[0042] When the route calculation application 250 cal-
`culates a new route to the destination, it uses the weight-
`ed turn costs for those intersections to which the weight-
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`6
`
`Hyundai Exhibit 1017, Page 6 of 19
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00173
`
`

`

`11
`
`EP 1 146 496 B1
`
`12
`
`ings were applied, i.e., those