NAVIGATION LANE GUIDANCE
`
`CROSS REFERENCE TO RELATED APPLICATIONS
`
`[0001]
`
`This application is a continuation of co-pending US. Patent Application No.
`
`15/976,741 , filed May 10, 2018, which is a continuation of US. Patent Application No.
`
`15/904,635, filed February 26, 2018, now US. Patent No. 10,012,516, issued July 3, 2018 which
`
`is a continuation of US. Patent Application No. 15/672,026, filed August 8, 2017, now US.
`
`Patent No. 9,933,272, issued April 3, 2018, which is a continuation of US. Patent Application
`
`No. 14/717,979, filed May 20, 2015, now US. Patent No. 9,816,830, issued November 14, 2017.
`
`All of the above applications are incorporated by reference herein in its entirety.
`
`BACKGROUND
`
`[0002]
`
`The described embodiments relate generally to providing driving guidance, and
`
`particularly to providing lane guidance to improve lane selection while navigating a route.
`
`[0003]
`
`Navigation services provide directions for a user to follow to reach a destination. The
`
`directions are provided as a navigation route, instructing a user which roads to use to arrive at the
`
`destination. Current navigation services typically provide navigation services on a turn-by-turn
`
`basis. That is, the navigation system specifies a turn from one road to another. However, users
`
`are often faced with roads that include several lanes of traffic, without knowing which lanes are
`
`best before the turn, or during the turn which turning lane is preferable. Since lanes may merge
`
`with other lanes, split into multiple lanes, be ineligible to perform a desired turn, and so forth,
`
`20662/41897/FW/10384352.1
`
`_ 1 _
`
`

`

`users may spend considerable time navigating lanes on a road to identify preferred lanes for an
`
`unfamiliar route.
`
`SUMMARY
`
`[0004]
`
`A navigation system provides lane guidance along a navigation route. The navigation
`
`system provides turn-by-turn directions along a navigation route (e.g., a set of roads or road
`
`segments) from a start position (or a current position) to a destination, for example, by indicating
`
`which roads will provide an efficient route. Each road or road segment includes one or more
`
`lanes, particular ones of which enable a driver to take individual actions designated by the
`
`navigation route, such as turning right, turning left, staying right at a lane split, etc. The
`
`navigation route may also identify lane relationships that occur as a consequence of the manner
`
`in which road segments connect. For example, performing an action of turning right on a lane
`
`second from the right on a first road segment in a route may place the user in a middle lane of the
`
`next road segment.
`
`[0005]
`
`The navigation system determines lane scoring information for lanes along the
`
`navigation route. To score the lanes, the navigation system determines a lane distance that the
`
`lane continues along the navigation route. Certain lanes may be eligible to perform the next
`
`action for continuing along the route, while other lanes proceed in other directions that do not
`
`continue along the route. To determine a score for a lane, the navigation system determines how
`
`long a driver may continue along the lane while following actions on that lane that continue on
`
`along the route. For example, a navigation route may specify that a user should continue along a
`
`road for the next 5,000 feet from a specified position. At that specified position, there are two
`
`lanes, one which is required to turn right in 500 feet, while the other continues along the route for
`
`20662/41897/FW/10384352.l
`
`_ 2 _
`
`

`

`more than 5,000 feet. These lanes are scored by determining how far the user may continue
`
`along the lanes, in this example, the lane which is required to turn right in 500 feet scores lower
`
`than the lane that continues along the navigation route.
`
`[0006]
`
`As noted, to measure and score each lane, the navigation system determines a lane
`
`distance identifying how far the lane continues along the route. In the previous example, the lane
`
`distance for the lane that is forced to turn right is 500 feet, as that lane no longer continues along
`
`the route after it is forced to turn. The lane distance for the lane may be measured to a maximum
`
`look-ahead value, which can be based, for example, on a distance or driving time ahead of the
`
`current position for lane guidance. When determining the lane distance for a lane, the navigation
`
`system follows the lane through turns and other actions in the navigation route to include in the
`
`lane distance any subsequent road segment and lane on the subsequent road accessed by the
`
`evaluated road. The lane on the subsequent road may be similarly evaluated to determine further
`
`distance along that lane and additional actions along the navigation route that continue in that
`
`lane. Each lane is scored using the associated lane distance, with increasing scores when the lane
`
`distance is higher, indicating that a user may stay in that lane for a longer amount of time without
`
`requiring further lane changes. The scoring may also be affected by expected traffic, merges or
`
`splits of the road, and other features. Using the scoring, the scored lanes may be sent to a user,
`
`using video or audio instructions to indicate the preferred lane for the user’s position.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`[0007]
`
`Fig. 1 illustrates an environment for a navigation system 100 according to one
`
`embodiment.
`
`[0008]
`
`Fig. 2 illustrates an example of a navigation route.
`
`20662/41897/FW/10384352.l
`
`_ 3 _
`
`

`

