CN113805572B - Motion planning methods and devices - Google Patents

Abstract

This application relates to the field of artificial intelligence, specifically to the field of autonomous driving, and provides a method and device for motion planning. The method includes: obtaining driving environment information, which includes location information of dynamic obstacles; and characterizing the status of the driving environment information. Input the trained reinforcement learning network model and obtain the prediction time domain output by the reinforcement learning network model. The prediction time domain represents the duration or number of steps for predicting the motion trajectory of dynamic obstacles; use the prediction time domain for motion planning. The prediction time domain is obtained through reinforcement learning, which can dynamically change with changes in the driving environment, allowing the autonomous vehicle to flexibly respond to dynamic obstacles during the interaction between the autonomous vehicle and dynamic obstacles.

Description

Motion planning methods and devices

Technical field

This application relates to the field of artificial intelligence, and specifically to a method and device for motion planning.

Background technique

Key technologies for autonomous driving include perception and positioning, planning and decision-making, and execution control. Among them, planning decisions include motion planning, which is a method to navigate an autonomous vehicle from its current location to its destination while complying with road traffic rules.

In actual open road scenarios, the scenarios to be processed by autonomous driving are very complex, especially in dynamic traffic scenarios, that is, in traffic scenarios where there are dynamic obstacles (pedestrians or vehicles) (also called other traffic participants), automatic driving There is gaming behavior when driving vehicles interact with dynamic obstacles. In this scenario, autonomous vehicles are required to be able to flexibly deal with dynamic obstacles.

Currently, motion planning solutions lack the ability to flexibly respond to dynamic obstacles during interaction with dynamic obstacles.

Contents of the invention

This application provides a motion planning method and device, which can enable the autonomous vehicle to flexibly respond to dynamic obstacles during the interaction between the autonomous vehicle and dynamic obstacles.

In a first aspect, a method of motion planning is provided. The method includes: obtaining driving environment information, where the driving environment information includes position information of dynamic obstacles; inputting the state representation of the driving environment information into the trained reinforcement learning The network model obtains the prediction time domain output by the reinforcement learning network model, where the prediction time domain represents the duration or number of steps for predicting the motion trajectory of the dynamic obstacle; and uses the prediction time domain to perform motion planning.

The input of the reinforcement learning network model is driving environment information, and the output of the reinforcement learning network model is the prediction time domain. In other words, the state in the reinforcement learning algorithm is the driving environment information, and the action is the prediction time domain. The reinforcement learning network model in the embodiment of this application can also be called a predictive time domain policy network.

By using the reinforcement learning method, the prediction time domain is determined in real time based on the driving environment information, so that the prediction time domain is not fixed, but can dynamically change with the change of the driving environment. Therefore, motion planning based on the prediction time domain can be realized in The interaction between autonomous vehicles and dynamic obstacles enables autonomous vehicles to flexibly deal with dynamic obstacles.

The autonomous vehicle drives according to the motion trajectory obtained by motion planning based on the predicted time domain obtained using the reinforcement learning method, which can dynamically adjust the driving style during interaction with dynamic obstacles. Driving style indicates whether driving behavior is aggressive or conservative.

In the existing technology, the prediction time domain is fixed. It can be considered that the driving style of autonomous vehicles is fixed, and the traffic scenes are complex and changeable. If the driving style of autonomous vehicles is fixed, it is difficult to balance communication efficiency and driving safety.

In this application, the prediction time domain is obtained through reinforcement learning, and the size of the prediction time domain is not fixed, but changes dynamically with changes in the driving environment. That is to say, for the different movement states of dynamic obstacles , the prediction time domain can be different. Therefore, in this application, as the driving environment of the self-driving vehicle changes, the prediction time domain can be large or small, and the corresponding driving style of the self-driving vehicle can be conservative or aggressive, so that it can be realized during the interaction with dynamic obstacles. Dynamically adjust your driving style.

In conjunction with the first aspect, in one possible implementation, using the prediction time domain for motion planning includes: using the prediction time domain as a hyperparameter to predict the motion trajectory of the dynamic obstacle; According to the position information of the static obstacles included in the driving environment information and the predicted movement trajectory of the dynamic obstacles, the movement trajectory of the autonomous vehicle is planned.

In conjunction with the first aspect, a possible implementation further includes: controlling the autonomous vehicle to drive according to the motion trajectory obtained by the motion planning.

In a second aspect, a data processing method is provided. The method includes: obtaining training data for the reinforcement learning network model based on data obtained by interacting with the driving environment of autonomous driving; using the training data, Perform reinforcement learning training on the reinforcement learning network model to obtain the trained reinforcement learning network model, wherein the input of the reinforcement learning network model is driving environment information, and the output of the reinforcement learning network model is prediction Time domain, the prediction time domain represents the duration or number of steps for predicting the motion trajectory of dynamic obstacles in autonomous driving.

The input of the reinforcement learning network model is driving environment information, and the output of the reinforcement learning network model is the prediction time domain.

Applying the reinforcement learning network model trained using the data processing method provided by this application to autonomous driving, a more appropriate prediction time domain can be determined based on the driving environment during the motion planning process, and motion planning can be performed based on this prediction time domain. It can be realized that the autonomous vehicle can flexibly respond to dynamic obstacles during the interaction between the autonomous vehicle and dynamic obstacles.

Combined with the second aspect, in a possible implementation, obtaining the training data of the reinforcement learning network model based on the data obtained by interacting with the driving environment of autonomous driving includes: obtaining the training data through the following steps Describe a set of samples in the training data <state s, action a, reward r>.

Obtain driving environment information, and use the driving environment information as the state s, which includes the location information of dynamic obstacles; input the state s into the reinforcement learning network model to be trained, and obtain the reinforcement learning network The prediction time domain of the model output is used as the action a, where the prediction time domain represents the duration or number of steps for predicting the motion trajectory of the dynamic obstacle; use the prediction time domain to perform Motion planning is used to obtain the movement trajectory of the self-driving vehicle; by controlling the self-driving vehicle to drive according to the movement trajectory of the self-driving vehicle, the reward r is obtained.

In conjunction with the second aspect, in a possible implementation, obtaining the reward r includes: calculating the reward r according to a reward function, wherein the reward function takes into account any one or more of the following factors : Driving safety, traffic efficiency of autonomous vehicles, and traffic efficiency of other traffic participants.

In a third aspect, a data processing device is provided. The device includes an acquisition unit, a prediction unit and a planning unit.

