(19) United States
`(12) Patent Application Publication (10) Pub. No.: US 2006/0116818 A1
`Chao et al.
`(43) Pub. Date:
`Jun. 1, 2006
`
`US 200601 16818A1
`
`(54) METHOD AND SYSTEM FOR MULTIPLE
`ROUTENAVIGATION
`(75) Inventors: Yi-Chung Chao, Fremont, CA (US);
`Robert Rennard, Gilroy, CA (US);
`Salman Dhanani, Redmond, WA (US)
`Correspondence Address:
`IRENE HU
`2033 RALSTON AVE, PMB 146
`BELMONT, CA 94.002 (US)
`(73) Assignee: Televigation, Inc., Sunnyvale, CA
`(21) Appl. No.:
`11/004,198
`
`(22) Filed:
`
`Dec. 1, 2004
`
`Publication Classification
`
`(51) Int. Cl.
`GOIC 2L/30
`
`(2006.01)
`
`(52) U.S. Cl. ...................... 701/211: 701/208; 455/4.56.1:
`455/457; 340/990
`
`(57)
`
`ABSTRACT
`
`Method and system for providing multiple route navigation
`guidance. The system comprises a client integrated with a
`mobile communication device (e.g. PDA, cellular telephone,
`etc.) and a server communicating via wireless carriers and
`networks. The server obtains a users initial position, a
`user-designated destination, and calculates multiple routes
`from the user's initial position to the destination. The client
`displays turn-by-turn navigation instructions to the user
`using the multiple routes sent by the server. If the client
`detects a deviation from the multiple routes, the client sends
`a request for new multiple routes to the server. Then, the
`server recalculates new multiple routes from the user's
`current position to the destination and sends navigation
`information related to the new multiple routes to the client.
`
`
`
`
`
`
`
`CLIENT SENDSUSER COORDINATES
`
`sERVERDETERMINEsusER's INITIALLOCATION AND CALCULATESMULTIPLEY
`
`ROUTES
`
`client Receives THEcAlcuATED MULTIPLE RouTESFROM THE SERVER
`AND STORES THE MULTIPLE ROUTES
`
`58
`
`
`
`510
`-4-
`DOESUSER
`---
`MOVE ALONG ONE OF THE MULTIPLE
`---
`ROUTES?
`-512.
`I YES
`THE CLIENT PROVIDES THE USER WITHNAVIGATION GUIDANCE
`
`End
`NAVIGATION.
`
`56
`-514.
`(
`YES
`USER REACHED DESTINATION?c
`-
`
`
`
`No
`
`Hyundai Exhibit 1020, Page 1 of 15
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00173
`
`

`

`Patent Application Publication Jun. 1, 2006 Sheet 1 of 7
`
`US 2006/01 16818 A1
`
`„-/ T?R?S
`
`NOITÝÐIAWN.
`
`
`
`
`
`
`
`
`
`
`
`Hyundai Exhibit 1020, Page 2 of 15
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00173
`
`

`

`Patent Application Publication Jun. 1, 2006 Sheet 2 of 7
`
`US 2006/01 16818 A1
`
`s
`
`
`
`: 2
`S3883. 9 p.
`co:
`555 he Lu
`E.
`S. A
`99.99 SEES
`to coo s f
`
`
`
`S.
`
`Hyundai Exhibit 1020, Page 3 of 15
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00173
`
`

`

`Patent Application Publication Jun. 1, 2006 Sheet 3 of 7
`
`US 2006/0116818A1
`
`
`
`Hyundai Exhibit 1020, Page 4 of 15
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00173
`
`

`

`Patent Application Publication Jun. 1, 2006 Sheet 4 of 7
`
`US 2006/01 16818 A1
`
`
`
`Hyundai Exhibit 1020, Page 5 of 15
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00173
`
`

`

`Patent Application Publication Jun. 1, 2006 Sheet 5 of 7
`
`US 2006/01 16818 A1
`
`
`
`Hyundai Exhibit 1020, Page 6 of 15
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00173
`
`

`

