WO2022100835A1

WO2022100835A1 - Computing system and method for trajectory planning in a simulation road driving environment

Info

Publication number: WO2022100835A1
Application number: PCT/EP2020/081899
Authority: WO
Inventors: Imre PALIK
Original assignee: Automotive Artificial Intelligence AAI GmbH
Current assignee: Automotive Artificial Intelligence AAI GmbH
Priority date: 2020-11-12
Filing date: 2020-11-12
Publication date: 2022-05-19
Anticipated expiration: 2023-05-12
Also published as: DE112020007765T5

Abstract

The present invention relates to a computer-implemented method adapted for planning trajectories of two or more simulated vehicles in a simulation road-driving environment, and a computing system adapted for simulating a road-driving environment for two or more road vehicles.

Description

Automotive Artificial Intelligence (AAI) GmbH, Berlin, Germany

COMPUTING SYSTEM AND METHOD FOR TRAJECTORY PLANNING IN A SIMULATION ROAD DRIVING ENVIRONMENT

TECHNICAL FIELD:

The present invention relates to a computer-implemented method for planning trajectories of two or more simulated vehicles in a simulation road-driving environment, and a computing system adapted for simulating a road-driving environment for two or more road vehicles.

PRIOR ART:

Human driving decisions on roads can essentially be considered to comprise several abstract levels or phases forming a driving stack. Based on a particular road situation, a driver may decide to carry out a particular high-level maneuver e.g. overtake and formulate a motion plan accordingly and apply control functions on actuators (throttle, brake, steer) to execute the decision.

With this invention, we are trying to attack parts of the motion-planning problem in the context of simulated traffic. The problem of simulating traffic is different from trajectory planning for self-driving vehicles because it has different engineering constraints as follows:

Limited computational Resources: In a simulated road-driving environment, trajectories of hundreds of vehicles (traffic agents) are simulated at high real-time factor. The computational resources available for planning trajectories of simulated vehicles are, however, only a fraction of what is available for available for planning trajectories of self- driving vehicles. An increase of the computational resources is technically and economically challenging.

Dependence on Map: In a simulated road-driving environment the map, which comprises the road data including data on one or more lanes and lane boundaries, is the only source of truth. In contrast to self-driving cars, map issues, i.e. deficiencies in road data, cannot be corrected via sensor inputs in simulated road driving environments and thus lead to a higher dependency on the quality of the map data. At the same time, it is apparent that users of simulation environments tend to use maps with lower quality data (possibly constructed maps) for simulated road driving environments in comparison to trajectory planning for real-life level 4 (L4) autonomous vehicles. Due to the higher dependency on the quality of the map data in simulated driving environments, a decrease in quality has a negative impact on the planned trajectories.

Agent variability: In order to provide a realistic traffic simulation the generated trajectories should be unique, i.e., the trajectory planning system should provide different trajectories for the same initial conditions, and thus provide sufficient agent variability.

To be able to fit within the performance requirement of the problem, it is possible to divide the motion-planning problem into the following three sub-problems:

1. Path planning: i.e., planning the path of the simulated autonomous vehicle between its current position, and some position it wants to reach in the future.

2. Longitudinal motion planning: i.e., motion planning restricted to the planned path.

3. Path evaluation: i.e., checking if the generated path is still suitable for the given traffic situation.

From these three sub-problems the path planning problem is the most computationally intensive. Therefore, we would like to execute it relatively rarely. While the other two problems can be dealt with in an efficient way. Thus, they can be reevaluated at the decision frequency of the agent.

Splines have been frequently used in robotics for path planning of mobile robots. They are also applicable for trajectory planning for autonomous vehicles. The problem of path planning consists of constructing a naturally parametrized curve, that satisfies the initial and terminal conditions. Together with other requirements, such as keeping within the lane boundaries. At present, in particular a center-line based approach is used to plan a trajectory. Such a center-line based approach, however, does not always provide realistic trajectories. Furthermore, in case the quality of map data is decreased and/or at joining points of lanes, the center-line based approach may lead to degenerated trajectories. In addition, the center-line based approach may lead to physically unreasonable driving characteristics, such as high lateral acceleration and/or high jerk.

These issues may be in part attended by adding various constraints on the curve generation (see e.g., the work of Hiroyuki Kano and Hiroyuki Fujioka. “Spline trajectory planning for path with piecewise linear boundaries.” In 9th EUROSIM Congress on Modelling and Simulation, Oulu, Finland, 12-16 September 2016, pages 434-445. Linkdping University Electronic Press, 122018). The approach followed by Hiroyuki Kano and Hiroyuki Fujioka results in lots of constraints on a real-world highway map. This means, solving the constraint satisfaction problem would not be computationally feasible, and the resulting spline would have lots of control points, and thus high memory footprint. Moreover, the usefulness of all those constraints still depends on the quality of the map used. Accordingly, such a curve generation would still not be computationally feasible in the context of trajectory panning for traffic simulation in a simulation road-driving environment and would not allow for randomized behaviour of the traffic agents.

Thus, there exists a need in providing an improved computing system and method for trajectory planning of two or more simulated vehicles in a simulation road driving environment, wherein the method is computationally feasible for simulated vehicles, is less sensitive for map qualities and is suitable to provide different trajectories for the same initial conditions, and thus provide sufficient agent variability and behavioral control for a realistic traffic simulation.

BRIEF DESCRIPTION OF THE INVENTION:

The aforementioned need is attended to at least in part by means of the claimed inventive subject matter. Advantages (preferred embodiments) are set out in the detailed description hereinafter and/or the accompanying figures as well as in the dependent claims.

Accordingly, a first aspect of this invention relates to a computer-implemented method for planning trajectories of two or more simulated vehicles in a simulation road- driving environment with one or more lanes per road respectively having smooth lane boundaries, characterized in that the method comprises or consists of the following steps: a) Providing a driving stack comprising map data of the simulation road driving environment comprising data to perform the following functions: i. For any point on the map a lane-based s-coordinate value can be determined, ii. For any s-coordinate value the map provides corresponding lane boundary points, iii. Lanes can be traversed by s-coordinate, and iv. For any lane, at a given s-coordinate, its neighboring lanes can be determined, b) Subsampling the map data of step a), determining an estimate road curvature based on the subsampled data and calculating lateral acceleration of each of the respective simulated vehicles based on subsampled map data and the estimated road curvature, and c) Planning trajectories for each of the simulated vehicle in the simulation road driving environment respectively based on the data of step b) using a splinebased trajectory generation method, wherein the planned trajectories of each simulated vehicle respectively represent a curvature comprised of one or more subsection trajectories curves, wherein in case of two or more subsection trajectory curves the subsequent subsection curves are respectively joined together.

