(12) United States Patent
`Khavakh et al.
`
`US007054742B2
`(io) Patent No.: US 7,054,742 B2
`(45) Date of Patent:
`*May 30, 2006
`
`(54) METHOD AND SYSTEM FOR ROUTE
`CALCULATION IN A NAVIGATION
`APPLICATION
`
`(75) Inventors: Asta Khavakh, Lake Zurich, IL (US);
`William McDonough, Glen Ellyn, IL
`(US); Oleg Voloshin, Deerfield, IL
`(US); Yaoguang Wang, Rosemont, IL
`(US)
`
`(73) Assignee: Navteq North America, LLC,
`Chicago, IL (US)
`
`( * ) Notice: Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`This patent is subject to a terminal dis­
`claimer.
`
`(21) Appl. No.: 10/651,091
`(22) Filed:
`Aug. 28, 2003
`(65)
`Prior Publication Data
`US 2004/0039520 Al Feb. 26, 2004
`
`Related U.S. Application Data
`
`(62) Division of application No. 10/259,897, filed on Sep. 27,
`2002, now Pat. No. 6,678,611, which is a division of
`application No. 09/920,493, filed on Aug. 1, 2001, now Pat.
`No. 6,487,497, which is a division of application No.
`09/714,314, filed on Nov. 16, 2000, now Pat. No. 6,298,303,
`which is a division of application No. 09/047,698, filed on
`Mar. 25, 1998, now Pat. No. 6,192,314.
`
`(51)
`
`Int. Cl.
`G01C 21/36
`
`(2006.01)
`
`(52) U.S. Cl................................................................ 701/209
`
`(58) Field of Classification Search ......... 701/200 201,
`701/208-209, 207; 342/357.01, 357.13, 454-457;
`340/988, 990
`See application file for complete search history.
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`2/1986 Tachi et al.
`4,570,227 A
`8/1988 Itoh et al.
`4,763,270 A
`11/1988 Ueno et al.
`4,782,447 A
`12/1988 Hirose et al.
`4,794,528 A
`1/1989 Nakayama et al.
`4,796,189 A
`3/1989 Adams et al.
`4,812,990 A
`5/1990 Yamada
`4,926,336 A
`6/1990 Yamada
`4,937,753 A
`7/1991 Ikeda et al.
`5,031,104 A
`8/1991 Nakahara et al.
`5,041,983 A
`4/1992 Yamada et al.
`5,103,400 A
`12/1992 Yamada et al.
`5,168,452 A
`2/1993 Link
`5,184,303 A
`2/1993 Short
`5,187,667 A
`4/1993 Yoshida
`5,204,817 A
`11/1993 Tamai et al.
`5,262,775 A
`12/1993 Martin et al.
`5,272,638 A
`3/1994 Tamai et al.
`5,291,412 A
`3/1994 Tamai et al.
`5,291,413 A
`3/1994 Tamai et al.
`5,291,414 A
`4/1994 Tamai et al.
`5,303,159 A
`5/1994 Tamai
`5,311,434 A
`
`(Continued)
`
`Primary Examiner—Thu V. Nguyen
`(74) Attorney, Agent, or Firm—Frank J. Kozak; Jon D.
`Shutter; Lawrence M. Kaplan
`(57)
`ABSTRACT
`A method for route calculation using real time traffic con­
`ditions is disclosed. A transmission that includes weightings
`indicative of traffic conditions on roads is received. Then, a
`solution route is calculated by forming a list of road seg­
`ments. The list is formed by expanding a search tree
`comprised of gates. Each gate represents a physical location
`on a road segment and an accessible direction relative
`thereto. Each gate to which a weighting applies is incre­
`mented by an amount indicated in the transmission. The
`solution route is determined by expanding the search tree,
`which includes determining and evaluating successor gates.
`
`10 Claims, 13 Drawing Sheets
`
`represented by
`■PORTAL’
`
`Hyundai Exhibit 1016, Page 1 of 33
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00172
`
`

