CN113954867B

CN113954867B - A method, device, equipment and storage medium for fast calculation of object-to-collision time

Info

Publication number: CN113954867B
Application number: CN202111153557.5A
Authority: CN
Inventors: 何华海; 韩旭
Original assignee: Guangzhou Weride Technology Co Ltd
Current assignee: Guangzhou Weride Technology Co Ltd
Priority date: 2021-09-29
Filing date: 2021-09-29
Publication date: 2023-10-20
Anticipated expiration: 2041-09-29
Also published as: CN113954867A

Abstract

The application discloses a method, a device, equipment and a storage medium for rapidly calculating the collision time of an object, which comprise the following steps: s1, acquiring all < points and line segments > in two objects to form a total < points and line segments > set; s2, calculating TTCs of each of the total < point, line segment > sets according to the speeds, accelerations and movement directions of the two objects to form a TTC set; and S3, taking the minimum value in the TTC set as the TTC of the two objects. According to the method, whether collision occurs between the objects or not is not required to be checked in each time step, so that time is greatly saved, and the calculation efficiency of TTC is improved.

Description

Method, device, equipment and storage medium for rapidly calculating time from object to collision

Technical Field

The present application relates to the field of autopilot technology, and in particular, to a method, apparatus, device, and storage medium for rapidly calculating an object collision time.

Background

When two objects of arbitrary shape collide, they may collide at any edge. However, for TTCs (Time To Collision ) between arbitrarily shaped objects, no known fast algorithm exists.

The existing TTC calculation method is mainly calculated in a simulation mode, namely: in each time step, the motion of the objects is simulated and checked for overlap. If overlapping, then a collision between the objects is considered to have occurred. However, this method is time-consuming because it requires checking at each time step, which is disadvantageous in that the calculation efficiency of TTC is improved.

Disclosure of Invention

Therefore, the technical problem solved by the embodiments of the present application is to provide a method, apparatus, device and storage medium for fast calculating the time from object to collision, which do not need to check whether collision occurs between objects in each time step, thus greatly saving time and being beneficial to improving the calculation efficiency of TTC.

In order to solve the technical problems, the technical scheme adopted by the application comprises the following specific contents:

in one aspect, an embodiment of the present application provides a method for quickly calculating an object collision time, including:

s1, acquiring all < points and line segments > in two objects to form a total < points and line segments > set;

s2, calculating TTCs of each of the total < point, line segment > sets according to the speeds, accelerations and movement directions of the two objects to form a TTC set;

and S3, taking the minimum value in the TTC set as the TTC of the two objects.

Further, the step S1 includes:

acquiring all endpoints in a first object and all line segments in a second object;

traversing all endpoints in a first object, and respectively pairing each endpoint with each line segment in a second object to form a first < point, line segment > set;

acquiring all line segments in a first object and all endpoints in a second object;

traversing all endpoints in the second object, and respectively pairing each endpoint with each line segment in the first object to form a second < point, line segment > set;

and combining the first < point, line segment > set and the second < point, line segment > set to form the total < point, line segment > set.

Further, when a certain endpoint C belongs to a first object and a certain line segment AB belongs to a second object, the method for calculating TTC of the < point, line segment > includes:

acquiring the speed of an endpoint CAnd acceleration->Two endpoints of the certain line segment AB are respectively defined as a first endpoint A and a second endpoint B;

defining the displacement between the certain end point C and the first end point A of the certain line segment AB as displacement AC;

if the certain endpoint C reaches any point U on the certain line segment AB within the time t, the certain endpoint C is considered to collide with the certain line segment AB; at this time, the time t is TTC, and the calculation formula of the time t is:

wherein ,

when a certain endpoint C belongs to a second object and a certain line segment AB belongs to a first object, the calculation method of TTC of the < point, line segment > includes:

wherein ,

preferably, the method for rapidly calculating the collision time of the object provided by the embodiment of the application further includes:

and S4, changing the movement directions of the two objects in a preset angle range, and repeating the steps S1 to S3 to obtain a TTC generalization range of the two objects.

More preferably, the predetermined angle range is [ -1 °, +1 ° ].

More preferably, the step S4 further includes:

s5, changing the transverse distance between the two objects, and calculating TTCs of the two objects according to the changed transverse distance.