A second aspect of this invention relates to a computing system for simulating a road driving environment in driving situations for two or more simulated vehicles comprising or consisting of one or more processors, a memory device coupled to the one or more processors, one or more neural networks for decision making in simulated driving situations, characterized in that the processor is adapted to perform the inventive trajectory planning method steps. A third aspect of the invention relates to a computer program product comprising instructions which, when the program is executed by a computer, cause the computer to carry out the inventive trajectory planning method steps.

A fourth aspect of this invention relates to a computer-readable data carrier having stored thereon the inventive computer program product.

A fifth aspect of this invention relates to an autonomous vehicle computing system interacting with the autonomous vehicle trained in the inventive computing system for simulating a road driving environment in driving situations for two or more simulated vehicles according to the second inventive aspect.

The inventive aspects of the present invention as disclosed hereinbefore can comprise any possible (sub-)combination of the preferred inventive embodiments as set out in the dependent claims or as disclosed in the following detailed description and/or in the accompanying figures, provided the resulting combination of features is reasonable to a person skilled in the art.

BRIEF DESCRIPTION OF THE DRAWINGS:

Further characteristics and advantages of the present invention will ensue from the accompanying drawings, wherein

Fig. 1 shows a flow chart characterizing an embodiment of the inventive trajectory planning method.

Figs. 2a) and 2b) show schematic lane boundaries, wherein Fig. 2a) shows smooth lane boundaries and Fig. 2b) shows non-smooth lane boundaries.

Fig. 3 shows schematic noisy lane boundaries.

Fig. 4 shows schematic lane boundaries (continuous line) and their piece-wise linear approximation of the lane boundary after subsampling (dashed line).

DETAILED DESCRIPTION OF THE INVENTION:

As set out in more detail hereinafter, the inventor of the different aspects of this invention has found out that the computer-implemented systems and methods according to the present invention enable trajectory planning of two or more simulated vehicles in a simulation road driving environment, which is computationally feasible for two or more simulated vehicles, is less sensitive with respect to map qualities and is able to provide different trajectories for the same initial conditions, and thus provides sufficient agent variability and behavioral control for a realistic traffic simulation.

As the feasibility of a planned trajectory is dependent on the traffic around the given simulated vehicles in the simulation environment, the present invention facilitates revising the trajectory at any time point, wherein the newly planned trajectory of the respectively simulated vehicle represents a smooth continuation of the used portion of the previous planned trajectory of the respective simulated vehicle. In particular, the present inventive trajectory planning method aims to continue with the velocity, acceleration and jerk of the respectively simulated vehicle traversing the curve.

In the context of the present invention, the expression “an additionally or alternatively preferred embodiment’ or “an additionally or alternatively further preferred embodiment’ or “an additional or alternative way of configuring this embodiment’ means that the feature or feature combination disclosed in this preferred embodiment can be combined in addition to or alternatively to the features of the inventive subject matter including any preferred embodiment of each of the inventive aspects, provided the resulting feature combination is reasonable to a person skilled in the art.

Further, in the context of the present invention, the expressions “comprising" or “containing" shall be understood to have a broad meaning similar to the term “including" and will be understood to imply the inclusion of a stated integer or step or group of integers or steps but not the exclusion of any other integer or step or group of integers or steps. This definition also applies to variations on the term “comprising" such as “comprise" and “comprises" as well as variations on the term “containing" such as “contain" and “contains".

Moreover, in the context of the present invention, the expression “configured’ shall be understood as in connection with systems and computer program components. For a system of one or more computers to be configured to perform particular operations or actions, it means that the system has installed on it software, firmware, hardware, or a combination of them that in operation cause the system to perform operations or actions. For one or more computer programs to be configured to perform particular operations or actions means that the one or more programs include instructions that, when executed by a data processing apparatus, cause the apparatus to perform the operations or actions.

In addition, in the context of the present invention, the expression “trajectory” or “trajectories" relates to the path of the simulated vehicle or the two or more simulated vehicles respectively in motion on the simulated road as a function of time. The expression “subsection trajectory” refers to the planned or in other words generated part of the trajectory, which spans the suitable planning I generation time. According to one preferred embodiment, the suitable planning I generation time is 8 seconds and the subsection trajectory, thus, covers the path, which the respective simulated vehicle traverses in this time. The subsection trajectory is generally regenerated prior to the end of the subsection trajectory and the subsequent subsection trajectories are joined with suitable methods, preferably joined smoothly.

Further, in the context of the present invention, the expression “smooth lane" or “smooth lane boundary” or “smoothness of the lane boundary” means that subsampling the map data will provide a good approximation of the real world lane boundary, such as represented in Figure 2a) and no real-world jumps are expected in the lane boundary, such as represented in Figure 2b). Accordingly, certain traffic lanes within cities exhibiting abrupt changes are not covered by the trajectory planning method of the present invention.

To achieve the inventive subject matter, advantages and objects thereof, the present invention as disclosed in this application is directed to systems and methods that make use of computer hardware and software to plan trajectories of two or more simulated vehicles in a simulation environment respectively using reinforcement learning algorithms and techniques. The “simulated vehicle" (in the context of the present invention synonymously called “traffic agent’ or “virtual traffic agent’) can for example be a car, truck, bus, bike or motorbike. The simulated vehicles exhibiting the inventively planned trajectories in the simulation environment may in particular be advantageous, as they may interact, cooperate with and challenge an autonomous vehicle system controlling an autonomous vehicle under test.

Thus, the inventive systems and methods furthermore have the technical effect and benefit of providing an improvement to autonomous vehicle computing technology, in case the autonomous vehicle is trained in the inventive simulation environment exhibiting the inventively planned trajectories.