`Patent Application Publication Jun. 1, 2006 Sheet 6 of 7
`
`US 2006/0116818A1
`
`a
`
`
`
`CLIENTINPUTSSELECTSADESTINATION
`
`CLIENT SENDSUSER COORDINATES
`
`SERVERDETERMINESUSER's INITIAL LOCATION AND CALCULATES MULTIPLE
`ROUTES
`
`- 502
`
`-506
`
`- 508
`
`WWWW
`
`------
`
`-
`
`CLIENT RECEIVES THE CALCULATED MULTIPLE ROUTES FROM THESERVER
`ANESTORES THE MULTIPLE ROUTES
`
`
`
`
`
`
`
`
`
`
`
`- 510
`- N
`- DOESUSER N
`3 MOVE ALONG ONE OF THE MULTIPLE
`r-
`ROUTES
`le:
`
`
`
`THE CLENT PROVIDES THE USER WITHNAVIGATION GUIDANCE
`
`516. 6.
`Avon
`
`END
`
`
`
`- 54.
`
`3SER REACHED DESTINATION)-
`
`NO
`
`FIG. 5
`
`Hyundai Exhibit 1020, Page 7 of 15
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00173
`
`

`

`Patent Application Publication Jun. 1, 2006 Sheet 7 of 7
`
`US 2006/0116818A1
`
`506
`Ya
`
`SERVER PREDICTS THE ORIGIN BASED ON THE POSITION INFORMATION
`
`602
`
`YES
`
`-604
`NO
`SVELOCITY EQUAL TOZEROc
`
`
`
`.606
`
`SERVERSEARCHESFORTHEROADS
`NEARBYTHE USER AND CONSIDERS
`TWO HEADINGS ONEACH ROAD
`
`NO
`
`
`
`
`
`
`
`3 INDETERMININGUSER.
`NLOCATION? -
`YES.
`60
`serversenDsouery to THE
`CLIENT FOR AUSERINPUT
`- 612
`CLIENT SENDS ANSWERTO THE
`QUERYTORESOLVE THE
`AMBIGUITY
`
`
`
`
`
`
`-614
`
`
`
`SERVER CALCULATES AT LEAST ONE ROUTE
`
`FIG. 6
`
`Hyundai Exhibit 1020, Page 8 of 15
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00173
`
`

`