In another aspect, an embodiment of the present application provides an apparatus for quickly calculating an object collision time, including:

the acquisition module is used for acquiring all the points and line segments in the two objects to form a total point and line segment set;

the processing module is used for calculating TTCs of each of the total < point, line segment > sets according to the speeds, accelerations and movement directions of the two objects to form a TTC set;

and the output module is used for taking the minimum value in the TTC set as the TTC of the two objects.

Further, the device for rapidly calculating the collision time of the object provided by the embodiment of the application further comprises:

and the generalization module is used for changing the motion directions of the two objects in a preset angle range, and repeating the operations of the acquisition module, the processing module and the output module to obtain TTC generalization ranges of the two objects.

In yet another aspect, an embodiment of the present application provides an apparatus, including a memory, a processor, and a computer program stored in the memory and capable of running on the processor, where the processor implements the steps of the method for quickly calculating an object-to-collision time of any one of the above when the processor executes the computer program.

In yet another aspect, an embodiment of the present application provides a storage medium having stored therein a computer program, which when executed by a processor, performs the steps of the method for rapidly calculating an object-to-collision time of any one of the above.

In summary, compared with the prior art, the technical scheme provided by the embodiment of the application has the following beneficial effects:

1. the embodiment of the application forms a total < point, line segment > set by acquiring all < point, line segment > in two objects; calculating TTCs of each of the total < point, line segment > sets according to the speeds, accelerations and movement directions of the two objects to form a TTC set; and finally, taking the minimum value in the TTC set as the TTC of the two objects. Compared with the prior art, whether collision occurs between objects or not is not needed to be checked in each time step, so that time is greatly saved, and the calculation efficiency of TTC is improved.

2. The embodiment of the application forms a first set of points and line segments by traversing all endpoints in a first object and pairing each endpoint with each line segment in a second object respectively; traversing all endpoints in the second object, and respectively pairing each endpoint with each line segment in the first object to form a second set of points and line segments; and finally, combining the first < point, line segment > set and the second < point, line segment > set to form the total < point, line segment > set, so that all the < point, line segment > of the two objects can be accurately acquired, and the probability of omission is greatly reduced.

3. According to the embodiment of the application, the movement directions of the two objects are changed in the preset angle range, and the S1 to S3 are repeated to obtain the TTC generalization range of the two objects, so that the perceived danger is effectively and accurately predicted, and the driving safety is greatly improved.

Drawings

Fig. 1 is a flowchart of a method for quickly calculating the time to collision of an object according to a first exemplary embodiment of the present application.

Fig. 2 is a flowchart of a method for quickly calculating the time to collision of an object according to a second exemplary embodiment of the present application.

Fig. 3 is a flowchart of a method for quickly calculating the time to collision of an object according to a third exemplary embodiment of the present application.

Fig. 4 is a schematic structural diagram of an object-to-collision time rapid computing device according to a fourth exemplary embodiment of the present application.

Fig. 5 is a schematic structural view of an apparatus according to a fifth exemplary embodiment of the present application.

Fig. 6 is a schematic diagram of the derivation of TTC of the present application.

Detailed Description

The present embodiment is only for explanation of the present application and is not to be construed as limiting the present application, and modifications to the present embodiment, which may not creatively contribute to the present application as required by those skilled in the art after reading the present specification, are all protected by patent laws within the scope of claims of the present application.

For the purpose of making the objects, technical solutions and advantages of the embodiments of the present application more apparent, the technical solutions of the embodiments of the present application will be clearly and completely described below with reference to the accompanying drawings in the embodiments of the present application, and it is apparent that the described embodiments are some embodiments of the present application, but not all embodiments of the present application. All other embodiments, which can be made by those skilled in the art based on the embodiments of the application without making any inventive effort, are intended to be within the scope of the application.

The terms "comprises," "comprising," or any other variation thereof, are intended to cover a non-exclusive inclusion, such that a process, method, system, article, or apparatus that comprises a list of steps or elements is not necessarily limited to those steps or elements but may include other steps or elements not expressly listed or inherent to such process, method, article, or apparatus.

