Patent Description:
This document describes methods, apparatuses, and systems for SD to HD navigation route determination. The present invention is defined by the appending claims and the thereby defined scope of protection. Independently thereof, this document describes for example a route builder configured to receive a navigation route generated for a host vehicle. The navigation route includes a list of waypoints generated using an SD map database. The route builder matches the list of waypoints to lane geometry data maintained in an HD map database and outputs an HD navigation route to a path planning sub-system to control the vehicle navigating the route. The HD navigation route includes the list of waypoints, additional waypoints, and lane geometry data. The vehicle path planning and trajectory control systems can then operate the host vehicle in a roadway environment following the HD navigation route.

This document also describes other operations of the above-summarized systems, techniques, apparatuses, and other methods set forth herein, as well as means for performing these methods.

This Summary introduces simplified concepts for SD to HD navigation route determination, further described below in the Detailed Description and Drawings. This Summary is not intended to identify essential features of the claimed subject matter, nor is it intended to determine the scope of the claimed subject matter.

Details of one or more aspects of SD to HD navigation route determination are described in this document regarding the following figures. The same numbers are used throughout the drawings to reference like features and components:.

Navigation systems are an important technology for assisted-driving and autonomous-driving systems. Some of these vehicle-based systems may require a navigation system to provide navigation routes to a particular destination and provide HD map data. In contrast to SD map data, HD map data can include stop bars, lane information, finely spaced waypoints, lane centerline points, curvature data, information regarding traffic control devices, localization data, and three-dimensional data.

HD map data may be necessary for many features of vehicle-based systems, including traffic-jam assist (TJA), lane-centering assist (LCA), automatic lane change (ALC), and autonomous driving. For example, HD maps are critical for these systems to understand the roadway environment, plan navigation routes, plan driving trajectories along a roadway, and control the vehicle along a navigation route. However, many mobile and in-vehicle navigation systems do not provide navigation routes with an adequate level of detail to enable such technologies. Instead, the systems often provide navigation routes using SD map databases that generally include waypoints, roads, segment names, and rough details of the length of a segment.

In contrast, this document describes techniques for SD to HD navigation route determination. A route builder can use an existing SD map database to generate HD navigation routes for use in assisted-driving and autonomous-driving systems. The route builder can receive a navigation route generated for a vehicle. The navigation route includes a list of waypoints generated using the SD map database. The route builder can then match the list of waypoints to lane geometry data maintained in an HD map database and output the HD navigation route to a vehicle controller of the host vehicle. The HD navigation route includes the list of waypoints, additional waypoints, and lane geometry data. The vehicle controller can then operate the vehicle in a roadway environment along the HD navigation route. In this way, vehicles can use assisted-driving and autonomous-driving systems with existing SD based navigation systems.

This section describes just one example of how the described techniques and systems can perform SD to HD navigation route determination. This document describes other examples and implementations.

<FIG> illustrates an example road environment <NUM> in which a route builder <NUM> can perform SD to HD navigation route determination according to techniques described in this disclosure. <FIG> illustrates the route builder <NUM> as part of a system (not shown) implemented within a vehicle <NUM>. Although presented as a car, vehicle <NUM> can represent other motorized vehicles (e.g., a motorcycle, a bus, a tractor, a semi-trailer truck, or construction equipment). In general, manufacturers can mount or install the route builder <NUM> in any moving platform traveling on the roadway.

Vehicle <NUM> is traveling along a navigation route on a roadway. Although presented as a road (e.g., a highway) with lanes and lane markers in <FIG>, the roadway can be any type of designated travel routes for a vehicle, including for example virtual water lanes used by ships and ferries, virtual air lanes used by unmanned aerial vehicles (UAVs) and other aircraft, train tracks, tunnels, or virtual underwater lanes. The navigation route includes a list of multiple low-precision waypoints <NUM>. The waypoints <NUM> can include respective geographic locations (e.g., latitude and longitude coordinates) provided in sequence according to the desired direction of vehicle travel on sections of the roadway. Each waypoint <NUM> can include a latitude and longitude coordinate that, for example, can typically have a six-meter accuracy.

The roadway includes one or more lanes, with the lanes represented by centerline points <NUM>, lane segments <NUM>, and lane segment groups (LSGs) <NUM> by the route builder <NUM>. The lane segments <NUM> represent respective portions of a roadway lane. For example, the lane segments <NUM>-<NUM>, <NUM>-<NUM>, and <NUM>-<NUM> represent respective portions of the current road in which vehicle <NUM> is traveling. One or more lane segments <NUM> with the same travel direction are included in an LSG <NUM>. The LSGs <NUM> are generally respective portions of a group of lanes in the same travel direction that do not split with unchanging lane markers. For example, the LSG <NUM>-<NUM> includes the lane segments <NUM>-<NUM> and <NUM>-<NUM>. The LSG <NUM>-<NUM> includes the lane segments <NUM>-<NUM> and <NUM>-<NUM>. The LSG <NUM>-<NUM> includes the lane segments <NUM>-<NUM> and <NUM>-<NUM>. Each of the LSGs <NUM> may include a plurality of lines (e.g., vectors of points, lane markers). In some implementations, each of the LSGs <NUM> may include a predetermined origin. The origins can be centered laterally in the respective LSGs <NUM> and at the beginning of each LSG <NUM>. The locations of the origins relative to the respective LSGs <NUM> may vary without departing from the scope of this disclosure.