According to the first aspect of the present invention, a computer-implemented method for planning trajectories of two or more simulated vehicles in a simulation roaddriving environment with one or more lanes per road respectively having smooth lane boundaries is provided. As already set out above, lanes exhibiting abrupt changes are not intended to be covered by the inventive trajectory planning method. Preferably, the lanes exhibiting smooth lane boundaries relate to highway lanes more preferably exhibiting no junctions. In case of junctions are comprised in the lane, route planning methods in particular providing geometry feedback for rout planning have to be incorporated into the inventive trajectory planning method.

The inventive method comprises or consists of the following steps:

Step a): A driving stack comprising map data of the simulation road-driving environment is provided comprising data to perform the following functions: i. For any point on the map a lane-based s-coordinate value can be determined, ii. For any s-coordinate value the map provides corresponding lane boundary points, iii. Lanes can be traversed by s-coordinate, and iv. For any lane, at a given s-coordinate, its neighboring lanes can be determined.

In other words, the map may be regarded to represent an oracle performing the above functions. According to the present invention, it is accepted that this oracle can provide erroneous answers.

The inventive trajectory planning method (alternatively called “trajectory planner”) is preferably plugged into the driving stack of a simulator system and uses a map interface provided by the simulator to get map data information, preferably from ODR formatted map files of roads, preferably highways, such as ODR sample file for KA Sudtangente (German part of a highway) provided by Atlatec. According to an additionally or alternatively preferred embodiment of the present invention, ODR map files are used, which provide one or more, preferably all of the following functions comprising or consisting of:

• Get the start and end s coordinates for any lane segment,

• Get the left and right lane boundary points from a lane segment identifier and a valid s coordinate on the lane segment,

• Get the neighboring lane segment’s identifier from a lane segment identifier, and

• traverse lane segments in driving direction.

According to an additionally or alternatively preferred embodiment of the present invention the driving stack provides one or more, preferably all of the following input parameters for trajectory planning comprising or consisting of:

• vehicle position (both map coordinate, and road-based coordinate),

• vehicle velocity,

• preferred maximum lateral acceleration,

• vehicle size, and

• action (continue lane, change left, change right).

According to an additionally or alternatively preferred embodiment of the present invention, the inventive method is conducted within a computational traffic simulator according to the second aspect of the present invention.

Step b): Subsampling the map data of step a), determining an estimate road curvature based on the subsampled data and calculating lateral acceleration of each of the respective simulated vehicles based on subsampled map data and the estimated road curvature. According to the present invention, the map data is subsampled both to decrease computational load and to average out mapping errors. The lateral acceleration based estimation is advantageous in order to increase the subsampling density around curves. It is assumed in the context of the present invention that the simulated vehicles will slow down when approaching steep curves. According to an additionally or alternatively preferred embodiment of the present invention, the map data is subsampled based on an estimated speed of a respective simulated vehicle and calculating a distance of a respectively simulated vehicle based on the estimated speed and a suitable time, preferably 1 second, and using this calculated distance as an s-value distance for subsampling the map boundaries.

According to an additionally or alternatively preferred embodiment of the present invention, the reference speed of this respective simulated vehicle is modified and step b) is performed again, in case the calculated lateral acceleration of a respectively simulated vehicle is outside a predetermined threshold value. Sensible threshold values for allowed lateral acceleration can generally be derived from measuring human driving behaviour. In other words, in case the calculated lateral acceleration of a respectively simulated vehicle is too high, namely above 10 m/s², in particular above 1.5 m/s² for motorbikes and buses, above 2 m/s² for lorries I trucks and above 3.5 m/s² for passenger cars, the reference speed is adjusted, preferably reduced, and the features of method step b) are again conducted. Such an adjustment of reference speed and repetition of features of method step b) is conducted as long as necessary in order to calculate a suitable lateral acceleration of a respective simulated vehicle.

Step c): Planning trajectories for each of the simulated vehicle in the simulation road driving environment respectively based on the data of step b) using a spline-based trajectory generation method, wherein the planned trajectories of each simulated vehicle respectively represent a curvature comprised of one or more subsection trajectories curves, wherein in case of two or more subsection trajectory curves the subsequent subsection curves are respectively joined together.

The trajectory planning problem is generally to be regarded PSPACE, in particular a PSPACE-hard decision problem (BMSDE: Brian Paden, Michal Cap, Sze Zheng Yong, Dmitry Yershov, and Emilio Frazzoli, A Survey of Motion Planning and Control Techniques for Self-driving Urban Vehicles, 2016).

According to an additionally or alternatively preferred embodiment of the present invention, the subsequent subsection curves are respectively joined together exhibiting a smooth continuation. According to an additionally or alternatively preferred embodiment of the present invention, wherein further in step c) a centerline of each lane comprising a simulated vehicle is respectively derived from the data and an estimate direction of the respective lanes, in particular including every relevant point for calculation purposes, is respectively determined based on its derived centerline.

According to an additionally or alternatively preferred embodiment of the present invention, a constraint satisfaction problem method is used in step c) to set up suitable constraints, wherein the constraint satisfaction problem generally uses either linear constraints or non-linear constraints. The use of linear constraints when specifying the trajectory seems to be more computationally feasible in comparison to non-linear constraints. Linear constraint satisfaction problems can be solved efficiently with existing solvers, e.g. COIN-OR Linear Program code, in short: Clp (John Forrest, et al., COIN-OR Clp, https://www.coin-or.org/Clp/userguide/). Linear constraints, however, cannot express G² or higher continuity. This means, lateral acceleration, and jerk cannot be directly constrained, they need to be kept within reasonable bounds through the second-order effects of some linear constraints.

The map data is subsampled in step b) of the inventive method in order to avoid a drastic increase of the number of constraints.

According to an additionally or alternatively preferred embodiment of the present invention, simplifications can be made noticing that real-world trajectories tend not to be too wiggly, thus, the number of control points can also be drastically reduced. Accordingly, the present invention comprises one or more of the following simplifications on the trajectory planning method:

• The trajectory length as measured by the change of the s-coordinate is limited to what can be traversed by the vehicle in 8 seconds. This might sound long from the autonomous driving point of view, but the present invention is trying to avoid recalculating the trajectory as long as it is possible in order to improve the computational feasibility.

