METHOD AND SYSTEM FOR ASCERTAINING AN EXPECTED DEVICE CONTOUR

Abstract

A method for ascertaining an expected contour of a mobile or stationary device for avoiding collisions, using at least one control unit that is internal external to the device includes: obtaining a movement trajectory of the device, which contains probability densities based on state estimation, at least based on expected values and covariances; obtaining a base polyhedron and an approximate contour of the device having a limited number of corners, a confidence interval within which a collision with the static and dynamic surroundings of the device is to be avoided being defined; transforming the base polyhedron to the at least one probability density of the movement trajectory that describes the state estimation; and, for each corner of the transformed base polyhedron, computing a transformed device contour, and ascertaining the expected contour of the device with inclusion of all transformed device contours.

Claims

1. A method for ascertaining an expected contour of a mobile or stationary device for avoiding collisions, the method being performed by at least one control unit that is internal or external to the device, the method comprising: obtaining a movement trajectory of the device, wherein the movement trajectory is based on at least expected values and covariances; obtaining a base polyhedron and an approximate contour of the device each having a limited number of corners; transforming the base polyhedron to at least one probability density of the movement trajectory, the at least one probability density describing a state estimation; for each corner of the transformed base polyhedron, determining a transformed device contour; and ascertaining the expected contour of the device based on a combination of all of the transformed device contours.

2. The method of claim 1, wherein the expected contour of the device is formed from a surface or a volume that is spanned by all of the transformed device contours.

3. The method of claim 1, wherein the obtaining of the base polyhedron includes integrating a standard normal distribution over a volume of the base polyhedron in a manner by which a predefined confidence interval, within which a collision with static and dynamic surroundings of the device is to be avoided, is met.

4. The method of claim 1, wherein the transformation of the base polyhedron includes a decomposition of the covariances, a multiplication of each corner of the base polyhedron by a decomposition, and an addition of an expected value of the expected values of the probability density to each corner of the base polyhedron.

5. The method of claim 1, further comprising transmitting the expected contour of the device to a collision check unit of the device.

6. The method of claim 1, wherein the movement trajectory with the probability density, the base polyhedron, the approximate contour, and a confidence interval, within which a collision with static and dynamic surroundings of the device is to be avoided, are ascertained in advance or offline.

7. The method of claim 1, wherein the transformation, the determination of the at least one transformed device contour, and the ascertainment of the expected contour are carried out in situ or online with inclusion of all of the at least one transformed device contour.

8. The method of claim 1, wherein the device is a mobile or stationary robot, a vehicle, or an aircraft, and includes the at least one control unit.

9. The method of claim 1, wherein the movement trajectory has at least one translatory degree of freedom.

10. The method of claim 1, wherein the movement trajectory has at least one rotatory degree of freedom.

11. A system for ascertaining an expected contour of a mobile or stationary device for avoiding collisions, the system comprising: at least one control unit, wherein the at least one control unit is configured to: obtain a movement trajectory of the device, wherein the movement trajectory is based on at least expected values and covariances; obtain a base polyhedron and an approximate contour of the device each having a limited number of corners; transform the base polyhedron to at least one probability density of the movement trajectory, the at least one probability density describing a state estimation; for each corner of the transformed base polyhedron, determine a transformed device contour; and ascertain the expected contour of the device based on a combination of all of the transformed device contours.

Description

BRIEF DESCRIPTION OF THE DRAWING

[0034] FIG. 1 is a schematic illustration of a system with a movement trajectory of a device, with three-dimensional uncertainties in the form of ellipsoids, according to an example embodiment of the present invention.

[0035] FIG. 2 is a perspective illustration of a base polyhedron, according to an example embodiment of the present invention.

[0036] FIG. 3 is an illustration of an approximate contour of the device, according to an example embodiment of the present invention.

[0037] FIG. 4 is a schematic illustration of an enclosed probability mass of the base polyhedron as a function of the inner radius of the base polyhedron, according to an example embodiment of the present invention.

[0038] FIG. 5 is a perspective illustration of a transformed base polyhedron and the associated uncertainty in the form of an ellipsoid, according to an example embodiment of the present invention.

[0039] FIG. 6 is a schematic illustration of an expected contour and possible contours of the device, according to an example embodiment of the present invention.

DETAILED DESCRIPTION