Each of the lane segments <NUM> includes an array of centerline points <NUM> that represent the lateral center of the respective lane segment <NUM>. The centerline points <NUM> are organized or associated with a lane segment <NUM>.

In the depicted environment <NUM>, one or more sensors (not illustrated) are mounted to or integrated within the vehicle <NUM>. The route builder <NUM> uses an SD map database to generate a navigation route to a desired destination. The navigation route includes multiple waypoints <NUM>. The route builder <NUM> matches the waypoints <NUM> provided by the SD-map database to lane geometry data from an HD map database to generate an HD navigation route. The HD map database can include the centerline points <NUM>, the lane segments <NUM>, and the LSGs <NUM> for relevant portions of the roadway along the navigation route. Details of the HD navigation route generation are discussed further below.

<FIG> illustrates an example system with the route builder <NUM> that can perform SD to HD navigation route determination according to techniques described in this disclosure. Vehicle <NUM> includes one or more processors <NUM>, computer-readable storage medium (CRM) <NUM>, one or more communication components <NUM>, and one or more vehicle-based systems <NUM>. The vehicle <NUM> can also include one or more sensors (e.g., a camera, a radar system, a global positioning system (GPS), a global navigation satellite system (GNSS), a lidar system, an inertial measurement unit (IMU)) to provide input data to the one or more vehicle-based systems <NUM>.

The processor <NUM> can include, as non-limiting examples, a system on chip (SoC), an application processor (AP), an electronic control unit (ECU), a central processing unit (CPU), or a graphics processing unit (GPU). The processor <NUM> may be a single-core processor or a multiple-core processor implemented with a homogenous or heterogenous core structure. The processor <NUM> may include a hardware-based processor implemented as hardware-based logic, circuitry, processing cores, or the like. In some aspects, functionalities of the processor <NUM> and other components of the route builder <NUM> are provided via integrated processing, communication, or control systems (e.g., an SoC), which may enable various operations of the vehicle <NUM> in which the system is embodied.

The CRM <NUM> described herein excludes propagating signals. The CRM <NUM> may include any suitable memory or storage device such as random-access memory (RAM), static RAM (SRAM), dynamic RAM (DRAM), non-volatile RAM (NVRAM), read-only memory (ROM), or Flash memory useable to store device data (not illustrated) and the map data of a map manager <NUM>.

The processor <NUM> executes computer-executable instructions stored within the CRM <NUM> to perform the techniques described herein. For example, the processor <NUM> can execute the map manager <NUM> to process and access map data <NUM> or cause the route builder <NUM> to perform SD to HD navigation route determination.

The map manager <NUM> includes the map data <NUM>. The map manager <NUM> can store the map data <NUM>, process updated map data received from a remote source, and retrieve portions of the map data <NUM> for the route builder <NUM>. The map data <NUM> can include information to generate SD navigation routes, including the waypoints <NUM>, for the vehicle <NUM>. The map data <NUM> can also include HD map data received from a remote source or a database that provides lane geometry data for sections of the roadways along an SD navigation route. The lane geometry data can include the centerline points <NUM>, the lane segments <NUM>, the LSGs <NUM>, and other details associated with roadways (e.g., curvature, traffic control devices, stop bars, localization data, and three-dimensional data). The route builder <NUM> can associate road attributes to LSGs <NUM> or lane segments <NUM>. For example, the route builder <NUM> can associate speed limits to lane segments <NUM>, road curvature to lane segments <NUM> or centerline points <NUM>, and stop signs to LSGs <NUM>. In the depicted system, the map manager <NUM> is illustrated as located on or within the vehicle <NUM>. In other implementations, the map manager <NUM> or another implementation of the map manager <NUM> can be located remote from vehicle <NUM> (e.g., in the cloud or on a remote computer system) and provide the map data <NUM> or a subset of the map data <NUM> to the vehicle <NUM> and the route builder <NUM>.

Similarly, the processor <NUM> can execute the route builder <NUM> to perform SD to HD navigation route determination based on the map data <NUM>. The route builder <NUM> can include a map interface <NUM>, a lane matcher <NUM>, a weight module <NUM>, and a path builder <NUM>. The map interface <NUM> can access the HD map database within the map data <NUM> to obtain the centerline points <NUM>, lane segments <NUM>, LSGs <NUM>, and other landmark data for the different components of the route builder <NUM>. The lane matcher <NUM> can use map data <NUM> to match the waypoints <NUM> from the SD navigation route to lane geometry data in the HD map database. The weight module <NUM> determines possible lanes the vehicle <NUM> can use to follow the SD navigation route. The weight module <NUM> can, for example, determine an HD navigation route that addresses lane and roadway splits and merges along the SD navigation route. The path builder <NUM> can define a list of continuous lane segments <NUM> for vehicle <NUM> to travel along the HD navigation route.