The acquisition unit is used to acquire driving environment information, where the driving environment information includes location information of dynamic obstacles. The prediction unit is used to input the state representation of the driving environment information into the trained reinforcement learning network model, and obtain the prediction time domain output by the reinforcement learning network model. The prediction time domain represents the response to the dynamic obstacle. The duration or number of steps for motion trajectory prediction. The planning unit is used for motion planning using the prediction time domain.

Combined with the third aspect, in a possible implementation, the planning unit is configured to: use the prediction time domain as a hyperparameter to predict the motion trajectory of the dynamic obstacle; and according to the driving environment information The included position information of static obstacles and the predicted movement trajectory of the dynamic obstacles are used to plan the movement trajectory of the autonomous vehicle.

In conjunction with the third aspect, in a possible implementation, the device further includes a control unit configured to control the autonomous vehicle to drive according to the motion trajectory obtained by the motion planning.

A fourth aspect provides a data processing device, which includes an acquisition unit and a training unit.

The acquisition unit is configured to obtain training data of the reinforcement learning network model based on data obtained through interaction between the reinforcement learning network model and the driving environment of autonomous driving. The training unit is configured to use the training data to perform reinforcement learning training on the reinforcement learning network model to obtain the trained reinforcement learning network model. Wherein, the input of the reinforcement learning network model is driving environment information, and the output of the reinforcement learning network model is the prediction time domain. The prediction time domain represents the duration or number of steps for predicting the motion trajectory of dynamic obstacles in autonomous driving. .

Combined with the fourth aspect, in a possible implementation, the root acquisition unit is used to obtain a set of samples <state s, action a, reward r> in the training data through the following steps.

Driving environment information is obtained and used as the state s, where the driving environment information includes position information of dynamic obstacles. Input the state s into the reinforcement learning network model to be trained, obtain the prediction time domain output by the reinforcement learning network model, and use the prediction time domain as the action a, where the prediction time domain represents the relationship between the The duration or number of steps for dynamic obstacle motion trajectory prediction. The prediction time domain is used for motion planning to obtain the motion trajectory of the autonomous vehicle. The reward r is obtained by controlling the self-driving vehicle to drive according to the motion trajectory of the self-driving vehicle.

In conjunction with the fourth aspect, in a possible implementation, the acquisition unit is configured to calculate the reward r according to a reward function, wherein the reward function takes into account any one or more of the following factors: driving safety characteristics, the traffic efficiency of autonomous vehicles, and the traffic efficiency of other traffic participants.

A fifth aspect provides an autonomous vehicle, including the data processing device provided in the third aspect.

In conjunction with the fourth aspect, in a possible implementation manner, the autonomous vehicle further includes the data processing device provided in the fourth aspect.

In a sixth aspect, a data processing device is provided. The device includes: a memory for storing a program; a processor for executing the program stored in the memory. When the program stored in the memory is executed, the processor is configured to execute the above-mentioned first step. aspect or methods in the second aspect.

In a seventh aspect, a computer-readable medium is provided. The computer-readable medium stores program code for device execution. The program code includes a method for executing the above-mentioned first or second aspect.

An eighth aspect provides a computer program product containing instructions, which when the computer program product is run on a computer, causes the computer to execute the method in the first aspect or the second aspect.

A ninth aspect provides a chip. The chip includes a processor and a data interface. The processor reads instructions stored in a memory through the data interface and executes the method in the first aspect or the second aspect.

Optionally, as an implementation manner, the chip may further include a memory, in which instructions are stored, and the processor is configured to execute the instructions stored in the memory. When the instructions are executed, the The processor is configured to execute the method in the above first or second aspect.

Based on the above description, in this application, the prediction time domain is obtained through reinforcement learning, so the size of the prediction time domain is not fixed, but changes dynamically with changes in the driving environment. That is to say, for dynamic obstacles The prediction time domain may be different for different movement states. Therefore, in this application, as the driving environment of the self-driving vehicle changes, the prediction time domain can be large or small, and the corresponding driving style of the self-driving vehicle can be conservative or aggressive, so that it can be realized during the interaction with dynamic obstacles. Dynamically adjust your driving style.

Description of drawings

Figure 1 is a schematic block diagram of an autonomous driving system.

Figure 2 is a schematic diagram of an autonomous driving scenario.

Figure 3 is a schematic diagram of the principle of reinforcement learning.

Figure 4 is a schematic flowchart of a motion planning method provided by an embodiment of the present application.

FIG. 5 is another schematic flowchart of the motion planning method provided by the embodiment of the present application.

Figure 6 is a schematic flow chart of a method for training a reinforcement learning network model provided by an embodiment of the present application.

FIG. 7 is a schematic flow chart of step S610 in FIG. 6 .

Figure 8 is a schematic diagram of another scenario of autonomous driving.

Figure 9 is a schematic block diagram of a data processing device provided by an embodiment of the present application.

Figure 10 is another schematic block diagram of a data processing device provided by an embodiment of the present application.

Figure 11 is another schematic block diagram of a data processing device provided by an embodiment of the present application.

Figure 12 is another schematic block diagram of a data processing device provided by an embodiment of the present application.

Figure 13 is a schematic diagram of a chip hardware structure provided by an embodiment of the present application.

Detailed ways

With the advent of smart driving, intelligent vehicles have become the focus of research by major manufacturers. The smart car generates the desired path based on various parameters input by the sensor, and provides the corresponding control volume to the subsequent controller. Intelligent driving is also called autonomous driving. Key technologies for autonomous driving include perception and positioning, decision-making and planning, and execution control. As an example, as shown in FIG. 1 , the automatic driving system may include a perception module 110 , a decision planning module 120 and an execution control module 130 .

The environment perception module 110, the decision planning module 120 and the execution control module 130 in the autonomous driving system are exemplarily described below.

The environment sensing module 110 is responsible for collecting environmental information, such as information about obstacles such as other vehicles and pedestrians, and traffic rule information such as traffic signs and traffic lights on the road.

The decision planning responsible for the decision planning module 120 can be divided into the following three levels.

1) Global path planning (route planning) refers to, after receiving a destination information, combining the map information and the current location information and attitude information of the vehicle to generate an optimal global path as subsequent local path planning. reference and guidance. The "optimal" here can refer to conditions such as the shortest path, the fastest time, or must pass through a specified point.