• Cubic splines are used with 11 control points, and with uniform knot placements. Such an embodiment, however, results in splines with G² continuity. (Do no direct constraints on Jerk.) • Lane boundary constraints are only used at seven uniformly placed points along the trajectory. (In line with the constraints on the spline used.)

• Direction constraints are used to keep the trajectory within lane bounds. The direction constraints can be derived from the sub-sampled boundary point pairs.

These simplifications are roughly consistent with human driving behaviour (see Christopher J. Nash et al, “A review of human sensory dynamics for application to models of driver steering and speed control”, Biol Cybern. 2016, 110: 91 -116), in the sense, that the trajectory is planned based on points roughly 1 second apart.

To provide variability with the trajectory generated, and to avoid numerical instability issues, the present invention aims to find the Chebyshev-centre of the constraint polyhedron (see e.g., CO-2009: Stephen Boyd and Lieven Vandenberghe, Convex Optimization, 2004 Cambrige University Press). Then the trajectory can be generated by random sampling from the inscribed Chebyshev-ball. Finding the Chebyshev-centre is also advantageous, as it provided a better behaving trajectory, then an edge point of the constraint polygon.

According to an additionally or alternatively preferred embodiment of the present invention, in step c) each subsection trajectory curve of a respectively simulated vehicle i. has an initial starting point of the respectively simulated vehicle, which relates to the initial state of the simulated vehicle in the respective subsection trajectory, and has a final point in the respective subsection trajectory curve, which is randomly set and which may optionally be constrained by one or more behavioral constraints, and/or ii. has a length as measured by the change of the s-coordinate, which is limited to what can be safely traversed by the respective simulated vehicle in integer numbers of seconds, preferably wherein the length is 8 seconds or less, and/or iii. is regenerated when the respectively simulated vehicle is 1 second away from the end of the curve as measured in step ii), or when behavioral changes of the simulated vehicle requires it, and/or iv. uses a cubic, or higher order spline with uniform knot placements, wherein the number of control points are equal to the number of seconds it takes for the respectively simulated vehicle to traverse the curve plus the order of the spline, and/or v. uses lane boundary constraints at uniformly placed points along the planned subsection trajectory curve of a respectively simulated vehicle, preferably one lane boundary constraint for each second, and/or vi. uses one or more direction constraints to keep the planned respective subsection trajectory within the respective lane boundary, wherein the direction constraints are preferably derived from sub-sampled lane boundary constraints.

According to an additionally or alternatively preferred embodiment of the present invention, the length of the respective subsection trajectory is initially estimated as a function of speed of the simulated vehicle at its initial starting point of the subsection trajectory and as a function of the lane curvature as well as the allowed lateral acceleration of the respective simulated vehicle in the subsection trajectory.

According to an additionally or alternatively preferred embodiment of the present invention, in step c) the uniform knot placement, the subsampled boundary points are utilized as gate constraints, wherein the following four constraints are derived from the subsampled points: v_d - c_d >e_t |7_d|

v_d - C_d < 8 v_d - C_d > -8 wherein v_d represents the vector difference of the right and the left boundary point, c_d represents the vector difference of the spline at the corresponding knot value and the left boundary point,

8 represents the fuzz factor, that is proportional (but much slower) to s_p, the s cordinate difference between two sampling points, and v_d represents the unit vector perpendicular to v_d. According to an additionally or alternatively preferred embodiment of the present invention, in step c) the one or more direction constraints are respectively defined within a fixed range around an angle calculated as piece-wise linear approximation of the center line, with one node at the mid-point of the respective gates, wherein preferably the direction constraints are extended along the derivative spline as piece-wise-linear lane boundary constraints.

According to an additionally or alternatively preferred embodiment of the present invention, wherein in case a linear constraint satisfactory method is used, each subsection trajectory curve and subsequent subsection trajectory curve of a respective simulated vehicle forming a curvature are joined at G¹ continuity. In addition to this, if the curvature at the discontinuity is sufficiently far from 0 (> 10^-4 in one implementation), then the sign of the curvature is fixed by a constraint at the two sides of the discontinuity. In other words, the sign of the curvature is kept if the derivative is > 0, preferably the sign function has a discontinuity > 10^-4.

According to an additionally or alternatively preferred embodiment of the present invention, wherein in case a linear constraint satisfactory method is used, one or more road curvature constraints are put on the sign of the curvature at the respective gate points of the subsection trajectory curve and preferably at the derivative of the subsection trajectory curve, wherein the one or more road curvature constraints are only used if a change of the reference heading between two neighboring gates is greater or equal than the fuzz angle used for determining the direction constraints, with the proviso that at the end point of the subsection trajectory curve and there, where only a single neighboring gate exists, no road curvature constraint is used.

According to an additionally or alternatively preferred embodiment of the present invention, wherein in case a non-linear constraint satisfactory method is used, each subsection trajectory curve and subsequent subsection trajectory curve of a respective simulated vehicle forming a curvature have a G² or G³ continuity.

According to an additionally or alternatively preferred embodiment of the present invention, wherein in case a non-linear constraint satisfactory method is used, the curvature is constrained directly to be close to the road curvature, and to be within the curvature tolerance of the respectively simulated vehicle. According to an additionally or alternatively preferred embodiment of the present invention, wherein the planned trajectories of step c) comprise at least one lane change subsection trajectory, wherein the gate constraints of the respective lane change subsection trajectory cover at least two lanes, the starting point of the subsection lane change trajectory curve is predetermined in one origin lane and the end point of the subsection trajectory curve is predetermined in another target lane, and wherein preferably the urgency of the lane change is predetermined between 2 seconds and 8 seconds in a lane change request, wherein preferably the fuzz factor is added only to the side of the direction constraint pointing toward the target lane.

All features and embodiments disclosed with respect to the first aspect of the present invention are combinable alone or in (sub-)combination with any one of the second to fifth aspects of the present invention including each of the preferred embodiments thereof, provided the resulting combination of features is reasonable to a person skilled in the art.