The communication components <NUM> can include a vehicle-based system interface <NUM>. The vehicle-based system interface <NUM> can transmit data over a communication network of the vehicle <NUM> between various components of the vehicle <NUM> or between components of the vehicle <NUM> and external components. For example, when the map manager <NUM> and the route builder <NUM> are integrated within the vehicle <NUM>, the vehicle-based system interface <NUM> may facilitate data transfer therebetween. When the map manager <NUM> is remote to the vehicle <NUM>, the vehicle-based system interface <NUM> may facilitate data transfer between the vehicle <NUM> and a remote entity that has the map manager <NUM>. The communication components <NUM> can also include a sensor interface (not illustrated) to relay measurement data from sensors as input to the vehicle-based systems <NUM> or other components of the vehicle <NUM>.

The vehicle-based system interface <NUM> can transmit HD navigation route data to the vehicle-based systems <NUM> or another component of the vehicle <NUM>. In general, the HD navigation route data provided by the vehicle-based system interface <NUM> is in a format usable by the vehicle-based systems <NUM>. In some implementations, the vehicle-based system interface <NUM> can send information to the route builder <NUM>, including, as a non-limiting example, the speed or heading of the vehicle <NUM>. The route builder <NUM> can use this information to configure itself appropriately. For example, the route builder <NUM> can adjust a starting point of an HD navigation route based on the speed of the vehicle <NUM>.

The vehicle-based systems <NUM> can use data from the route builder <NUM> to operate the vehicle <NUM> on the roadway. The vehicle-based systems <NUM> can include an assisted-driving system and an autonomous-driving system (e.g., an Automatic Cruise Control (ACC) system, Traffic-Jam Assist (TJA) system, Lane-Centering Assist (LCA) system, L3/L4 Autonomous Driving on Highways (L3/L4) system). Generally, the vehicle-based systems <NUM> use the HD navigation route data provided by the route builder <NUM> to perform a function. For example, the assisted-driving system can provide automatic cruise control and monitor for an object (as detected by another system on the vehicle <NUM>) in the lane in which the vehicle <NUM> is traveling. The route data from the route builder <NUM> may identify the lane segments <NUM>.

The vehicle-based systems <NUM> may move the vehicle <NUM> to a particular location on the roadway while navigating the vehicle <NUM> along the navigation route. The autonomous-driving system can also move vehicle <NUM> to a specific location on the roadway to avoid collisions with objects detected by other systems (e.g., a radar system, a lidar system) on the vehicle <NUM> and move the vehicle <NUM> back to the original navigation route. The HD navigation route data provided by the route builder <NUM> can provide information about the locations of the lanes and uncertainties in the locations of the lanes to enable the autonomous-driving system to perform a lane change or steer the vehicle <NUM>.

<FIG> illustrates example conceptual diagrams <NUM> through <NUM> illustrating an SD to HD navigation route determination according to techniques described in this disclosure. The route builder <NUM> obtains an SD navigation route from a navigation system or mobile device. The SD navigation route includes a heading (e.g., direction) and a list of waypoints. The list of waypoints includes a start waypoint <NUM>, intermediate waypoints <NUM>, and a finish waypoint <NUM>.

In conceptual diagram <NUM>, the route builder <NUM> or the lane matcher <NUM> can identify an anchor point from an HD map database to finish the navigation route and a heading <NUM>. Starting with the finish waypoint <NUM>, the lane matcher <NUM> can iterate backward through the list of waypoints until a lane segment in the HD map database is identified that contains the waypoint coordinates. The lane segment can then be identified as a finish road segment <NUM>. The finish road segment <NUM> does not necessarily include the finish waypoint <NUM> (e.g., if the destination is a building or parking area adjacent to a roadway).

In conceptual diagram <NUM>, the route builder <NUM> or the lane matcher <NUM> can identify an anchor point from an HD map database to start the navigation route. Beginning with the start waypoint <NUM>, the lane matcher <NUM> can iterate forward through the list of waypoints until a lane segment in the HD map database is identified that contains the waypoint coordinates. The lane segment can then be identified as a start road segment <NUM>. The start road segment <NUM> does not necessarily include the start waypoint <NUM> (e.g., if the starting place is a building or parking area adjacent to a roadway).

In conceptual diagram <NUM>, the route builder <NUM> or the lane matcher <NUM> expands the list of waypoints via interpolation. The list of waypoints in the SD navigation route is often sparsely spaced along the route, resulting in some lane segments <NUM> (e.g., short lane segments) not being included in the SD navigation route. The lane matcher <NUM> can interpolate the list of waypoints to add waypoints <NUM> for missed lane segments <NUM> and provide a means to create a weighting metric based on the number of waypoints contained within a lane segment <NUM>. The lane matcher <NUM> can apply a linear or cubic interpolation method across the coordinates for the list of waypoints to generate a HD navigation route with a dense set of waypoints. Generally, the lane matcher <NUM> configures the minimum spacing among the waypoints to be no greater than half the length of the shortest candidate lane segment in the route to ensure a lane segment is not skipped.

In the conceptual diagrams <NUM> and <NUM>, the route builder <NUM> or the weight module <NUM> can assign weight values to lane segments <NUM>. The weight module <NUM> can create a histogram with a slot for each LSG <NUM> and lane segment <NUM> within a particular LSG <NUM>. The weight module <NUM> iterates through each waypoint and accumulates the number of waypoints that are geometrically contained within each LSG <NUM> and lane segment <NUM>. In the conceptual diagram <NUM>, LSGs <NUM> do not have any waypoints and thus will not be included in the HD navigation route generated by the route builder <NUM>. In the conceptual diagram <NUM>, lane segments <NUM> include waypoints and will be included in the HD navigation route. In contrast, lane segments <NUM> do not have any waypoints and will not be included in the HD navigation route. The weighting process allows the route builder <NUM> to determine a lane segment <NUM> for each portion of the HD navigation route. For example, the SD navigation route can lack information or waypoints regarding merging an on-ramp and interstate or off-ramps exiting an interstate.

