Patent Description:
At least partially autonomous vehicles, i.e. vehicles capable of autonomous longitudinal and lateral control with the driver taking their hands off the steering wheel on certain types of roads, typically rely on map data to determine a path of the at least partially autonomous vehicle. On an at least partially-controlled access multilane highway, i.e. a road with multiple lanes per direction with each direction physically separated from the other and access and egress therefrom at least for some sections limited to on-ramps and off-ramps respectively, map data may include information regarding a number of lanes at any given point of an at least partially-controlled access multilane highway, as well as information on how lanes are connected to one another in case a lane ends or starts. However, such information may be incomplete or may be missing entirely for some sections of the at least partially controlled-access highway. Consequently, the at least partially autonomous vehicle may be unable to determine longitudinal and lateral control while driving on sections of the at least partially controlled-access highway with incomplete or missing map data. This may in particular be an issue if the at least partially autonomous vehicle is approaching a target off-ramp, i.e. when the vehicle is about leave the at least partially controlled-access multilane highway. The driver would thus be required to take over control of the at least partially autonomous vehicle in these situations.

Document <CIT> discloses a lane-level route optimizer, which may provide an optimal route on a highway towards an off ramp. A cost value is added for any lane changes, so that the optimal route minimises the number of lane changes.

It is an objective of the present disclosure to enable an at least partially autonomous vehicle to determine an egress route while driving on at least partially controlled-access multilane highway with sectionally incomplete map data.

To achieve this objective, the present disclosure provides a method for determining an egress route for a vehicle to a target off-ramp of an at least partially controlled-access multilane highway. The method comprises obtaining map data regarding the at least partially controlled-access multilane highway. The map data is arranged in a plurality of links. Each link defines for a corresponding section of the at least partially controlled-access multilane highway a geographic position. At least a subset of the plurality of links includes at least one of a lane number and lane relationship information. The method further comprises generating an egress route graph based on the map data and the target off-ramp. The egress route graph comprises a plurality of egress route nodes and a plurality of egress route edges. The plurality of egress route edges includes lane direction edges based on the lane numbers and the lane relationship information of the plurality of links and lane change edges corresponding to lane changes between lanes of the at least partially controlled-access multilane highway. Each egress route node of the plurality of egress route nodes defines a start and an end of the lane direction edges based on the geographic positions of the plurality of links. The method further comprises assigning to each egress route edge a confidence value indicative of an existence probability of each egress route edge and a cost value indicative of the cost of traversing each egress route edge. The method further comprises determining the egress route. The egress route corresponds to a path through the egress route graph to the target off-ramp, which has an optimized total confidence value and an optimized total cost value.

The present disclosure further provides an automotive control unit. The automotive control unit comprises at least one processing unit and a memory coupled to the at least one processing unit and configured to store machine-readable instructions. The machine-readable instructions cause the at least one processing unit to obtain map data regarding the at least partially controlled-access multilane highway. The map data is arranged in a plurality of links. Each link defines for a corresponding section of the at least partially controlled-access multilane highway a geographic position. At least a subset of the plurality of links includes at least one of a lane number and lane relationship information. The machine-readable instructions further cause the at least one processing unit to generate an egress route graph based on the map data and the target off-ramp. The egress route graph comprises a plurality of egress route nodes and a plurality of egress route edges. The plurality of egress route edges includes lane direction edges based on the lane numbers and the lane relationship information of the plurality of links and lane change edges corresponding to lane changes between lanes of the at least partially controlled-access multilane highway. Each egress route node of the plurality of egress route nodes defines a start and an end of the lane direction edges based on the geographic positions of the plurality of links. The machine-readable instructions further cause the at least one processing unit to assign to each egress route edge a confidence value indicative of an existence probability of each egress route edge and a cost value indicative of the cost of traversing each egress route edge. The machine-readable instructions further cause the at least one processing unit determine the egress route. The egress route corresponds to a path through the egress route graph to the target off-ramp, which has an optimized total confidence value and an optimized total cost value.

The present disclosure further provides a vehicle comprising the automotive control unit.

Examples of the present disclosure will be described with reference to the following appended drawings, in which like reference signs refer to like elements.

It should be understood that the above-identified drawings are in no way meant to limit the present disclosure. Rather, these drawings are provided to assist in understanding the present disclosure. The person skilled in the art will readily understand that aspects of the present invention shown in one drawing may be combined with aspects in another drawing or may be omitted without departing from the scope of the present disclosure.

The present disclosure generally provides a method for determining an egress route for a vehicle to a target off-ramp of an at least partially controlled-access multilane highway as well as an automotive control unit configured to execute instructions implementing the method for determining the egress route and a vehicle including the automotive control unit.