`US 2006/01 16818 A1
`
`Jun. 1, 2006
`
`METHOD AND SYSTEM FOR MULTIPLE ROUTE
`NAVIGATION
`
`CROSS REFERENCE TO RELATED
`APPLICATIONS
`0001) This application relates to U.S. Pat. No. 6,807,483,
`“Method And System For Prediction-Based Distributed
`Navigation,” issued on Oct. 19, 2004, and U.S. patent
`application Ser. No. 10/619,974, “Method and System for
`Distributed Navigation filed on Jul. 15, 2003; both appli
`cations being hereby incorporated in its entirety by refer
`CCC.
`
`BACKGROUND INFORMATION
`0002) 1. Field of Invention
`0003. The present invention relates generally to naviga
`tion systems and location-based information delivery, and
`more particularly, to a method and system for a multiple
`route navigation system wherein a client provides navigation
`guidance using the multiple routes calculated by a remote
`SeVe.
`0004 2. Description of Related Art
`0005 Presently, a rapid growth in technological fields
`Such as the personal digital assistant (PDA) and cellular
`telephones has fueled consumer interest in products that
`provide on-call real-time guidance and communication. One
`Such technological advance is a navigation system that
`allows its users to reach destinations by providing turn-by
`turn instructions along a calculated route.
`0006 Conventional navigation systems are typically sat
`ellite-based Global Positioning System (GPS) devices that
`have been incorporated into automobile navigation systems.
`Additional information regarding conventional navigation
`systems can be found in U.S. Pat. Nos. 5,938,720, 5,928,
`307, 5,922,042, 5,912,635, 5,910,177, 5,904,728, 5,902,350,
`all incorporated herein by reference. Such conventional
`automobile navigation systems, however, are expensive and
`inconvenient to use. Therefore, there is a need to incorporate
`navigation capabilities so that a user may access real-time
`turn-by-turn route instructions via personal handheld
`devices such as a wireless cellular phone or a personal
`digital assistant (PDA) device.
`0007) A variety of systems are known in the art for
`providing users with electronic routing maps and navigation
`aids. A typical approach can be found in U.S. Pat. Applica
`tion Publication 2004/0030493, by Pechatnikov et al., that
`discloses a method for displaying a corridor map on a mobile
`client. Such a conventional navigation system, however, has
`several obstacles to overcome. One such obstacle is the
`amount of geographic data needed to provide reasonably
`detailed navigational information. Small handheld devices
`comprise limited embedded memory that may not be
`adequate for storing a large amount of geographic informa
`tion essential for navigational purposes.
`0008. Due to limited client memory capacity, conven
`tional distributed navigation systems assign a nominal route
`calculation tasks to the server, and allocate rerouting calcu
`lations almost exclusively to the server. Typically, the client
`requests a rerouting calculation whenever the user deviates
`from the nominal route. In order to retrieve and display
`
`navigation information to the user, the client must frequently
`communicate with the server. Such constant communication
`may be time consuming and the information may be inac
`curate due to communication delays. Thus, there is a need
`for a client-server navigation system, wherein the client can
`provide navigation guidance to the user without resorting to
`the server frequently for a new nominal route.
`
`SUMMARY OF THE INVENTION
`0009. The present invention provides a method and sys
`tem for providing multiple route navigation guidance. The
`system comprises a client integrated with a mobile commu
`nication device (e.g. PDA, cellular telephone, etc.) and a
`server communicating via wireless carriers and networks.
`0010. In one embodiment, the server receives a destina
`tion sent by the client, determines a users initial position
`and proceeds to calculate a set of destination routes. The
`server then sends a set of routing information including
`navigation information related to the set of destination
`routes to the client and the client displays turn-by-turn
`navigation instructions to the user. Moreover, while the user
`is traveling from the initial position to the destination, the
`client periodically queries the user's position with position
`ing techniques such as the Global Positioning System
`(GPS). If a deviation from the set of destination routes is
`detected, the client sends a request for a new set of desti
`nation routes to the server. Then, the server calculates a new
`set of destination routes from the user's current position to
`the destination and sends navigation information related to
`the new set of destination routes to the client.
`0011. The present invention reduces excessive reroute
`communication between the client and the server in a
`navigation system by storing the navigation information in
`the client and providing turn-by-turn navigation instruction
`via the client. The reduced communication between the
`client and the server further diminishes possible reroute
`errors caused by communication delays. Moreover, the
`amount of navigation information stored in the client is
`dynamic and may depend on factors such as the clients
`storage and/or processing capabilities.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`0012. The accompanying drawings that are incorporated
`in and form a part of this specification illustrate embodi
`ments of the invention and together with the description,
`serve to explain the principles of the invention:
`0013 FIG. 1A is an architectural diagram illustrating an
`embodiment of an interactive real-time multiple route navi
`gation System.
`0014 FIG. 1B is an architectural diagram illustrating an
`alternative embodiment of an interactive real-time multiple
`route navigation system.
`0015 FIG. 2 is a schematic diagram of server-calculated
`multiple routes from a user origin to a destination, wherein
`a client is capable of rerouting independently of the server
`according to one embodiment of the present invention.
`0016 FIGS. 3A-C are schematic diagrams illustrating
`various approaches to calculate multiple routes at the origin
`in which the velocity of the user is zero in accordance with
`one embodiment of the present invention.
`
`Hyundai Exhibit 1020, Page 9 of 15
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00173
`
`

`