In conceptual diagram <NUM>, the route builder <NUM> or the path builder <NUM> creates the HD navigation route <NUM>. The path builder <NUM> creates a sequence of connected lane segments <NUM> to complete navigation from the start waypoint <NUM> to the finish waypoint <NUM>. The HD navigation route <NUM> includes handling interstate or highway on-ramps and off-ramps along with connector roads. The path builder <NUM> traverses the road network from the finish waypoint <NUM> backward to the start waypoint <NUM>. The path builder <NUM> may use candidate matching logic to determine the correct path for mergers in the road lane segments.

<FIG> illustrates an example conceptual diagram <NUM> of a software method to perform SD to HD navigation route determination according to techniques described in this disclosure. The route builder <NUM> of <FIG> and <FIG> or another component can perform the software method illustrated in the conceptual diagram <NUM>.

Inputs to the route builder <NUM> include the waypoints <NUM> and data originating from an HD map database <NUM>. The waypoints <NUM> include a list of waypoints for the navigation route provided by an SD navigation system. The waypoints <NUM> include multiple geographic locations (e.g., latitude and longitude coordinates) provided in sequence according to the desired direction of travel to reach the desired destination. As described above, the waypoints <NUM> generally have an accuracy of approximately plus or minus three meters.

The HD map database <NUM> includes the relevant road network data for the navigation route. The HD map database <NUM> includes lane geometry data and the associated lane connectivity information. The lane geometry data generally has an accuracy of ten centimeters. The HD map database <NUM> can include road network data for a particular region (e.g., North America, Europe, Asia), country, state, county, or city.

At <NUM>, the route builder <NUM> validates the waypoints <NUM>. The validation includes a basic check on the waypoint coordinates along with a bounds check to ensure the navigation route overlays the contents of the HD map database <NUM> (e.g., a navigation route along Chinese roads may not match to HD map database <NUM> for European roads). The route builder <NUM> can also analyze the navigation route to determine if the waypoints <NUM> exit and reenter the HD road network (e.g., the navigation route includes exiting a highway to stop for refueling or recharging in an urban area not covered by the HD map database <NUM> and then reentering the highway). If so, the route builder <NUM> may split the HD navigation route into multiple paths.

At <NUM>, the route builder <NUM> calls a splitting operation when the navigation route includes gaps not covered by the road network within the HD map database <NUM>. In such scenarios, the navigation route can be partitioned into multiple sub-routes that include continuous paths on the road network. The multiple sub-routes are submitted as inputs to operations <NUM> through <NUM>.

At <NUM>, the route builder <NUM> queries the HD map database <NUM> to obtain lane geometry data for the route determination.

At <NUM>, the route builder <NUM> identifies the last or finish road segment <NUM> containing one of the waypoints <NUM>. The finish road segment <NUM> is determined from the lane geometry data in the HD map database <NUM>. The waypoints <NUM> can continue off or outside the HD map database <NUM>, so the route builder <NUM> can limit the HD navigation route to where the lane geometry data in the HD map database <NUM> ends.

At <NUM>, the route builder <NUM> identifies the first or start road segment <NUM> containing one of the waypoints <NUM>. The start road segment <NUM> is determined from the lane geometry data in the HD map database <NUM>. The waypoints <NUM> can begin off or outside the HD map database <NUM>, so the route builder <NUM> can limit the HD navigation route to where the lane geometry data in the HD map database <NUM> starts.

At <NUM>, the route builder <NUM> interpolates the waypoints <NUM> to add additional waypoints to the navigation route at a configurable spacing (e.g., every <NUM>). The configurable spacing may be static (e.g., fixed) or dynamic (e.g., based on the shortest lane segment <NUM> or LSG <NUM> along the navigation route). The additional waypoints improve the weighting performed by the route builder <NUM> and close gaps for lane segments <NUM> or LSGs <NUM> missed by the waypoints <NUM>.

The route builder <NUM> can also maintain a list or array of lane node objects that have been matched to the waypoints in the navigation route. The lane nodes include connectivity data to link previous and next lane nodes together to form the road network.

At <NUM>, the route builder <NUM> determines a weight for each potential lane segment <NUM> and LSG <NUM> along the navigation route. The route builder <NUM> can store an accumulation of waypoints within each lane segment <NUM> and LSG <NUM> (e.g., within a histogram, array, or variable set).

At <NUM>, the route builder <NUM> creates a path for the navigation route. The path is based on the weights for the potential lane segments <NUM> and LSGs <NUM> by crawling the navigation route in reverse. The created path includes path lane segments <NUM> within the HD map database <NUM> to travel from the starting point to the finish point. The path lane segments <NUM> can be defined or identified using a list or array of lane segment identifications to define the navigation route at a lane level. Similarly, the path lane segments <NUM> can include a list or array of LSG identifications to define the navigation route at a road section level.