`[0009]
`
`Fig. 3 illustrates an example method for providing lane guidance in connection with a
`
`navigation route according to one embodiment.
`
`[0010]
`
`Fig. 4 illustrates an example interface for providing lane guidance to a user.
`
`[0011]
`
`Figs. 5A and 5B illustrate example interfaces for providing compound lane guidance
`
`according to one embodiment.
`
`[0012]
`
`The figures depict various embodiments of the present invention for purposes of
`
`illustration only. One skilled in the art will readily recognize from the following discussion that
`
`alternative embodiments of the structures and methods illustrated herein may be employed
`
`without departing from the principles of the invention described herein.
`
`DETAILED DESCRIPTION
`
`[0013]
`
`Fig. 1 illustrates an environment for a navigation system 100 according to one
`
`embodiment. The navigation system 100 receives requests for a navigation route from a user
`
`device 120 via a network 130 and provides the requested navigation route and related lane
`
`guidance to the user device 120. The navigation route describes a list of road segments for a
`
`vehicle to navigate from a start position to a destination, which includes a set of actions for the
`
`user to perform while navigating the roads, such as turning left, turning right, or continuing
`
`straight. The navigation system 100 provides lane guidance to the user device 120 to indicate
`
`particular lanes that are preferable at various points in the navigation route. This lane guidance
`
`may indicate, for example, an ordered or score preference for lanes at a particular part of the
`
`navigation route.
`
`[0014]
`
`The user device 120 (or other system providing requests to the navigation system
`
`100) provides a navigation request to the navigation system 100. The user device 120 is any
`
`20662/41897/FW/10384352.l
`
`_ 4 _
`
`

`

`suitable computing system, such as an in-vehicle navigation system or car dashboard. The user
`
`device may also be a laptop, a handheld computing device (such as a mobile phone or tablet
`
`computer), and the like that provide computing and location information to the navigation system
`
`100 as described herein. The user device 120 may also be any additional electronic used for
`
`travel.
`
`[0015]
`
`According to some examples, a user can operate the user device 120 to make a
`
`request for navigation to the navigation system 100. The request for navigation may designate,
`
`for example, a destination for the navigation, or a search string for the navigation system 100 to
`
`identify the destination by searching a database for a destination using the search string. For
`
`example, the user can provide input, via an input mechanism, such as a touch-sensitive display of
`
`the user device 120, to specify an address or a point of interest as the destination the user wishes
`
`to travel to. The user device 120 in some embodiments includes a positioning system, such as a
`
`global positioning system (GPS) receiver, or other means of determining the position of the user
`
`device 120, such as by triangulation to local wireless receivers. The location of the user device
`
`120 may be included with the request. The user device 120 receives a navigation route from the
`
`navigation system 100 and provides instructions from the navigation route to the user, including,
`
`in one example, step-by-step guidance as the navigation route is followed (e.g., by presenting
`
`content to a display of the user device 120 and/or outputting audio using a set of speakers).
`
`When the navigation route includes lane guidance information, the user device 120 can also
`
`display the route guidance information on the display of the user device 120 and/or output audio
`
`corresponding to the lane guidance information (e.g., by voice). The user device 120 may
`
`receive lane guidance as part of the received navigation route or routing information, or the user
`
`device 120 may request lane guidance from the navigation system 100 as the route is navigated.
`
`20662/41897/FW/10384352.l
`
`_ 5 _
`
`

`

