WO2018099782A1

WO2018099782A1 - Method for collision testing with computing-time efficiency in path planning for a vehicle

Info

Publication number: WO2018099782A1
Application number: PCT/EP2017/080057
Authority: WO
Inventors: Torsten Scherer; Markus Ferch; Christopher Parlitz; Sheung Ying Yuen-Wille; Yorck Von Collani; Stefan Leibold
Original assignee: Robert Bosch Gmbh
Priority date: 2016-11-30
Filing date: 2017-11-22
Publication date: 2018-06-07
Also published as: DE102016223829A1

Abstract

The invention relates to a method for collision testing with computing-time efficiency in path planning for a vehicle (2), wherein distance values until collision with an obstacle (3) are calculated for each (x,y) pair ((x_n,y_n)) of a discrete 2-D grid (1) of the environment of the vehicle (2). In the method, the following steps are performed: First, the (x,y) pairs ((x_n,y_n)) relevant in an expansion step are determined in the vehicle coordinate system, which (x,y) pairs are stored in a first list together with associated curve parameters (r_n) of paths (p_n) for reaching said (x,y) pairs ((x_n,y_n)). Then all relevant (x,y) pairs ((x_n,y_n)) are transformed into an environment model coordinate system. This is followed by a collision test by comparison of the transformed (x,y) pairs ((x_n,y_n)) with the environment model. Thereafter, a second list having collision-free paths is generated by means of the collision-free curve parameters from the first list and by means of an expansion of the paths (p₁, p₂, p₅), whereupon the second list is sorted according to total-cost-optimized nodes. Finally, it is checked whether a total-cost-optimized node is a sought destination point (4) of the path planning.

Description

Description title

Method for computing time-efficient collision checking during path planning for a vehicle

The present invention relates to a method for computing time-efficient

Collision check during path planning for a vehicle. Furthermore, the invention relates to a computer program that performs each step of the method when it runs on a computing device, as well as a machine-readable

Storage medium storing the computer program. Finally, the invention relates to an electronic control device which is set up to carry out the method according to the invention.

State of the art

Nowadays, automatically moving vehicles or robots are used in many situations. The environment of the vehicles can change constantly, for example, by people or moving obstacles. To navigate through the changing environment, such automated vehicles use path planning and discovery methods. Different methods for path planning are known. In the following, two of these path planning methods are briefly described.

In the presence of a global path planner, the Curvature Distance Lookup (CDL) method provides the vehicle under local navigation

Considering the vehicle kinematics to move collision-free in the direction of a target. A discrete 2D grid is created for the surroundings of the vehicle, whose intersection points (x, y) pairs are assigned. Now a set of curves is defined, which determines the movement of the vehicle depending on the vehicle kinematics on curves with different curve parameters - for example, those radii - describes. For each curve parameter of the family of curves, a distance check is then carried out. For each (x, y) pair along a curve with the respective curve parameter, the distance values up to a collision with the vehicle contour become offline

(Pre-) charged. These calculated distance values are then stored together with the corresponding curve parameters in a table and made available for further collision checking at runtime. For this purpose, online sensor data are evaluated, which provide information about the environment of the vehicle.

In addition, the path planning of the so-called A * (A-star / A-Star) algorithm is known, by means of a path planning in greater distances for

free-moving, self-propelled robot is performed. The A * algorithm is used for self-propelled vehicles with axle steering (Ackermann drive), where the vehicle can not turn on the spot

extended so-called hybrid A * algorithm. To determine a path taking into account the vehicle kinematics, a 4D grid is used which comprises the spatial dimensions (x and y) as well as the vehicle orientation and its direction of travel. Depending on geometric vehicle sizes such as e.g. its center distance is also defined a discrete set of curves, which describes, as described above, the movement of the vehicle in a planning step for different curve parameters. In addition, the obstacles detected by sensors and a pre-made environment map are mapped as environmental information in the 4D grid. From this, a collision-free path to the destination is finally determined.

For both methods, collision-checking procedures are essential in which it is checked whether a vehicle collides with an obstacle on its way. Also for the collision test various methods are known. Two such collision checking methods will be described below.

In a first collision check procedure, the vehicle is simply interpreted as a point. In the course of reducing the vehicle to a point, a circle is placed around the center of the vehicle, which is the complete one