<FIG> illustrates an example conceptual diagram <NUM> of a software method to identify a finish road segment <NUM> for a navigation route. The conceptual diagram <NUM> provides a more detailed description of operation <NUM> (e.g., identifying the finish segments) of <FIG>. The route builder <NUM> of <FIG> and <FIG> or the lane matcher <NUM> of <FIG> can perform the software method illustrated in the conceptual diagram <NUM>.

Inputs to the lane matcher <NUM> include the waypoints <NUM> and the HD map database <NUM>. As described above, the waypoints <NUM> include a list of waypoints for the navigation route and are provided by the SD navigation system. The HD map database <NUM> includes the relevant road network data for the navigation route. The HD map database <NUM> includes lane geometry data and the associated lane connectivity information.

At <NUM>, the lane matcher <NUM> iterates through the waypoints <NUM> in reverse until a waypoint is identified within an HD map lane node (e.g., lane segment <NUM>, LSG <NUM>, or a combination thereof).

At <NUM>, the lane matcher <NUM> calls or initiates a lane node module <NUM> for each waypoint <NUM> to determine if the respective waypoint coordinates are contained within a lane node of the HD map database <NUM>.

At <NUM>, the lane node module <NUM> queries the HD map database <NUM> for the lane nodes that contain the waypoint coordinates. The lane node module <NUM> can expand the waypoint coordinates by a configurable amount (e.g., ten meters) to find a lane node even when the waypoint is not included within the road network of the HD map database <NUM>. The expanded coordinates may help identify the finish lane segment and LSG <NUM> when the waypoint coordinates are inaccurate.

At <NUM>, the lane node module <NUM> iterates through the queried lane nodes to determine a match.

At <NUM>, the lane node module <NUM> obtains the lane geometry to create a polygon for the lane area. The polygon is used to determine if the waypoint position is contained within the lane node.

At <NUM>, the lane node module <NUM> determines whether the waypoint is contained within the lane area to identify the matching lane segment <NUM>. If a matching lane node is found, a reference or identification for the lane node is returned to the lane matcher <NUM>. If a matching lane node is not found, the lane node module <NUM> returns to operation <NUM>.

If no lane nodes are matched by the lane node module <NUM>, the waypoint is likely off the road. The lane node module <NUM> checks the waypoint to determine if it is located to the right of the rightmost lane or the left of the leftmost lane. The lane node module <NUM> can return the appropriate lane to the lane matcher <NUM>.

At <NUM>, the lane matcher <NUM> determines whether the lane node for the waypoint has been found. At <NUM>, if the lane node has been found, the lane matcher <NUM> identifies the finish road segment <NUM>. The finish road segment <NUM> can be identified by identification values based on the matching lane node. If the lane node has not been found, the lane matcher <NUM> returns to operation <NUM> to iterate through the waypoints <NUM>.

<FIG> illustrates an example conceptual diagram <NUM> of a software method to identify a start road segment <NUM> for a navigation route. The conceptual diagram <NUM> provides a more detailed description of operation <NUM> (e.g., identifying the start segments) of <FIG>. The route builder <NUM> of <FIG> and <FIG> or the lane matcher <NUM> of <FIG> can perform the software method illustrated in the conceptual diagram <NUM>.

Inputs to the lane matcher <NUM> include the waypoints <NUM> and the HD map database <NUM>. As described above, the waypoints <NUM> include a list of waypoints for the navigation route and are provided by the SD navigation system. The HD map database <NUM> includes the relevant road network data for the navigation route. The HD map database <NUM> includes the lane geometry data and the associated lane connectivity information.

At <NUM>, the lane matcher <NUM> iterates through the waypoints <NUM> until a waypoint is identified within an HD map lane node (e.g., lane segment <NUM>, LSG <NUM>, or a combination thereof).

At <NUM>, the lane matcher <NUM> calls or initiates the lane node module <NUM> for each waypoint <NUM> to determine if the respective waypoint's coordinates are contained within a lane node of the HD map database <NUM>. The lane node module <NUM> performs the same or similar operations as described in reference to <FIG>.

At <NUM>, the lane node module <NUM> queries the HD map database <NUM> to find the lane nodes that contain the waypoint coordinates. The lane node module <NUM> can expand the waypoint coordinates by a configurable amount (e.g., ten meters) to find a lane node even when the waypoint is not included within the road network of the HD map database <NUM>. The expanded coordinates help identify the start lane segment and LSG <NUM> when the waypoint coordinates are inaccurate.

At <NUM>, the lane node module <NUM> determines whether the waypoint is contained within the lane area to identify the matching lane segment <NUM>. If a matching lane node is found, a reference or identification for the lane node is returned to the lane matcher <NUM>. If a matching lane node is not found, then the lane node module <NUM> returns to operation <NUM>.

If no lane nodes are matched by the lane node module <NUM>, the waypoint is likely off the road, and the lane node module <NUM> checks the waypoint to determine if it is located to the right of the rightmost lane or the left of the leftmost lane. The lane node module <NUM> can return the appropriate lane to the lane matcher <NUM>.