The method generates an egress route graph based on map data. More precisely, the map data of the at least partially controlled-access multilane highway is arranged in links, which include lane information. The lane information may e.g. specify for at least for some sections of the at least partially controlled-access multilane highway a number of lanes as well as how lanes are connected if lanes start or end. The method takes the links and the included lane information and generates an egress route graph based on the links and the included lane information. If lane information for a section of the at least partially controlled-access multilane highway is incomplete or missing, the method estimates egress route nodes and egress route edges of the egress route graph corresponding to the section of the at least partially controlled-access multilane highway with incomplete lane information. To account for the estimation of egress route edges and egress route nodes of the egress route graph, the method assigns each egress route edge of the egress route graph a confidence value, which indicates the confidence the method has that a given egress route edge exists. The method further assigns each egress route edge a cost value, which indicates the cost of traversing the respective egress route edge with the vehicle performing the method. Based on the egress route graph and the assigned confidence value and the assigned cost value, the method determines an egress route toward the target off-ramp by determining a path through the egress route graph which minimizes the total cost and maximizes the total confidence associated with reaching the target off-ramp.

The method may further update the egress route graph based on sensor data of the vehicle as the vehicle travels along the egress route and may accordingly update the egress route in order to take into account surrounding traffic impacting cost values of the egress route edges as well as changing confidence values of the egress route edges, e.g. based on the surrounding traffic or environment features detected by the vehicle.

This general concept will be explained with reference to the appended drawings, with <FIG> providing a flowchart of a method <NUM> for determining an egress route for a vehicle to a target off-ramp of an at least partially controlled-access multilane highway, and <FIG> illustrating various aspects of method <NUM>. In addition, <FIG> illustrates a vehicle according to the present disclosure and <FIG> illustrates an automotive controller configured to perform method <NUM>.

It will be understood that dashed boxes in <FIG> illustrate optional steps of method <NUM>.

Method <NUM> is configured to determine an egress route for a vehicle, such as vehicle <NUM> of <FIG>, to a target off-ramp of an at least partially controlled-access multilane highway, such as at least partially controlled-access multilane highway <NUM> of <FIG> or of <FIG>.

Vehicle <NUM> in the context of the present disclosure refers to any kind of motor vehicle configured to transport people and/or cargo. The motor of vehicle <NUM> may be any kind of motor, such as an electric motor or an internal combustion engine. Vehicle <NUM> may e.g. be a passenger vehicle as shown in <FIG>. It will however be understood that the vehicle <NUM> may also be a bus, a truck or any other kind of vehicle including one or more sensors <NUM> and an automotive control unit <NUM> enabling vehicle <NUM> to drive in a partially automated manner. In other words, automotive control unit <NUM> and one or more sensors <NUM> are configured to enable at least partial driving automation, i.e. level <NUM> as defined in standard J3016 of SAE International. Accordingly, method <NUM> provides the egress route to functions within automotive control unit <NUM> which control longitudinal and lateral movement to guide vehicle <NUM> to the target off-ramp under supervision of a driver of vehicle <NUM>. It will be understood that automotive control unit <NUM> and one or more sensors <NUM> may enable higher levels of automation, i.e. the egress route may be used as input for lateral and longitudinal control of vehicle <NUM> with limited or without supervision by the driver, or even with no driver present.

The one or more sensors <NUM> may be configured to capture sensor data indicative of the environment of vehicle <NUM>, which may provide the environmental awareness enabling at least partial driving automation. For example, the one or more sensors <NUM> may provide vehicle <NUM> with information on the position and size of other vehicles <NUM> and trucks <NUM> of <FIG>. To this end, the one or more sensors <NUM> may be radar sensors, which may be configured to emit radio waves in order to determine a distance, an angle and a velocity of objects around the vehicle based on the reflected radio waves. The one or more sensors <NUM> may be light detection and ranging (LIDAR) sensors, which are configured to emit laser beams in order to determine a distance, an angle and a velocity of objects around vehicle <NUM> based on the reflected laser beams. The one or more sensors <NUM> may be cameras, which capture images of the environment of the vehicle. The one or more sensors <NUM> may be thermographic cameras, which capture images of the environment of vehicle <NUM> based on infrared radiation. It will be understood that LIDAR sensors, radar sensors or cameras are merely provided as examples of sensor types of the one or more sensors <NUM>. For example, the one or more sensors <NUM> may also be ultrasonic sensors. More generally, the one or more sensors <NUM> may be any type of sensor capable of capturing sensor data indicative of the environment of vehicle <NUM>. It will further be understood that the one or more sensors <NUM> may include multiple sensors of various types of sensors. Further, the one or more sensors <NUM> of the same type may exhibit different properties, e.g. by being configured to capture sensor data at different ranges, such as a close range, a middle range and a far range. For example, vehicle <NUM> may include three close range radar sensors each at a front and a back of vehicle <NUM>, a middle range to far range radar sensor at the back of vehicle <NUM>, a LIDAR sensor at the front of vehicle <NUM>, a rear-facing camera at the back of vehicle <NUM>, a front-facing camera at the front of the vehicle, a front-facing camera at the rear-view mirror and a rear-facing close range to middle range radar sensor in each door-mounted outer rear view mirror. It will be understood that vehicle <NUM> may include more or fewer automotive sensors than shown in <FIG> and discussed in the above example.

Automotive control unit <NUM> will be discussed in more detail below with regard to <FIG>.