Common global path planning algorithms include Dijkstra and A-Star algorithms, as well as various improvements based on these two algorithms.

2) Behavioral layer (behavioral layer) refers to making specific behavioral decisions (for example, after receiving the global path) based on the environmental information obtained from the environment sensing module 110 and the current driving path of the vehicle. Changing lanes to overtake, following, yielding, parking, entering and exiting the station, etc.).

Common behavioral decision-making layer algorithms include: finite state machines, decision trees, rule-based reasoning models, etc.

3) Motion planning refers to generating a motion trajectory that satisfies various constraints (such as safety, dynamic constraints of the vehicle itself, etc.) based on specific behavioral decisions made by the behavioral decision-making layer. The motion trajectory is used as an input to the execution control module 130 to determine the driving path of the vehicle.

The execution control module 130 is responsible for controlling the driving path of the vehicle according to the motion trajectory output by the decision planning module 120 .

In actual open road scenes, autonomous driving has to deal with very complex scenes, including: empty road scenes, scenes sharing the road with pedestrians and obstacles, empty intersection scenes, busy intersection scenes, and pedestrians violating traffic rules. /Vehicle scenes, normal driving vehicle/pedestrian scenes, etc. For example, in the dynamic traffic scene shown in Figure 2, there are other traffic participants: pedestrians and other moving vehicles. For autonomous vehicles, pedestrians and other moving vehicles are dynamic obstacles. There is gaming behavior in the interaction between autonomous vehicles and dynamic obstacles. Therefore, in dynamic traffic scenarios, autonomous vehicles are required to flexibly deal with dynamic obstacles.

At present, the main implementation methods of motion planning are based on search (for example, A* class algorithm), sampling (for example, RRT class algorithm), parameterized trajectory (for example, Reeds-Shepp curve) and optimization (for example, based on Frenet coordinate system) solutions that lack the ability to flexibly respond to dynamic obstacles during interaction with them.

In response to the above problems, this application provides a motion planning method that can enable autonomous vehicles to flexibly respond to dynamic obstacles during interaction with dynamic obstacles.

In order to better understand the embodiments of the present application, the reinforcement learning involved in the embodiments of the present application is first described below.

Reinforcement learning (RL) is used to describe and solve problems in which an agent learns strategies to maximize returns or achieve specific goals during its interaction with the environment. A common model of reinforcement learning is the Markov decision process (MDP). MDP is a mathematical model for analyzing decision-making problems. Reinforcement learning is where an agent learns in a "trial and error" manner, and the reward obtained through interaction with the environment guides behavior. The goal is to enable the agent to obtain the maximum reward. In reinforcement learning, the reinforcement signal (i.e., reward) provided by the environment evaluates the quality of the generated action, rather than telling the reinforcement learning system how to generate the correct action. Since the external environment provides little information, the agent must rely on its own experience to learn. In this way, the agent acquires knowledge in an action-evaluation (i.e., reward) environment and improves its action plan to adapt to the environment. Common reinforcement learning algorithms include Q-learning, policy gradient, actor-critic, etc.

As shown in Figure 3, reinforcement learning mainly contains five elements: agent, environment, state, action and reward. Among them, the input of the agent is the state, and the output for action. The training process of reinforcement learning is: through multiple interactions between the agent and the environment, the actions, states, and rewards of each interaction are obtained; these multiple groups (actions, states, rewards) are used as training data to train the agent once. Using the above process, the agent is trained for the next round until the convergence conditions are met.

As an example, the process of obtaining the actions, status, and rewards of an interaction is shown in Figure 3. The current state of the environment s0 is input to the agent, and the action a0 output by the agent is obtained. The calculation is based on the relevant performance indicators of the environment under the action a0. The reward r0 for this interaction. At this point, the action a0, action a0 and reward r0 for this interaction are obtained. Record the action a0, action a0 and reward r0 of this interaction for subsequent use in training the agent. The next state s1 of the environment under the action a0 is also recorded in order to realize the next interaction between the agent and the environment.

The technical solutions in this application will be described below with reference to the accompanying drawings.

Figure 4 is a schematic flow chart of a motion planning method 400 provided by an embodiment of the present application. Taking the automatic driving system shown in Figure 1 as an example, the method 300 can be executed by the decision planning module 120. As shown in Figure 4, the method 400 includes steps S410, S420, and S430.

S410, obtain driving environment information.

The driving environment information includes location information of dynamic obstacles. Dynamic obstacles represent various moving obstacles such as pedestrians and vehicles in the driving environment. Dynamic obstacles can also be called dynamic traffic participants. Dynamic obstacles include, for example, other moving vehicles or pedestrians.

For example, the driving environment information may also include road structure information, location information of static obstacles, location information of autonomous vehicles, etc. Among them, road structure information includes traffic rules information such as traffic signs and traffic lights on the road.

The method of obtaining the driving environment information may be to obtain the driving environment information based on the information collected by various sensors on the autonomous vehicle. This application does not limit the method of obtaining driving environment information.

S420: Input the state representation of the driving environment information into the trained reinforcement learning network model, and obtain the prediction time domain output by the reinforcement learning network model. The prediction time domain represents the duration or number of steps for predicting the motion trajectory of the dynamic obstacle.

The reinforcement learning network model in the embodiment of this application represents the agent in the reinforcement learning method (as shown in Figure 3).

The input of the reinforcement learning network model is driving environment information, and the output of the reinforcement learning network model is the prediction time domain. In other words, the state in the reinforcement learning algorithm is the driving environment information, and the action is the prediction time domain. The reinforcement learning network model in the embodiment of this application can also be called a predictive time domain policy network.

It should be noted that the state representation of the driving environment information represents data after processing the driving environment information. In practical applications, the processing method of driving environment information can be determined based on the definition of state in the reinforcement learning algorithm.

In practical applications, the definition of the state in the reinforcement learning algorithm can be designed according to the application requirements. This application does not limit this.

The prediction time domain mentioned in the embodiment of this application represents the duration or number of steps for predicting the motion trajectory of dynamic obstacles.

As an example, assume that the prediction time domain is positioned as the prediction duration. For example, the prediction time domain is 5, which means that the duration for predicting the motion trajectory of dynamic obstacles is 5 time units. This time unit can be preset.

As another example, assume that the prediction time domain positioning is the number of prediction steps. For example, the prediction time domain is 5, which means that the number of steps for predicting the motion trajectory of a dynamic obstacle is 5 unit steps. The unit step size can be preset.