According to the second aspect of the present invention, the invention provides a computing system for simulating a road driving environment in driving situations for two or more simulated vehicles comprising or consisting of one or more processors, a memory device coupled to the one or more processors, one or more neural networks for decision making in simulated driving situations, characterized in that the processor is adapted to perform the trajectory planning method steps according to the first inventive aspect.

The inventive computing system for simulating a road driving environment (simulator system) preferably exhibits a driving stack into with the inventive trajectory planning map is plugged into and uses a map interference in order to retrieve the map data information, preferably from ODR formatted map files of roads, preferably highways, such as ODR sample file for KA Sudtangente (German part of a highway) provided by Atlatec.

According to the third aspect of the present invention, the invention provides a computer program product comprising instructions which, when the program is executed by a computer, cause the computer to carry out the trajectory planning method steps of the first inventive aspect. According to the fourth aspect of the present invention, the invention provides a computer-readable data carrier having stored thereon the computer program product of the third inventive aspect.

According to the fifth aspect of the present invention, the invention provides an autonomous vehicle computing system interacting with the autonomous vehicle trained in the computing system for simulating a road-driving environment in driving situations for two or more simulated vehicles according to the second inventive aspect.

The present invention is described in the following based on exemplary embodiments, which merely serve as examples and which shall not limit the scope of the present protective right.

DETAILED DESCRIPTION OF FIGURES

Further characteristics and advantages of the present invention will ensue from the following description of example embodiments of the inventive aspects with reference to the accompanying figures.

All of the features disclosed hereinafter with respect to the example embodiments and I or the accompanying figures can alone or in any sub-combination be combined with features of the two aspects of the present invention including features of preferred embodiments thereof, provided the resulting feature combination is reasonable to a person skilled in the art.

Figure 1 ) shows a flow chart characterizing an embodiment of the inventive trajectory planning method according to the first inventive aspect.

As a first step 110 there is the desire to plan a trajectory automatically using a computer-implemented method for planning trajectories of two or more simulated vehicles in a simulation road-driving environment with one or more smooth lanes per road respectively having smooth lane boundaries.

Accordingly, a driving stack comprising map data of the simulation road driving environment comprising data to perform the following functions is provided in a suitable computer simulation system, preferably comprising a map interface: i. For any point on the map a lane-based s-coordinate value can be determined, ii. For any s-coordinate value the map provides corresponding lane boundary points, iii. Lanes can be traversed by s-coordinate, and iv. For any lane, at a given s-coordinate, its neighboring lanes can be determined.

The driving stack preferably provides one or more, preferably all of the following input parameters for trajectory planning comprising or consisting of:

• vehicle position (both map coordinate, and road-based coordinate),

• vehicle velocity,

• preferred maximum lateral acceleration,

• vehicle size, and

• action (continue lane, change left, change right).

According to step 121 the provided map data of step 110 is subsampled, preferably based on speed.

According to step 122 an estimate road curvature is determined based on the subsampled data.

According to step 123 lateral acceleration of each of the respective simulated vehicles is calculated based on subsampled map data and the estimated road curvature.

According to step 124 the result of the calculation on lateral acceleration is evaluated in step 125 on whether it complies with a suitable value, preferably a predetermined threshold value or whether it exceeds the suitable value, preferably the predetermined threshold value. In case it exceeds the threshold for lateral acceleration of a respective simulated vehicle, the reference speed is modified, preferably reduced in step 126 and steps 121 to 124 are again repeated as often as necessary in order to comply with the predetermined threshold of lateral acceleration.

In case the calculated lateral acceleration complies with the predetermined threshold in step 124, a direction of trajectory is estimated in step 131 based on a derived centerline of the respective simulated vehicle when planning the trajectories for each of the simulated vehicles in the simulation road driving environment using a splinebased trajectory generation method, wherein the planned trajectories of each simulated vehicle respectively represent a curvature comprised of one or more subsection trajectories curves, wherein in case of two or more subsection trajectory curves the subsequent subsection curves are respectively joined together.

According to step 132 suitable constraints are set up, which are discussed in detail below.

According to step 133 a Chebyshev-centre of a resulting constraint polyhedron is determined and solved form the Chebyshev-ball. According to step 134 the subsection trajectory curve is determined by randomizing the whole constraint polyhedron, preferably wherein the subsection trajectory curve is determined by randomized sampling from an inscribed Chebyshev-ball, wherein randomized sampling is preferably conducted in such a way that points closer to the center of the Chebyshev-ball are sampled with a higher probability than points farther away from the Chebyshev-center, preferably wherein the radius of the Chebyshev-ball is maximized.

According to step 140 the trajectory, in particular the subsection trajectory of a respective simulated vehicle is ready to be applied to the simulated vehicle in the simulation environment.

Smoothness of the lane boundary means that subsampling the map data will provide a good approximation of the real world lane boundary, i.e., no real-world jumps are expected in the lane boundary, i.e., any abrupt changes in the lane boundary can be treated as mapping errors.

An abrupt change is a change that can fall between two samples in a way that its presence remains undetectable in the boundary reconstructed from the samples. For example, in Figs. 2a) and 2b), if the lanes are sampled in the way marked by the dotted lines, the boundary glitch of the “non-smooth” lane in Fig. 2b) would completely disappear, and after reconstruction the lanes of Figs. 2a) and 2b) would appear relatively similar. For more information see the section on subsampling. Furthermore, in the real world most of the traffic lanes have smooth boundaries, with the notable exception of certain traffic lanes within cities.

Fig. 3 shows schematic noisy lane boundaries as may be present in view of mapping errors. According to the present invention, the map data is subsampled to get a good smooth approximation and, thus to average out I level out mapping errors.

Fig. 4 shows schematic lane boundaries (continuous line) and their piece-wise linear approximation of the lane boundary after subsampling (dashed line). As it is visible from Fig. 4, doing a piece-wise linear approximation of the lane boundary after subsampling is not really helpful as the resulting piecewise linear curve can be different enough from the lane boundary to potentially lead the trajectory out of the lane, and to disallow useful parts of the lane from the trajectory. To mitigate this issue, the length of the trajectory should correspond to the curviness of the road as further explained below.

EXAMPLE PART

Computational Feasibility