`[0016]
`
`The network 130 provides a pathway for communication between the user device 120
`
`and the navigation system 100. The network 130 is any suitable type of network for this
`
`communication, which may be wired or wireless, and may pass through intermediary switches
`
`and nodes between the user device 120 and navigation system 100. Each of the navigation
`
`system 100 and the user device 120 can include communication sub-systems, such as wireless
`
`transceivers, to exchange data over the network 130.
`
`[0017]
`
`The navigation system 100 includes various modules and data stores for performing
`
`route navigation and lane guidance. As described herein, a module or a component can include
`
`or correspond to a program, a sub-routine, a portion of a program, or a software component or
`
`hardware component capable of performing one or more stated tasks or functions. A module or
`
`a component can exist on a hardware component independently of other modules or components,
`
`or alternatively, can be a shared element or process of other modules, programs, or machines. In
`
`the example of Fig. 1, the navigation system 100 can include a front end module 102, a routing
`
`module 104, a lane guidance module 106, and atraff1c module 108. The navigation system 100
`
`also includes a map data store 110. In some examples, various features described herein as
`
`relating to the navigation system 100 may be implemented by the user device 120. For example,
`
`in one implementation, the routing and/or lane guidance modules can be implemented by the
`
`user device 120, while in another implementation, the navigation system 100 can be wholly
`
`implemented by the user device 120 rather than comprising a separate system.
`
`[0018]
`
`The map data store 110 includes map data used for generating navigation routes. The
`
`map data includes roads, addresses, intersections, destination information (e.g., points of interest
`
`and business information), and other data for generating navigation information of roads. The
`
`map data can also specify the number of lanes for a road at various parts of the road, permitted
`
`20662/41897/FW/10384352.1
`
`_ 6 _
`
`

`

`actions from particular lanes (such as whether a lane must turn right, may turn right or go
`
`straight, or must go straight), maximum speed of a road, average speed of drivers on a road, and
`
`so forth. Still further, in one example, the map data may be stored as a plurality of layers, e.g.,
`
`individual layers for highway roads, for major streets, and for minor streets, while in another
`
`example, the map data may be stored as a graph, with road segments representing connections
`
`between nodes in the graph. The nodes may represent intersections or other transitions between
`
`roads in the graph.
`
`[0019]
`
`The front end module 102 receives requests for navigation from the user device 120.
`
`The front end module 102 also transmits the navigated routes and lane guidance to the user
`
`device 120. The front end module 102 communicates with the user device 120 according to the
`
`protocols used by the user device 120 to access the navigation system 100. For example, the
`
`front end module 102 may provide the navigation route using a protocol specialized for the user
`
`device 120, and may not be responsible for generating an interface for display to the user. In
`
`alternative embodiments, the front end module 102 can provide an interface (e.g., a web page)
`
`for display to the user device 120, can provide an application programming interface (API) to a
`
`program operated on the user device 120, or can communicate with a proprietary application
`
`associated with the navigation system 100 that is stored on the user device 120, among other
`
`configuration options. After receiving the navigation request, the front end module 102 transfers
`
`the navigation request to routing module 104.
`
`[0020]
`
`The routing module 104 generates a navigation route from a start position to a
`
`destination. The routing module 104 accesses the map data store 110 to identify possible routes
`
`and road segments that a vehicle can travel on to get from the start position to the destination.
`
`The routing module 104 scores the possible routes and identifies a preferred route to reach the
`
`20662/41897/FW/10384352.l
`
`_ 7 _
`
`

`