The prediction time domain in the embodiment of the present application can also be expressed as the prediction time domain of the planner used to plan the movement trajectory of dynamic obstacles.

It should be noted that the reinforcement learning network model used in the motion planning method 400 (and the method 500 to be described below) provided by the embodiment of the present application is an already trained model. Specifically, the prediction time is based on the driving environment prediction. The domain is a model trained for the training target. Regarding the training method of the reinforcement learning network model, it will be described below in conjunction with Figure 6, and will not be described in detail here.

S430: Use the prediction time domain to perform motion planning.

For example, the process of using prediction time domain for motion planning includes the following steps:

1) Use the prediction time domain obtained in step S420 as a hyperparameter to predict the motion trajectory of the dynamic obstacle;

2) Based on the position information of static obstacles in the driving environment information and the predicted movement trajectories of dynamic obstacles, use the planning algorithm to plan the movement trajectory of the autonomous vehicle.

It should be noted that the method of motion planning for an autonomous vehicle based on the predicted duration or number of steps of the motion trajectory of the dynamic obstacle (i.e., the prediction time domain in the embodiment of the present application) can refer to the existing technology, and this article will not elaborate on this. narrate.

It should be understood that the self-driving vehicle can drive according to the motion trajectory of the self-driving vehicle obtained in step S430 until the driving task is completed.

For example, the self-driving vehicle drives step C1 according to the motion trajectory of the self-driving vehicle obtained in step S430. If the driving task is not completed, a new state is reacquired based on the updated driving environment, steps S420 and S430 are continued, and the following steps are performed: The motion trajectory of the autonomous vehicle obtained in step S430 travels for step C2. If the driving task is not completed, the above operation continues to be looped. If the driving task is completed, the autonomous driving ends. Among them, the values of C1 and C2 involved can be preset or determined in real time according to the driving environment. C1 and C2 can be the same or different.

Taking C1 and C2 as the same and taking a value of 10 as an example, the self-driving vehicle can travel for 10 unit steps according to the motion trajectory of the self-driving vehicle obtained in step S430. The unit step size can be preset.

By using the reinforcement learning method, the prediction time domain is determined in real time based on the driving environment information, so that the prediction time domain is not fixed, but can dynamically change with the change of the driving environment. Therefore, motion planning based on the prediction time domain can be realized in The interaction between autonomous vehicles and dynamic obstacles enables autonomous vehicles to flexibly deal with dynamic obstacles.

For example, an autonomous vehicle drives according to a motion trajectory obtained by motion planning based on the predicted time domain obtained using reinforcement learning methods, which can dynamically adjust the driving style during interaction with dynamic obstacles.

Driving style indicates whether driving behavior is aggressive or conservative.

For example, when the prediction time domain is large, the corresponding driving style can be regarded as conservative; when the prediction time domain is small, the corresponding driving style can be regarded as aggressive.

In the existing technology, the prediction time domain is fixed. It can be considered that the driving style of autonomous vehicles is fixed, and the traffic scenes are complex and changeable. If the driving style of autonomous vehicles is fixed, it is difficult to balance communication efficiency and driving safety.

In this application, the prediction time domain is obtained through reinforcement learning, and the size of the prediction time domain is not fixed, but changes dynamically with changes in the driving environment. That is to say, for the different movement states of dynamic obstacles , the prediction time domain can be different. Therefore, in this application, as the driving environment of the self-driving vehicle changes, the prediction time domain can be large or small, and the corresponding driving style of the self-driving vehicle can be conservative or aggressive, so that it can be realized during the interaction with dynamic obstacles. Dynamically adjust your driving style.

An example of the motion planning method provided by the embodiment of the present application is described below with reference to FIG. 5 .

Figure 5 is a schematic flow chart of a motion planning method 500 provided by an embodiment of the present application.

S510, obtain driving environment information.

The driving environment information includes location information of dynamic obstacles.

Driving environment information can also include road structure information, location information of static obstacles, location information of autonomous vehicles, etc.

S520: Input the state representation of the driving environment information obtained in step S510 into the trained reinforcement learning network model to obtain the prediction time domain output by the reinforcement learning network model.

S530: Perform motion planning on the self-driving vehicle based on the prediction time domain obtained in step S520, and obtain the planned trajectory of the self-driving vehicle.

Step S530 may include the following two steps:

1) Use the prediction time domain obtained in step S520 as a hyperparameter to predict the motion trajectory of the dynamic obstacle;

2) Based on the position information of static obstacles in the driving environment information and the predicted movement trajectories of dynamic obstacles, use the planning algorithm to plan the movement trajectory of the autonomous vehicle.

S540: Control the self-driving vehicle to drive C steps according to the movement trajectory of the self-driving vehicle obtained in step S530, or in other words, execute the first C steps of the movement trajectory of the self-driving vehicle obtained in step S530, where C is a positive integer.

S550, determine whether the driving task is completed. If so, the automatic driving operation ends. If not, go to step S510.

The motion planning method provided by the embodiment of the present application uses a reinforcement learning method to determine the prediction time domain in real time based on the driving environment information, so that the prediction time domain is not fixed, but can dynamically change with the change of the driving environment, thus based on Motion planning in this prediction time domain can enable the autonomous vehicle to flexibly respond to dynamic obstacles during the interaction between the autonomous vehicle and dynamic obstacles.

For example, applying the motion planning method provided by the embodiments of this application to autonomous driving can dynamically adjust the driving style during interaction with dynamic obstacles.

Figure 6 is a schematic flow chart of a data processing method 600 provided by an embodiment of the present application. For example, the method 600 can be applied to train the reinforcement learning network model used in the methods 400 and 500 . The method 600 includes the following steps.

S610: Obtain training data for the reinforcement learning network model based on the data obtained from the interaction between the reinforcement learning network model and the driving environment of the autonomous driving. The input of the reinforcement learning network model is driving environment information, and the output of the reinforcement learning network model is the prediction time domain. The prediction time domain represents the duration or number of steps for predicting the motion trajectory of dynamic obstacles in autonomous driving.

S620: Use the training data to perform reinforcement learning training on the reinforcement learning network model to obtain a trained reinforcement learning network model.

The reinforcement learning network model in the embodiment of this application represents the agent in the reinforcement learning method (as shown in Figure 3). The training data of the reinforcement learning network model includes multiple groups of samples, and each group of samples can be expressed as <state s, action a, reward r>. Regarding the meaning of state s, action a, and reward r, please refer to the previous description in conjunction with Figure 3, and will not be repeated here.