At least partially controlled-access multilane highway <NUM>, hereinafter referred to as highway <NUM>, may be any kind of road with multiple lanes per direction with the directions being separated from one another e.g. by a strip of land, a median barrier or a combination of both. Further, access onto and egress from highway <NUM> is at least partially controlled, i.e. access onto and egress from highway <NUM> is at least in some sections of highway <NUM> limited to on-ramps and off-ramps. For example, access onto and egress from highway <NUM> may be fully controlled, in which case highway <NUM> may be referred to as a controlled-access highway, such as a freeway, an interstate or a motorway. In a further example, some sections of highway <NUM> may include at-grade intersections, in which case highway <NUM> may also be referred to as a limited-access highway, a dual-carriageway or an expressway. Examples of one direction including an off-ramp of highway <NUM> are shown in <FIG> and <FIG>.

In step <NUM>, method <NUM> obtains map data, such as map data <NUM>, regarding the at least partially controlled-access multilane highway <NUM>.

Map data <NUM>, as e.g. illustrated in <FIG> and <FIG>, is configured to provide location information regarding highway <NUM>. To this end, map data <NUM> is arranged in a plurality of links, such as links I<NUM> to I<NUM> of <FIG>. Each link defines for a corresponding section of highway <NUM> a geographic position of the section, e.g.by defining a start and an end of the section in terms of the geographic coordinate system (GCS) as defined in the European Petroleum Survey Group (EPSG) Geodetic Parameter Dataset or any other representation of geographic positions. In both <FIG> and Fig. 2A, the starts and the ends of the sections and thus the starts and the ends of the links are illustrated as nodes with a node indicating a corresponding start location of a link and a corresponding end location of a link. Further, <FIG> illustrates, based on the vertical dotted lines, that the start locations of the links and the end locations of the links correspond to the start and the end, respectively, of sections of highway <NUM>. It will accordingly be understood that a link in the context of the present disclosure refers to a representation of the geographic position and the length of a section of highway <NUM>. The links may be of different lengths, as shown in <FIG> and <FIG>, or may be of equal length. Further, the links may represent straight sections as well as curved sections of highway <NUM>.

In addition to providing a representation of the geographic position of a section of highway <NUM>, at least a subset of the plurality of links further respectively includes lane information, which comprises at least one of a lane number and lane relationship information. The lane number is a number indicating how many lanes a given section of highway <NUM> includes. The lane relationship information defines how the lanes of a given section connect to lanes of neighboring sections, i.e. the section preceding a given section and the section succeeding a given section.

While every link defines the geographic position of each section, not every link may respectively include lane information. Further, not every link may include both a lane number and lane relationship information. Accordingly, four types of link may exist: links only defining the geographic position of a given section, links defining a lane number of a given section in addition to the geographic position, links defining lane relationship information of a given section in addition to the geographic position, and links including both a lane number and lane relationship information in addition to defining the geographic position.

The fact that not all links may include lane information is illustrated by links I<NUM> and I<NUM> in <FIG>, which do not include lane information, and their corresponding sections of highway <NUM>, which are illustrated by pointed lines and a question mark. That is, map data <NUM> indicates the start and end of the sections of highway <NUM> corresponding to links I<NUM> and I<NUM> but does not indicate whether the lanes of the preceding sections continue through the sections corresponding to links I<NUM> and I<NUM> or end within these sections and how they connect to the next sections of highway <NUM> corresponding to links including lane numbers. In other words, the lane information of map data <NUM> may be partially incomplete. The incompleteness of the lane information may extend to on-ramps and off-ramps, i.e. map data <NUM> may indicate the presence of a ramps but not on which side of highway <NUM> the respective ramps are located.

The lane information included in each link of map data <NUM> may further include lane change information indicative of permissible changes between lanes. The lane change information may e.g. be based on road markings or traffic regulations. For example, map data <NUM> may indicate the presence of a shoulder, onto which a lane change may not be allowed unless in case of an emergency or a breakdown. Accordingly, the lane change information may not indicate lane changes onto the shoulder. However, in countries allowing use of the shoulder during peak traffic or similar conditions, the lane change information may indicate such temporarily permissible lane changes.

It will be understood that the plurality of links of map data <NUM> may include further information or may include additional data inconsistencies as discussed above. For conciseness, the above discussion of map data <NUM> focuses only on aspects of map data <NUM> relevant to the present disclosure.

In step <NUM>, method <NUM> generates an egress route graph, such as egress route graph <NUM> of <FIG>, based on map data <NUM> and the target off-ramp. More precisely, based on map data <NUM> egress route graph <NUM> provides a representation of all conceivable paths between the location of vehicle <NUM> on highway <NUM> and the target off-ramp, i.e. the off-ramp of highway <NUM> at which vehicle <NUM> should exit highway <NUM>, as e.g. determined by a navigation function of automotive controller <NUM>. Since vehicle <NUM> is typically located on a link of map data <NUM> when egress route graph <NUM> is generated, egress route graph <NUM> may start at a location behind vehicle <NUM> in order to include the entirety of the link which vehicle <NUM> currently traverses.

