(19)
`
`(12)
`
`(45) Date of publication and mention
`of the grant of the patent:
`30.05.2007 Bulletin 2007/22
`
`(21) Application number: 04714853.1
`
`(22) Date of filing: 26.02.2004
`
`(cid:6)(cid:27)&(cid:11)(cid:11)(cid:12)(cid:17)(cid:12)(cid:12)(cid:15)(cid:12)(cid:17)(cid:24)(cid:12)(cid:6)
`EP 1 611 416 B1
`
`(11)
`
`EUROPEAN PATENT SPECIFICATION
`(51) Int Cl.:(cid:3)
`G01C21/36(2006.01)
`
`(86) International application number:
`PCT/GB2004/000794
`
`(87) International publication number:
`WO 2004/076976 (10.09.2004 Gazette 2004/37)(cid:3)
`
`(54) NAVIGATION DEVICE AND METHOD FOR DISPLAYING ALTERNATIVE ROUTES
`
`NAVIGATIONSEINRICHTUNG UND VERFAHREN ZUM ANZEIGEN ALTERNATIVER ROUTEN
`
`DISPOSITIF DE NAVIGATION ET PROCEDE POUR L’AFFICHAGE DE DIFFERENTS ITINERAIRES
`POSSIBLES
`
`(84) Designated Contracting States:
`AT BE BG CH CY CZ DE DK EE ES FI FR GB GR
`HU IE IT LI LU MC NL PT RO SE SI SK TR
`
`(30) Priority: 26.02.2003 GB 0304358
`07.03.2003 GB 0305175
`
`(43) Date of publication of application:
`04.01.2006 Bulletin 2006/01
`
`(60) Divisional application:
`07105925.7
`(73) Proprietor: Tomtom International B.V.(cid:3)
`1017 CT Amsterdam (NL)(cid:3)
`
`(72) Inventors:
`• PINKUS, Ayal
`NL-(cid:3)1017 CT Amsterdam (NL)(cid:3)
`
`• NEEF, Edwin
`NL-(cid:3)1017 CT Amsterdam (NL)(cid:3)
`• JURGENS, Sven-(cid:3)Erik
`NL-(cid:3)1017 CT Amsterdam (NL)(cid:3)
`• GRETTON, Mark
`London NW1 6DE (GB)(cid:3)
`
`(74) Representative: Langley, Peter James et al
`Origin Limited,
`52 Muswell Hill Road
`London N10 3JR (GB)(cid:3)
`
`(56) References cited:
`US-(cid:3)A- 5 243 528
`US-(cid:3)A- 5 877 751
`
`US-(cid:3)A- 5 859 628
`US-(cid:3)A- 5 928 307
`
`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 611 416B1
`
`Hyundai Exhibit 1018, Page 1 of 13
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00173
`
`