As shown in Figure 7, in the embodiment of the present application, step S610 includes: obtaining a set of samples <state s, action a, reward r> in the training data of the reinforcement learning network model through the following steps S611 to step S614.

S611, obtain the driving environment information and use the driving environment information as the state s.

The driving environment information includes location information of dynamic obstacles.

For example, the driving environment information may also include road structure information, location information of static obstacles, location information of autonomous vehicles, etc.

The method of obtaining the driving environment information may be to obtain the driving environment information based on the information collected by various sensors on the autonomous vehicle. This application does not limit the method of obtaining driving environment information.

S612, input the state s into the reinforcement learning network model to be trained, obtain the prediction time domain output by the reinforcement learning network model, and use the prediction time domain as the action a, where the prediction time domain represents the prediction of the motion trajectory of the dynamic obstacle. Duration or number of steps.

S613, use the prediction time domain for motion planning to obtain the motion trajectory of the autonomous vehicle.

Step S613 may include the following two steps:

1) Use the prediction time domain obtained in step S612 as a hyperparameter to predict the motion trajectory of the dynamic obstacle;

2) Based on the position information of static obstacles in the driving environment information and the predicted movement trajectories of dynamic obstacles, use the planning algorithm to plan the movement trajectory of the autonomous vehicle.

S614, obtain the reward r by controlling the autonomous vehicle to drive according to the motion trajectory of the autonomous vehicle.

For example, by controlling the autonomous vehicle to drive according to the motion trajectory of the autonomous vehicle, updated driving environment information is obtained, and the reward r is calculated based on the updated driving environment information. Among them, the strategy for obtaining reward r based on the updated driving environment information can be determined according to application requirements, and this application does not limit this.

It should be understood that by executing multiple rounds of steps S611 to S614 in a loop, multiple groups of samples <state s, action a, reward r> can be obtained. Among them, before each execution of the next round of steps S611 to step S614, the reinforcement learning network model will update the mapping relationship between the state s and the action a based on the reward obtained in the previous round of step S614.

Use these sets of samples as training data to train the reinforcement learning network model. Continue to use the above process to train the reinforcement learning network model for the next round until the model convergence conditions are met, and then the trained reinforcement learning network model is obtained.

Optionally, in step S614 of this embodiment, the reward r can be calculated through the cost function.

The cost function can be designed according to application requirements.

Optionally, the cost function may be determined based on the game behavior between the autonomous vehicle and other vehicles.

As examples, considerations in designing this cost function include any one or more of the following:

Driving safety, traffic efficiency of autonomous vehicles, and traffic efficiency of other traffic participants (e.g., other vehicles).

As an example, the reward r is obtained according to the following piecewise function, which can be called the cost function:

The first section "-0.5×time_step" in this piecewise function is used to encourage autonomous vehicles to complete the driving task as soon as possible, out of consideration for the traffic efficiency of autonomous vehicles. Among them, Time_step represents the timing information of the driving task.

The second section "-10" in this piecewise function is used to punish collision behavior for safety reasons.

The third segment "10" in this piecewise function is used to reward completing the driving task.

The fourth segment "5" in this piecewise function is used to reward other vehicles for passing through the narrow road, so that the reinforcement learning algorithm not only considers the driving efficiency of the self-driving vehicle, but also considers the driving efficiency of other vehicles. This is to encourage consideration of other vehicles. Consideration of vehicle traffic efficiency.

When the reinforcement learning network model trained by the method 600 provided in the embodiment of the present application is applied to autonomous driving, a more appropriate prediction time domain can be determined according to the driving environment during the motion planning process, and motion planning can be performed based on the prediction time domain. This enables the autonomous vehicle to flexibly respond to dynamic obstacles during the interaction between the autonomous vehicle and dynamic obstacles.

The following describes an example of applying the method provided by the embodiment of the present application to the narrow road meeting scene as shown in Figure 8.

The driving task of the narrow road meeting scene shown in Figure 8 is that the self-driving vehicle and other vehicles (moving) want to pass through the narrow road. The two vehicles drive without considering the right of way. The self-driving vehicle follows the form of the other vehicle. Behavior adjusts its own driving behavior.

Step 1), obtain the state in the reinforcement learning algorithm.

For example, through lidar, two-dimensional feasible area information and infeasible area information are obtained. For example, these area information (including two-dimensional feasible area information and infeasible area information) are represented as an 84×84 projection matrix.

For example, in order to enable the reinforcement learning network model to describe the movements of autonomous vehicles and other vehicles, the projection matrices of the last 4 frames with an interval of 5 in the historical projection matrix can be transformed according to the current vehicle coordinate system, and the resulting projection A sequence of matrices as input to a reinforcement learning network model.

Step 2), input the state obtained in step 1), that is, the matrix sequence, into the reinforcement learning network model to obtain the prediction time domain of the dynamic obstacles by the planning algorithm.

For example, the network structure of the reinforcement learning network model can adopt the ACKTR algorithm. The ACKTR algorithm is a policy gradient algorithm under the Actor-Critic framework. The ACKTR algorithm includes policy network and value network.

For example, in order to process matrix inputs, value network and policy network models containing convolutional layers and fully connected layers can be designed. Use the matrix sequence obtained in step 1) as the input of the reinforcement learning network model. The output value of the policy network is designed as the prediction time domain of the planning algorithm for dynamic obstacles. For the description of the prediction time domain, please refer to the previous article and will not be repeated here.

Step 3), use the prediction time domain obtained in step 2) as a hyperparameter, and use the uniform speed prediction model to predict the trajectory of other dynamic vehicles in this time domain step.

Based on static obstacles and trajectory prediction of dynamic obstacles, for example, polynomial programming algorithm is used for motion planning. The polynomial algorithm is a planning algorithm based on sampling. The algorithm performs planning under the Frenet coordinate system of structured roads. It first samples the lateral distance deviated from the lane centerline and the longitudinal expected speed, and then uses a fifth-order polynomial fitting to generate A set of alternative trajectories, and finally the trajectories are optimized according to the cost function of the planner, the optimal trajectory is output, and motion planning is completed.

It should be understood that the self-driving vehicle can drive according to the motion trajectory of the self-driving vehicle obtained in step 3) until the driving task is completed.