Egress route graph <NUM> comprises a plurality of egress route nodes and a plurality of egress route edges. Accordingly, egress route graph <NUM> may be defined as shown in equation (<NUM>). <MAT> In equation (<NUM>), G<NUM> denotes egress route graph <NUM>, V denotes the vertices of egress route graph <NUM>, i.e. the plurality of egress route nodes, and E denotes the edges of egress route graph <NUM>, i.e. the of egress route edges.

The plurality of egress route edges includes lane direction edges and lane change edges. The plurality of egress route edges may thus be defined as shown in equation (<NUM>). <MAT> In equation (<NUM>), eld1 to eldn denote lane direction edges and elc1 to elcm denote lane change edges. Accordingly, egress route graph <NUM> may, as defined in equation (<NUM>), include n lane direction edges and m lane change edges.

Lane direction edges correspond to lanes of a section of highway <NUM>. In other words, each lane direction edge represents a lane of highway <NUM> with the direction of each lane direction edge indicating the direction of travel of the corresponding lane. Accordingly, the number of lane direction edges is based on the lane number discussed above. If the lane number of a link and thus the number of lanes of a section of highway <NUM> is missing, the number of lane direction edges is determined based on the closest preceding link including a lane number and the closest succeeding link including a lane number. More precisely, the number of lane direction edges corresponds to all conceivable connections between the lanes of the closest preceding link including a lane number and the lanes of the closest succeeding link including a lane number. Conceivable in the context of connections refers to connections which are typically present on at least partially controlled-access multilane highways. For example, if the closest succeeding link including a lane number indicates one lane less than the closest preceding link including a lane number, one of the two rightmost lanes or of the two leftmost lanes of the closest preceding link may terminate and may accordingly connect to the leftmost lane or the rightmost lane of the closest succeeding link including a lane number.

The lane direction edges are connected to one another based on the lane relationship information of the plurality of links. That is, each lane direction edge is connected to neighboring lane direction edges based on the connections indicated by the respective lane relationship information. In the context of the present disclosure, the expression "neighboring lane direction edges" is to be understood as referring to lane direction edges preceding and succeeding a given lane direction edge in the direction of travel of a lane of highway <NUM> as determined based on the geographic positions of the plurality of links. If a lane relationship information of a given link is missing the connections may be determined based on lane relationship assumption. The lane relationship assumption may be a set of connection rules, which may be specific to a type of highway <NUM> or which may be country-specific. The lane relationship assumption may be based on the approach of connecting all lane direction edges between two neighboring sections. It will be understood that the lane relationship assumption may be any kind of determination of lane direction edge connections based on conceivable connections of lane direction edge connections, as discussed above.

The concept of generating lane direction edges based on links not including lane information and conceivable connections is illustrated in <FIG> with regard to links I<NUM> and I<NUM>. For links I<NUM> and I<NUM>, which do not include lane information, four lane direction edges are generated. In the case of link I<NUM>, the four lane direction edges connect the three lanes of the preceding section corresponding to link I<NUM> and the two lanes of the succeeding section corresponding to link I<NUM>. In the case of link I<NUM>, the four lane direction edges connect the two lanes of the preceding section corresponding to link I<NUM> and the three lanes of the succeeding section corresponding to link I<NUM>. Accordingly, the number of lane direction edges generated per link is based on the lane numbers of the plurality of links in both cases. In the case of links including a lane number, the number of lane direction edges generated per such link corresponds to the lane number. In the case of links not including a lane number, the number of lane direction edges generated per such link is derived from the lane numbers of preceding and succeeding links. Further, the connections of the lane direction edges to the neighboring lane direction edges in the example are based on lane relationship assumption, which in this example is based on the assumption that typically outermost lanes end or that new lanes typically start on the left or right of highway <NUM>.

It will be understood that lane direction edges corresponding to lanes of highway <NUM> are unidirectional, as shown in <FIG> and <FIG>. However, lane direction edges indicative of lanes at at-grade intersections may in some cases be bidirectional, indicating combined egress and access lanes in examples of highway <NUM> being a limited-access highway.

Lane change edges correspond to lane changes between lanes of highway <NUM>. That is, lane change edges indicate that a lane change between lanes of a given section of highway <NUM> is legally permissible, e.g. in view of road surface markings or traffic regulations, which may be indicated in the lane change information included in the plurality of links or which may be provided to method <NUM> by a lane change rule set. In some examples, method <NUM> may also generate lane change between all lane direction edges and account for this approach as discussed in detail below with regard to step <NUM>. While the lane change edges connect vertices of egress route graph <NUM> corresponding lanes of highway <NUM>, as e.g. shown in <FIG> and <FIG>, lane change edges do not indicate that a lane change is only possible at the location corresponding to the respective vertices. Lane changes may also be possible along two lanes represented by two parallel unidirectional edges of egress route graph <NUM> starting at the respective vertices. For example, a lane change may be possible for at least part of the unidirectional edges staring at the corresponding vertices or for the entirety of said lane direction edges until a subsequent vertex in the direction of travel is reached. The subsequent vertex may or may not be connected to a bidirectional edge, thereby indicating a potential change in lane change permissibility. This concept can e.g. be seen in <FIG>, which shows in the section of highway <NUM> corresponding to links I<NUM>, and I<NUM> that no lane change is permissible between the first lane and the second lane within these sections but that such a lane change is possible within the section of highway <NUM> corresponding to link I<NUM>.