`destination. The routing module 104 may generate a navigation route that minimizes Euclidean
`
`distance traveled or other cost function during the route, and may further access the traffic
`
`module 108 to receive traffic estimates that affect an amount of time it will take to travel on a
`
`particular route. Depending on implementation, the routing module 104 can generate one or
`
`more routes using various routing methods, such as Dijkstra’s algorithm, Bellman-Ford
`
`algorithm, or other algorithms. The routing module 104 may also use the traffic information to
`
`generate a navigation route that reflects expected conditions of the route (e.g., current day of the
`
`week or current time of day, etc.), such that a route generated for travel during rush-hour may
`
`differ from a route generated for travel late at night. The routing module 104 may also generate
`
`more than one navigation route to a destination and send more than one of these navigation
`
`routes to the user device 120 for selection by the user from among various possible routes.
`
`[0021]
`
`The traffic module 108 accesses and provides traffic data relating to roads and, where
`
`available, for individual lanes of traffic on a road. The traffic information may be based on data
`
`received from various sources, such as third-party providers, or by analyzing the speed of users
`
`navigating routes planned by the navigation system. For example, the traffic module 108 can
`
`receive, over the network 130, a plurality of GPS location points from individual user devices
`
`120 of a plurality of user devices 120. The traffic module 108 can determine traffic information
`
`along a particular road segment based on the GPS location points and their corresponding
`
`timestamps. The traffic information may reflect real-time data, and may include accidents and
`
`construction or road work that impacts traffic on a road, or may impact individual lanes of
`
`traffic. For example, an accident on the right-most lane of a highway may impact the right-most
`
`lanes of the highway more severely than the left-most lane of the freeway. The real-time data
`
`may be derived from a variety of sources, such as reports of road conditions from public or
`
`20662/41897/FW/10384352.l
`
`_ 8 _
`
`

`

`private sources, or crowd-sourced information from individual users navigating traffic. The
`
`traffic module 108 may also include historic information relating to the traffic on a road or lane
`
`as it varies with respect to particular repeatable periods of time, such as within a day or within a
`
`week. In addition, particular days of the year may be identified for purposes of traffic data, such
`
`as the days around particular holidays or other events that impact traffic, such as sporting events.
`
`[0022]
`
`The routing module 104 can also determine lane-by-lane traffic scoring based on
`
`inferences or rules of traffic related to a lane. For example, for a road segment that is typically
`
`not impacted by traffic, a lane that may continue along the road or turn onto another road may be
`
`impacted by traffic on the other road. If traffic is expected along the other road, that traffic may
`
`impact traffic in that lane, even for routes that continue along the first road. Similarly, a lane that
`
`has an upcoming merge with another lane, as is often the case with highway on-ramps, may
`
`score poorly relative to lanes that do not have to accommodate merging traffic. These features of
`
`a lane may impact the traffic score of the lane.
`
`[0023]
`
`The lane guidance module 106 determines lane guidance information for lanes of a
`
`given position along a road of a navigation route. The lane guidance module 106 can determine
`
`lane information (e.g., the number of lanes, which lanes go straight or turn at what location data
`
`points, etc.) for road segments of a navigation route from map data stored in the map data store
`
`110. The lane guidance information describes preferred lanes of the route, and may indicate lane
`
`guidance in several ways. In one example, the lane guidance information includes a score for
`
`each lane of a road segment of the route, which can correspond to a relative score that is relative
`
`to other lanes of the road segment (if more than one lane exists on the road segment) or
`
`correspond to an absolute score for each lane. In one embodiment, scores for the lanes are scaled
`
`relative to the highest-scoring lane and may indicate a percentile of the lane’s score compared to
`
`20662/41897/FW/10384352.l
`
`_ 9 _
`
`

`