For example, the self-driving vehicle drives several steps according to the motion trajectory of the self-driving vehicle obtained in step 3). If the driving task is not completed, continue to perform steps 1) to step 3), and follow the self-driving vehicle motion trajectory obtained in step 3). The motion trajectory is driven for several steps. If the driving task is not completed, the above operation continues to be cycled. If the driving task is completed, the automatic driving task ends.

The reinforcement learning network model involved in the example described in conjunction with Figure 8 can be trained using the method 600 in the above embodiment. The specific description is detailed above and will not be repeated here.

As can be seen from the above, the embodiment of the present application uses a reinforcement learning method to determine the prediction time domain in real time based on the driving environment information, so that the prediction time domain is not fixed, but can dynamically change with the change of the driving environment, so that based on the prediction time domain Motion planning in the domain can enable the autonomous vehicle to flexibly respond to dynamic obstacles during the interaction between the autonomous vehicle and dynamic obstacles.

Each embodiment described in this article can be an independent solution or can be combined according to the internal logic. These solutions all fall within the protection scope of this application.

The method embodiments provided by this application are described above, and the device embodiments provided by this application will be described below. It should be understood that the description of the device embodiments corresponds to the description of the method embodiments. Therefore, for content that is not described in detail, please refer to the above method embodiments. For the sake of brevity, they will not be described again here.

As shown in FIG. 9 , this embodiment of the present application also provides a data processing device 900 . The device 900 includes an environment sensing module 910 , a motion planning module 920 , and a vehicle control module 930 .

The environment sensing module 910 is used to obtain driving environment information and transfer the driving environment information to the motion planning module 920.

For example, the environment sensing module 910 is used to obtain driving environment information based on information collected by various sensors on the vehicle.

The driving environment information includes location information of dynamic obstacles.

Driving environment information can also include road structure information, location information of static obstacles, location information of autonomous vehicles, etc.

The motion planning module 920 is used to receive driving environment information from the environment sensing module 910, and use a reinforcement learning network model to obtain the prediction time domain of dynamic obstacles, and perform motion planning based on the prediction time domain to obtain the motion trajectory of the autonomous vehicle, And the planning control information corresponding to the motion trajectory is transferred to the vehicle control module 930.

For example, the motion planning module 920 is used to execute steps S420 and S430 in the method 400 provided in the above method embodiment.

The vehicle control module 930 is configured to receive planning control information from the motion planning module 920 and control the vehicle to complete the driving task according to the action instruction information corresponding to the planning control information.

The device 900 provided in the embodiment of this application can be installed on an autonomous vehicle.

As shown in Figure 10, this embodiment of the present application also provides a motion planning device 1000. The device 1000 is configured to execute method 400 or method 500 in the above method embodiment. The device 1000 includes an acquisition unit 1010, a prediction unit 1020 and a planning unit 1030.

The acquisition unit 1010 is used to acquire driving environment information, which includes location information of dynamic obstacles.

The prediction unit 1020 is used to input the state representation of the driving environment information into the trained reinforcement learning network model, and obtain the prediction time domain output by the reinforcement learning network model. The prediction time domain represents the duration or number of steps for predicting the motion trajectory of the dynamic obstacle.

The planning unit 1030 is used to perform motion planning using the prediction time domain.

For example, the operation of the planning unit 1030 to perform motion planning using the prediction time domain includes the following steps.

Use the prediction time domain as a hyperparameter to predict the movement trajectory of dynamic obstacles; plan the movement trajectory of the autonomous vehicle based on the position information of static obstacles included in the driving environment information and the predicted movement trajectory of dynamic obstacles. .

As shown in Figure 10, the device 1000 may also include a control unit 1040 for controlling the autonomous vehicle to drive according to the movement trajectory obtained by the movement planning.

For example, the prediction unit 1020, the planning unit 1030 and the control unit 1040 may be implemented by a processor. The acquisition unit 1010 can be implemented through a communication interface.

As shown in Figure 11, this embodiment of the present application also provides a data processing device 1100. The device 1100 is used to execute the method 600 in the above method embodiment. The device 1100 includes an acquisition unit 1110 and a training unit 1120.

The acquisition unit 1110 is configured to obtain training data for the reinforcement learning network model based on data obtained through interaction between the reinforcement learning network model and the driving environment of the autonomous driving.

The training unit 1120 is used to perform reinforcement learning training on the reinforcement learning network model using training data to obtain a trained reinforcement learning network model. Among them, the input of the reinforcement learning network model is driving environment information, and the output of the reinforcement learning network model is the prediction time domain. The prediction time domain represents the duration or number of steps for predicting the motion trajectory of dynamic obstacles in autonomous driving.

For example, the acquisition unit 1110 is used to obtain a set of samples <state s, action a, reward r> in the training data through steps S611 to S614 as shown in FIG. 7 . See the above description and will not go into details here.

As shown in Figure 12, this embodiment of the present application also provides a data processing device 1200. The device 1200 includes a processor 1210. The processor 1210 is coupled to a memory 1220. The memory 1220 is used to store computer programs or instructions. The processor 1210 is used to execute the computer programs or instructions stored in the memory 1220, so that the method in the above method embodiment be executed.

Optionally, as shown in Figure 12, the device 1200 may also include a memory 1220.

Optionally, as shown in Figure 12, the device 1200 may also include a data interface 1230, which is used to transmit data with the outside world.

Optionally, as a solution, the device 1200 is used to implement the method 400 in the above embodiment.

Optionally, as another solution, the device 1200 is used to implement the method 500 in the above embodiment.

Optionally, as another solution, the device 1200 is used to implement the method 600 in the above embodiment.

An embodiment of the present application also provides an autonomous vehicle, including a data processing device 900 as shown in FIG. 9 or a data processing device 1000 as shown in FIG. 10 .

Optionally, the autonomous vehicle further includes a data processing device 1100 as shown in Figure 11.

An embodiment of the present application also provides an autonomous vehicle, including a data processing device 1200 as shown in Figure 12.

Embodiments of the present application also provide a computer-readable medium that stores program code for device execution, and the program code includes the method for executing the above embodiments.

Embodiments of the present application also provide a computer program product containing instructions, which when the computer program product is run on a computer, causes the computer to execute the method of the above embodiments.

An embodiment of the present application also provides a chip. The chip includes a processor and a data interface. The processor reads instructions stored in the memory through the data interface and executes the method of the above embodiment.