As already set out above, the general path-planning problem is PSPACE-hard. To make the planning computationally feasible, the inventive method is restricted according to the preferred embodiment discussed herein below to linear constraints when specifying the trajectory. Alternatively, the inventive method can use non-linear constraints as discussed hereinbefore.

Linear constraint satisfaction problems can be solved efficiently with existing solvers (e.g., COIN-OR Linear Program code or in short Clp). As linear constraints cannot express G² or higher continuity, lateral acceleration and jerk cannot be directly constrained with this method. According to this embodiment of the inventive method the lateral acceleration and jerk have preferably to be kept within reasonable bounds through the second-order effects of some linear constraints.

Simplifying the Boundary Constraints

The approach followed in “Spline trajectory planning for path with piecewise linear boundaries” can mean many constraints on a real-world map (Hiroyuki Kano and Hiroyuki Fujioka, ibid). This means, solving the constraint satisfaction problem according to this approach would not be computationally feasible, and the resulting spline would have lots of control points, and thus high memory footprint. Moreover, the usefulness of all those constraints are no better than the quality of the map used. In other words, the less the quality of the map, which is generally not as good in simulation environments, the less the usefulness of those constraints.

To avoid the explosion of the number of constraints, the inventive trajectory planning method already sub-samples the map data. Additional simplifications can preferably be made by noticing that real-world trajectories tend not to be too wiggly, thus, the number of control points can also be reduced. Based on this the following simplifications can be conducted within the inventive trajectory planning method, in particular according to the present inventive embodiment:

• The trajectory length as measured by the change of the s-coordinate may preferably be limited to what can be traversed by the vehicle in 8 seconds. This might sound long from the autonomous driving point of view, but using 8 seconds as suitable time, the inventive method, in particular of the present embodiment avoids recalculating the trajectory as long as it is possible and, thus, reduces the computational load.

• Cubic splines preferably uses 11 control points, more preferably with uniform knot placements. The best achievable continuity with such splines is G² continuity. This still does not allow to direct constraints on Jerk.

• Lane boundary constraints are preferably only used at seven uniformly placed points along the trajectory, more preferably in line with the constraints on the spline used.

• Direction constraints are preferably used to keep the planned trajectory within lane bounds. The direction constraints can preferably be derived from the subsampled boundary point pairs.

These simplifications are roughly consistent with human driving behaviour, in the sense, that the trajectory is planned based on points suitably timed apart, preferably about 1 second apart. Trajectory Length

As the lane boundary is effectively sub-sampled according to the inventive trajectory planning method, the planned subsection of trajectory (subsection trajectory) can gloss over some road features, and thus the simulated vehicle can potentially leave its lane (see Fig. 4). To mitigate this risk, the length of the subsection trajectory corresponds according to a preferred embodiment of the inventive method to the curviness of the road. The initial speed of the simulated vehicle can preferably be used according to the inventive method to get an initial length estimate. More preferably, this estimate should be refined by estimating the lane section's curvature. From the determined curvature and from an allowed predetermined lateral acceleration a modified new, preferably lower speed can be derived. Taking into account the above mentioned 8 seconds constraint, this will result in a shorter distance of the planned subsection trajectory.

Sensible values for a suitable lateral acceleration can generally be derived from measuring human driving behaviour. Suitable lateral acceleration is generally 10 m/s² and below, in particular 1.5 m/s² and below for motorbikes and buses, 2 m/s² and below for lorries I trucks and 3.5 m/s² and below for passenger cars.

Building the Linear Program

Some of the physical constraints that the present invention intends to comply with cannot be expressed by linear constraints. Accordingly, the linear constraints of the first inventive aspect are chosen based on various heuristics that intend to limit extreme behaviour. In turn, however, these constraints may in certain cases over or underconstrain the subsection trajectory.

To provide variability with the planned subsection trajectory, and to avoid numerical instability issues, the present invention is preferably aiming to find a Chebyshev-centre of the constraint polyhedron (see e.g., Convex Optimization). Then the subsection trajectory can be generated by random sampling from the inscribed Chebyshev-ball. Finding the Chebyshev-centre is advantageous for the inventive trajectory planning method, as it provides a better behaving subsection trajectory in comparison to an edge point of the constraint polygon. When defining a spline according to the inventive method, the initial and the final point are generally fixed. The initial point comes from the initial state of the simulated vehicle, while the final point can be set randomly, optionally constrained by behavioural constraints. According to the preferred embodiment of the present invention, such a set up provides 18 free variables for the control points, and an additional positive constrained variable for the radius of the Chebyshev-ball.

Requiring G¹ continuity provides an equality constraint according to which the inventive embodiment then has 18 variables all together.

As an objective function, the radius of the Chebyshev-ball is preferably maximized.

Gate Constraints

Specifying gate constraints for the uniform knot placement, i.e., requiring that the spline should be within the gate specified by the two lane-edge points for the corresponding parameter value within the knot vector, could be regarded as a good solution in order to eliminate seven more parameters. However, solving the equality constraints results in a numerically unstable system. Thus, this solution does not seem to be a fruitful approach and, thus, is preferably not used in the inventive method.

According to the present invention, the control point is preferably constrained to a thin rectangle around the line segment. In order to take account of possible incorrectness of the map data, the inventive method preferably provides some room to the solver. According to this preferred embodiment, the inventive method has, thus, four constraints for each of the seven gates.

Direction Constraints

After determining the lane length of the subsection trajectory, the inventive method preferably approximates the lane direction via defining a piece-wise linear approximation of the centre line, more preferably with nodes at the gates. Taking map errors into account, this tends to be a better approximation of the lane direction, then what can directly be derived from the gate.

To avoid over-fitting the inventive approximation, preferably a range around this direction is defined. This embodiment can also be thought as taking the uncertainties of map, steering, and human perception into account. When defining this range, it should be kept in mind that a tight range can end up over-fitting the constraints, while a loose range allows the spline to be too wiggly. Both of these cases can end up providing high lateral acceleration values. Thus, according to a preferred embodiment of the inventive method, the range to be defined is ±3.5° around the calculated angle.