It will be understood that the lane change edges may be bidirectional, as shown in <FIG> and <FIG>, or may be unidirectional, if a lane change from one lane to the other is permissible but not the other way round.

Each egress route node of the plurality of egress route nodes defines a start and an end of the lane direction edges based on the geographic positions of the plurality of links. In other words, the egress route nodes include the geographical positions defining the start and the end of the sections of highway <NUM> as defined in the links of map data <NUM>. More precisely, each egress route node corresponds to a connection of two lane direction edges and includes the geographic position of connection. It will be understood that each egress route node thus corresponds to a beginning of one section and an end of a corresponding succeeding section of highway <NUM>.

Based on the above definitions of egress route graph <NUM> and the elements of egress route graph <NUM>, step <NUM> may include steps <NUM> to <NUM>.

In step <NUM>, method <NUM> may generate, a number of lane direction edges for each link including a lane number with the number of lane direction edges generated for each link corresponding to the lane number. For each link which also includes lane relationship information, each lane direction edge is connected to two neighboring lane direction edges based on the lane relationship information. For each link which does not include lane relationship information, each lane direction edge is connected to two neighboring lane direction edges based on a lane relationship assumption, as discussed above.

In step <NUM>, method <NUM> may generate, for each link not including a lane number, a number of lane direction edges based on lane numbers of neighboring links respectively including a lane number. That is, method <NUM> may generate for each link not including a lane number, a number of lane direction edges, which are connected to neighboring lane direction edges based on conceivable connections between lane direction edges as discussed above.

In step <NUM>, method <NUM> may generate, at each connection of two lane direction edges, an egress route node. Each egress route node includes a geographic position based on the links corresponding to the respective two lane direction edges. More precisely, the geographic position included in each egress route node corresponds to an end of a link and a beginning of a subsequent link. It will be understood that as part of step <NUM>, method <NUM> may not generate more than one egress route node per geographical position.

In step <NUM>, method <NUM> may generate lane change edges indicative of lane changes between at least a subset of the plurality of egress route nodes. The generation of the lane change edges may be based on lane change information included in the plurality of links or may be based on known traffic regulations governing lane changes or any other type of information indicating permissible lane changes.

It will be understood that steps <NUM> to <NUM> merely represent an example of how egress route graph <NUM> may be generated based on the principles discussed above with regard to step <NUM>. Method <NUM> may, in step <NUM>, generate egress route graph <NUM> in any way suitable based on the principles discussed above.

In step <NUM>, method <NUM> assigns to each egress route edge a confidence value. and a cost value. In other words, method <NUM> may assign in step <NUM> to each egress route two weights. Accordingly, egress route graph <NUM> is a weighted graph.

The confidence value is indicative of an existence probability of each egress route edge. That is, the confidence value may indicate how probable the existence of each egress route appears to be. For example, in the case of a lane direction edge based on a link including both lane numbers and lane relationship information, it can be assumed that the corresponding lane of highway <NUM> and thus the lane direction edge definitely exists. In such cases, the confidence value may indicate a high existence probability, such as a maximum existence probability. If either one or both the lane number and lane relationship information are not included in a given link, the corresponding lane direction edge may or may not exist, given that the corresponding lane direction edge may be based on neighboring lane directions or assumptions concerning the connection of the lane direction edge with neighboring lane direction edges. In such cases, the confidence value method <NUM> assigns to the corresponding lane direction edges may reflect at least some level of uncertainty regarding the existence of such lane direction edges. The same principles apply to lane change edges. If lane change edges are based on lane change information of links of map data <NUM>, the confidence value may indicate a high existence probability, such as a maximum existence probability. If lane change edges have been generated in step <NUM> based on a lane change rule set or based on the approach of generating lane change edges between all lane direction edges, the confidence value assigned by method <NUM> may reflect at least some level of uncertainty regarding the existence of such lane change edges. In summary, the confidence value may also be understood as indicating the confidence method <NUM> has that a given egress route edge exists.

To provide an example of the above concept, method <NUM> may assign a confidence value in a range of <NUM> to <NUM> to each egress route edge, with <NUM> indicating that a given egress route edge does not exist and <NUM> indicating that a given egress route edge does exist, i.e. a value of <NUM> may indicate a maximum existence probability. If an egress route edge is based on lane information or lane change information included in the links of map data <NUM>, method <NUM> may assign a confidence value of <NUM>, i.e. the maximum probability value. Method <NUM> may also account for the quality of map data <NUM> by assigning a value less than <NUM> in these cases, such as <NUM>, <NUM> or <NUM>, if map data <NUM> is considered to be not fully accurate. If an egress route edge is based on lane relationship assumptions, lane change rule sets or based on the approach of generating lane change edges between all lane direction edges, method <NUM> may assign a confidence value of <NUM> to reflect the existence uncertainty discussed above. If method <NUM> is more or less confident in the existence of an egress route edge, method <NUM> may also assign a value higher than or lower than <NUM>, such as <NUM> or <NUM>, respectively.