Optionally, as an implementation manner, the chip may also include a memory, in which instructions are stored. The processor is configured to execute the instructions stored in the memory. When the instructions are executed, the processor is configured to execute the method in the above embodiment.

Figure 13 is a chip hardware structure provided by an embodiment of the present application. The chip includes a neural network processor 1300. The chip can be installed in any one or more of the following devices:

The device 900 shown in FIG. 9 , the device 1000 shown in FIG. 10 , the device 1100 shown in FIG. 11 , and the device 1200 shown in FIG. 12 .

Methods 400, 500 or 600 in the above method embodiments can all be implemented in the chip as shown in Figure 13.

The neural network processor 1300 is mounted on the main processor (Host CPU) as a co-processor, and the main CPU allocates tasks. The core part of the neural network processor 1300 is the arithmetic circuit 1303. The controller 1304 controls the arithmetic circuit 1303 to obtain data in the memory (weight memory 1302 or input memory 1301) and perform operations.

In some implementations, the computing circuit 1303 includes multiple processing units (process engines, PEs) internally. In some implementations, arithmetic circuit 1303 is a two-dimensional systolic array. The arithmetic circuit 1303 may also be a one-dimensional systolic array or other electronic circuit capable of performing mathematical operations such as multiplication and addition. In some implementations, arithmetic circuit 1303 is a general-purpose matrix processor.

For example, assume there is an input matrix A, a weight matrix B, and an output matrix C. The operation circuit 1303 obtains the corresponding data of matrix B from the weight memory 1302 and caches it on each PE in the operation circuit 1303. The operation circuit 1303 obtains the matrix A data from the input memory 1301 and performs matrix operation on the matrix B, and stores the partial result or final result of the matrix in an accumulator (accumulator) 1308.

The vector calculation unit 1307 can further process the output of the operation circuit 1303, such as vector multiplication, vector addition, exponential operation, logarithmic operation, size comparison, etc. For example, the vector calculation unit 1307 can be used for network calculations of non-convolutional/non-FC layers in neural networks, such as pooling, batch normalization, local response normalization, etc. .

In some implementations, the vector calculation unit can 1307 store the processed output vector into a unified memory (which may also be referred to as a unified buffer) 1306 . For example, the vector calculation unit 1307 may apply a nonlinear function to the output of the operation circuit 1303, such as a vector of accumulated values, to generate an activation value. In some implementations, vector calculation unit 1307 generates normalized values, merged values, or both. In some implementations, the processed output vector can be used as an activation input to the arithmetic circuit 1303, such as for use in a subsequent layer in a neural network.

Method 400, 500 or 600 in the above method embodiment may be executed by 1303 or 1307.

The unified memory 1306 is used to store input data and output data.

The input data in the external memory can be transferred to the input memory 1301 and/or the unified memory 1306 through the storage unit access controller 1305 (direct memory access controller, DMAC), the weight data in the external memory can be stored in the weight memory 1302, and the weight data in the external memory can be stored in the weight memory 1302. The data in unified memory 1306 is stored in external memory.

A bus interface unit (BIU) 1310 is used to implement interaction between the main CPU, the DMAC and the fetch memory 1309 through the bus.

An instruction fetch buffer 1309 connected to the controller 1304 is used to store instructions used by the controller 1304;

The controller 1304 is used to call instructions cached in the memory 1309 to control the working process of the computing accelerator.

Generally, the unified memory 1306, the input memory 1301, the weight memory 1302 and the instruction memory 1309 are all on-chip memories, and the external memory is a memory external to the NPU. The external memory can be double data rate synchronous dynamic random access. Memory (double data rate synchronous dynamic random access memory, DDR SDRAM), high bandwidth memory (high bandwidth memory, HBM) or other readable and writable memory.

Unless otherwise defined, all technical and scientific terms used herein have the same meaning as commonly understood by one of ordinary skill in the technical field to which this application belongs. The terminology used herein in the description of the application is for the purpose of describing specific embodiments only and is not intended to limit the application.

It should be noted that the first, second, third or fourth numerical numbers involved in this article are only for convenience of description and are not used to limit the scope of the embodiments of the present application.

Those of ordinary skill in the art will appreciate that the units and algorithm steps of each example described in conjunction with the embodiments disclosed herein can be implemented with electronic hardware, or a combination of computer software and electronic hardware. Whether these functions are performed in hardware or software depends on the specific application and design constraints of the technical solution. Skilled artisans may implement the described functionality using different methods for each specific application, but such implementations should not be considered beyond the scope of this application.

Those skilled in the art can clearly understand that for the convenience and simplicity of description, the specific working processes of the systems, devices and units described above can be referred to the corresponding processes in the foregoing method embodiments, and will not be described again here.

In the several embodiments provided in this application, it should be understood that the disclosed systems, devices and methods can be implemented in other ways. For example, the device embodiments described above are only illustrative. For example, the division of the units is only a logical function division. In actual implementation, there may be other division methods. For example, multiple units or components may be combined or can be integrated into another system, or some features can be ignored, or not implemented. On the other hand, the coupling or direct coupling or communication connection between each other shown or discussed may be through some interfaces, and the indirect coupling or communication connection of the devices or units may be in electrical, mechanical or other forms.

The units described as separate components may or may not be physically separated, and the components shown as units may or may not be physical units, that is, they may be located in one place, or they may be distributed to multiple network units. Some or all of the units can be selected according to actual needs to achieve the purpose of the solution of this embodiment.

In addition, each functional unit in each embodiment of the present application can be integrated into one processing unit, each unit can exist physically alone, or two or more units can be integrated into one unit.

If the functions are implemented in the form of software functional units and sold or used as independent products, they can be stored in a computer-readable storage medium. Based on this understanding, the technical solution of the present application is essentially or the part that contributes to the existing technology or the part of the technical solution can be embodied in the form of a software product. The computer software product is stored in a storage medium, including Several instructions are used to cause a computer device (which may be a personal computer, a server, or a network device, etc.) to execute all or part of the steps of the methods described in various embodiments of this application. The aforementioned storage media include: Universal Serial Bus flash disk (UFD) (UFD can also be referred to as U disk or USB flash drive), mobile hard disk, read-only memory (ROM), random access Various media that can store program code, such as random access memory (RAM), magnetic disks, or optical disks.

The above are only specific embodiments of the present application, but the protection scope of the present application is not limited thereto. Any person familiar with the technical field can easily think of changes or substitutions within the technical scope disclosed in the present application. should be covered by the protection scope of this application. Therefore, the protection scope of this application should be subject to the protection scope of the claims.