`US 2006/01 16818 A1
`
`Jun. 1, 2006
`
`0017 FIGS. 4A-B are schematic diagrams illustrating
`various approaches to predict users initial position in which
`the velocity of the user is non-zero in accordance with
`another embodiment of the present invention.
`0018 FIG. 5 is an illustrative flow chart showing the
`steps for communication between client and server in a
`real-time multiple route navigation system according to one
`embodiment of the present invention.
`0019 FIG. 6 is an illustrative flow chart showing the
`steps for determining the origin and calculating multiple
`routes according to one embodiment of the present inven
`tion.
`
`DETAILED DESCRIPTION
`0020) The following description is presented to enable
`one of ordinary skill in the art to make and use the invention
`and is provided in the context of a patent application and its
`requirements. In the following description, specific nomen
`clature is set forth to provide a thorough understanding of
`the present invention. It will be apparent to one skilled in the
`art that the specific details may not be necessary to practice
`the present invention. Furthermore, various modifications to
`the embodiments will be readily apparent to those skilled in
`the art and the generic principles herein may be applied to
`other embodiments not necessarily enumerated herein.
`Thus, the present invention is not intended to be limited to
`the embodiments shown but is to be accorded the widest
`scope consistent with the principles and features described
`herein.
`0021 One of the key components of a navigation system
`is the determination of the location (or position) of a user. It
`is intended that the term location referred to herein com
`prises a geographic location or geographic information
`relating to the position of an object. A location may contain
`three-dimensional information that completely defines the
`exact position of an object. In some additional embodiments,
`a location may contain information that is not sufficient to
`completely define the position of an object. Broadly defined,
`as used herein, a location also may include speed, time,
`direction of movement, etc. of an object.
`0022. One skilled in the art would appreciate that the
`format with which a location is expressed is not critical to
`some embodiments of the invention. For example, in some
`embodiments, location information is presented in the for
`mat of (x, y), where x and y are two ordinates that define the
`geographic location, i.e., a position of a user. In an alterna
`tive embodiment, location information is presented by lon
`gitude and latitude related information. In another embodi
`ment of the present invention, the location information also
`includes a velocity element comprising a speed component
`and a heading component.
`0023 FIG. 1A shows an architecture for an interactive
`real-time multiple route navigation system 100 in accor
`dance to one embodiment of the present invention. The
`various components and their interaction will now be
`described. Wireless device 104 may take the form of a
`cellular telephone, satellite telephone, wireless Personal
`Digital Assistant (PDA), personal computer or other suitable
`device having wireless communications capability. Herein
`after, a term “client device' (or, shortly “client') may be
`used interchangeably with the term "wireless device” as one
`
`of the major functions of wireless device 104 may be
`receiving navigation information from a server.
`0024 Wireless device 104 may be equipped with posi
`tioning capability that takes the form of, for example, Global
`Positioning Systems (GPS) that may receive signals from a
`GPS satellite 102, Enhanced 911 (E911), or some other
`positioning systems as they become available. One skilled in
`the art will appreciate that the present invention is not
`limited to any particular positioning technology. In one
`embodiment, wireless device 104 is manufactured with
`built-in positioning capabilities. In FIG. 1A, only two
`wireless devices 104a–b are shown for clarity illustration.
`However, it should be apparent to those of ordinary skill that
`the present invention may be practiced with nay number of
`wireless devices.
`0.025
`Wireless device 104 may not need to carry map
`information. The only limitation with respect to the memory
`and CPU is that wireless device 104 has sufficient memory
`to store multiple routes (or, equivalently, a set of destination
`routes) transmitted from a server and CPU capability to
`guide the user using the stored multiple routes, as will be
`explained later. In one embodiment, the capabilities of
`wireless device 104 may be enhanced through interfacing
`with modular attachments. A major function of wireless
`device 104 is to provide an interface between the invention
`and a user.
`0026. As will be described more fully below, wireless
`device 104 may provide a user interface for displaying
`graphical, textual or audible information. The user interface
`incorporates the user's sensory capabilities within the inven
`tion, allowing the user to interact with electromechanical
`components of the invention, such as by allowing the user to
`relay and receive location information by means of audible
`signals, voice, or audiovisual, graphical, or combination
`thereof of location information displayed or transmitted on
`wireless device 104. Where a text-displaying device is used,
`enhanced performance is achieved through wireless device
`104 displaying several lines of text. One skilled in the art
`realizes that many more implementations are possible for
`wireless device 104 without deviating from the teachings of
`this invention.
`0027. In one embodiment, where wireless device 104 is
`equipped with directional capabilities such as through the
`use of gyroscope, geomagnetic sensing, or GPS provided
`heading, the system 100 may provide real-time directional
`as well as navigational information. Illustratively, the system
`100 may determine that the user must proceed north and the
`user is facing north, wireless device 104 may display an
`upward pointing arrow indicating that the user should pro
`ceed straight ahead. However, where the user must proceed
`north and he is facing south, wireless device 104 may show
`a downward pointing arrow indicating that the user should
`proceed backward or, more reasonably, turn around to face
`north and then proceed. In another implementation with a
`more enhanced display, more detailed and broader map
`information may be displayed with more stylistic prompts to
`the user.
`0028. In another embodiment, wireless device 104 may
`be connected to an accessory display. For example, a wire
`less device 104 appropriate for walking may be enhanced by
`interfacing with a device with additional features such as a
`car-mounted display or portable computer to become better
`
`Hyundai Exhibit 1020, Page 10 of 15
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00173
`
`

`

`US 2006/01 16818 A1
`
`Jun. 1, 2006
`
`equipped for automobile navigation. In certain embodiments
`of the invention, the accessory device provides, without
`limitation, enhanced display capabilities, enhanced memory
`capacity, increased computational power, or increased
`throughput.
`0029) Referring back to FIG. 1A, wireless carrier 106
`may provide wireless connectivity between wireless device
`104 and navigation server 114 to be described further below.
`Examples of wireless carrier 106 may include cellular
`telephone carriers and satellite communications carriers. In
`achieving wireless connectivity, wireless carriers may pro
`vide an existing infrastructure for the wireless devices and
`distributed navigation servers. Because of the adaptive inter
`action with the user, information ranging from general to
`very specific may be relayed to the user for a wide range of
`navigation applications.
`0030. While keeping within the teachings of the inven
`tion, wireless carrier 106 may provide positioning informa
`tion such as through GPS, E911 or other positioning sys
`tems. Alternatively, positioning information may be
`obtained through a third party means and then used by
`wireless carrier 106. For example, wireless service resellers,
`wireless internet service providers (ISPs), or satellite wire
`less carriers, among others, may provide the services nec
`essary to practice the invention. In an embodiment of the
`invention, wireless carrier 106 may receive and transmit
`analog or digital information from the wireless device 104
`and direct such information downstream to other compo
`nents of the invention. Similarly, wireless carrier 106 may
`receive information from components of the invention and
`then direct such information to wireless device 104.
`0031. As shown in FIG. 1A, wireless carrier 106 may be
`connected to gateway 110 via network 108, wherein gate
`way 110 may be further connected to navigation server 114
`through another network 112. Gateway 110 may be provided
`by, among others, wireless carriers, ISPs, or other telecom
`munications providers. In one embodiment of the invention,
`networks 108 and 112 may be the Internet. The Internet
`provides advantages because it is a widely distributed net
`work reaching many areas of the world. In another embodi
`ment, networks 108 and 112 may be implemented as a
`proprietary network. By implementing a specialized net
`work, networks 108 and 112 may be customized to provide
`minimal latency and optimal performance.
`0032. As shown in FIG. 1A, a navigation server 114 may
`be incorporated as part of the invention by communicating
`via network 112. Navigation server 114 may comprise street
`map information, traffic, weather, and other navigation
`related as well as points of interest information to facilitate
`accurate navigation and flexibility. In this manner, wireless
`device 104 may be not burdened with carrying all the
`necessary information required to process proper navigation.
`In one embodiment, navigation server 114 may also process
`location specific information Such as real-time traffic infor
`mation. In an alternative embodiment, traffic information
`may be obtained from a separate server 116 of other service
`providers. By observing and comparing their positions,
`speeds and times, and making further comparisons with
`nominal Street speed limits in a map database, real-time
`traffic information may be generated by the server 116 and
`then directed to the navigation server 114. At each request of
`multiple route calculation from the wireless device 104,
`
`navigation server 114 may dynamically determine new
`multiple routes for a particular user responsive to ever
`changing conditions. The technique to determine new mul
`tiple routes will be detailed later.
`0033. An alternative embodiment 120 of the system
`architecture of the present invention is shown in FIG. 1B. As
`shown in FIG. 1B, wireless device 124, GPS satellite 122,
`wireless carrier 126 and navigation server 130 may be
`substantially similar to their counterparts described in FIG.
`1A. Direct links 128, however, provide an alternative
`embodiment to the function of gateway 110 and networks
`108 and 112 of FIG. 1A. The direct link architecture is
`applicable where Internet infrastructure is not well estab
`lished or fast response is desired for user navigation or other
`location specific information services. Illustratively, TI,
`Frame Relay, etc. linked by a LAN or WAN are appropriate
`for direct link 128. In another embodiment, direct links 128
`may be implemented as hard-wired connections between
`wireless carrier 126 and navigation server 130 where wire
`less carrier 126 and navigation server 130 are collocated in
`a central office.
`0034 FIG. 2 is a schematic diagram of server-calculated
`multiple routes 200 from a user origin to a destination,
`wherein a client is capable of rerouting independently of the
`server, according to one embodiment of the present inven
`tion. As illustrated in FIG. 2, multiple routes 200 may be a
`vector map and include a user initial position denoted
`"origin”202, a destination 204, a preferred route denoted
`214, intermediate points 206a-e and road branches 208, 210,
`212, 215, 216 and 218. By the term “vector map' is meant
`that each of the multiple routes comprises a set of coordi
`nates. For the purpose of illustration, only five intermediate
`points 206 and six road branches 208, 210, 212, 215, 216
`and 218 are shown in FIG. 2. However, it should be
`apparent to those of ordinary skill in the art that the present
`invention can be practiced with any number of points and
`branches.
`0035 Navigation server 114 receives GPS information
`from a client 104 to determine the origin 202. The technique
`to determine the origin 202 will be explained in following
`sections. Navigation server 114 also receives information of
`the destination 204 from the client 104. Then, based on
`origin 202 and destination 204, it may determine multiple
`routes 200 that may include preferred route 214 and road
`branches 208, 210, 212, 215, 216 and 218. Each of the road
`branches 208, 210, 212, 215, 216 and 218 represent a route
`that the user can take intentionally or unintentionally devi
`ating from preferred route 214.
`0036.
`It is noted that road branch 213 at point 206a may
`not be included in the multiple routes 200 since it may not
`be likely that the user may deviate onto the branch 213 by
`mistake, i.e., the branch 213 is a low risk branch. The risk
`probability of deviation at each road branch of the interme
`diate points 206 may be evaluated. In case of low risk
`probability, such branch may not be included in multiple
`routes 200 so that the volume of data included in multiple
`routes 200 may be optimized. The risk probability may be
`based on several parameters) such as statistical data, geo
`metric complexity of the intersection and size of the branch,
`etc. The risk probability may be also determined by the
`users habit. For example, rather than staying on the calcu
`lated multiple routes 200, the user has consistently selected
`
`Hyundai Exhibit 1020, Page 11 of 15
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00173
`
`