`

`US 7,054,742 B2
`Page 2
`
`U.S. PATENT DOCUMENTS
`11/1994 Hayami et al.
`5,369,588 A
`12/1994 Nomura
`5,371,678 A
`5,410,485 A
`4/1995 Ichikawa
`6/1995 Maegawa et al.
`5,428,545 A
`8/1995 Inoue et al.
`5,442,349 A
`10/1995 Odagaki et al.
`5,459,667 A
`11/1995 Tsuyuki
`5,467,276 A
`5,475,387 A
`12/1995 Matsumoto
`3/1996 Yagyu et al.
`5,502,640 A
`4/1996 Nobe et al.
`5,506,774 A
`4/1996 Kanki
`5,506,779 A
`4/1996 Smith, Jr.
`5,508,930 A
`4/1996 Fujita et al.
`5,513,110 A
`5/1996 Seda
`5,519,619 A
`
`5,521,826 A
`5,550,538 A
`5,557,522 A
`5,559,511 A
`5,608,635 A
`5,612,881 A
`5,638,280 A
`5,652,706 A
`5,659,476 A
`5,899,955 A
`5,938,720 A
`6,038,509 A
`6,128,571 A
`6,751,609 Bl *
`
`5/1996 Matsumoto
`8/1996 Fujii et al.
`9/1996 Nakayama et al.
`9/1996 Ito et al.
`3/1997 Tamai
`3/1997 Moro to et al.
`6/1997 Nishimura et al.
`7/1997 Morimoto et al.
`8/1997 LeFebvre et al.
`5/1999 Yagyu et al.
`8/1999 Tamai
`3/2000 Poppen et al.
`10/2000 Ito et al.
`6/2004 Nomura ............................. 707/3
`
`* cited by examiner
`
`Hyundai Exhibit 1016, Page 2 of 33
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00172
`
`

`

`U.S. Patent
`
`May 30, 2006
`
`Sheet 1 of 13
`
`US 7,054,742 B2
`
`FIG. 1
`
`Hyundai Exhibit 1016, Page 3 of 33
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00172
`
`

`

`U.S. Patent May 30, 2006 Sheet 2 of 13
`
`US 7,054,742 B2
`
`Hyundai Exhibit 1016, Page 4 of 33
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00172
`
`

`

`U.S. Patent
`
`May 30, 2006
`
`Sheet 3 of 13
`
`US 7,054,742 B2
`
`GEOGRAPHIC DATABASE 30
`
`LAYER n
`
`SEGMENT
`
`ID
`
`L.NODE R.NODE RANK = n other
`
`NODE
`ID LAT
`
`LONG
`
`LAYER 1
`
`SEGMENT
`
`ID
`
`L.NODE R.NODE RANK=1
`
`other
`
`NODE
`ID LAT
`
`LONG
`
`LAYER 0
`
`SEGMENT
`L.NODE I Ir.NODeI |RANK=O | lother
`
`ID
`
`NODE
`[io~] |LAT I Ilong
`
`FIG. 3
`
`Hyundai Exhibit 1016, Page 5 of 33
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00172
`
`

`

`U.S. Patent
`
`May 30, 2006
`
`Sheet 4 of 13
`
`US 7,054,742 B2
`
`Hyundai Exhibit 1016, Page 6 of 33
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00172
`
`

`