According to a further preferred embodiment, only constraining the direction at the gate is not preferred, as this would still allow the spline to run amok between the gates. Noticing that the direction constraints at the gates effectively provide gate constraints on the derivative spline, the direction constraints are preferably extended along the derivative spline as piece-wise-linear boundary constraint, using the machinery described in Spline trajectory planning for path with piecewise linear boundaries (Hiroyuki Kano and Hiroyuki Fujioka, ibid). This inventive approach has the added benefits of disallowing cusps, loops, or other degenerate cases. Such an inventive preferred embodiment of the trajectory planning method will provide additional two constraints for each segment of the subsection trajectory.

As G¹ continuity only defines the direction, but not the magnitude of the initial derivative, the inventive method preferably still has a positivity constraint at the start of the spline. In addition, the end direction may preferably be kept fuzzy. Such an inventive preferred embodiment of the trajectory planning method will provide the inventive method with two more constraints. So all-together the preferred embodiment of the inventive method exhibits preferably 19 direction related constraints.

Continuity

As G² continuity is not expressible in the form of linear constraints, the inventive method according to the present embodiment uses G¹ continuity, which determines the direction of the tangent of the curve.

In addition to this, the inventive method according to the preferred embodiment can also express the sign of the curvature at the joining point as a linear constraint. The caveat of this approach is that the sign function has a discontinuity at 0. Therefore, the inventive method according to the present embodiment only uses this constraint when the magnitude of the curvature is sufficiently far away from 0, preferably 10’⁴. In line with human driving behaviour, the inventive trajectory planning method preferably does not to wait to regenerate the subsection trajectory until the simulated vehicle reaches the end of the respective subsection trajectory and instead regenerates the respective subsection trajectory when the simulated vehicle passed a suitable length, preferably 7/8^th of the planned subsection trajectory. In other words, as according to the preferred embodiment the time of the subsection trajectory is 8 seconds, the respective subsection trajectory is regenerated after 7/8^th, i.e. after 7 seconds and, thus, 1 second prior to the end of the subsection trajectory.

Curvature Constraints

Similarly, to how the inventive trajectory planning method acts on continuity, the inventive trajectory planning method preferably also puts constraints on the sign of the curvature at the gate points of the curve, so that the direction of the curvature is the same as the curvature of the road. However, here, the issues of the discontinuity of the sign function is made worse by the possible errors in the curvature estimator. So these constraints are only used if the change of the reference heading between the two neighbouring gates are at least 3.5°.

As the heading approximation is the worst at the end point of the curve, and there the inventive trajectory planning method only has a single neighbouring gate, no curvature constraint is preferably used at that point.

Preferably adding these linear constraints on the derivative of the curve helps relaxing the direction constraints according to another embodiment of the inventive method. Without the constraints on the derivatives, the best behaviour was observed at a fuzz factor of 1.5° as opposed to 3.5° with the derivative constraints.

This means, the preferred embodiment of the present invention using the linear program has at least 47 and at most 55 constraints, and 18 variables. Therefore, for linear programming standards it is a tiny problem, and can be solved swiftly with off-the self-solvers.

Lane Changes

With the above-explained procedure, it is possible to generate subsection trajectories that follow a lane. The same approach can easily be extended to provide lane change subsection trajectories. This also provides a nice example of how to encode various behavioural requirements into the constraint.

In order to provide lane change subsection trajectories, the gate constraints are preferably extended to cover two or more lanes. Such a preferred embodiment will provide lane-change-like behaviour, if the start point is in one lane, and the end point is in another lane. However, the behaviour can be unnatural, as the trajectory might enter and leave the target lane several times (so called “running amok”), before settling down there.

In order to provide an upper bound on how fast the lane change will be finished, the urgency of the lane change is according to a preferred embodiment of the present invention defined between 2 and 8, in other words between 2 seconds and 8 seconds. According to this preferred embodiment, starting at the corresponding gate the inventive method restricts the simulated vehicle to the target lane.

To avoid the simulated vehicle leaving and re-entering the target lane before the specified gate, the inventive method preferably uses one-sided direction constraints before reaching the gate specified in the lane change request. In other words, for left change, the inventive method preferably only varies the direction derived from the gate constraints to the left, and for right lane changes to the right. More preferably, the onesided range can be increased as getting closer to the critical gate.

Results

In the following tables we compare the lateral acceleration and lateral jerk of the planned trajectories according to the present invention (see table 1 ) with the lateral acceleration and lateral jerk of planned trajectories according to an alternative planning method not according to the present invention both using the KA-Sudtangente ODR sample map (German part of a highway) provided by Atlatec. Table 1 :

Table 2

As can be seen from the result data, the lateral acceleration and lateral jerk of the planned subsection trajectories from the inventive method exhibit smaller values.

Accordingly, the present invention provides a simulation environment of for a plurality of simulated cars, which is computationally feasible and less sensitive with respect to map qualities, and also provides realistic behaviour at higher probability, sufficient agent variability and behavioural control for displaying a realistic traffic simulation.

Claims

27 Claims:

1. A computer-implemented method for planning trajectories of two or more simulated vehicles in a simulation road driving environment with one or more smooth lanes per road respectively having smooth lane boundaries, characterized in that the method comprises or consists of the following steps: b) Providing a driving stack comprising map data of the simulation road driving environment comprising data to perform the following functions: i. For any point on the map a lane-based s-coordinate value can be determined, ii. For any s-coordinate value the map provides corresponding lane boundary points, iii. Lanes can be traversed by s-coordinate, and iv. For any lane, at a given s-coordinate, its neighboring lanes can be determined, c) Subsampling the map data of step a), determining an estimate road curvature based on the subsampled data and calculating lateral acceleration of each of the respective simulated vehicles based on subsampled map data and the estimated road curvature, and d) Planning trajectories for each of the simulated vehicle in the simulation road driving environment respectively based on the data of step b) using a splinebased trajectory generation method, wherein the planned trajectories of each simulated vehicle respectively represent a curvature comprised of one or more subsection trajectories curves, wherein in case of two or more subsection trajectory curves the subsequent subsection curves are respectively joined together.

2. The method according to claim 1 , wherein in step b) the map data is subsampled based on an estimated speed and calculating a distance of a respectively simulated vehicle based on the estimated speed and a suitable time, preferably 1 second and using this calculated distance as an s-value distance for subsampling the map boundaries.