`the highest-scoring lane. As further described below, the scores for individual lanes may be
`
`generated based on a distance or time that a lane continues along the navigation route, which
`
`may be modified based on other factors reflecting desirability of a lane, such as expected traffic
`
`in the lane. The lane guidance information can be stored in the map data store 110 or another
`
`database accessible by the navigation system 100.
`
`[0024]
`
`The starting position in the navigation route for which the lane information is
`
`generated is typically a location of the user (i.e., as provided by the user device 120), as the user
`
`navigates the route. However, the lane information may also be generated for positions along the
`
`entire navigation route. For example, the lane guidance module 106 may evaluate lane
`
`information at certain intervals, such as every 100 meters, of the navigation route. In one
`
`embodiment, rather than measuring intervals by distance, the lane information is evaluated at
`
`specified time intervals, such as the expected distance traveled on the navigation route each five
`
`minutes. In another embodiment, to optimize space and provide continuous lane guidance
`
`without regard to specific distances or time, lane information is generated by the lane guidance
`
`module 106 at each point that the number of lanes or the connections to future or proceeding
`
`lanes change. In this embodiment, between these evaluated points, the change in score may be
`
`interpolated when user module 120 displays such lane information.
`
`[0025]
`
`To generate the lane guidance information, the lane guidance module 106 identifies
`
`the lanes of the road segment at the position being evaluated. For each lane, the lane guidance
`
`module 106 determines the length ahead of the position that the lane remains part of the
`
`navigation route, termed a lane distance. The lane guidance module 106 may determine the
`
`length ahead of the position up to a look-ahead distance (e.g., in other words, determine the lane
`
`distance for a particular lane from the position being evaluated to the look-ahead distance, such
`
`20662/41897/FW/10384352.l
`
`_ 10 _
`
`

`

`as one mile). The look-ahead distance may be a static value or may vary. The look-ahead
`
`distance may vary as specified by a user of the user device 120, or may vary based on a travel
`
`speed at the position or based on a type of road at the position or a travel time. For example, the
`
`look-ahead distance for a highway may be greater than a look-ahead distance on a city street, and
`
`a look-ahead distance for a vehicle traveling quickly on the highway may be greater than a
`
`vehicle traveling slowly on the highway. The look-ahead distance may be determined by the
`
`lane guidance module 106, or may be determined by the user device 120. In one embodiment,
`
`the user device 120 may set the look-ahead distance to any value below that generated by lane
`
`guidance module 106 as may be convenient for or selected by the user.
`
`[0026]
`
`As the lane guidance module 106 evaluates a lane, the actions along the navigation
`
`route are checked using map data to determine whether an action (e.g., to turn right or left) is
`
`requned,andxvhmhertheacfionisvahdforfluulane.\Vhenthelanedoesnotpennfithe
`
`required action, the lane distance of the lane ends, which may be prior to the look-ahead
`
`distance. For example, when the action requires a user to turn right and the evaluated lane is
`
`rmmmdwumflfitmehmdmmmefimmflmemwmmmwdmmMpmm.Wmmflwkmas
`
`valid for the required action, the lane guidance module 106 identifies which lane on the
`
`subsequent road segment receives a vehicle taking the action from the lane. In this way, the lane
`
`on the subsequent road segment is “followed” to determine the lane distance for the evaluated
`
`lane. Thus, the lane distance may represent distance along the lane that a user may continue
`
`while incorporating lanes in subsequent roads after executing actions for the navigation route.
`
`The look-ahead distance may include more than one action in determining the look-ahead for a
`
`lane.
`
`20662/41897/FW/10384352.l
`
`_ 11 _
`
`

`

`[0027]
`
`In an alternate embodiment, rather than a “look-ahead” from a given position, the
`
`lane guidance module 106 may determine the lane distance based on a “look-back” from further
`
`points along the route, such that the lane guidance module 106 evaluates lane guidance
`
`beginning from the destination in the route, and follows the route towards the beginning of the
`
`route in generating lane guidance. By following the route guidance from the destination to the
`
`beginning, the lane guidance module 106 may count at each position in the navigation route how
`
`far each lane was a part of the route already assessed by the lane guidance module 106. In one
`
`embodiment, rather than evaluate each position, the lane guidance module 106 evaluates points
`
`at which the lanes available on the route change (e.g., merge, split, or are part of a turn).
`
`[0028]
`
`After determining a lane distance for a lane, additional scoring features may also be
`
`determined for the lane. The scoring features may include various aspects of a lane that suggest
`
`the lane will be a better lane for the navigation route. One scoring feature includes expected
`
`traffic for the lane. The lane guidance module 106 accesses the traffic module 108 to determine
`
`expected traffic for the lane, which may be impacted by the time of day of the route or current
`
`lane conditions as described above with respect to the traffic module 108. Another scoring
`
`feature includes whether the lane includes a merge or a split later on in the route. For example, a
`
`merge designates that another lane is combined with the current lane, while a split indicates that
`
`an additional lane is created from the lane. When a merge occurs, traffic is likely to be increased
`
`while vehicles from the different lanes merge together, and likewise when a split occurs, vehicles
`
`in the current lane are likely able to accelerate, as the traffic in one lane may now be split among
`
`two. Thus, the scoring for a merge reduces the desirability of a lane and scoring for a split
`
`increases the desirability of a lane. Additionally, lanes may be scored by the type of traffic
`
`permitted for a vehicle. For example, a vehicle identified as a High Occupancy Vehicle (HOV)
`
`20662/41897/FW/10384352.l
`
`_ 12 _
`
`

`

