Method for tracking multiple target objects, device, and computer program for implementing the tracking of multiple target objects for the case of moving objects

Abstract

A method for tracking multiple target objects, moving objects to be tracked being projected onto a grid map having grid cells, the method including the following tasks to be executed in each time: computing the velocity distribution for the next time step with the aid of a transition velocity distribution, which indicates how the objects associated with a grid cell in question move from one time step to the next, based on the preceding velocity distribution; for each grid cell, calculating a transitional probability information item, which indicates, for objects in each grid cell, probabilities of the objects in question reaching possible, further grid cells, as a function of the velocity distribution; calculating an occupancy probability for each grid cell for a subsequent time, based on the transitional probability information item; operating a system as a function of the occupancy probabilities for the grid cells.

Claims

1. A method for tracking multiple target objects, moving objects to be tracked being projected onto a grid map having grid cells, the method comprising: computing a velocity distribution for a next time step with a transitional velocity distribution, which indicates how the objects associated with a grid cell move from one time step to the next time step, based on the preceding velocity distribution; calculating, for each of the grid cells, a transitional probability information item, which indicates, for objects in each of the grid cells, probabilities of the objects reaching possible, further grid cells, as a function of the velocity distribution; calculating an occupancy probability for each of the grid cells for a subsequent time step, based on transitional probability information item; and operating a system as a function of the occupancy probabilities for the grid cells wherein: the transitional velocity distribution for each of the grid cells is calculated as a function of a supplied plan, with a trained neural network and with a multivariate Gaussian model, the transitional velocity distribution is ascertained from an acceleration distribution, with a neighboring transitional velocity distribution obtained with the aid of the neural network, using the multivariate Gaussian model, and the transitional velocity distribution for a particular grid cell is ascertained, in that: an acceleration distribution is ascertained from the neighboring transitional velocity distribution by subtraction; the acceleration distribution is expanded to a range of grid cells with the aid of the multivariate Gaussian model, and rendered discrete for grid cells situated about the particular grid cell; and the velocity distribution for the next time step from the expanded acceleration distribution in the grid cells situated about the particular grid cell is ascertained; a robot is controlled as a function of the occupancy probabilities for the grid cells.

2. The method of claim 1, wherein a velocity distribution is initially provided for each of the grid cells.

3. The method of claim 1, wherein the neural network is provided, in that: measurement data regarding occupancies of grid cells over a number of time steps are provided in one or more training environments, which are described by one or more training plans; for each of the grid cells, frequencies for each combination of occupancies of adjacent grid cells are determined, the frequencies each indicating how often the condition is satisfied, that a particular, adjacent grid cell is occupied in the preceding time step, that the particular grid cell is occupied in the current time step, and that a particular, adjacent grid cell is occupied in a subsequent time step; probabilities are ascertained from the frequencies for each of the grid cells, so as to obtain a neighboring transitional velocity distribution for training; and the neural network, in particular, of a convolutional neural network, is trained, using the neighboring transitional velocity distribution for training and the one or more training plans.

4. The method of claim 3, wherein the neighboring transitional velocity distribution for each of the grid cells of the grid map of the defined local environment is modeled as a function of the specified plan and the trained neural network.

5. The method of claim 1, wherein the measurement indicates an occupancy and/or velocity of one or more of the grid cells in a current time step, and the occupancy probability is corrected based on the measurement.

6. An apparatus for executing a method of tracking multiple target objects, moving objects to be tracked being projected onto a grid map having grid cells, comprising: a device configured to perform the following: calculating a velocity distribution for the next time step with a transition velocity distribution, which indicates how the objects associated with a particular grid cell move from one time step to the next, based on the preceding velocity distribution; calculating, for each of the grid cells, a transitional probability information item, which indicates, for objects in each of the grid cells, probabilities of the objects reaching possible, further grid cells, as a function of the velocity distribution; calculating an occupancy probability for each of the grid cells for a subsequent time step, based on the transitional probability information item; and operating a system as a function of the occupancy probabilities for the grid cells wherein: the transitional velocity distribution for each of the grid cells is calculated as a function of a supplied plan, with a trained neural network and with a multivariate Gaussian model, and the transitional velocity distribution is ascertained from an acceleration distribution, with a neighboring transitional velocity distribution obtained with the aid of the neural network, using the multivariate Gaussian model, and the transitional velocity distribution for a particular grid cell is ascertained, in that: an acceleration distribution is ascertained from the neighboring transitional velocity distribution by subtraction; the acceleration distribution is expanded to a range of grid cells with the aid of the multivariate Gaussian model, and rendered discrete for grid cells situated about the particular grid cell; and the velocity distribution for the next time step from the expanded acceleration distribution in the grid cells situated about the particular grid cell is ascertained; a robot is controlled as a function of the occupancy probabilities for the grid cells.