3. The method according to claim 1 or 2, wherein in step b) in case the calculated lateral acceleration of a respectively simulated vehicle is outside a predetermined tolerance value, the reference speed of this respective simulated vehicle is modified and step b) is performed again.

4. The method according to any one of claims 1 to 3, wherein further in step c) a centerline of each lane comprising a simulated vehicle is respectively derived from the data and an estimate direction of the respective lanes, in particular including every relevant point for calculation purposes, is respectively determined based on its derived centerline

5. The method according to any one of claims 1 to 4, wherein in step c) a constraint satisfaction problem method is used to set up suitable constraints.

6. The method according to claim 5, wherein in step c) a Chebyshev-centre of a resulting constraint polyhedron is determined and the subsection trajectory curve is determined by randomizing the whole constraint polyhedron, preferably wherein the subsection trajectory curve is determined by randomized sampling from an inscribed Chebyshev-ball, wherein randomized sampling is preferably conducted in such a way that points closer to the center of the Chebyshev-ball are sampled with a higher probability than points farther away from the Chebyshev-center, preferably wherein the radius of the Chebyshev-ball is maximized.

7. The method according to any one of claims 1 to 6, wherein in step c) each subsection trajectory curve of a respectively simulated vehicle i. has an initial starting point of the respectively simulated vehicle, which relates to the initial state of the simulated vehicle in the respective subsection trajectory, and has a final point in the respective subsection trajectory curve, which is randomly set and which may optionally be constrained by one or more behavioral constraints, and/or ii. has a length as measured by the change of the s-coordinate, which is limited to what can be safely traversed by the respective simulated vehicle in integer numbers of seconds, preferably wherein the length is 8 seconds or less, and/or iii. is regenerated when the respectively simulated vehicle is 1 second away from the end of the curve as measured in step ii), or when behavioral changes of the simulated vehicle requires it, and/or iv. uses a cubic, or higher order spline with uniform knot placements, wherein the number of control points are equal to the number of seconds it takes for the respectively simulated vehicle to traverse the curve plus the order of the spline, and/or v. uses lane boundary constraints at uniformly placed points along the planned subsection trajectory curve of a respectively simulated vehicle, preferably one lane boundary constraint for each second, and/or vi. uses one or more direction constraints to keep the planned respective subsection trajectory within the respective lane boundary, wherein the direction constraints are preferably derived from sub-sampled lane boundary constraints.

8. The method according to any one of claims 1 to 7, wherein the length of the respective subsection trajectory is initially estimated as a function of speed of the simulated vehicle at its initial starting point of the subsection trajectory and as a function of the lane curvature as well as the allowed lateral acceleration of the respective simulated vehicle in the subsection trajectory.

9. The method according to claim 7 or 8, wherein in step c) the uniform knot placement, the subsampled boundary points are utilized as gate constraints, wherein the following four constraints are derived from the subsampled points: v_d - c_d >e_t |7_d|

v_d - C_d < 8 v_d - C_d > -8 wherein v_d represents the vector difference of the right and the left boundary point, c_d represents the vector difference of the spline at the corresponding knot value and the left boundary point, 6 represents the fuzz factor, that is proportional (but much slower) to s_p, the s cordinate difference between two sampling points, and v_d represents the unit vector perpendicular to v_d.

10. The method according to any one of claims 5 to 9, wherein in step c) the one or more direction constraints are respectively defined within a fixed range around an angle calculated as piece-wise linear approximation of the center line, with one node at the mid-point of the respective gates, wherein preferably the direction constraints are extended along the derivative spline as piece-wise-linear lane boundary constraints.

11. The method according to any one of claims 5 to 10, wherein in case a linear constraint satisfactory method is used, each subsection trajectory curve and subsequent subsection trajectory curve of a respective simulated vehicle forming a curvature have a G¹ continuity.

12. The method according to claim 11 , wherein the sign of the curvature is kept if the derivative is > 0, preferably the sign function has a discontinuity > 10^-4.

13. The method according to any one of claims 5 to 12, wherein in case a linear constraint satisfactory method is used, one or more road curvature constraints are put on the sign of the curvature at the respective gate points of the subsection trajectory curve and preferably at the derivative of the subsection trajectory curve, wherein the one or more road curvature constraints are only used if a change of the reference heading between two neighboring gates is greater or equal than the fuzz angle used for determining the direction constraints, with the proviso that at the end point of the subsection trajectory curve and there, where only a single neighboring gate exists, no road curvature constraint is used.

14. The method according to any one of claims 5 to 10, wherein in case a non-linear constraint satisfactory method is used, each subsection trajectory curve and subsequent subsection trajectory curve of a respective simulated vehicle forming a curvature have a G² or G³ continuity.

15. The method according to any one of claims 5 to 10 and 14, wherein in case a nonlinear constraint satisfactory method is used, the curvature is constrained directly 31 to be close to the road curvature, and to be within the curvature tolerance of the respectively simulated vehicle. The method according to any one of claims 1 to 15, wherein the planned trajectories of step c) comprise at least one lane change subsection trajectory, wherein the gate constraints of the respective lane change subsection trajectory cover at least two lanes, the starting point of the subsection lane change trajectory curve is predetermined in one origin lane and the end point of the subsection trajectory curve is predetermined in another target lane, and wherein preferably the urgency of the lane change is predetermined between 2 seconds and 8 seconds in a lane change request, wherein preferably the fuzz factor is added only to the side of the direction constraint pointing toward the target lane. A computing system for simulating a road driving environment in driving situations for two or more simulated vehicles comprising or consisting of one or more processors, a memory device coupled to the one or more processors, one or more neural networks for decision making in simulated driving situations, characterized in that the processor is adapted to perform the trajectory planning method steps of any one of claims 1 to 16. A computer program product comprising instructions which, when the program is executed by a computer, cause the computer to carry out the trajectory planning method steps of any one of claims 1 to 16. A computer-readable data carrier having stored thereon the computer program product of claim 18. An autonomous vehicle computing system interacting with the autonomous vehicle trained in the computing system for simulating a road driving environment in driving situations for two or more simulated vehicles according to claim 17.