`may indicate a preference for any HOV-specific lanes, while a non-HOV vehicles would be
`
`expected not occupy such a lane. In another example, a designated truck lane may be expected
`
`to move at a slower speed and may further have a lower speed limit for traffic in the designated
`
`truck lane. Accordingly, non-truck vehicles may receive a penalty to the score function for that
`
`lane. Further, local motor vehicle code may indicate when being in a left lane (in a right-hand
`
`drive country) is inappropriate except to pass, in which case the score may indicate that the right-
`
`most lane of good lanes is best for avoiding merge traffic while not impeding the smooth flow of
`
`passing vehicles.
`
`[0029]
`
`Such score interpretation may be configurable by the user to include or exclude
`
`various scoring features. For example, different types of drivers may want a particular scoring
`
`feature more than other types of drivers. In another example, the lane scoring module 106 may
`
`modify the lane scores to suggest (i.e., score higher) further left (passing) lanes when real-time
`
`traffic indicates that the current more right (non-passing) lane is slower that the typical traff1c-
`
`free speed of vehicles on the road. The further right (non-passing lanes) may also be suggested
`
`when further left lanes are shown by real-time traffic to be slower than typical traff1c-free speed
`
`of vehicles, to discourage prolonged driving in the passing lane. This scoring may only be used
`
`within a certain speed range, such as within 0-5 miles of a speed limit for the road.
`
`[0030]
`
`In a situation where lane scores are relatively equal for a certain amount of time or
`
`distance ahead, the scoring algorithm may attempt to distribute lane load across relatively similar
`
`lanes to increase overall road throughput by using as much lane capacity as possible. Such
`
`distribution scoring may use the current real-time speed of the current lane to inform the server’s
`
`traff1c module, helping inform other vehicles around them of the best traffic lane or lanes to be
`
`in. Scores may be modified both by the lane guidance module and by the user device 120,
`
`20662/41897/FW/10384352.l
`
`_ 13 _
`
`

`

`depending on which module is closest to the data necessary to make the most efficient score
`
`adjustments.
`
`[0031]
`
`Using the lane distance and any applicable scoring features, at a road segment for a
`
`given current position of the user device 120, the lane guidance module 106 generates a score for
`
`each of the one or more lanes at that road segment. The scores for each lane may be scaled
`
`based on the score for the highest-scoring lane. These scores may be converted to a percentile.
`
`For example, a first lane may score 15, a second lane 60, a third lane 75, and a fourth lane 0 as a
`
`raw score (e.g., from left to right). The lane guidance module 106 identifies the third lane as the
`
`maximum-scoring lane, and adjusts the raw scores as a percentile of the maximum-scoring lane.
`
`This score provides that the first lane is 20% of the maximum, the second lane 80%, the third
`
`lane 100%, and the fourth lane 0% of the maximum score. The percentage-based lane score may
`
`also be rounded to a nearest percentile, such as the nearest 25th or 10th percentile.
`
`[0032]
`
`The lane guidance module 106 may also generate lane guidance information for lanes
`
`after the next action along the navigation route. Thus, the lane guidance information may
`
`indicate scores for lanes after a user turns left or right, for example, and then again may indicate
`
`scores for lanes after the user perform the sub sequent action, and so forth. This additional
`
`guidance may be termed “compound” lane guidance, as it provides lane guidance for a given
`
`position as well as a subsequent position of along the route. The compound lane guidance
`
`information may be generated when the evaluated position is within a threshold distance or time
`
`of the action. To perform this lane guidance operation, the lane guidance module 106 identifies a
`
`sub sequent action from the position and generates lane guidance information for a second
`
`position on the next road after the subsequent action. Thus, if a user is two miles from a turn to
`
`the right onto another road (and within the compound guidance threshold), the lane guidance
`
`20662/41897/FW/10384352.1
`
`_ 14 _
`
`

`