At <NUM>, the lane matcher <NUM> determines whether the lane node for the waypoint has been found. At <NUM>, if the lane node has been found, the lane matcher <NUM> identifies the start road segment <NUM>. The start road segment <NUM> can be identified by identification values based on the matching lane node. If the lane node has not been found, the lane matcher <NUM> returns to operation <NUM> to iterate through the waypoints.

<FIG> illustrates an example conceptual diagram <NUM> of a software method to interpolate the waypoints <NUM> for a navigation route. The conceptual diagram <NUM> provides a more detailed description of operation <NUM> (e.g., interpolating the waypoints <NUM>) of <FIG>. The route builder <NUM> of <FIG> and <FIG> or the lane matcher <NUM> of <FIG> can perform the software method illustrated in the conceptual diagram <NUM>.

Inputs to the lane matcher <NUM> include the waypoints <NUM>. As described above, the waypoints <NUM> include the list of waypoints for the navigation route and are provided by the SD map database. The output of the lane matcher <NUM> is a dense set of waypoints <NUM> to better match the lane segments <NUM> of the navigation route. The dense set of waypoints <NUM> can be stored as a variable that defines the navigation route.

At <NUM>, the lane matcher <NUM> iterates through the waypoints <NUM>. The iteration generates a dynamic list of waypoints and allows for the additional waypoints to the list while iterating.

At <NUM>, lane matcher <NUM>, for each pair of adjacent waypoints in the list, calculates a Euclidian distance between the respective waypoints. At <NUM>, the lane matcher <NUM> determines whether the distance between the waypoints is greater than a distance threshold (e.g., <NUM> meters). The distance threshold can be adjusted to provide the desired weighting for the weight module <NUM>. At <NUM>, if the distance is greater than the distance threshold, the lane matcher <NUM> interpolates between the waypoints to determine the coordinates of an intermediate waypoint. It then adds the intermediate waypoint to the list between the waypoints. The lane matcher <NUM> then iterates to the intermediate waypoint at operation <NUM> and continues the operations of the conceptual diagram <NUM>. If the distance is not greater than the distance threshold, then the lane matcher <NUM> returns to operation <NUM> and iterates to the next waypoint in the list. When the lane matcher <NUM> has iterated through the list of waypoints to the final waypoint, the lane matcher outputs the dense set of waypoints <NUM>.

<FIG> illustrates an example conceptual diagram <NUM> of a software method to determine segment weights for SD to HD navigation route determination. The conceptual diagram <NUM> provides a more detailed description of operation <NUM> (e.g., determining the segment weights) of <FIG>. The route builder <NUM> of <FIG> and <FIG> or the weight module <NUM> of <FIG> can perform the software method illustrated in the conceptual diagram <NUM>.

Inputs to the weight module <NUM> include the dense set of waypoints <NUM> and the HD map database <NUM>. As described above, the dense set of waypoints <NUM> includes a list of waypoints for the navigation route output by the lane matcher <NUM>. The HD map database <NUM> includes the relevant road network data for the navigation route. The HD map database <NUM> includes the lane geometry data and the associated lane connectivity information. Outputs from the weight module <NUM> include lane segment weights <NUM> and LSG weights <NUM> based on the number of waypoints.

At <NUM>, the weight module <NUM> assigns a finish lane node to a lane node variable, which initializes a current lane node to account for the high probability that the last waypoint matches. At <NUM>, the weight module <NUM> iterates through the dense set of waypoints <NUM> from the last waypoint (e.g., the end of the navigation route) to the first waypoint (e.g., the start of the navigation route). At <NUM>, the weight module <NUM> determines whether the respective lane node contains the current waypoint. The weight module <NUM> can call a specific object (e.g., a lane node object) to make the determination. If the waypoint is contained within the lane node, then the weight module <NUM> continues to operation <NUM>, as described below.

If the waypoint is not within the lane node, at <NUM>, the weight module <NUM> searches for a matching lane node. The weight module <NUM> can call the lane node module <NUM> to determine if the HD map database <NUM> includes a lane node that contains the current waypoint. The lane node module <NUM> performs the same or similar operations as described in reference to <FIG> and <FIG>.

At <NUM>, the weight module <NUM> determines whether a matching lane node is found. If a matching lane node is not found, then the current waypoint is discarded, and the weight module <NUM> returns to operation <NUM> to continue to the next waypoint in the dense set of waypoints <NUM>. At <NUM>, if a matching lane node is found, the weight module <NUM> assigns the lane node to a lane node variable. At <NUM> and <NUM>, the weight module <NUM> increments the lane segment weight <NUM> and the LSG weight <NUM>, respectively, for the current lane node.

<FIG> illustrate example conceptual diagrams <NUM>-<NUM>, <NUM>-<NUM>, and <NUM>-<NUM>, respectively, of a software method to generate the path lane segments <NUM> for the HD navigation route. The conceptual diagrams <NUM>-<NUM> through <NUM>-<NUM> provide a more detailed description of operation <NUM> (e.g., creating the path lane segments <NUM>) of <FIG>. The route builder <NUM> of <FIG> and <FIG> or the path builder <NUM> of <FIG> can perform the software method illustrated in the conceptual diagrams <NUM>-<NUM> through <NUM>-<NUM>.