Claims (17)

1. A method of motion planning, comprising:

acquiring driving environment information, wherein the driving environment information comprises position information of dynamic obstacles;

inputting the state representation of the driving environment information into a trained reinforcement learning network model, and obtaining a prediction time domain output by the reinforcement learning network model, wherein the prediction time domain represents the duration or the number of steps of motion trail prediction of the dynamic obstacle, the prediction time domain is determined in real time by the reinforcement learning network model according to the driving environment information, the driving environment information is the state information of the reinforcement learning network model, and the prediction time domain is the action information of the reinforcement learning network model;

and performing motion planning by using the prediction time domain.

2. The method of claim 1, wherein said utilizing said prediction horizon for motion planning comprises:

Taking the prediction time domain as a super parameter, and predicting the motion trail of the dynamic obstacle;

and planning the movement track of the automatic driving vehicle according to the position information of the static obstacle and the predicted movement track of the dynamic obstacle, which are included in the driving environment information.

3. The method according to claim 1 or 2, further comprising:

and controlling the automatic driving vehicle to run according to the motion trail obtained by the motion planning.

4. A method of data processing, comprising:

obtaining training data of the reinforcement learning network model according to data obtained by interaction between the reinforcement learning network model and an automatic driving environment;

training the reinforcement learning network model by utilizing the training data to obtain the trained reinforcement learning network model,

the method comprises the steps that input of a reinforcement learning network model is driving environment information, output of the reinforcement learning network model is prediction time domain, the prediction time domain represents duration or step number of motion track prediction of an automatic driving dynamic obstacle, the prediction time domain is determined in real time by the reinforcement learning network model according to the driving environment information, the driving environment information is state information of the reinforcement learning network model, and the prediction time domain is action information of the reinforcement learning network model.

5. The method of claim 4, wherein the obtaining training data for the reinforcement learning network model based on data obtained from interaction of the reinforcement learning network model with a driving environment of an autopilot comprises:

a set of samples < state s, action a, reward r > in the training data is obtained by:

acquiring driving environment information, wherein the driving environment information is used as the state s, and the driving environment information comprises the position information of dynamic obstacles;

inputting the state s into a reinforcement learning network model to be trained, obtaining a prediction time domain output by the reinforcement learning network model, and taking the prediction time domain as the action a, wherein the prediction time domain represents the duration or the step number of motion trail prediction of the dynamic obstacle;

performing motion planning by utilizing the prediction horizon to obtain a motion trail of the automatic driving vehicle;

and obtaining the rewards r by controlling the automatic driving vehicle to run according to the movement track of the automatic driving vehicle.

6. The method of claim 5, wherein the obtaining the prize r comprises:

calculating the reward r according to a reward function, wherein the reward function takes into account any one or more of the following factors:

Driving safety, traffic efficiency of an automatically driven vehicle, traffic efficiency of other traffic participants.

7. An apparatus for motion planning, comprising:

an acquisition unit configured to acquire driving environment information including position information of a dynamic obstacle;

the prediction unit is used for inputting the state representation of the driving environment information into the trained reinforcement learning network model, obtaining a prediction time domain output by the reinforcement learning network model, wherein the prediction time domain represents the duration or the step number of the motion track prediction of the dynamic obstacle, the prediction time domain is determined in real time by the reinforcement learning network model according to the driving environment information, the driving environment information is the state information of the reinforcement learning network model, and the prediction time domain is the action information of the reinforcement learning network model;

and the planning unit is used for planning the motion by utilizing the prediction time domain.

8. The apparatus of claim 7, wherein the planning unit is configured to:

taking the prediction time domain as a super parameter, and predicting the motion trail of the dynamic obstacle;

and planning the movement track of the automatic driving vehicle according to the position information of the static obstacle and the predicted movement track of the dynamic obstacle, which are included in the driving environment information.

9. The apparatus according to claim 7 or 8, further comprising:

and the control unit is used for controlling the automatic driving vehicle to run according to the motion track obtained by the motion planning.

10. An apparatus for data processing, comprising:

the system comprises an acquisition unit, a control unit and a control unit, wherein the acquisition unit is used for acquiring training data of a reinforcement learning network model according to data obtained by interaction between the reinforcement learning network model and an automatic driving environment;

a training unit for training the reinforcement learning network model by using the training data to obtain the reinforcement learning network model after training,

the method comprises the steps that input of a reinforcement learning network model is driving environment information, output of the reinforcement learning network model is prediction time domain, the prediction time domain represents duration or step number of motion track prediction of an automatic driving dynamic obstacle, the prediction time domain is determined in real time by the reinforcement learning network model according to the driving environment information, the driving environment information is state information of the reinforcement learning network model, and the prediction time domain is action information of the reinforcement learning network model.

11. The apparatus according to claim 10, wherein the acquisition unit is configured to obtain the set of samples < state s, action a, reward r > in the training data by:

acquiring driving environment information, wherein the driving environment information is used as the state s, and the driving environment information comprises the position information of dynamic obstacles;

inputting the state s into a reinforcement learning network model to be trained, obtaining a prediction time domain output by the reinforcement learning network model, and taking the prediction time domain as the action a, wherein the prediction time domain represents the duration or the step number of motion trail prediction of the dynamic obstacle;

performing motion planning by utilizing the prediction horizon to obtain a motion trail of the automatic driving vehicle;

and obtaining the rewards r by controlling the automatic driving vehicle to run according to the movement track of the automatic driving vehicle.

12. The apparatus of claim 11, wherein the obtaining unit is configured to calculate the reward r according to a reward function, wherein the reward function takes into account any one or more of the following factors:

driving safety, traffic efficiency of an automatically driven vehicle, traffic efficiency of other traffic participants.

13. An autonomous vehicle, comprising:

an apparatus for motion planning according to any of claims 7-9.

14. The autonomous vehicle of claim 13, further comprising:

apparatus for data processing according to any of claims 10 to 12.

15. An apparatus for data processing, comprising:

a memory for storing executable instructions;

a processor for invoking and executing said executable instructions in said memory to perform the method of any of claims 1-6.

16. A computer readable storage medium, characterized in that it has stored therein program instructions which, when executed by a processor, implement the method of any of claims 1 to 6.

17. A computer program product, characterized in that it comprises a computer program code for implementing the method according to any of claims 1 to 6 when said computer program code is run on a computer.