EP-4738305-A1 - A METHOD, APPARATUS, AND COMPUTER-READABLE MEDIUM FOR TRAJECTORY SELECTION IN AUTONOMOUS NAVIGATION

EP4738305A1EP 4738305 A1EP4738305 A1EP 4738305A1EP-4738305-A1

Abstract

Embodiments of the present disclosure relate to methods for autonomous navigation. A computer program, a computer-readable data carrier and an apparatus are also disclosed. The method for autonomous navigation comprising: obtaining, from a multimodal predictor, one or more candidate trajectories for traffic participants; obtaining, using reachability analysis, respective candidate navigation corridors for each candidate trajectory; obtaining, for each candidate trajectory, a cumulated area of each of the respective candidate navigation corridors; classifying, for each candidate trajectory, a candidate navigation corridor having a greatest cumulated area as relevant corridor, thereby obtaining a class of relevant corridors; obtaining an overlap score between each pair of the relevant corridors in the class of relevant corridors; determining that at least one obtained overlap score, corresponding to at least one pair of the relevant corridors, exceeds a predetermined threshold; replacing, in the class of relevant corridors, each pair of the at least one pair of the relevant corridors with an intersection of said each pair, thereby obtaining an updated class of relevant corridors; and using, by a branch model predictive control, BMPC, the updated class of relevant corridors for generating a predicted trajectory and control commands to an autonomous system.

Inventors

Bouzidi, Mohamed-Khalil
Dr. Reichardt, Jörg

Assignees

AUMOVIO Germany GmbH

Dates

Publication Date: 20260506
Application Date: 20241129

Claims (13)

A method for autonomous navigation comprising: obtaining (110), from a multimodal predictor, one or more candidate trajectories for traffic participants; obtaining (120), using reachability analysis, respective candidate navigation corridors for each candidate trajectory; obtaining (130), for each candidate trajectory, a cumulated area of each of the respective candidate navigation corridors; classifying (140), for each candidate trajectory, a candidate navigation corridor having a greatest cumulated area as relevant corridor, thereby obtaining a class of relevant corridors; obtaining (150) an overlap score between each pair of the relevant corridors in the class of relevant corridors; determining (160) that at least one obtained overlap score, corresponding to at least one pair of the relevant corridors, exceeds a predetermined threshold; replacing (170), in the class of relevant corridors, each pair of the at least one pair of the relevant corridors with an intersection of said each pair, thereby obtaining an updated class of relevant corridors; and using (180), by a branch model predictive control, BMPC, the updated class of relevant corridors for generating a predicted trajectory and control commands to an autonomous system.
The method of any previous claim, wherein the reachability analysis comprises: for each candidate trajectory: obtaining, at each control interval, a reachable set using reachability analysis, wherein the reachable set represents a set of possible states of the autonomous system, said states including at least one of positions and velocities, wherein the control interval represents a time between successive control commands of the BMPC; approximating, at each control interval, said reachable set using zonotopes, thereby obtaining a zonotope approximation of said reachable set, wherein the zonotopes provide a simplified representation of the reachable set; and applying, at each control interval, a Minkowski sum to the zonotope approximation, thereby obtaining a forward reachable set representing a candidate navigation corridor of a traffic participant, wherein the forward reachable set represents a set of possible states the autonomous system can reach over several control intervals.
The method of claims 1 or 2, wherein obtaining an overlap score between each pair of the relevant corridors in the class of relevant corridors comprises obtaining, for each pair of the relevant corridors, an intersection over union, IoU, value representing said overlap score.
The method of any previous claim, wherein obtaining an overlap score between each pair of the relevant corridors in the class of relevant corridors comprises: for each pair of the relevant corridors: obtaining, at each control interval, an intersection over union, IoU, value between respective two zonotope approximations of the pair of relevant corridors, wherein the control interval represents a time between successive control commands of the BMPC; and multiplying the IoU values obtained at all control intervals across a control time horizon, thereby obtaining a multiplication value that represents the overlap score of the pair of relevant corridors, wherein the control time horizon represents a total duration over which the predicted trajectory of the BMPC is planned.
The method of any previous claim, wherein using, by the BMPC, the updated class of relevant corridors for controlling an autonomous system comprises translating the corridors of the updated class of relevant corridors into convex constraints for the BMPC.
The method of claim 5, wherein translating the corridors of the updated class of relevant corridors into convex constraints for the BMPC comprises: expressing a lateral boundary and a longitudinal boundary of each corridor, of the updated class of relevant corridors, in Frenet coordinates, for obtaining simplified lateral and longitudinal boundaries; converting the simplified longitudinal boundary into a first inequality constraint for longitudinal progress; converting the simplified lateral boundary into a second inequality constraint for lateral deviation; and including the first and second inequality constraints in a BMPC optimization problem.
The method of claim 6, wherein expressing a lateral boundary and a longitudinal boundary of each corridor in Frenet coordinates comprises assuming that all lanes along each corridor, of the updated class of relevant corridors, are parallel.
The method of claim 6 or 7, wherein converting the simplified longitudinal boundary into the first inequality constraint for longitudinal progress comprises, for each control interval: obtaining a longitudinal progress that tracks the autonomous system's position along a reference path; and defining a minimum and maximum allowable progress, for the longitudinal progress, within the simplified longitudinal boundary, thereby obtaining the inequality constraint for the longitudinal boundary.
The method of claims 6 or 7, wherein converting the simplified longitudinal boundary into the first inequality constraint for longitudinal progress comprises, for each control interval: obtaining a first normal vector for a reference point associated with a minimum allowable longitudinal progress along a predefined reference path of the autonomous system, wherein the minimum allowable longitudinal progress is within the simplified longitudinal boundary; obtaining a second normal vector for a reference point associated with a maximum allowable longitudinal progress along the predefined reference path of the autonomous system, wherein the maximum allowable longitudinal progress is within the simplified longitudinal boundary; and computing a minimum progress constraint based on the first normal vector, and a maximum progress constraint based on the second normal vector, thereby obtaining the inequality constraint for the longitudinal boundary.
The method of claims 6 or 7, wherein converting the simplified lateral boundary into the second inequality constraint for lateral deviation comprises, for each control interval: obtaining a normal vector for a reference point along a predefined reference path of the autonomous system; obtaining the lateral deviation as a perpendicular distance from the autonomous system's current position to the reference point; setting bounds for the lateral deviation in terms of the normal vector, thereby obtaining the inequality constraint for the lateral boundary.
A computer program comprising instructions which, when the computer program is executed by a computer, cause the computer to carry out a method of any one of the preceding claims.
A computer-readable data carrier having stored thereon the computer program of claim 11.
An apparatus (400) comprising: one or more interfaces (410) for communication; a memory (430); and a data processing circuit (420) configured to carry out the method of any one of claims 1 to 10.