`U.S. Patent
`
`May 30, 2006
`
`Sheet 5 of 13
`
`US 7,054,742 B2
`
`CONFIGURATION
`OBJECT 64
`parameters ¢4(1)
`
`VEHICLE OBJECT 68
`
`FIG. 5
`
`TIME OBJECT 69
`(START TIME 69(1)
`
`other 69(n)
`
`FIG. 8
`
`ROUTE OBJECT 60
`
`LIST OF
`SEGMENTS
`60(1)
`
`LIST 60(2) OF WAYPOINT
`DATA STRUCTURES
`
`WAYPOINT 400
`
`WAYPOINT 400
`
`WAYPOINT 400
`
`FIG. 6
`
`FIG. 7
`
`START DATE/TIME 60(3) |
`
`RT. GENERATION
`DATE/TIME 60(4)
`
`VEHICLE OBJ. 68
`
`GEO DB VER. 60(5)
`
`S-FLAG 60(6)
`
`OTHER 60(n)
`
`Hyundai Exhibit 1016, Page 7 of 33
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00172
`
`

`

`U.S. Patent
`
`May 30, 2006
`
`Sheet 6 of 13
`
`US 7,054,742 B2
`
`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-
`
`DESCRIPTION 104
`
`DELAY 112
`
`PORTAL106
`
`LOCUS 92
`
`DIRECTIONS 107
`
`ENFORCE SIDE FLAG 109
`
`PORTAL 106
`
`LOCUS 92
`
`DIRECTIONS 107
`
`ENFORCE SIDE FLAG 109
`
`Hyundai Exhibit 1016, Page 8 of 33
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00172
`
`

`

`U.S. Patent May 30, 2006 Sheet 7 of 13
`
`US 7,054,742 B2
`
`SEGMENT ENTITY
`represented by
`
`Hyundai Exhibit 1016, Page 9 of 33
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00172
`
`

`

`U.S. Patent
`
`May 30, 2006
`
`Sheet 8 of 13
`
`US 7,054,742 B2
`
`Hyundai Exhibit 1016, Page 10 of 33
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00172
`
`

`

`U.S. Patent
`
`May 30, 2006
`
`Sheet 9 of 13
`
`US 7,054,742 B2
`
`ROUTE CALCULATION OBJECT 50
`
`Hyundai Exhibit 1016, Page 11 of 33
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00172
`
`

`

`U.S. Patent
`
`May 30, 2006
`
`Sheet 10 of 13
`
`US 7,054,742 B2
`
`ROUTE CALCULATION OBJECT 50
`
`Hyundai Exhibit 1016, Page 12 of 33
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00172
`
`

`

`U.S. Patent
`
`May 30, 2006
`
`Sheet 11 of 13
`
`US 7,054,742 B2
`
`FIG. 16
`
`ROUTE OBJECT WAYPOINT
`DATA STRUCTURE 400
`
`DESCRIPTION 404
`POSITION (LAT, LONG) 422
`
`2 LOCI (ENTRANCE/EXIT) 422
`
`DISTANCE 418
`
`TIME 416
`
`COST 414
`
`INDEX TO
`SEGMENT LIST 424
`
`TYPE (ORIGIN/
`DESTINATION/
`INTERMEDIATE) 420
`
`GATE 124
`ASSOCIATED NODE 125
`
`TARGET NODE 127
`
`PREDECESSOR 131
`
`SEGMENT 129
`
`TIME 130
`
`COST 132
`
`DISTANCE 133
`FIG. 17
`
`FIG. 20
`
`ROUTE CALCULATION OBJECT
`WAYPOINT DATA STRUCTURE 450
`
`DESCRIPTION 404
`
`POSITION (LAT, LONG) 402
`
`2 LOCI (ENTRANCE/EXIT) 422
`
`PORTAL 106
`
`LOCUS 92
`
`DIRECTIONS 107
`
`ENFORCE SIDE FLAG 109
`
`PORTAL 106
`
`LOCUS 92
`
`DIRECTIONS 107
`
`ENFORCE SIDE FLAG 109
`
`DELAY 421
`
`COST 414
`
`TIME 416
`
`DISTANCE 418
`
`Hyundai Exhibit 1016, Page 13 of 33
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00172
`
`

`

`U.S. Patent
`
`May 30, 2006
`
`Sheet 12 of 13
`
`US 7,054,742 B2
`
`SEED GATE 108
`
`POSITION 125
`LOCUS FROM
`PORTAL
`
`TARGET NODE 127
`
`SEGMENT 129
`SEGMENT FROM
`LOCUS
`
`PREDECESSOR 131
`
`FIG. 18
`
`LIST OF SEGMENTS 500
`
`SEGMENT
`
`SEGMENT
`
`FIG. 19
`
`SEGMENT
`
`Hyundai Exhibit 1016, Page 14 of 33
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00172
`
`

`

`U.S. Patent May 30, 2006 Sheet 13 of 13
`
`US 7,054,742 B2
`
`Z k
`
`Hyundai Exhibit 1016, Page 15 of 33
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00172
`
`

`

`1
`METHOD AND SYSTEM FOR ROUTE
`CALCULATION IN A NAVIGATION
`APPLICATION
`
`REFERENCE TO RELATED APPLICATIONS
`The present is a divisional of Ser. No. 10/259,897, filed on
`Sep. 27, 2002, now U.S. Pat. No. 6,678,611, which was a
`divisional of Ser. No. 09/920,493 filed Aug. 1, 2001, now
`U.S. Pat. No. 6,487,497, which was a divisional of Ser. No.
`09/714,314 filed Nov. 16, 2000, now U.S. Pat. No. 6,298,
`303, which was a division of Ser. No. 09/047,698 filed Mar.
`25,1998, now U.S. Pat. No. 6,192,314, the entire disclosures
`of which are incorporated herein by reference.
`
`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
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 7,054,742 B2
`
`2
`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 elfectively a route that includes stops at one or more
`intermediate locations along the way between a starting
`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 dilferent 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 oil 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.
`
`Hyundai Exhibit 1016, Page 16 of 33
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00172
`
`

`

`US 7,054,742 B2
`
`3
`is a diagram illustrating the components of the
`FIG. 9
`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.
`is a diagram illustrating the geographic features
`FIG. 12
`represented by the waypoint object of FIG. 11.
`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.
`
`5
`
`10
`
`15
`
`20
`
`4
`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­
`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
`
`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 FIG. 17 when used as a seed gate.
`FIG. 19 is a diagram illustrating the list of solution routes
`in FIG. 15.
`25
`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
`30
`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 nonvolatile 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
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Hyundai Exhibit 1016, Page 17 of 33
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00172
`
`

`

`5
`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
`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 in
`order to operate the navigation system. The navigation
`system 10 uses the map database 30 stored oil 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
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 7,054,742 B2
`
`6
`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
`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 Calcula­
`tion 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-tums,” “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.
`
`Hyundai Exhibit 1016, Page 18 of 33
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00172
`
`

`

`7
`(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
`route object 60 also contains waypoint information 60(2)
`describing the origin, destination, and intermediate way­
`points and indicating where they are located relative to the
`list 60(1) of road segments. (This waypoint information is
`contained in a plurality of route waypoint data structures 400
`derived from the route calculation object waypoint data
`structure 550, described below.) The output route object 60
`is provided to the navigation application 47 that uses the list
`60(1) of road segment data records and the waypoint infor­
`mation 60(2) in the route object 60 to provide various
`navigation functions, such as provide instructions to the
`driver, generate graphical display maps of the route, and so
`on.
`In addition, the route object 60 may include other items of
`data. These items may include a start date/time 60(3). This
`item of data may be derived from the start date/time 69(1),
`described below. The route object 60 may also include a
`route generation start date/time 60(4). This item of data
`corresponds to the date and time at which the route was
`calculated. The route object 60 also may include a copy of
`the vehicle object 68, described above. The route object 60
`may also include data 60(5) that indicates the version of the
`geographic database that was used in developing the list of
`segments 60(1). The route object 60 may also include an
`“s-flag” item of data 60(6). This item of data indicates
`whether particular kinds of segment or node records are
`included in the list of segments 60(1). In particular, in some
`databases, there are segment records that represent aggre­
`gations of individual road segments and node records that
`represent a plurality of nodes. If either of these kinds of
`records is included in the list of segments 60(1), the s-flag
`item of data 60(6) is set. In addition, the route object 60 may
`include other kinds of data 60(n).
`(4) . The (Input) Route Object.
`When providing certain functions as descri