In embodiments of the application, words such as "exemplary" or "such as" are used to mean serving as an example, instance, or illustration. Any embodiment or design described herein as "exemplary" or "e.g." in an embodiment should not be taken as preferred or advantageous over other embodiments or designs. Rather, the use of words such as "exemplary" or "such as" is intended to present related concepts in a concrete fashion.

The terms "first," "second," and the like in this disclosure are used for distinguishing between similar elements or items having substantially the same function and function, and it should be understood that there is no logical or chronological dependency between the terms "first," "second," and "n," and that there is no limitation on the amount and order of execution.

Embodiments of the application are described in further detail below with reference to the drawings.

Fig. 1 is a method for quickly calculating the time to collision of an object according to a first exemplary embodiment of the present application, the main steps of the method are described as follows:

and S3, taking the minimum value in the TTC set as the TTC of the two objects.

The embodiment of the application forms a total < point, line segment > set by acquiring all < point, line segment > in two objects; calculating TTCs of each of the total < point, line segment > sets according to the speeds, accelerations and movement directions of the two objects to form a TTC set; and finally, taking the minimum value in the TTC set as the TTC of the two objects. Compared with the prior art, whether collision occurs between objects or not is not needed to be checked in each time step, so that time is greatly saved, and the calculation efficiency of TTC is improved.

It should be noted that the two objects may be vehicles at the same time, or one of the two objects may be a vehicle and the other object may be an obstacle.

Fig. 2 is a diagram showing a second exemplary embodiment of the present application, which provides a method for quickly calculating the time to collision of an object, which is further improved on the basis of the first exemplary embodiment, specifically improved as follows:

the S1 comprises the following steps:

The embodiment of the application forms a first set of points and line segments by traversing all endpoints in a first object and pairing each endpoint with each line segment in a second object respectively; traversing all endpoints in the second object, and respectively pairing each endpoint with each line segment in the first object to form a second set of points and line segments; and finally, combining the first < point, line segment > set and the second < point, line segment > set to form the total < point, line segment > set, so that all the < point, line segment > of the two objects can be accurately acquired, and the probability of omission is greatly reduced.

The overall process of obtaining the total < point, line segment > set in S1 is described in detail below by listing two examples:

first example: it is assumed that both objects are rectangular. The four endpoints of the first object are A, B, C, D respectively and all the line segments that make up the first object are AB, BC, CD, DA respectively. The four endpoints of the second object are W, X, Y, Z respectively, and all the line segments constituting the second object are WX, XY, YZ, ZW respectively. Then, the < points, line segments > constituting the first < point, line segment > set are specifically < a, WX >, < a, XY >, < a, YZ >, < a, ZW >, < B, WX >, < B, XY >, < B, YZ >, < B, ZW >, < C, WX >, < C, XY >, < C, YZ >, < C, ZW >, < D, WX >, < D, XY >, < D, YZ >, < D, ZW >; the < points, line segments > constituting the second < point, line segment > set are specifically < W, AB >, < W, BC >, < W, CD >, < W, DA >, < X, AB >, < X, BC >, < X, CD >, < X, DA >, < Y, AB >, < Y, BC >, < Y, CD >, < Y, DA >, < Z, AB >, < Z, BC >, < Z, CD >. Therefore, the < points, line segments > constituting the total < point, line segment > set are specifically < A, WX >, < A, XY >, < A, YZ >, < A, ZW >, < B, WX >, < B, XY >, < B, YZ >, < B, ZW >, < C, WX >, < C, XY >, < C, YZ >, < C, ZW >, < D, WX >, < D, XY >, < D, YZ >, < D, ZW >, < W, AB >, < W, BC >, < W, CD >, < W, DA >, < X, AB >, < X, BC >, < X, CD >, < X, DA >, < Y, AB >, < Y, BC >, < Y, CD >, < Y, DA >, < Z, DA >, < BC >.