Inputs to the path builder <NUM> include the dense set of waypoints <NUM> and the HD map database <NUM>. As described above, the dense set of waypoints <NUM> includes the list of waypoints for the navigation route that is output by the lane matcher <NUM>. The HD map database <NUM> includes the relevant road network data for the navigation route. The HD map database <NUM> includes the lane geometry data and the associated lane connectivity information. Outputs from path builder <NUM> include the path lane segments <NUM> and the HD navigation route.

At <NUM>, the path builder <NUM> assigns the LSG from the finish lane node to an LSG variable, which initializes the process to start from the end of the navigation route and work in reverse through lane and road mergers. At <NUM>, the path builder <NUM> iterates through the dense set of waypoints <NUM> from finish to start to determine the matching lane segments <NUM>.

At <NUM>, the path builder <NUM> adds a currently matched LSG to the navigation route. Path builder <NUM> can accumulate identification information for the list of matching LSGs for the navigation route. At <NUM>, path builder <NUM> obtains all the lane segments <NUM> for the current LSG <NUM> from the HD map database <NUM>.

At <NUM>, the path builder <NUM> queries the HD map database <NUM> to obtain the previous LSG <NUM> for the currently matched LSG <NUM>. For continuous roads, a single LSG <NUM> is retrieved. Merger conditions result in multiple previous LSGs <NUM> to be evaluated by the path builder <NUM> to determine the correct path. At <NUM>, the path builder <NUM> determines whether a previous LSG is found. If no previous LSG is found, this indicates the end of the road within the HD map database <NUM>, and the path builder <NUM> terminates the software method and outputs the path lane segments <NUM>.

At <NUM>, if a previous LSG is found, the path builder <NUM> determines whether the previous LSG is a starting LSG. If the previous LSG is the starting LSG, this indicates the path is complete from the finish waypoint to the start waypoint of the HD navigation route, and the path builder <NUM> terminates the software method and outputs the path lane segments <NUM>. At <NUM>, if the previous LSG is not the starting LSG, then the path builder <NUM> determines whether a single previous LSG was found. If a single LSG was obtained in operation <NUM>, then the path builder <NUM> proceeds to operation <NUM>, as described in greater detail below.

At <NUM>, if multiple LSGs were obtained as the previous LSG(s), then the path builder <NUM> determines the correct LSG. For example, a candidate LSG module <NUM> can be called to choose the correct path to continue building the HD navigation route. The candidate LSG module <NUM> can walk through each candidate LSG to compare the LSG weights <NUM> between each option. At <NUM>, the candidate LSG module <NUM> iterates through each lane segment <NUM> for each previous LSG. At <NUM>, the candidate LSG module <NUM> determines a lane segment weight <NUM> for each lane segment <NUM>. At <NUM>, the candidate LSG module <NUM> determines whether a match exists by identifying whether any lane segment <NUM> has a lane segment weight <NUM> greater than zero. If no match exists, the candidate LSG module <NUM> returns to operation <NUM>. If a match exists, at <NUM>, the candidate LSG module <NUM> adds the LSG to the output list of candidate LSGs.

At <NUM>, the path builder <NUM> determines whether there are any candidate LSGs. If there are no candidate LSGs, the path builder <NUM> terminates the software method and outputs the path lane segments <NUM>. If there is at least one candidate LSG, at <NUM>, the path builder <NUM> determines whether there is a single candidate LSG. At <NUM>, if multiple candidate LSGs are present, the path builder <NUM> determines the correct LSG. The path builder <NUM> can call a best LSG module <NUM> to determine the correct LSG. The best LSG module <NUM> iterates through each candidate path to compare the overall match weights between each candidate LSG. At <NUM>, the best LSG module <NUM> queries the HD map database <NUM> to find multiple merging paths. At <NUM>, the best LSG module <NUM> calculates and accumulates the match weights for each lane segment of the candidate LSGs. At <NUM>, the best LSG module <NUM> selects the highest weighted lane segment. At <NUM>, the path builder <NUM> assigns the current LSG variable equal to the previous or candidate LSG and returns to operation <NUM>.

<FIG> illustrates an example flowchart <NUM> as an example process performed by a route builder for SD to HD navigation route determination. Flowchart <NUM> is shown as sets of operations (or acts) performed, but not necessarily limited to the order or combinations in which the operations are shown herein. Further, one or more of the operations may be repeated, combined, or reorganized to provide other methods. In portions of the following discussion, reference may be made to route builder <NUM> of <FIG> and entities detailed therein, references to which are made for example only. The techniques are not limited to performance by one entity or multiple entities.

At <NUM>, a route builder receives a navigation route for a host vehicle from an SD map database that includes a list of waypoints. For example, the route builder <NUM> can receive the navigation route for vehicle <NUM> from the SD map database. The navigation route includes the list of waypoints <NUM>. The SD map database can be installed in the vehicle <NUM> or located remote from the vehicle <NUM> (e.g., in the cloud, on a remote computer system, on a mobile device, other mobile computing system). If the SD map database is remote to or separate from the vehicle <NUM>, the navigation route can be wirelessly communicated to vehicle <NUM> (e.g., via cellular, WiFi, Bluetooth, other wireless communication).