Vehicle contour encloses. The radius of this circle serves as a factor for the Reduction. At the same time, as the vehicle is reduced to a point, the obstacles are increased or "inflated" by the same factor - that is, this radius - and the collision check finally checks to see if the point vehicle is in the increased obstacle If not, the path is collision-free.

In a second collision checking method, the vehicle contour is regarded as a polygon. A polygon approximates the most rectangular one

Vehicle contour much more accurate than a circle. At the second

Collision check method is examined within each planning step, whether the start and end states each collide with obstacles. For this purpose, it is determined whether this polygon contains or intersects obstacles. If this is not the case, the path is considered collision-free. Since such a test is computationally expensive, only the start and end states are considered.

Disclosure of the invention

The method is used for computing time-efficient collision checking during path planning for a vehicle, wherein the vehicle can in particular have a complex vehicle contour and a complex vehicle kinematics. Here, the environment of the vehicle is divided by a discrete 2D grid, with intersections of the 2D grid (x, y) pairs are assigned. In this 2D grid, the vehicle is at the origin so that the (x, y) pairs are in the

Vehicle reference coordinate system. Preferably, the 2D grid is determined depending on the environment. For example, the 2D grid becomes more meshed, i. with a higher local resolution, chosen if there are many obstacles in the area as expected or the

Obstacles are packed tightly and path planning becomes more difficult due to increased shunting movements. A typical example of this is a warehouse with shelves and moving objects that are present as an obstacle. When in the environment, on the other hand

As expected, there are fewer objects, the 2D grid is chosen wider mesh and thus reduced its resolution. As a result, larger distances can be planned in advance and the computing time can be significantly reduced. For each of these (x, y) pairs, distance values up to a collision of the vehicle with an object are calculated in advance. In a first step of the path planning method, the distance values are used to determine the (x, y) pairs relevant to an expansion step for all curves in the family of curves, ie the (x, y) pairs which, in an expansion step, touch the vehicle contour and are therefore relevant to the collision check. The choice of the expansion step depends, among other things, on the type of vehicle, the environment of the vehicle, the current task or operating conditions of the vehicle and the choice of the 2D grid.

For example, in an environment crowded with objects, where the distance to one of the obstacles is small, such as a warehouse, an automated forklift performs a different expansion step than a self-propelled transport robot on a factory floor, where the transport robot has sufficient space to pass around Has obstacles and can keep a big distance.

Subsequently, among the determined (x, y) pairs, those (x, y) pairs are identified which can be reached by paths describing different curves with associated curve parameters. Subsequently, these (x, y) pairs are combined. In a further step of the method, the relevant (x, y) pairs are stored together with the associated curve parameters of the determined paths for reaching the relevant (x, y) pairs in a first list. In particular, close to the vehicle, hence near the origin of the model-based vehicle coordinate system, many (x, y) pairs appear multiple times in the first list. By the

Reordering of the first list, the multiply named (x, y) pairs are summarized and need not be recalculated separately below. This significantly reduces the computation time required, especially in the following collision check. This first list represents the touched

Areas in the vehicle coordinate system, when the vehicle with the respective curve parameter and the associated path length in a

Expansion step moves. Advantageously, the aforementioned steps are carried out offline in an electronic control unit of the vehicle. This minimizes the computational effort in the subsequent collision check.

The collision check then finds by comparing the (x, y) pairs with a Environment model instead. Preferably, this environment model is a combination of dynamic obstacles detected by sensors and a pre-made map with static obstacles located around the vehicle. Here are the vehicle and the

Obstacles in the reference coordinate system of the environment model. In order to be able to use the data from the aforementioned first list, all (x, y) pairs from the first list are changed from the vehicle coordinate system into the

Environment model coordinate system transformed.

In particular, the collision check can be performed by checking whether the transformed (x, y) pair in question

Environment model coordinate system within an obstacle that is recorded in the environment model is located. Such a collision method is preferably performed online through local navigation. The steps outlined above significantly simplify the on-line Collision Checking process so that the collision-free path planning of local navigation is more time-efficient. In addition, in the collision check, in addition to the start and end states, intermediate states up to a resolution of the 2D grid are also checked. The collision check results in curves from the family of curves that are collision-free. The curves used in the collision test