Second example: assuming that a first object of the two objects is a triangle and a second object is a hexagon. The three endpoints of the first object are A, B, C, and all the line segments forming the first object are AB, BC, CA. The six endpoints of the second object are U, V, W, X, Y, Z, respectively, and all the line segments that make up the second object are UV, VW, WX, XY, YZ, ZU, respectively. Then, the < points, line segments > constituting the first < point, line segment > set are specifically < a, UV >, < a, VW >, < a, WX >, < a, XY >, < a, YZ >, < a, ZU >, < B, UV >, < B, VW >, < B, WX >, < B, XY >, < B, ZU >, < C, UV >, < C, VW >, < C, WX >, < C, XY >, < C, YZ >, < C, ZU >; the < points, line segments > constituting the second < point, line segment > set are specifically < U, AB >, < U, BC >, < U, CA >, < V, AB >, < V, BC >, < V, CA >, < W, AB >, < W, BC >, < W, CA >, < X, AB >, < X, BC >, < X, CA >, < Y, AB >, < Y, BC >, < Y, CA >, < Z, AB >, < Z, BC >, < Z, CA >. Therefore, the < points, line segments > constituting the total < point, line segment > set are specifically < A, UV >, < A, VW >, < A, WX >, < A, XY >, < A, YZ >, < A, ZU >, < B, UV >, < B, VW >, < B, WX >, < B, XY >, < B, YZ >, < B, ZU >, < C, UV >, < C, VW >, < C, WX >, < C, XY >, < C, YZ >, < C, ZU >, < U, AB >, < U, BC >, < U, CA >, < V, AB >, < V, CA >, < W, AB >, < W, BC >, < W, CA >, < X, AB >, < X, CA >, < Y, BC >, < Z, Z >.

By analogy, for two objects of arbitrary shape, all < points, line segments > of the two objects can be obtained by a similar method to the two examples above, forming a total < point, line segment > set.

An exemplary embodiment of the present application provides a method for quickly calculating the time to collision of an object, which is further improved on the basis of the first exemplary embodiment, and the specific improvement is as follows:

when a certain endpoint C belongs to a first object and a certain line segment AB belongs to a second object, the calculation method of TTC of the < point, line segment > includes:

wherein ,

taking an example that a certain endpoint C belongs to a first object and a certain line segment AB belongs to a second object, the deriving process of the time t is described in detail with reference to fig. 6, which is specifically as follows:

at time t, the end point C of the first object reaches any one point U on the line segment AB of the second object, and u=uab is defined.

Thus, the following derivation procedure is derived:

wherein ,

when t is equal to or greater than 0 and the value range of u is 0 equal to or greater than u equal to or less than 1, the end point C collides with the AB, and the time t is TTC.

Similarly, when a certain endpoint C belongs to the second object and a certain line segment AB belongs to the first object, the deducing process of the time t is completely identical to the deducing process of the time t when the certain endpoint C belongs to the first object and the certain line segment AB belongs to the second object, which is not described herein.

Through the above-described derivation process, TTC can be calculated quickly and efficiently.

When two vehicles run in parallel but are close to each other, human drivers feel unsafe even if TTCs are infinite, that is, the two vehicles never collide. For this reason, it is necessary to introduce a TTC generalization range.

Fig. 3 is a schematic diagram of a method for quickly calculating the time to collision of an object according to a third exemplary embodiment of the present application, which is further improved on the basis of the above-mentioned embodiments, and the specific improvement is as follows:

the method further comprises the steps of:

According to the embodiment of the application, the movement directions of the two objects are changed in the preset angle range, and the S1 to S3 are repeated to obtain the TTC generalization range of the two objects, so that the perceived danger is effectively and accurately predicted, and the driving safety is greatly improved.

The inventors found in practicing embodiments of the present application that: the perceived risk is proportional to both the lateral distance and the absolute velocity between the two objects. Accordingly, a further exemplary embodiment of the present application provides a method for quickly calculating an object time-to-collision, which is further improved on the basis of the above third exemplary embodiment, specifically as follows:

when the preset angle range is [ -1 °, +1° ], the two objects can be considered to be moving in parallel.

When the two objects move in parallel, the step S4 further includes:

The following describes in detail the specific method of calculating TTCs of the two objects from the changed lateral distances in four cases:

first case: the two objects move in the same direction and each have a velocity of 10 m/s.

Wherein the unit lateral distance np.tan (np.pi×2/180) =0.035.

After a movement of 10 meters, the lateral distance between the two objects will decrease by 0.035 x 10 meters = 0.35 meters. In other words, if two objects are 0.35 meters apart, they will collide within ttc=10 meters/(10 meters/second) =1 second, and the lateral hazard distance at this time is 0.35 meters.