It will be understood that the value range of <NUM> to <NUM> is merely provided as an example. Method <NUM> may assign confidence values based on any kind of value range or based on any other metric indicative of a range from "egress route edge does most probably not exist" to "egress route edge does most likely exist".

In accordance with the above principles regarding confidence values, step <NUM> may include steps <NUM> and <NUM>. In step <NUM>, method <NUM> may assign to each egress route edge corresponding to a link including at least one of a lane number and lane relationship information a confidence value indicative of a maximum existence probability. In step <NUM>, method <NUM> may assign to each egress route edge not corresponding to a link including at least one of a lane number and lane relationship information a confidence value indicative of an existence probability of the respective egress route edge.

The cost value is indicative of the cost of traversing each egress route edge. That is, the cost value reflects whether any additional cost in addition to the cost already incurred by driving along highway <NUM> toward the target off-ramp. Accordingly, following along a lane direction edge may incur no additional cost while changing lanes may, incur additional costs, e.g. due a necessary reduction in speed. Further, the closer an egress route edge is to the target off-ramp, the urgency to navigate toward the target off-ramp increases, which may likewise be included in the cost value assigned to egress route edges of egress route graph <NUM> closer to the target off-ramp. Accordingly, the cost of traversing each egress route edge may take into account various cost factors, such as those described above or additional costs indicative of the cost of reaching the target-off ramp.

Using a value range of <NUM> to <NUM> again as an example, a value of zero may indicate no additional cost associated with traversing a given egress route edge while a value of <NUM> may indicate maximum additional cost associated with traversing a given egress route edge. To reflect the increasing urgency with increasing proximity to the target-off ramp, method <NUM> may assign cost values gradually approaching <NUM> with increasing proximity to the target off ramp. For example, a lane direction edge corresponding to the leftmost lane of highway <NUM> at the same position of highway <NUM> as the target off-ramp (cf. e.g. link I<NUM> in <FIG>) may be assigned a cost value of <NUM> given that it may be difficult to impossible to still reach the target off-ramp from this lane direction edge. Accordingly, lane direction edges at the beginning of egress route edges may have a cost value <NUM>. For the lane furthest away from the target off-ramp, e.g. the leftmost lane in <FIG> and <FIG>, the cost value may approach <NUM> with increasing proximity to the target off-ramp. For the lane closest to the target off-ramp, e.g. the rightmost lane in <FIG> and <FIG>, the cost value may stay close to or remain <NUM> with increasing proximity to the target off-ramp. With regard to the lane change edges, the cost value may reflect a base lane change cost, such as <NUM> or <NUM>, With increasing proximity to the target off-ramp, the cost value assigned by method <NUM> may increase steeply for lane change edges connected to lane direction edges corresponding to the leftmost lane of highway <NUM>. By contrast, the cost value assigned by method <NUM> may only increase slowly for lane change edges connected to the rightmost lane of highway <NUM>.

In addition, a given egress route edge assigned a confidence value indicative of the given egress route edge most likely not existing may be assigned a cost value of <NUM> or of infinity to also reflect the lack of probability that the given egress route edge exists also in the cost value.

It will be understood that the value range of <NUM> to <NUM> is merely provided as an example. Method <NUM> may assign cost values based on any kind of value range or based on any other metric indicative of a range from "no additional cost" to "maximum additional cost".

In accordance with the above principles regarding cost values, step <NUM> may include steps <NUM> to <NUM>.

In step <NUM>, method <NUM> may assign to each lane direction edge a lane cost based on a drivable speed during traversal of the lane direction edge. For example, the lane cost based on drivable speed may be zero if a given lane direction edge can be traversed at the national speed limit or a speed set by the driver of vehicle <NUM> or set by an autonomous driving function of vehicle <NUM>. If the drivable speed is lower than such a speed limit or set speed, the lane cost based on a drivable speed may increase with decreasing speed. The lane cost based on a drivable speed may also take into account sensor data of the one or more sensors <NUM>, which may indicate the drivable speed.

In step <NUM>, method <NUM> may assign to each lane change edge a lane change cost. The lane change cost may be based on at least one of a lane change success probability, a traffic density in a target lane of a corresponding lane change and a lane change direction cost. The lane change direction cost may account for the fact that switching lanes form a faster lane, such as the leftmost lane in <FIG> and <FIG>, to a slower lane, may be easier to perform than a lane change from a slower lane to a faster lane. The lane change success probability, the traffic density in a target lane of a corresponding lane change and the lane change direction cost may also take into account sensor data of the one or more sensors <NUM>.

In step <NUM>, method <NUM> may assign to each egress route edge an urgency cost, the urgency cost being indicative of a remaining distance to the target off-ramp. As discussed above, the further away in terms of lanes an egress route edge is while approaching the target off-ramp, the higher the urgency to navigate toward the off-ramp. This urgency may be reflected by the urgency, which may accordingly increase the lower the remaining distance, in particular in the case of egress route edges associated with the lane farthest away from the target off-ramp, such as the leftmost lane in <FIG> and <FIG>.