Collisions with obstacles are discarded.

For local navigation, a second list with tree structure is generated in which a start position exists as the start node. Starting from the start node, the above-mentioned collision check is performed in an iteration and in

Connection expands the associated paths with collision-free curve parameters. The second list is extended with the end positions of these paths as nodes. The nodes in the second list contain position information (location and orientation) as well as a consumption value and an estimated consumption value to reach the destination point. Of the

Consumption Value contains the consumption that occurred when executing the associated expansion step. The total cost is a combination of the consumption value and the estimated consumption to the destination point.

In a further step, the second list is after the

sorted total cost-optimized nodes and identified the node with the lowest total costs. In other words, the path is sought in which the vehicle has the lowest total cost to reach the node. Finally, it is checked whether this overall cost-optimized node represents the sought-after destination of the path planning. If this is the case, the path is found, otherwise the iteration step is repeated with the collision check, the first list with the (x, y) pairs in the

Vehicle coordinate system is now transformed to the position of the total cost-optimized node in the environment model coordinate system. As an advantage, especially in a densely packed environment, the drivable areas are used unrestrictedly for path planning.

The computer program is set up to perform each step of the method, in particular when it is performed on a computing device or controller. It allows the implementation of the method in a conventional electronic control unit without having to make any structural changes. For this it is on the machine-readable

Storage medium stored.

By putting the computer program on a conventional

electronic control unit will receive the electronic control unit, which is set up to carry out the path planning for the vehicle. In particular, the electronic control unit is set up to carry out the following method steps offline:

- Determination of the relevant (x, y) pairs

- combining the relevant (x, y) pairs; and

- storing the relevant (x, y) pairs;

Brief description of the drawings

Embodiments of the invention are illustrated in the drawings and explained in more detail in the following description.

FIG. 1 shows a 2D grid of an environment for a vehicle with which path planning can be carried out according to an embodiment of the method according to the invention. FIG. 2 shows a flow chart of an embodiment of the method according to the invention. embodiment

FIG. 1 shows a 2D grid 1 of an environment for a vehicle 2.

In addition to the vehicle 2, an obstacle 3 and a target point 4 are recorded in the 2D grid 1. The vehicle 2 comprises an electronic control unit 5, which carries out the method according to the invention. In addition, five possible paths are pi,

Ρ2, Ρ3, p, Ρ5 of an expansion step, which have been found according to an embodiment of the method according to the invention for the movement of the vehicle 2. These five paths pi, P2, P3, p, Ps each describe a curve with associated curve parameter, wherein a third path p3 pursues a straight line, which is interpreted as a circular path with radius infinite.

A first path pi should lead to the destination point 4 in a subsequent expansion step, which is indicated as a dashed line. By way of example, for the first path pi, its curve parameters, in the present case in the form of its radius ri, and two relevant (x, y) pairs (xi, yi), (X2, y2) are shown. The other paths p2, p3, p, ps also each have corresponding curve parameters, in the form of the respective radius, which, however, are not shown in FIG. 1 for the sake of clarity. While the first (x, y) pair (xi, yi) is reached only by the first path Pi, the second (x, y) pair (X2, y2) of all five paths pi, P2, Ρ3, p , ps go through. In real application situations can be due to the significantly larger number of paths and in particular in densely packed

In the environment used, narrower 2D grids find many such (x, y) pairs that are traversed by multiple paths.

FIG. 2 shows a flow diagram of an embodiment of the invention

inventive method. In a preparatory step will be

Distance values are determined, for example, by the curvature distance lookup method 10. At the beginning of the method, the (x, y) pairs relevant in an expansion step, ie the (x, y) pairs, which can collide with the vehicle in the expansion step, determined 11. Subsequently, (x, y) pairs, which are traversed by several paths p _n summarized 12. In one another step is a storage 13 of these relevant (x, y) pairs

along with the associated radii r _{n of} the paths p _n for reaching these (x, y) pairs in a first list Li. The steps performed so far are performed offline directly on the electronic control unit 5 of the vehicle 2.

In addition, an online transformation 14 of all (x, y) pairs in the first list Li from the vehicle coordinate system to the current vehicle position in