Description

The present disclosure relates to autonomous navigation. In particular, the present disclosure relates to reachability-based trajectory selection for branch model predictive control used for autonomous driving. In the context of autonomous driving, the prediction of future behavior of traffic participants (such as pedestrians, cyclists, and other vehicles) is loaded with uncertainty. This uncertainty stems from the fact that traffic participants (TPs) exhibit a wide variety of potential behaviors in any given scenario, influenced by various factors such as road conditions, traffic rules, driver intent, and environmental stimuli. As such, it is crucial for autonomous vehicles to be able to predict and adapt to these potential behaviors in real-time, ensuring safe navigation within dynamic traffic environments. Traditional trajectory prediction models have primarily relied on single-mode predictions, which assume a single, deterministic future path for each traffic participant. However, this approach fails to capture the inherent multimodal nature of real-world driving scenarios, where a traffic participant may follow multiple potential trajectories depending on contextual variables. To address this limitation, state-of-the-art trajectory predictors now generate multimodal predictions, considering a range of possible future behaviors. These predictions are typically probabilistic in nature, encompassing several potential modes that reflect different possible outcomes. In parallel with trajectory prediction, motion planning is a critical component of autonomous driving systems. Motion planners, such as the Branch Model Predictive Control (BMPC), are responsible for determining the optimal trajectory for the vehicle, considering the predicted trajectories of surrounding traffic participants, as well as the vehicle's own motion capabilities and safety constraints. However, for the motion planner to ensure safety and comfort, it must account for the full range of potential outcomes, including all possible deviations in the predicted trajectories of other traffic participants. In the context of autonomous driving, the prediction of traffic participant behavior is inherently multimodal, meaning that for any given situation, multiple potential outcomes may exist. These outcomes, also referred to as modes of traffic participant behavior, must be considered by the motion planner in order to ensure safe and efficient operation of the autonomous vehicle. A common approach for modeling these uncertainties is through the use of a BMPC comprising a scenario tree, which represents the different possible futures of all traffic participants within a given timeframe. Each branch of the scenario tree corresponds to a potential outcome, and the branches are generated based on the predicted behavior (e.g. trajectories) of each traffic participant. However, as the number of traffic participants increases, the size of the scenario tree grows exponentially, as the number of possible combinations of traffic participant behaviors (e.g. predicted trajectories) increases. This exponential growth leads to a significant increase in the computational complexity of solving the BMPC optimization problem. As the size of the tree expands, the time required to solve the optimization problem increases, making real-time applications of the BMPC increasingly infeasible. Therefore, it becomes essential to implement pruning techniques to reduce the size of the scenario tree while still maintaining safety and reliability. Due to the computational limitations inherent in BMPC, it is common practice to set a threshold that ignores low-probability scenarios (e.g., those with a probability of occurrence below a certain value, such as 5%). While this approach can help reduce the size of the scenario tree and improve computational efficiency, it may introduce significant safety risks. This is because even low-probability events, when aggregated across multiple TPs, could represent a non-negligible risk. For example, if 5% of participants are predicted to choose a particular action in a given situation, neglecting those scenarios might omit critical outcomes, potentially overlooking dangerous behaviors such as unexpected lane changes, sudden braking, or other rare but high-risk actions. Ignoring such probabilities may therefore lead to an unsafe trajectory planning, as the vehicle may fail to account for rare but hazardous events that could otherwise result in collisions or other dangerous situations. Accordingly, the limitations of current planning and control methods for autonomous driving comprise several key challenges. Restricting the scenario tree by pruning low-probability scenarios can lead to uncomfortable or dangerous driving if previously unconsidered scenarios suddenly materialize, potentially resulting in unexpected maneuvers or collisions. Additionally, capturing all possible outcomes of uncertainty within the scenario tree is not computationa