In step <NUM>, method <NUM> determines the egress route. The egress route corresponds to a path through egress route graph <NUM> to the target off-ramp which has an optimized total confidence value and an optimized total cost value. In other words, method <NUM> may in step <NUM> apply an algorithm for determining a shortest path through egress route graph <NUM> in view of the cost values and confidence values assigned to the egress route graph edges in step <NUM>. Examples of algorithm for determining a shortest path through egress route graph <NUM> may include, but are not limited to, Dijkstra's algorithm, A* algorithm, Bellman-Ford algorithm or Floyd-Warshall algorithm. To this end, step <NUM> may include step <NUM>, in which method <NUM> may determine a shortest path through the egress route graph having a lowest associated total cost value and a maximum associated total confidence value.

It will be understood that the egress route may not include egress route edges with a confidence value indicative of the lowest existence probability. Likewise, egress route edges with a cost value indicative of the highest additional traversal cost may be excluded from the egress route.

Method <NUM> may include a step <NUM>, in which method <NUM> updates the egress route graph based on the sensor data captured by the one or more sensors of <NUM> of vehicle <NUM>. As discussed above, the sensor data may be indicative of at least one of a traffic condition on each lane of highway <NUM>, which is illustrated in <FIG>. In <FIG> vehicle <NUM> may be ware of other vehicle <NUM> and trucks <NUM> based on the sensor data of one or more sensors <NUM>. The sensor data may be further be indicative of road surface markings, as e.g. indicated by the solid lines toward the target-off ramp of highway <NUM> in <FIG>. The sensor data may be further indicative of an end of a lane of highway <NUM>. Based on the sensor data of the one or more sensors, method <NUM> may update egress route graph <NUM> and more precisely the weights of the egress route edges. To this end, step <NUM> may include step <NUM>, in which method <NUM> may update the probability value and the cost value of each egress route edge of the plurality of egress route edges based on the sensor data of one or more sensors <NUM>.

To provide an example of updating the probability value based on the sensor data, a probability value of an egress route edge initially set to a value indicating a lower existence probability due to corresponding to a link of map data <NUM> without lane information or lane change information, may be increased, e.g. even to the maximum existence probability if the sensor data indicates the existence of the lane. In the contrary, if the sensor data indicates that an egress route edge generated based on a link without lane information or lane change information does not exist, the probability value may be updated to indicate the lowest existence probability. In the context of lane change edges, the probability value of these edges may be updated based on detected road surface markings, which may indicate that lane changes may not be permissible. If such road markings are detected, the respective probability values may be set to the lowest probability value.

To provide an example of updating the cost value based on the sensor data, the cost value associated with an egress route edge may be increased or decreased, respectively, based on a traffic density detected by the one or more sensors. Analogously, if the drivable speed is determined by the sensor data to increase or decrease, the cost values of the corresponding egress route edges are decreased or increased, respectively.

Steps <NUM> and <NUM> may be continuously performed while vehicle <NUM> travels toward the target off-ramp. That is, method <NUM> initially assigns in step <NUM> probability values and confidence values to the egress route edges based on which method <NUM> determines in step <NUM> an initial egress route. Afterward, method <NUM> may update the probability values and confidence values in step <NUM> and re-determine the egress route in step <NUM> and repeat these steps until reaching the target off-ramp. This concept is indicated in <FIG> by the bidirectional arrow between steps <NUM> and <NUM>. Accordingly, by repeatedly performing steps <NUM> and <NUM>, the egress route determined in step <NUM> may constantly take into account the current position of vehicle <NUM> and the sensor data captured by the one or more sensors <NUM>.

It will be understood that while steps <NUM> and <NUM> may be performed continuously, the egress route may only be determined once without updates to the egress route graph, for example if highway <NUM> is reserved to automated vehicles only, in which case vehicle <NUM> may broadcast its route intention to other vehicles on highway <NUM>. In such cases, no re-destination of the egress route and updating of egress route graph <NUM> may be necessary.

<FIG> shows automotive control unit <NUM> configured to perform method <NUM>. automotive control unit <NUM> may include a processor <NUM>, a graphics processing unit (GPU) <NUM>, automotive processing system <NUM>, a memory <NUM>, a removable storage <NUM>, a storage <NUM>, a cellular interface <NUM>, a global navigation satellite system (GNSS) interface <NUM> and a communication interface <NUM>.

Processor <NUM> may be any kind of single-core or multi-core processing unit employing a reduced instruction set (RISC) or a complex instruction set (CISC). Exemplary RISC processing units include ARM based cores or RISC V based cores. Exemplary CISC processing units include x86 based cores or x86-<NUM> based cores. Processor <NUM> may perform instructions causing automotive control unit <NUM> to perform method <NUM>. Processor <NUM> may be directly coupled to any of the components of computing device <NUM> or may be directly coupled to memory <NUM>, GPU <NUM> and a device bus.