Environment model coordinate system performed. A collision check 15 is carried out online in which an environment model of the vehicle 2 is compared with the transformed (x, y) pairs from the first list Li. As shown in FIG. 1, obstacles 3 are registered in the environment model in the environment model. Consequently, it is checked in the collision check 15 whether the

(x, y) pair in the obstacle 3 is located. If this is the case, the corresponding curve parameter r _n leads to a collision of the vehicle 2 with the obstacle 3 and this curve parameter r _n and the associated path p _n are consequently discarded during path planning 16. Is the relevant (x, y) pair however, in no obstacle 3, the radius r _{n is} collision-free. From the first list Li, the collision check 15 finds the collision-free radii r _n , their associated paths pi, P2, ps expands 17 and thereby generates a second list L2 with collision-free paths pi, P2, ps. Then the second list L2 sorted by total cost-optimized node 19, wherein a node to reach the vehicle 2 has the lowest total cost, placed at the top of the second list L2 and as

defined total cost-optimized node. Finally, a check 20 is made as to whether the overall cost-optimized node is the target point 4 sought for path planning. If this is not the case, the transformation 14 of the relevant (x, y) pairs is carried out again and the method is repeated from this step. By contrast, if the total cost-optimized node is the target point 4 sought, the path 21 is found and the vehicle 2 can be moved along this path pi, P2, Ps without collision.

Referring to Figure 1, it will be noted that, according to the collision method known in the art, the second (x, y) pair (X2, y2) in all path schedules for the five paths pi, P2, P3, p, Ps each is checked separately. According to the method of the invention, this second (x, y) pair (X2, y2) summarized 12 and only once checked in the following. A third path P3 and a fourth path p terminate in the obstacle 3, so that they are discarded 16 after the collision procedure 15. The second list L2 therefore contains only the radii r belonging to the first path pi, to the second path P2 or to the fifth path ps. Since a fifth path ps away from the destination point 4, it can be assumed that this does not belong to a total cost-optimized node, so that the fifth path ps in the path planning in the sorting 18 is prioritized lower.

Claims

claims

Method for computing time efficient collision checking in a

Path planning for a vehicle (2), in which for each (x, y) pair ((x _n , yn)) of a discrete 2D grid (1) of the surroundings of the vehicle (2)

Distance values up to the collision with an obstacle (3) are calculated by the following steps:

Determining (11) the (x, y) pairs relevant in an expansion step

Combining the (x, y) pairs that are traversed by multiple paths (p _n ) (12);

Storing (13) the relevant (x, y) pairs ((x _n , yn)) with associated ones

Curve parameters (r _n ) of paths (p _n ) to reach these (x, y) -

Pairs ((x _n , yn)) in a first list (Li);

Transform (14) all relevant (x, y) pairs ((x _n , yn)) into one

Environment model coordinate system;

Collision check (15) by comparing the (x, y) pairs ((x _n , yn)) with an environment model;

Expanding (17) the paths (pi, P2, ps) with collision-free curve parameters from the first list (Li) and generating (18) a second list (L2);

Sort (19) the second list

(L2) for total cost-optimized nodes; and

Check (20) whether a total cost optimized node is a searched destination (4) of path planning.

A method according to claim 1, characterized in that the 2D grid (1) is determined depending on the environment.

3. The method according to any one of the preceding claims, characterized

characterized in that determining (11) the relevant (x, y) pairs ((xn, yn)) and combining (12) the relevant (x, y) pairs ((Χη, Υη)) and storing (13) the relevant (x, y) pairs ((x _n , yn)) is performed offline in an electronic control unit (5) of the vehicle (2).

4. The method according to any one of the preceding claims, characterized

characterized in that in the environmental model obstacles (3) located in the vicinity of the vehicle (2) are recorded.

5. The method according to claim 4, characterized in that the

Collision check is performed by checking whether the relevant (x, y) pair ((x _n , y _n )) in an obstacle (3), which is recorded in the environment model.

6. The method according to claim 5, characterized in that the

Collision check is carried out online by means of local navigation.

7. Computer program which is set up every step of the

Method according to one of claims 1 to 6 perform.

8. Machine-readable storage medium on which a

Computer program according to claim 7 is stored.

9. Electronic control unit (5), which is adapted to carry out by means of a method according to one of claims 1 to 6, a path planning for a vehicle (2).