At <NUM>, responsive to receiving the navigation route, the route builder matches the list of waypoints to lane geometry data maintained in an HD map database. For example, the route builder <NUM> matches the list of waypoints <NUM> to lane geometry data in response to receiving the navigation route. The lane geometry data is maintained in the HD map database <NUM>. The HD map database <NUM> can be installed in the vehicle <NUM> or stored remotely (e.g., in the cloud or another computer system). The HD map database <NUM> can include road segment data (e.g., lane segments <NUM>, LSGs <NUM>, associated connectivity data) for roads of a particular region (e.g., North America). For example, the HD map database <NUM> can be located remote from the vehicle <NUM> and execute the operation <NUM> remote from the vehicle <NUM>. The HD map database <NUM> can then send the HD navigation route, including the path lane segments <NUM>, via wireless communication to the vehicle <NUM>.

The route builder <NUM> can match the list of waypoints <NUM> to the lane geometry data by identifying the finish road segment and the start road segment of the HD navigation route. The route builder <NUM> can identify the finish road segment (e.g., the finish lane segment and LSG <NUM>) by starting with the last waypoint in the list of waypoints <NUM> and iterating backward through the list of waypoints <NUM> to identify the finish lane segment that includes coordinates of a waypoint in the list of waypoints <NUM>. The route builder <NUM> can identify the start road segment (e.g., the start lane segment and LSG <NUM>) by starting with the first waypoint in the list of waypoints <NUM> and iterating forwards through the list of waypoints <NUM> to identify the start lane segment that includes coordinates of a waypoint in the list of waypoints <NUM>.

The route builder <NUM> can then interpolate the list of waypoints <NUM> between the start road segment and the finish road segment to generate the dense set of waypoints <NUM>. The dense set of waypoints <NUM> includes the list of waypoints <NUM> and the additional waypoints. The interpolation of the list of waypoints <NUM> can be performed by applying linear interpolation or cubic interpolation across coordinates of the list of waypoints to generate the dense set of waypoints <NUM>. The spacing between waypoints in the dense set of waypoints <NUM> is generally configurable and can be less than half the length of the shortest candidate road segment among the candidate road segments.

The route builder <NUM> can weight the candidate road segments between the start and finish road segments. The candidate road segments include lane segments <NUM> and LSGs <NUM>. The route builder <NUM> performs the weighting by iterating through each waypoint in the dense set of waypoints <NUM> and accumulating a number of waypoints geometrically contained within each lane segment and each LSG in the candidate road segments.

The route builder <NUM> can create the HD navigation route that includes the path lane segments <NUM> between the start and finish road segments. The path lane segments <NUM> can be determined in reverse order. The route builder <NUM> applies candidate matching logic to determine the lane segments <NUM> from the finish road segment to the start road segment, including determining the correct road segments at mergers in the candidate road segments. The path lane segments <NUM> can also be determined in a forward manner in other implementations. For example, the route builder <NUM> can apply candidate matching logic to determine the lane segments <NUM> from the start road segment to the finish road segment, including determining the correct road segments at mergers in the candidate road segments. The HD navigation route includes a sequential list of the path lane segments <NUM> from the starting point to the finish point of the navigation route.

At <NUM>, the route builder outputs the HD navigation route in response to matching the lane geometry data to the list of waypoints. The HD navigation route is output to a vehicle controller of the host vehicle. For example, route builder <NUM> outputs an HD navigation route to a vehicle controller, including vehicle-based systems <NUM>. The HD navigation route includes the list of waypoints <NUM>, additional waypoints, and the lane geometry data. The HD navigation route can also have the path lane segments <NUM>.

At <NUM>, the vehicle controller operates the host vehicle in a roadway environment along the HD navigation route. For example, the vehicle-based systems <NUM> can operate vehicle <NUM> on roads to navigate the HD navigation route.

Claim 1:
A method comprising:
receiving, from a standard-definition (SD) map database, a navigation route for a host vehicle (<NUM>), the navigation route including a list of waypoints (<NUM>), the list of waypoints including a start waypoint (<NUM>), intermediate waypoints (<NUM>), and a finish waypoint (<NUM>);
responsive to receiving the navigation route, matching the list of waypoints to lane geometry data maintained in a high-definition (HD) map database by:
identifying a finish road segment (<NUM>) in the HD map database that contains coordinates of a first respective waypoint, the first respective waypoint comprising the finish waypoint (<NUM>) or a first other waypoint among the list of waypoints;
identifying a start road segment (<NUM>) in the HD map data database that contains coordinates of a second respective waypoint, the second respective waypoint comprising the start waypoint (<NUM>) or a second other waypoint among the list of waypoints;
interpolating the list of waypoints between the start road segment (<NUM>) and the finish road segment (<NUM>) to generate a dense set of waypoints, the dense set of waypoints including the list of waypoints and additional waypoints;
for road segments within the HD map database between the start road segment (<NUM>) and the finish road segment (<NUM>), determining candidate road segments by identifying one or more waypoints within the dense set of waypoints geometrically contained within each candidate road segment, the candidate road segments including candidate lane segment groups and candidate lane segments within each candidate lane segment group; and
creating a HD navigation route that includes path lane segments (<NUM>) between the start road segment (<NUM>) and the finish road segment (<NUM>), the HD navigation route including the list of waypoints, additional waypoints, and the lane geometry data;
outputting, to a vehicle controller, the HD navigation route; and
operating, with the vehicle controller, the host vehicle (<NUM>) in a roadway environment along the HD navigation route.