GPU <NUM> may be any kind of processing unit optimized for processing graphics related instructions or more generally for parallel processing of instructions. As such, GPU <NUM> may be configured to generate a display of information, such as ADAS information or telemetry data, to a driver of the vehicle, e.g. via a head-up display (HUD) or a display arranged within the view of the driver. GPU <NUM> may be coupled to the HUD and/or the display via connection 420C. GPU <NUM> may further perform at least a part of method <NUM> to enable fast parallel processing of instructions relating to method <NUM>. It should be noted that in some embodiments, processor <NUM> may determine that GPU <NUM> need not perform instructions relating to method <NUM>. GPU <NUM> may be directly coupled to any of the components of automotive control unit <NUM> or may be directly coupled to processor <NUM> and memory <NUM>. In some embodiments, GPU <NUM> may also be coupled to the device bus.

Automotive processing system <NUM> may be any kind of system-on chip configured to provide trillions of operations per second (TOPS) in order to enable automotive control unit <NUM> to implement one or more ADAS while driving. Automotive processing system <NUM> may interface only with processor <NUM> or may interface with other devices via the system bus. Automotive processing system <NUM> may for example perform the instructions related to updating egress route graph <NUM> and re-determining the egress route graph based on updated egress route graph <NUM>. Automotive processing system <NUM> may further determine the lateral and longitudinal control of vehicle <NUM> toward the target-off-ramp of highway <NUM>.

Memory <NUM> may be any kind of fast storage enabling processor <NUM>, GPU <NUM> and automotive processing system <NUM> to store instructions for fast retrieval during processing of instructions as well as to cache and buffer data. Memory <NUM> may be a unified memory coupled to processor <NUM> and GPU <NUM> and automotive processing system <NUM> in order to enable allocation of memory <NUM> to processor <NUM>, GPU <NUM> and automotive processing system <NUM> as needed. Alternatively, processor <NUM>, GPU <NUM> and automotive processing system <NUM> may be coupled to separate processor memory 440a, GPU memory 440b and automotive processing system memory 440c.

Removable storage <NUM> may be a storage device which can be removably coupled with automotive control unit <NUM>. Examples include a digital versatile disc (DVD), a compact disc (CD), a Universal Serial Bus (USB) storage device, such as an external SSD, or a magnetic tape. It should be noted that removable storage <NUM> may store data, such as instructions of method <NUM> and/or map data <NUM>, or may be omitted.

Storage <NUM> may be a storage device enabling storage of program instructions and other data. For example, storage <NUM> may be a hard disk drive (HDD), a solid state disk (SSD) or some other type of non-volatile memory. Storage <NUM> may for example store the instructions of method <NUM>.

Removable Storage <NUM> and storage <NUM> may be coupled to processor <NUM> via the system bus. The system bus may be any kind of bus system enabling processor <NUM> and optionally GPU <NUM> as well as automotive processing system <NUM> to communicate with the other devices of automotive control unit <NUM>. Bus <NUM> may for example be a Peripheral Component Interconnect express (PCIe) bus or a Serial AT Attachment (SATA) bus.

Cellular interface <NUM> may be any kind of interface enabling automotive control unit <NUM> to communicate via a cellular network, such as a <NUM> network or a <NUM> network.

GNSS interface <NUM> may be any kind of interface enabling automotive control unit <NUM> to receive position data provided by a satellite network, such as the Global Positioning System (GPS), the Global Navigation Satellite System (GLONASS) or Galileo. The position data may be used when generating and updating egress route graph <NUM> and when determining and re-determining the egress route.

Communications interface <NUM> may enable computing device <NUM> to interface with external devices, either directly or via network, via connection 480C. Communications interface <NUM> may for example enable computing device <NUM> to couple to a wired or wireless network, such as Ethernet, Wifi, a Controller Area Network (CAN) bus or any bus system appropriate in vehicles. For example, automotive control unit <NUM> may be coupled to the one or more sensors <NUM> to receive information about the environment of vehicle <NUM> in order to update egress route graph <NUM>. Communications interface <NUM> may also include a USB port or a serial port to enable direct communication with an external device.

Automotive control unit <NUM> may be integrated with the vehicle, e.g. beneath the cabin, under the dashboard or in the trunk of vehicle <NUM>.

Claim 1:
Method, executed by an automotive control unit, for determining an egress route for a vehicle to a target off-ramp of an at least partially controlled-access multilane highway, comprising:
obtaining map data regarding the at least partially controlled-access multilane highway, the map data being arranged in a plurality of links, each link defining for a corresponding section of the at least partially controlled-access multilane highway a geographic position, wherein at least a subset of the plurality of links includes at least one of a lane number and lane relationship information;
generating an egress route graph based on the map data and the target off-ramp, the egress route graph comprising a plurality of egress route nodes and a plurality of egress route edges, wherein:
the plurality of egress route edges includes lane direction edges based on the lane numbers and the lane relationship information of the plurality of links and lane change edges corresponding to lane changes between lanes of the at least partially controlled-access multilane highway, and
each egress route node of the plurality of egress route nodes defines a start and an end of the lane direction edges based on the geographic positions of the plurality of links;
characterized in that the method further comprises:
assigning to each egress route edge a confidence value indicative of an existence probability of each egress route edge and a cost value indicative of the cost of traversing each egress route edge; and
determining the egress route, the egress route corresponding to a path through the egress route graph to the target off-ramp having an optimized total confidence value and an optimized total cost value.