`

`1
`
`EP 1 611 416 B1
`
`2
`
`Description
`
`BACKGROUND OF THE INVENTION
`
`1. Field of the invention
`(cid:3)[0001] This invention relates to a navigation device that
`can display navigation data. The device find particular
`application as an in-(cid:3)car navigation system.
`
`2. Description of the prior art
`(cid:3)[0002] GPS based devices are well known and are
`widely employed as in-(cid:3)car navigation systems. Refer-
`ence may be made to the Navigator series software from
`the present assignee, TomTom B.V. This is software that,
`when running on a PDA (such as a Compaq iPaq) con-
`nected to an external GPS receiver, enables a user to
`input to the PDA a start and destination address. The
`software then calculates the best route between the two
`end-(cid:3)points and displays instructions on how to navigate
`that route. By using the positional information derived
`from the GPS receiver, the software can determine at
`regular intervals the position of the PDA (typically mount-
`ed on the dashboard of a vehicle) and can display the
`current position of the vehicle on a map and display (and
`speak) appropriate navigation instructions (e.g. ’turn left
`in 100 m’). Graphics depicting the actions to be accom-
`plished (e.g. a left arrow indicating a left turn ahead) can
`be displayed in a status bar and also be superimposed
`over the applicable junctions/(cid:3)turnings etc in the roads
`shown in the map itself. Reference may also be made to
`devices that integrate a GPS receiver into a computing
`device programmed with a map database and that can
`generate navigation instructions on a display. The term
`’navigation device’ refers to a device that enables a user
`to navigate to a pre-(cid:3)defined destination. The device may
`have an internal system for receiving location data, such
`as a GPS receiver, or may merely be connectable to a
`receiver that can receive location data.
`(cid:3)[0003]
`It is known to enable in-(cid:3)car navigation systems
`to allow the driver, whilst driving in a car along a route
`calculated by the navigation system, to initiate a route
`re-(cid:3)calculation. This is useful where the vehicle is faced
`with construction work or heavy congestion.
`(cid:3)[0004] Reference may be made to US 6118389 which
`discloses techniques for calculating a re-(cid:3)route. Initiating
`the re-(cid:3)route calculation requires activation of a specific
`detour switch, which may however be inconvenient to
`the user US 5928307 also describes a system with a
`dedicated ’avoid’ key on, a keyboard.
`(cid:3)[0005] Reference may also be made to US 5544060,
`which enables a device to preview the calculated route
`by displaying in successive screens each different road
`and turning that the vehicle has to take; the user however
`bas to manually sequence through each successive
`screen using a preview switch until he reaches die road
`that he wants to exclude from the route; he then selects
`
`a cancel switch; a new route is calculated which excludes
`the cancelled toad.
`(cid:3)[0006] Finally, reference may also be made to US
`5859628; although this docs not specifically describe any
`kind, of detour function for a navigation system, it does
`describe a touch screen based navigation device.
`(cid:3)[0007] The present invention aims to improve on the
`user interaction aspects of initiating a route re-(cid:3)calcula-
`tion.
`
`SUMMARY OF THE INVENTION
`(cid:3)[0008]
`In a first aspect, there is a navigation device
`programmed with a map database and software that en-
`ables a route to be planned to a destination, wherein the
`device is further programmed to be able to display a 2D
`or 3D road, navigation map on a touch screen display,
`the map showing the current position of the device on a
`planned route; characterised in that the user, can, by
`touching the screen, task away from the 2D or 3D navi-
`gation map to a menu screen which displays one or more
`options that, if selected through a further touch action,
`initiate a re-(cid:3)calculation of the route to find a detour away
`from the planned route.
`(cid:3)[0009] This user interaction, approach is simpler, more
`flexible and more intuitive than prior art approaches that
`require the user to activate a specific, hardware-(cid:3)based
`detour switch. Further, since a route re-(cid:3)calculation only
`requires 2 quick touch actions to the screen, it can be
`safely completed by a driver even whilst driving.
`(cid:3)[0010] The menu screen may display selectable op-
`tions relating to one or more of the following functions:(cid:3)
`
`(a) calculate alternative route;
`(b) calculate alternative route without including a pre-
`defined extent of the road ahead;
`(c) calculate alternative route without including a pre-
`defined road;
`(d) revert to original route.
`(cid:3)[0011] This approach gives the driver far greater flex-
`ibility in his route re-(cid:3)calculation options than was availa-
`ble with prior art, hard-(cid:3)wired detour switches.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`(cid:3)[0012] The present invention will be described with ref-
`erence to the accompanying drawings, in which Figure
`1 is a screen shot from a navigation device implementing
`the present invention; the screen shot shows a plan map
`view and a status bar running along the bottom of the
`display;(cid:3)
`Figure 2 is a screen shot from the navigation device im-
`plementing a 3-(cid:3)D view;(cid:3)
`Figure 3 is a screen shot from the navigation device
`showing various route planning functions that enable a
`user to require the device to plot a new route to the des-
`tination that (i) is an alternative route; (ii) avoids a road-
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`2
`
`Hyundai Exhibit 1018, Page 2 of 13
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00173
`
`

`

`3
`
`EP 1 611 416 B1
`
`4
`
`block immediately ahead; (iii) avoids predefined roads or
`(iv) is a reversion to the original route.
`
`DETAILED DESCRIPTION
`
`System Overview
`(cid:3)[0013] The present invention is implemented in soft-
`ware from TomTom B.V. called Navigator. Navigator soft-
`ware runs on a touch screen (i.e. stylus controlled) Pocket
`PC powered PDA device, such as the Compaq iPaq. It
`provides a GPS based navigation system when the PDA
`is coupled with a GPS receiver. The combined PDA and
`GPS receiver system is designed to be used as an in-
`vehicle navigation system. The invention may also be
`implemented in any other arrangement of navigation de-
`vice, such as one with an integral GPS receiver/(cid:3)compu-
`ter/(cid:3)display, or a device designed for non-(cid:3)vehicle use (e.g.
`for walkers) or vehicles other than cars (e.g. aircraft). The
`navigation device may implement any kind of position
`sensing technology and is not limited to GPS; it can hence
`be implemented using other kinds of GNSS (global nav-
`igation satellite system) such as the European Galileo
`system. Equally, it is not limited to satellite based location/
`velocity systems but can equally be deployed using
`ground-(cid:3)based beacons or any other kind of system that
`enables the device to determine its geographic location.
`(cid:3)[0014] Navigator software, when running on a PDA,
`results in a navigation device that causes the normal nav-
`igation mode screen shown in Figure 1 to be displayed.
`This view provides driving instructions using a combina-
`tion of text, symbols, voice guidance and a moving map.
`Key user interface elements are the following: a 2-(cid:3)D map
`1 occupies most of the screen. The map shows the user’s
`car and its immediate surroundings, rotated in such a
`way that the direction in which the car is moving is always
`"up". Running across the bottom quarter of the screen is
`the status bar 2. The current location of the device, as
`the device itself determines using conventional GPS lo-
`cation finding and its orientation (as inferred from its di-
`rection of travel) is depicted by an arrow 3. The route
`calculated by the device (using route calculation algo-
`rithms stored in device memory as applied to map data
`stored in a map database in device memory) is shown
`as darkened path 4 superimposed with arrows giving the
`travel direction. On the darkened path 4, all major actions
`(e.g. turning corners, crossroads, roundabouts etc.) are
`schematically depicted by arrows 5 overlaying the path
`4. The status bar 2 also includes at its left hand side a
`schematic 6 depicting the next action (here, a right turn).
`The status bar 2 also shows the distance to the next
`action (i.e. the right turn - here the distance is 220 meters)
`as extracted from a database of the entire route calcu-
`lated by the device (i.e. a list of all roads and related
`actions defining the route to be taken). Status bar 2 also
`shows the name of the current road 8, the estimated time
`before arrival 9 (here 2 minutes and 40 seconds), the
`actual estimated arrival time 10 (11.36am) and the dis-
`
`tance to the destination 11 (1.4Km). The GPS signal
`strength is shown in a mobile-(cid:3)phone style signal strength
`indicator 12.
`(cid:3)[0015]
`If the user touches the centre of the screen 13,
`then a navigation screen menu is displayed; from this
`menu, other core navigation functions within the Naviga-
`tor application can be initiated or controlled. Allowing core
`navigation functions to be selected from a menu screen
`that is itself very readily called up (e.g. one step away
`from the map display to the menu screen) greatly simpli-
`fies the user interaction and makes it faster and easier.
`(cid:3)[0016] The area of the touch zone which needs to be
`touched by a user is far larger than in most stylus based
`touch screen systems. It is designed to be large enough
`to be reliably selected by a single finger without special
`accuracy; i.e. to mimic the real-(cid:3)life conditions for a driver
`when controlling a vehicle; he or she will have little time
`to look at a highly detailed screen with small control icons,
`and still less time to accurately press one of those small
`control icons. Hence, using a very large touch screen
`area associated with a given soft key (or hidden soft key,
`as in the centre of the screen 13) is a deliberate design
`feature of this implementation. Unlike other stylus based
`applications, this design feature is consistently deployed
`throughout Navigator to select core functions that are
`likely to be needed by a driver whilst actually driving.
`Hence, whenever the user is given the choice of selecting
`on-(cid:3)screen icons (e.g. control icons, or keys of a virtual
`keyboard to enter a destination address, for example),
`then the design of those icons/(cid:3)keys is kept simple and
`the associated touch screen zones is expanded to such
`a size that each icon/key can unambiguously be finger
`selected. In practice, the associated touch screen zone
`will be of the order of at least 0.7 cm2 and will typically
`be a square zone. In normal navigation mode, the device
`displays a map. Touching the map (i.e. the touch sensi-
`tive display) once (or twice in a different implementation)
`near to the screen centre (or any part of the screen in
`another implementation) will then call up a navigation
`menu (see Figure 3) with large icons corresponding to
`various navigation functions, such as the option to cal-
`culate an alternative route, and re-(cid:3)calculate the route so
`as to avoid the next section of road (useful when faced
`with an obstruction or heavy congestion); or recalculate
`the route so as to avoid specific, listed roads.
`(cid:3)[0017] The actual physical structure of the device itself
`may be fundamentally no different from any conventional
`handheld computer, other than the integral GPS receiver
`or a GPS data feed from an external GPS receiver.
`Hence, memory stores the route calculation algorithms,
`map database and user interface software; a microproc-
`essor interprets and processes user input (e.g. using a
`device touch screen to input the start and destination
`addresses and all other control inputs) and deploys the
`route calculation algorithms to calculate the optimal
`route. ’Optimal’ may refer to criteria such as shortest time
`or shortest distance, or some other user-(cid:3)related factors.
`(cid:3)[0018] More specifically, the user inputs his start posi-
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`3
`
`Hyundai Exhibit 1018, Page 3 of 13
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00173
`
`

`

`5
`
`EP 1 611 416 B1
`
`6
`
`tion and required destination in the normal manner into
`the Navigator software running on the PDA using a virtual
`keyboard. The user then selects the manner in which a
`travel route is calculated: various modes are offered,
`such as a ’fast’ mode that calculates the route very rap-
`idly, but the route might not be the shortest; a ’full’ mode
`that looks at all possible routes and locates the shortest,
`but takes longer to calculate etc. Other options are pos-
`sible, with a user defining a route that is scenic - e.g.
`passes the most POI (points of interest) marked as views
`of outstanding beauty, or passes the most POIs of pos-
`sible interest to children or uses the fewest junctions etc.
`(cid:3)[0019] Roads themselves are described in the map da-
`tabase that is part of Navigator (or is otherwise accessed
`by it) running on the PDA as lines - i.e. vectors (e.g. start
`point, end point, direction for a road, with an entire road
`being made up of many hundreds of such sections, each
`uniquely defined by start point/end point direction param-
`eters). A map is then a set of such road vectors, plus
`points of interest (POIs), plus road names, plus other
`geographic features like park boundaries, river bounda-
`ries etc, all of which are defined in terms of vectors. All
`map features (e.g. road vectors, POIs etc.) are defined
`in a co-(cid:3)ordinate system that corresponds or relates to
`the GPS co-(cid:3)ordinate system, enabling a device’s position
`as determined through a GPS system to be located onto
`the relevant road shown in a map.
`(cid:3)[0020] Route calculation uses complex algorithms that
`are part of the Navigator software. The algorithms are
`applied to score large numbers of potential different
`routes. The Navigator software then evaluates them
`against the user defined criteria (or device defaults), such
`as a full mode scan, with scenic route, past museums,
`and no speed camera. The route which best meets the
`defined criteria is then calculated by a processor in the
`PDA and then stored in a database in RAM as a sequence
`of vectors, road names and actions to be done at vector
`end-(cid:3)points (e.g. corresponding to pre-(cid:3)determined dis-
`tances along each road of the route, such as after 100
`meters, turn left into street x).
`Route re-(cid:3)calculation
`(cid:3)[0021] An implementation of the present invention fa-
`cilitates access to functions that enable alternative routes
`to be calculated by placing a menu of graphical icons (or
`any other kind of way or option to allow selection of the
`functions, such as lists, check boxes etc.) on a menu
`screen that is easily accessed from the main navigation
`screen- i.e. the screen that is displayed during actual or
`simulated/(cid:3)preview navigation. As noted above, in normal
`navigation mode (and also the ’demonstrate route’ mode
`for simulated/(cid:3)preview navigation - see later), the device
`displays an animated map that shows the location of the
`navigation device as the journey progresses. Touching
`the map (i.e. the touch sensitive display) once (or twice
`in a different implementation) near to the screen centre
`(or any part of the screen in another implementation) will
`
`then call up a ’Recalculate’ menu screen (see Figure 3)
`with large icons corresponding to various navigation
`functions, such as the option to calculate an alternative
`route 3C ; re-(cid:3)calculate the route so as to avoid the next
`section of road 3A (useful when faced with a roadblock);
`and recalculate the route so as to avoid specific, listed
`roads 3B. The following sections describe these and oth-
`er alternative route functions in more detail. Some of
`these functions may be initiated directly from the Recal-
`culate menu screen; others may be at a deeper level in
`the menu structure. However, all can be initiated by se-
`lecting options such as graphical icons, lists, check boxes
`which are unambiguously associated with touch screen
`areas that are large enough to allow the user to select
`them with a fingertip whilst safely driving, typically at least
`0.7cm2 in area.
`
`Alternative route function: ’avoid roadblock’
`(cid:3)[0022] With this function, a user could select an ’avoid
`roadblock’ function 3A that causes the system to recal-
`culate a route on the basis that the road immediately
`ahead (or some user defined or system default distance
`ahead, e.g. 100 metres) is blocked.
`(cid:3)[0023] As noted earlier, a route planning algorithm in
`Navigator will work out an optimal route (optimal may
`refer to criteria such as shortest time or shortest distance,
`or some other factors) by exploring different routes and
`scoring them against the required criteria. In this way,
`one route which best meets the defied criteria is gener-
`ated. If whilst actually driving along a route, an unexpect-
`ed event occurs that requires the user to detour away
`from the pre-(cid:3)calculated route, such as a roadblock, the
`user can inform the Navigator software that his immedi-
`ate road ahead is blocked and require the software to re-
`calculate a new route, taking his current position as a
`new starting position, but taking the first turning possible
`away from the old calculated route. This first turning might
`be ahead or behind the current car position. The system,
`in constructing the new route, explores a large number
`of possible routes to the destination from the current po-
`sition, but excludes the road immediately ahead.
`(cid:3)[0024] Selecting the ’avoid roadblock’ function 3A has
`to be fast and involve the absolute minimum number of
`screen interactions to minimise driver distraction. This
`can be achieved by the user being able to switch from
`normal navigation mode (in which the current position of
`the car is shown on a map, as shown in Figures 1 or 2)
`to a Recalculate menu mode, as shown in Figure 3, by
`pressing a key or selecting any point on the screen or
`selecting a given region of the screen. Where a given
`region has to be selected. (e.g. the approximate centre
`of the map), then the touch activation zone is sufficiently
`large that it can readily and reliably be selected by a user
`with his fingertip without needing to look carefully at the
`screen for more than a moment. A touch zone of 0.7cm2,
`centred on the map, has been found to be sufficient.
`(cid:3)[0025] The Figure 3 menu mode displays a small
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`4
`
`Hyundai Exhibit 1018, Page 4 of 13
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00173
`
`

`

`7
`
`EP 1 611 416 B1
`
`8
`
`number of large icons, one of which is the ’avoid road-
`block’ 3A option. This can be selected with one touch;
`when this occurs, the software re-(cid:3)calculates the route
`and gives instructions in the normal manner (voice;
`and/or on screen navigation prompts) to allow the user
`to proceed to his destination but avoid the road immedi-
`ately ahead.
`
`Alternative route function: ’avoid specific road’
`(cid:3)[0026] This function allows a user to easily and rapidly
`select a specific, named road 3B to mark as blocked so
`that he can use information from real time traffic informa-
`tion broadcasts on the radio.
`(cid:3)[0027] When listening to the radio, a user may hear
`that a specific road or perhaps part of a motorway be-
`tween defined junctions is blocked or heavily congested.
`If that road is on the user’s calculated route, even though
`it might be many kilometres away, then he will want to
`have the software recalculate a new route as soon as
`possible. The system does this by calculating a route to
`the final destination using the current position as a start
`position and exploring different routes to the destination,
`but excluding the road indicated as to be avoided. The
`new route will then be calculated using normal route plan-
`ning algorithms and the user diverted onto the new route.
`(cid:3)[0028] Selecting the ’avoid specific road’ function 3B
`has also to be fast and involve the absolute minimum
`number of screen interactions to minimise driver distrac-
`tion. This can be achieved by the user being able to switch
`from normal navigation mode (Figures 1 or 2, in which
`the current position of the car is shown on a map) to a
`Recalculate menu mode as described earlier (e.g. se-
`lecting a given region on the screen); the Recalculate
`menu displays a small number of large icons, several of
`which are named roads 3B on the route which, if selected,
`can be selected with one touch; when this occurs, the
`software re-(cid:3)calculates the route and gives instructions in
`the normal manner (voice; and/or on screen navigation
`prompts) to allow the user to proceed to his destination
`but avoid the road immediately ahead. The device may
`have limited screen space to display many roads for ex-
`clusion; the Figure 3 implementation lists three. These
`three are selected using various weighting parameters
`(e.g. a prior history of the user wishing to avoid them; the
`next three major roads) or from dynamic, updated travel
`information received by the device from a traffic informa-
`tion data source, indicating that these are the next three
`roads on the route that are affected by traffic disturbance
`of some kind.
`(cid:3)[0029] A final ’original’ option 3D allows the user to
`clear all earlier re-(cid:3)calculation inputs and re-(cid:3)calculate the
`original route.
`(cid:3)[0030] A number of other navigation functions can be
`initiated from deeper in the menu hierarchy than the Fig-
`ure 3 menu. These are described below.
`
`Alternative route function: ’penalties’
`(cid:3)[0031] With this function, the system can also enable
`a user to mark certain points/(cid:3)regions as blocked or slow
`or to give penalties (or their inverse, awards) to a point/
`region to weight routing away from (or to) that point/(cid:3)region
`and have the system auto calculate an alternative route
`(or indeed the original route).
`(cid:3)[0032] Route planning algorithms operate by assign-
`ing scores to different possible routes in relation to dif-
`ferent criteria (e.g. scores for the time of journey, scores
`for the length of journey etc) and then determining which
`route has the best overall score. Normally, the user can-
`not interact directly with how the algorithm treats roads,
`junctions and other route features. But in Navigator it is
`possible: the user can directly alter the way the route
`planning algorithm evaluates or scores a route by award-
`ing penalties/(cid:3)awards to any items, e.g. points/(cid:3)regions,
`that affect the route planning scoring. The route planning
`algorithm stores a list of all roads/(cid:3)junctions in vector form
`associated with each calculated route from start to des-
`tination; each item (e.g. road section, turning etc.) will
`typically have several parameters associated with it that
`are used in the scoring process to evaluate a best route.
`Hence, it is straightforward to alter the route scoring
`based on giving different weightings to different kinds of
`items. For example, one user might dislike junctions; in
`which case, the route scoring could count junction num-
`bers in alternate routes and then weight more favourably
`routes with fewer junctions. Similarly, roads within certain
`user defined regions could have some of their scoring
`parameters altered to change the likelihood of a route
`being selected using them (either to increase or decrease
`the likelihood of selection). To enable the user to alter
`the weightings given to different items, the device could
`display a list of those items adjacent to check boxes (e.g.
`’Like’ and ’Don’t Like’). Each user could then set up a
`personal profile that defined his or her personal prefer-
`ences (e.g. one person might always prefer the scenic
`and historic; another straightforward driving with minimal
`junctions; yet another, always the shortest possible dis-
`tance, irrespective of complexity).
`(cid:3)[0033] Also, a user could penalise specific complex
`junctions on a simulated route (see ’Demonstrate route’
`function below) if they disliked them, or else could indi-
`cate that he wanted fewer turnings and the device would
`then count the number of turnings in alternative routes
`and give preference to the routes with fewer turnings.
`
`Alternative route function: auto generate
`(cid:3)[0034] A user can also simply select ’alternative route’
`3C if he wants to see another possible route: the system
`then recalculates a route, not using at least 80% of the
`roads from the prior route. If that route is still unsuitable,
`the user can obtain another alternative route again by
`selecting again ’alternative route’ 3C.
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`5
`
`Hyundai Exhibit 1018, Page 5 of 13
`Hyundai Motor Company v. Mel Navip LLC
`IPR2024-00173
`
`

`

`9
`
`EP 1 611 416 B1
`
`10
`
`Alternative route planning: selecting calculation
`modes
`(cid:3)[0035] A user can select ’normal’, ’strict’ and ’fast’ plan-
`ning modes: each results in different route planning al-
`gorithms being used that calculate the route either nor-
`mally, or strictly (which may take many minutes as a great
`many permutations are explored) or quickly, (which may
`take a few seconds only as many simplifying assump-
`tions are made about the optimal route).
`
`Alternative route planning: POI navigation
`(cid:3)[0036] The system offers a "navigate to nearby point
`of interest" option. This first provides a hot list of POI
`(point of interest) icons for the small set of most often
`used POI types.
`(cid:3)[0037] The list is initialized to generally useful POI
`types (for car drivers) like petrol stations, restaurants,
`parking spots etc. Hence, a user can very readily ask the
`program to calculate a new route that will navigate him
`to the nearest petrol station etc. This can happen during
`the course of a drive - i.e. the user realises that he is low
`on fuel and will need the route to be re-(cid:3)calculated to pass
`by a petrol station, whilst still maintaining the original des-
`tination.
`(cid:3)[0038] The system can in effect recalculate a route with
`the closest relevant POI as the destination and the cur-
`rent location as the start. The user can manually adjust
`the types to suit his own needs. Furthermore, at least
`one of the icons will self-(cid:3)adjust to the most recently used
`type not already in the list.
`(cid:3)[0039] Re-(cid:3)calculating a route to include a POI requires
`the system to implement a search for POIs. This would
`normally be done by defining a point and searching out-
`wards from that point to locate relevant POIs. Applying
`this approach to finding POIs along a route would be
`impossible on a PDA because you would in effect be
`replicating the search for all points along the route (po-
`tentially millions of separate searches for a long journey,
`which would be too great a load). In this implementation,
`this approach is reversed by taking each relevant POI
`and seeing if it is on a vector/(cid:3)line that that also defines
`part of the route - a simple and fast correlation process
`between POIs and route lines, that can rapidly be repeat-
`ed for all POIs of relevance and for each candidate route.
`This POI location method can be used whenever POIs
`need to be found. When re-(cid:3)calculating a route so that it
`includes a POI of a given type, the route calculation al-
`gorithm takes as its start position the current location and
`maintains the original destination. It then selects only
`those routes that include the POI of the required type
`(using the simple correlation process of seeing if any vec-
`tor of the calculated route matches the vector associated
`with each POI of the required type) and weights most
`favourably those with a POI nearest the current location.
`
`Demonstrate route function
`(cid:3)[0040] The present invention implements a ’Demon-
`strate route’ preview or simulation function. This allows
`the user to see the entire proposed route, as calculated
`by the Navigator software, in animated fashion as if he
`were driving it. First, a route is calculated in the normal
`manner. Then, a ’demonstrate route’ icon or menu option
`is automatically displayed by the device after the route
`is calculated. As with all major navigation functions, this
`is represented by a large icon with an associated touch
`screen area large enough to be readily selected by a
`fingertip, such as at least 0.7 cm2. After the icon has been
`selected, the device displays a sequence of preview
`maps that shows the car driving from the start position
`to the destination. Generally, the maps will be animated
`to scroll past a fixed point representing the vehicle posi-
`tion, although it is possible to arrange for the position of
`the vehicle to advance as though travelling along a road,
`or for there to be some combination of relative movement
`between car and route.
`(cid:3)[0041] Other useful control functions can mimic the vid-
`eo/(cid:3)media player control functions found on a PC; for ex-
`ample, to fast forward through the simulation/(cid:3)preview and
`to pause, play, and rewind. The status bar data (espe-
`cially time of arrival, further journey time and remaining
`distance) should remain accurate as the off-(cid:3)line simula-
`tion of the route plays. This gives the user a good feel
`for not only the spatial definition of the route, but also its
`temporal definition.
`(cid:3)[0042] During normal preview (e.g. when a ’play’ but-
`ton on a media player style control is selected), each road
`name is displayed in the status bar 8. One possible re-
`finement is to only display the road name if it will remain
`visible for more than a predetermined time (e.g. 1 sec-
`ond). Whilst the preview is fast forwarding, then road
`names may not be displayed if they would not be legible
`(in less sophisticated implementations this feature may
`be absent). Road names may also displayed if the pause
`is selected or if the simulated speed of the vehicle is
`otherwise slowed down below a defined level.
`(cid:3)[0043] During normal preview, road names are there-
`fore displayed in the status bar 8 or superimposed over
`the road itself in the map (whether 2-(cid:3)d or 3-(cid:3)D), in the
`same way that they are displayed during normal real-
`time operation, greatly enhancing the realism and utility
`of the preview function. For example, the ’demonstrate
`route’ function is very helpful in enabling users/(cid:3)passen-
`gers to assess and confirm that the route is acceptable.
`The user can familiarise himself with the road names in
`the same context as they will appear on the device when
`actually driving. For some vehicles, such as taxis, this