[0040] In the figures, the same design elements in each case have the same reference numerals. The method according to the present invention is explained below, based on the figures. Device 2 is a mobile device by way of example, and in particular is designed as a vehicle. The steps illustrated in FIGS. 1-4 are carried out, for example, offline or before vehicle 2 starts to travel. In the steps illustrated in FIGS. 5 and 6, the computation takes place online or during planning or while traversing a movement trajectory 4.

[0041] FIG. 1 shows a schematic illustration of a system. The system includes a device 2 or a vehicle 2 with an internal control unit 6. A movement trajectory 4 has been ascertained for vehicle 2. The system includes an external control unit 8 that can communicate with vehicle 2 via a communication link. Ascertained movement trajectory 4 of device 2 includes probability densities 10 that describe the state of device 2.

[0042] Probability densities 10 are location-dependent, and are illustrated as ellipsoids by way of example. In particular, ellipsoids 10 represent uncertainties in the x and y directions. The z component of the ellipsoids indicates the uncertainty in the orientation of vehicle 2. The orientation of vehicle 2 can be regarded as a rotatory degree of freedom theta. The method can be transferred to higher or lower dimensions or degrees of freedom without limitations.

[0043] Movement trajectory 4 begins at a start position 11 and ends at an end position 12.

[0044] The starting position of the method is a computed movement trajectory 4 with covariance, which are to be checked for collisions. The belief print can now be computed for each vehicle pose with uncertainty, for example 10 cm discretization of the path, as follows.

[0045] A user initially selects a base polyhedron 14. Such a base polyhedron 14 is illustrated in FIG. 2. By use of base polyhedron 14, an n-dimensional standard normal distribution is approximated, where n corresponds to the number of vehicle states, for example displayed in three dimensions as a sphere 16. Polyhedrons having few corners are particularly suited, since the computing time increases linearly with the number of corners. For example, platonic bodies, fullerenes, Archimedean bodies, Goldberg polyhedrons, and the like are particularly well suited. In the following discussion, the icosahedron has been selected from the platonic bodies as an example, since, with only twelve corners, it approximates a sphere 16 fairly well.

[0046] In the next step, the user specifies the confidence that is to be guaranteed for which no collision is present. For a vehicle having three states, this confidence corresponds to the probability mass of a 3D standard normal distribution which selected polyhedron 14 is to enclose as a function of a characteristic geometric size of the polyhedron (for example, an insphere radius or edge length). According to FIG. 4, the probability mass is computed from the integral of the standard normal distribution over the volume of polyhedron 14. In particular, FIG. 4 shows a schematic illustration of an enclosed probability mass of base polyhedron 14 as a function of an inner radius of base polyhedron 14. The associated coordinates of the corners of base polyhedron 14 for the predefined confidence are stored for the online computation. In addition, the user considers a meaningful approximation of the vehicle contour by a polygon, which is depicted in FIG. 3. The computing time increases linearly with the number of corners. In the following discussion, an approximate contour 18 of device 2 is approximated by a polygon having twenty corners.

[0047] FIG. 5 shows a perspective illustration of a transformed base polyhedron 14. The transformation takes place online or in situ. The points represent samples from the uncertainty for the qualitative check. Since the selected confidence in FIG. 5 is less than one, some samples are outside transformed base polyhedron 14.

[0048] Base polyhedron 14 from the previous step is transformed to each covariance of movement trajectory 4. This takes place, for example, via a Cholesky decomposition of the covariance (or alternatively, via a quadratic decomposition such as matrix square root decomposition, singular value decomposition, eigenvalue decomposition, and the like), multiplication of each corner of base polyhedron 14 by the decomposition of the covariance, and addition of the expected value of the vehicle pose to each corner of base polyhedron 14.

[0049] Each corner of the polyhedron now represents a vehicle configuration (x position, y position, theta, or orientation) to which expected device contour 18 from FIG. 3 is transformed.

[0050] Lastly, a convex hull 20 is formed over all transformed footprints 18.1, 18.2, 18.3, 18.4, 18.5 to obtain final belief print 20. This is depicted in FIG. 6.

[0051] Since a rotation involves nonlinear mapping, only for a polyhedron having an infinite number of corners can it be ensured that the predefined confidence from the offline computation is exactly met. However, in the motion planning for vehicles, the variance of the orientation is usually very small (also see FIG. 1), for which reason this effect is generally negligible (a small-angle approximation then results in linear mapping, even for rotation).

[0052] The approach can also be expanded in such a way that the confidence is always conservatively met. This can be shown, for example, when the probability distributions of the orientation and the x, y positions are independent. An expansion for correlation is likewise possible.