`

`US 2006/01 16818 A1
`
`Jun. 1, 2006
`
`a route that is not included in the multiple routes 200, and
`the client and/or server may then set the user selected route
`with Zero risk probability.
`0037. The amount of navigation information received by
`client 104 may depend on factors such as user-designated
`settings or storage and/or processing capabilities of the
`client 104. In one embodiment of the present invention, the
`client 104 may receive navigation information for the entire
`multiple routes 200 from origin 202 to destination 204. In a
`second embodiment, navigation server 114 may divide mul
`tiple routes 200 into several sections, such as sections 222,
`224 and 226, of constant (e.g. 100 feet per section) or
`varying (e.g. 50 feet from the user initial position for the first
`section, 100 feet for the second section, etc.) distances, and
`client 104 receives and stores multiple route information for
`the next section at the end of the current section or the
`beginning of the next section. In an embodiment where the
`section lengths are not constant, the length of each section
`may rely on various factors such as the street and branch
`density Surrounding the section. Moreover, regardless of
`how multiple routes 200 are divided, client 104 schedules
`the query of further sections of multiple routes 200 based on
`factors such as distance consumption and/or user speed.
`Once the user has traveled into the next section, previous
`section data may be removed from the storage of client
`device 104.
`0038. Upon receipt of multiple route data from a server,
`the client 104 may store the multiple routes data and user
`may start navigation from its origin 202 toward the desti
`nation 204 along preferred route 214. The client 104 may
`provide the user with turn-by-turn instructions along pre
`ferred route 214. However, as will be explained later, the
`user may take one of the branches 208, 210 and 212.
`Typically, client 104 may update its user location and
`direction based on the GPS information received from
`satellite 102. If the client 104 detects a deviation from the
`preferred route 216 into one of the three branches 208, 210
`and 212, it may provide the user with guidance. For
`example, the client 104 may suggest a u-turn 210b when the
`user is on the road 210 and proceed in the direction 210a.
`Likewise, when the user travels on branch (or, equivalently,
`road) 208 or 212 and proceeds in the direction 208a or 212a,
`the user may be guided back to the preferred route 214 by
`an instruction following the direction 208b or 212b, respec
`tively.
`0039. As mentioned, client 104 may receive GPS signal
`continuously and update the user's current position. Devia
`tion from the preferred route 214 is considered “local” if the
`user's current position is on one of the branches. Such as
`208, 210 and 212, included in the multiple routes 200. In
`case of local deviation, the client 104 may guide the user
`back to the preferred route 214 without requesting calcula
`tion of new preferred routes to the navigation server 114,
`which may translate into savings of excessive reroute com
`munication time between the client 104 and navigation
`server 114 and computional resources of the navigation
`server 114. If the user travels on a road that is not covered
`by the multiple routes 200, the client 104 may request new
`multiple routes to the navigation server 114, which is a
`fallback mechanism.
`0040. In one embodiment, a predefined or user and/or
`system set threshold value may be used to determine
`
`whether or not the user has deviated from multiple routes
`200. The threshold by which deviation is determined may
`vary depending on the area in which the user is traveling. For
`example, the threshold may be set relatively low in envi
`ronments that comprise little noise Such as a sparsely
`populated area or a highway where the positioning measure
`ments are relatively reliable; and the threshold may be set
`relatively high in environments that comprising a lot of
`noise Such as a business district of a downtown urban area
`where a multitude of high-rise structures may impair the
`accuracy of the positioning system. In another embodiment,
`the deviation detection may be a feature set by user prefer
`ence and can be turned on or off as desired.
`0041 At the intermediate point 206a, the user may be
`guided back to the preferred route 214 by a u-turn 216b if the
`user travels in a direction 216a on road 216. As mentioned,
`if a branch is determined to be at low risk, such as branch
`213, the branch may not be included in the multiple routes
`200. At the intersection 206b, the user may proceed in a
`direction 218a. Then, the client 104 may guide the userback
`to the preferred route 214 by a u-turn on the branch 218b or
`an alternative approach 218c along a road 220. At the
`destination 204, the user may overshoot as indicated by an
`arrow 222a. Then, the client 104 may guide the user to the
`destination by a u-turn 222b.
`0042. As mentioned above, navigation server 114 may
`determine origin 202 using GPS information sent by client
`104. FIG. 3A is a schematic diagram 300 illustrating one
`approach to calculate multiple routes at an origin in accor
`dance with one embodiment of the present invention. As
`shown in FIG. 3A, the origin 302 may be located in a
`parking lot or a shopping mall 301. In this case, navigation
`server 114 may not be able to determine which direction the
`user may select from eight possible directions 310a-h. To
`calculate multiple routes 200 considering all possible sce
`narios, navigation server 114 may search nearby roads using
`concentric circles 304, 306 and 308. Starting from the
`smallest circle 304, the roads touching the circles 304,306
`and 308 are searched until a satisfactory amount of map data
`is considered. Then, navigation server 114 may calculate
`multiple routes 200 that may include all of the possible
`scenarios. Using the calculated multiple routes 200, the
`client 104 can guide the user without requesting a new
`multiple routes.
`0043 FIG. 3B is a schematic diagram 320 illustrating
`another approach to calculate multiple routes at an origin in
`accordance with one embodiment of the present invention.
`As in FIG. 3A, the origin 302 may be located in a parking
`lot or a shopping mall 301. In this case, small circles 322
`may be shot around the origin and roads that intersect with
`the circles are searched until a satisfactory amount of map
`data is considered. Once the information on nearby roads is
`collected, navigation server 114 may follow the similar
`procedures as in the case of FIG. 3A to generate multiple
`routes 200.
`0044 FIG. 3C is a schematic diagram 330 illustrating
`one approach to calculate multiple routes at an origin in
`accordance with one embodiment of the present invention.
`As illustrated in FIG. 3C, the origin 331 may be located on
`road 340. If the velocity of the user is Zero, navigation server
`114 cannot determine which direction the user will select
`from two direction 332a and 334a. In this case, navigation
`
`Hyundai Exhibit 1020, Page 12 of 15
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00173
`
`

`

`US 2006/01 16818 A1
`
`Jun. 1, 2006
`
`server 114 may calculate multiple routes 200 considering
`both scenarios. Once the user selects one direction, say
`332a, client 104 may guide the user along direction 332b so
`that the user may proceed on road 338. A similar process
`may take place if the user chooses direction 334a. In this
`case, the user may be guided to road 336 via the direction
`334b.
`0045. As mentioned, as a fallback mechanism, client 104
`may request new multiple routes to navigation server 114 if
`user travels on a road that is not covered by the initial
`multiple routes. In this case, user may