7. A non-transitory computer readable medium having a computer program, which is executable by a processor, comprising: a program code arrangement having program code for tracking multiple target objects, moving objects to be tracked being projected onto a grid map having grid cells, tby performing the following: computing a velocity distribution for a next time step with a transitional velocity distribution, which indicates how the objects associated with a grid cell move from one time step to the next time step, based on the preceding velocity distribution; calculating, for each of the grid cells, a transitional probability information item, which indicates, for objects in each of the grid cells, probabilities of the objects reaching possible, further grid cells, as a function of the velocity distribution; calculating an occupancy probability for each of the grid cells for a subsequent time step, based on transitional probability information item; and operating a system as a function of the occupancy probabilities for the grid cells wherein: the transitional velocity distribution for each of the grid cells is calculated as a function of a supplied plan, with a trained neural network and with a multivariate Gaussian model, and the transitional velocity distribution is ascertained from an acceleration distribution, with a neighboring transitional velocity distribution obtained with the aid of the neural network, using the multivariate Gaussian model, and the transitional velocity distribution for a particular grid cell is ascertained, in that: an acceleration distribution is ascertained from the neighboring transitional velocity distribution by subtraction; the acceleration distribution is expanded to a range of grid cells with the aid of the multivariate Gaussian model, and rendered discrete for grid cells situated about the particular grid cell; and the velocity distribution for the next time step from the expanded acceleration distribution in the grid cells situated about the particular grid cell is ascertained; a robot is controlled as a function of the occupancy probabilities for the grid cells.

8. The computer readable medium of claim 7, wherein a velocity distribution is initially provided for each of the grid cells.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 shows a representation of a local environment, which is subdivided with the aid of a grid map, in order to implement a method of tracking multiple target objects.

(2) FIG. 2 shows an exemplary representation of a neighboring transitional velocity distribution associated with a grid cell in question.

(3) FIG. 3 shows a flow chart for illustrating a method of ascertaining a transition matrix.

(4) FIG. 4A shows a graphical illustration of the multivariate Gaussian Model for ascertaining a transitional velocity distribution from the neighboring transitional velocity distribution.

(5) FIG. 4B shows a graphical illustration of the multivariate Gaussian Model for ascertaining a transitional velocity distribution from the neighboring transitional velocity distribution.

(6) FIG. 4C shows a graphical illustration of the multivariate Gaussian Model for ascertaining a transitional velocity distribution from the neighboring transitional velocity distribution.

(7) FIG. 4D shows a graphical illustration of the multivariate Gaussian Model for ascertaining a transitional velocity distribution from the neighboring transitional velocity distribution.

DETAILED DESCRIPTION

(8) FIG. 1 shows a representation of a local environment in the form of a branching corridor (T-intersection). The local environment is subdivided into grid cells F with the aid of a grid map K, in order to execute a method of tracking multiple target objects. Grid cells F subdivide grid map K into segments of equal size in accordance with a Cartesian coordinate system, so that each of grid cells F represents a rectangular or square surface segment of the local environment.

(9) The analysis takes place in consecutive time steps.

(10) For each time step, each of grid cells F may be associated with information items, which indicate one or more states of the surface segment of the local environment denoted by grid cell F.

(11) Thus, a grid cell F may be preassigned an occupancy information item, which indicates that at least one moving object is associated with the grid cell F in question, that is, that the at least one moving object is located in the corresponding surface segment. The occupancy information for all grid cells 1 . . . n may be indicated by an occupancy vector O for all grid cells F, having element values of occ (occupied) and nocc (not occupied),

(12) $O=\left(\begin{array}{c}{O}_1\\ \mathrm{.Math.}\\ O_n\end{array}\right)\in {\left\{\mathrm{occ},\mathrm{nocc}\right\}}^n.$

(13) In addition, each grid cell F may be preassigned a velocity information item, which indicates the velocity at which the objects associated with grid cells F move, e.g., by a vector V, which includes the velocity in the x- and y-directions. The velocity information may be discretized into a number of grid cells per time step.

(14) $V=\left(\begin{array}{c}{V}_1\\ \mathrm{.Math.}\\ V_n\end{array}\right)\in {\left\{Z\times Z\right\}}^n$

(15) In the following, the combination of O and V is referred to as X:
X=(O,V)

(16) The following applies to a time step preceding the time step presently considered:
X.sup.−=(O.sup.−,V.sup.−)

(17) In particular, each grid cell F may be preassigned a measuring vector Z, which indicates, in accordance with a sensor measurement, an occupancy identification and/or a velocity information item for the grid cell F in question.
Z=(Z.sub.O,Z.sub.V), Z.sub.O∈{occ,nocc}.sup.n, Z.sub.V∈{z×z}.sup.n

(18) This measuring vector may be used for updating the occupancy information. To this end, P(O) and P(Z|O) are simply multiplied, in order to obtain P(O.sup.−) of the preceding time step.