`module 106 may generate lane guidance information for the current position as well as lane
`
`guidance information for the lanes on the other road after the right turn. This permits a user to
`
`identify, before the turn, which lanes are preferable on the new road, even when there may not be
`
`an immediate turn or other action on the new road.
`
`[0033]
`
`Fig. 2 illustrates an example of a navigation route. In this example, each road, Alm
`
`Street, Beech Street, and Cruise Street, is a one-way street for convenience of illustration. The
`
`navigation route, in this example, begins on Alm Street at start 220 and ends at destination 240.
`
`In one example, the start 220 can correspond to the position of the user device 120 at the time the
`
`navigation route was determined. The navigation route directs the user to continue North along
`
`Alm Street, turn right on Beech Street, and turn right again on Cruise Street. Thus, in this
`
`example, the actions for the navigation route include a right turn on Beech Street and a right turn
`
`on Cruise Street.
`
`[0034]
`
`As shown in Fig. 2, Alm Street includes lanes 201, 202, and 203, Beech Street
`
`includes lanes 204, 205, and 206, and Cruise Street includes lanes 207 and 208. A vehicle on
`
`each lane is permitted to perform certain actions at each intersection between streets as
`
`designated by permitted actions 210 and 212. These actions may be specified by signs on the
`
`road, and may be represented in the navigation system 100 as actions permitted at specific lanes.
`
`These actions may be defined by map data, and in some circumstances, some actions may be
`
`excluded by rules. For example, since Beech Street is a one-way street, no lanes 201-203 may
`
`turn onto Beech Street in a way contrary to the one-way street (e.g., vehicles cannot turn left onto
`
`Beech Street from Alm Street). In this example, on Alm Street at the intersection of Beech
`
`Street, lane 201 is required to continue on Alm Street, lane 203 is required to turn right onto
`
`Beech Street, and lane 202 may continue along Alm Street or turn on Beech Street. On Beech
`
`20662/41897/FW/10384352.1
`
`_ 15 _
`
`

`

`Street at the intersection with Cruise Street, lane 206 is required to turn right onto Cruise Street,
`
`while lanes 204 and 205 continue along Beech Street.
`
`[0035]
`
`In this example, the lane guidance module 106 evaluates lane guidance information at
`
`multiple instances, such as at positions 230, 232, and 234, representing distances far from an
`
`intersection (230), nearer to an intersection (232), and close to an intersection (234). These
`
`positions are selected for illustration only to illustrate the lane distance generated for various
`
`lanes and may represent lane guidance information generated for a user as the user travels
`
`through each of the positions 230, 232, and 234 as determined by location information. As noted
`
`above, lane guidance information may be generated for various points along the navigation route,
`
`and scoring for each lane may be further modified based on various features of the lanes.
`
`[0036]
`
`At position 230 on the navigation route, there are three lanes 201-203 on Alm Street.
`
`In this example, the look-ahead distance 240 (e.g., three hundred meters) for each lane from
`
`position 230 does not reach the intersection of Alm Street and Beech Street. Thus, in scoring
`
`each lane at position 230, the lane guidance module 106 may compute the same score for each
`
`lane unless other factors affect the scoring for individual lanes (e.g., traffic predictions). These
`
`road segments prior to a change in factors (i.e., change in lane conditions) along the route may
`
`also be associated with an offset score to add to each lane to adjust the score to that particular
`
`point based on the computed scores related to a point at which the factors change. For example,
`
`an offset score may be stored at the point of the intersection of Alm Street and Beech Street. The
`
`user device 120 may inte