Second case: the two objects move in the same direction and each have a velocity of 1 m/s.

As in the first case described above, but after a movement of 10 meters, at which time ttc=10 seconds, the two objects are not at risk of collision.

Third case: one of the objects is static (i.e. has a velocity of 0) and the other object is 10 m in front of the object at a velocity of 10 m/s.

As in the first case analysis above, but the lateral hazard distance is halved, i.e. 0.17 meters, another object will collide within ttc=10 meters/(10 meters/second) =1 second, which requires bypassing the stationary object, thereby preventing collision.

Fourth case: the two objects move towards each other at a speed of 10 m/s each and a longitudinal distance between the two objects of 20 m.

As analyzed above, ttc=1s, but the lateral hazard distance is doubled, i.e. 0.7m, so that there is no risk of collision.

Fig. 4 is a schematic diagram of an object-to-collision time fast computing device according to a fourth exemplary embodiment of the present application, where the computing device corresponds to the computing method in the foregoing embodiment, and the computing device includes:

In addition, as a further improvement of the object-to-collision time rapid computing device provided by the fourth exemplary embodiment of the present application, the object-to-collision time rapid computing device provided by the embodiment of the present application further includes:

The various modules of the computing device described above may be implemented in whole or in part by software, hardware, and combinations thereof. The above modules may be embedded in hardware or may be independent of a processor in the computer device, or may be stored in software in a memory in the computer device, so that the processor may call and execute operations corresponding to the above modules.

Fig. 5 is a device, which may be a server, provided by a fifth exemplary embodiment of the present application. The device includes a processor, a memory, and a communication interface connected by a system bus. Wherein the processor of the device is configured to provide computing and control capabilities. The memory of the device may be implemented by any type of volatile or nonvolatile memory device, including but not limited to: magnetic disks, optical disks, EEPROM, EPROM, SRAM, ROM, magnetic memory, flash memory, and PROMs. The memory of the device provides an environment for the running of an operating system and computer programs stored therein. The communication interface of the device is a network interface, and the network interface is used for communicating with an external terminal through network connection. The computer program, when executed by a processor, implements the loading method steps described in the above embodiments.

In a further embodiment of the application, a storage medium is provided, which stores a computer program which, when executed by a processor, implements the steps of the calculation method described in the above embodiments. The storage medium includes, but is not limited to: ROM, RAM, CD-ROM, magnetic disk, and floppy disk.

It will be apparent to those skilled in the art that, for convenience and brevity of description, only the above-described division of the functional units and modules is illustrated, and in practical application, the above-described functional distribution may be performed by different functional units and modules according to needs, i.e. the internal structure of the apparatus of the present application is divided into different functional units or modules to perform all or part of the above-described functions.

The embodiments of the present application have been described above with reference to the accompanying drawings, but the present application is not limited to the above-described embodiments, which are merely illustrative and not restrictive, and many forms may be made by those having ordinary skill in the art without departing from the spirit of the present application and the scope of the claims, which are to be protected by the present application.

Claims

1. A method for rapidly calculating the time to collision of an object, comprising:

s3, taking the minimum value in the TTC set as the TTC of the two objects;

2. The method for quickly calculating the time to collision of an object according to claim 1, wherein the step S1 comprises:

3. The method for quickly calculating the time to collision of an object according to claim 1, wherein when a certain endpoint C belongs to a first object and a certain line segment AB belongs to a second object, the method for calculating TTC of the < point, line segment > comprises:

wherein ,

4. the method for rapidly calculating the time to collision of an object according to claim 1, wherein the preset angle range is [ -1 °, +1 ° ].

5. The method for rapidly calculating the time to collision of an object according to claim 4, wherein the step S4 further comprises:

6. An object arrival time rapid computing device, comprising:

the output module is used for taking the minimum value in the TTC set as the TTC of the two objects;

7. An apparatus comprising a memory, a processor and a computer program stored in the memory and executable on the processor, the processor implementing the steps of the method for fast calculation of object-to-collision time as claimed in any one of claims 1-5 when the computer program is executed by the processor.

8. A storage medium having stored therein a computer program which, when executed by a processor, implements the steps of the object-to-collision time fast calculation method according to any one of claims 1-5.