(19) $P\left(O|Z\right)=P\left(Z|O\right)\frac{P\left(O\right)}{P\left(Z\right)}~P\left(Z|O\right)P\left(O\right)$

(20) Each grid cell F may also be assigned a transitional probability information item in the form of a transition matrix P(T), which specifies a transitional probability for every possible path of movement through the grid cell Z in question. Such a transition matrix P(T) specifies the transitional probabilities from each grid cell F to every other or the same grid cell.

(21) That is, for each grid cell F, the transitional probabilities indicate the probability that the same or one of the other grid cells F will be occupied in a subsequent time step.

(22) Transitional probability information item P(T) is determined as a function of current velocity distribution P(V) and indicates the probability that the objects inside of the grid cell in question will move into another specific grid cell or in the same grid cell.

(23) For a defined local environment, the neighboring transitional velocity probability matrix, which represents the neighboring transitional velocity distribution, is yielded from an evaluation of actual or modeled measurement data in a training environment, in that the following method is carried out over all of the measurement data.

(24) The method is explained with the aid of the flow chart of FIG. 3.

(25) In step S1, measurement data about occupancies of grid cells of a grid map, which represents a training environment, are provided over a number of time steps. The training environment is described, using a training plan. The training plan or specified plan, for which the described method of tracking multiple target objects is intended to be executed, may specify information about the local environment in a suitable manner, for example, in the form of an image, floor plan, accessibility matrix or the like.

(26) In step S2, frequencies of each combination of occupancies of adjacent grid cells F are determined for each grid cell F. Thus, 16 frequencies result, which each indicate how often the condition is satisfied, that a particular, adjacent grid cell F is occupied in the preceding time step, that the grid cell in question is occupied in the current time step, and that a particular, adjacent grid cell is occupied in a subsequent time step.

(27) In step S3, probabilities are ascertained from the frequencies for each of the grid cells, in order to obtain a neighboring transitional velocity distribution for training. As a function of the total number of satisfied conditions, corresponding probabilities for the transitions to and from the grid cell F in question are ascertained from the frequencies. Together with the plan of the local environment, which is specified in the training plan, the neighboring transitional velocity distributions for training obtained in this manner constitute the training data for a machine learning method used subsequently.

(28) In step S4, a neural network, in particular, a convolutional neural network, is trained, using the neighboring transitional velocity distribution for training and the training plan. For the training, a plurality of neighboring transitional velocity distributions for training may also be used for a plurality of training plans. Consequently, the convolutional neural network is trained on the basis of the training data of the neighboring transitional velocity distributions for training and the local environment underlying the training data, so that the patterns of movement, which are specified by the transitional probabilities, are set in relation to the movement spaces of the local environment, and rules are learned accordingly. During training, an information item regarding the training plan is applied on the input side, and the outputs of the neural network are accordingly trained to the neighboring transitional velocity distribution.

(29) In FIG. 2, a neighboring transitional velocity probability matrix is illustratively shown as an example of a neighboring transitional velocity distribution, as is predicted, for example, using a network. The neighboring transitional velocity distribution essentially corresponds to the transitional velocity matrix, except that it is only defined for the 4×4 velocity combinations of the adjacent cells.

(30) In step S5, a transitional probability information item for each grid cell of a grid map of the defined local environment is modeled as a function of the specified plan of the local environment. Thus, by specifying the plan of the local environment, a neighboring transitional velocity distribution for each grid cell may be specified with the aid of the trained neural network.

(31) In step S6, a transitional velocity distribution is calculated for each grid cell from the transitional probabilities of the neighboring transitional velocity distribution, which the aid of the multivariate Gaussian model.

(32) In step S7, the occupancy probability and velocity distribution P(V) for each cell is initialized arbitrarily (for example, constantly).

(33) In step S8, a transition matrix P(T) is calculated from current velocity distribution P(V).

(34) $P\left(T=t\right)=\underset{V^{-}}{\overset{}{.Math.}}\underset{a\in N}{\overset{}{.Math.}}{\mu }_a\left(P\left(V_a^{-}\right)P\left(T_a=t_a|V_a^{-}\right)\right)=\underset{a\in N}{\overset{}{.Math.}}{\mu }_a(P(V_a^{-}=v\left(a,t_a\right)$

(35) The transition matrix results from the probabilities of current velocities P(V). In this context, it is assumed that the occupancies in each grid cell continue to move according to the velocity distributions.

(36) In step S9, the occupancy probability P(O) for the next time step is calculated with the aid of the transitional probabilities P(T) and the occupancy probabilities of the last time step P(O.sup.−).

(37) The occupancy probability is derived as follows:

(38) $P\left(O_c=\mathrm{occ}\right)=1-P\left(O_c=\mathrm{nocc}\right)=1-\underset{a\in N}{\overset{}{.Math.}}\left(1-P\left(O_a^{-}=\mathrm{occ}\right)P\left(T_a=c\right)\right)$

(39) where P(O.sub.c=occ) corresponds to the probability that grid cell c is occupied, P(O.sub.c=nocc) corresponds to the probability that grid cell c is not occupied, N corresponds to the number of all grid cells, and P(T.sub.a=c) corresponds to the probability that one or more objects will move from grid cell a to grid cell c.

(40) Based on the occupancy prediction, a robot may be moved in a manner known per se, in order to prevent a collision.

(41) In step S10, the naïve velocity distribution P({hacek over (V)}.sub.c) is predicted with the aid of transitional probabilities P(T) and the velocity distribution of the last time step P(V.sup.−).

(42) $P\left({\hat{V}}_c=v\left(a,c\right)\right)=\underset{O^{-},T}{\overset{}{.Math.}}P\left(O^{-}\right)P\left(T\right)P\left({\hat{V}}_c=v\left(a,c\right)|O^{-},T\right)=P\left(O_a^{-}=\mathrm{occ}\right)P\left(T_a=c\right)$

(43) In step S11, the environmentally dependent velocity distribution of P(V) is predicted with the aid of transitional velocity distribution P(V|{hacek over (V)}.sub.c) (transitional velocity probabilities) and naïve velocity distribution P(V). Transitional velocity distribution P(V|{hacek over (V)}.sub.c) is calculated in accordance with a method subsequently executed, using a multivariate Gaussian model, which is illustrated by FIGS. 4A-4D.

(44) In step S12, probabilities P(X) are corrected, using measuring model P(Z|X). To this end, P(O) and P(Z|O) are simply multiplied, in order to obtain P(O.sup.−) of the preceding time step.

(45) $P\left(O|Z\right)=P\left(Z|O\right)\frac{P\left(O\right)}{P\left(Z\right)}~P\left(Z|O\right)P\left(O\right)$

(46) Instead of assuming the acceleration noise to be a normal distribution, as in previous approaches, the acceleration may also be assumed to be anisotropic. This is more compatible with an actual environment including moving persons, since they change moving direction more often and adjust walking speed markedly to the speeds of persons in the environment.

(47) The velocity prediction is carried out from a neighboring transitional velocity distribution. As an alternative to the Gaussian normal distribution, the acceleration noise may be estimated, using the difference of the velocity probabilities in two consecutive time steps, so that corresponding accelerations are yielded.
P.sub.NN(A,V.sup.−)

(48) A graphic representation of the neighboring transitional velocity distribution is shown in FIG. 4A. In this context, in the case of an occupancy transition in the direction of a grid field, the color shading in the grid field indicates the transitional occupancy probabilities that, starting from the middle grid field in the preceding time step, a step up/down/to the left/to the right is taken. In accordance with the training of the neural network for generating the transitional occupancy matrix, there are only corresponding probabilities for the grid cells directly adjacent to the grid cell F in question.

(49) Acceleration distributions are subsequently ascertained from the specific velocity distributions in accordance with A=V−V.sup.−, where V corresponds to a velocity between two consecutive time steps. In particular, V=R(t.sub.p)−R(t.sub.c) and V.sup.−=R(t.sub.c)−R(t.sub.a), where t.sub.a is the preceding time step, t.sub.c is the current time step, and t.sub.p is a subsequent time step. R corresponds to the grid cell location of the object. One recognizes that accelerations only occur, if a change in direction of the movement has been detected.

(50) Subsequently, with the aid of a multivariate Gaussian model, a continuous probability distribution regarding acceleration and velocity of the last time step is calculated and evaluated for expanded A and V.sup.−, the new transitions no longer having to be adjacent cells.

(51) $P\left(A,V^{-}\right)=\underset{\tilde{A},V^{-}}{\overset{}{.Math.}}{P}_{\mathrm{NN}}\left(\tilde{A},{\tilde{V}}^{-}\right).Math.N\left[\left(\tilde{A},{\tilde{V}}^{-}\right),\Sigma \right]\left(A,V^{-}\right)$

(52) where P.sub.NN(Ã,{tilde over (V)}.sup.−) corresponds to the 16 neighboring transitional probabilities after the transformation to the acceleration space, N( . . . ) corresponds to a four-dimensional Gaussian distribution having an average value vector (Ã,{tilde over (V)}.sup.−) and a covariance matrix Σ. The distribution is evaluated at the point (A, V.sup.−).

(53) Now, an inverse transformation to a transitional velocity distribution, which specifies velocity distributions in accordance with V=V.sup.−+A, is carried out. In this manner, one obtains P(V, V.sup.−)

(54) $P\left(V\right)=\underset{V^{-}}{\overset{}{.Math.}}P\left(V,V^{-}\right)P\left(V^{-}\right)$