METHOD FOR CHARACTERIZING THE ENVIRONMENT OF A MOBILE DEVICE, PRODUCING A STATIC SPACE GRID AND/OR A FREE SPACE GRID

Abstract

A method for characterizing the environment of a mobile device, wherein, for each iteration at a time t, the following steps are implemented: S10) Acquiring a plurality of distance measurements (z.sub.t) in the environment by way of at least one sensor; S20) Generating a pair (w.sub.t) of occupancy grids at the time t?1 (OG.sub.t-1) and at the time (OG.sub.t), each grid (OG.sub.t-1, OG.sub.t) fusing the distance measurements into a discretized spatial representation of the environment; S30) Generating a static space grid at the time (SG.sub.t), Or S40) Generating a free space grid at the time (FG.sub.t).

Claims

1. A method for characterizing the environment of a mobile device, wherein, for each iteration at a time t, the following steps are implemented: S10) Acquiring a plurality of distance measurements (z.sub.t) in the environment by way of at least one sensor; S20) Generating a pair (w.sub.t) of occupancy grids at the time t?1(OG.sub.t-1) and at the time t(OG.sub.t), each grid (OG.sub.t-1, OG.sub.t) fusing the distance measurements into a discretized spatial representation of the environment; S30) Generating a static space grid at the time (SG.sub.t), each cell (SG.sub.t(i)) of the static space grid at the time t having a subsequent probability of said cell being occupied by a static tangible body at the time t (P(s.sub.t|w.sub.1:t)), said subsequent probability P(s.sub.t|w.sub.1:t) being computed for each cell (SG.sub.t(i) by way of a binary Bayesian filter from: the subsequent probability of said cell being occupied by a static tangible body at the time ?1 (P(s.sub.t-1|w.sub.1:t-1)), said subsequent probability of said cell being occupied by a static tangible body at the time t?1 (P(s.sub.t-1|w.sub.1:t-1)) being injected directly at input of the binary Bayesian filter; what is referred to as a static prediction model corresponding to a probability of the cell being occupied by a static tangible body at the time t as a function of the state of the cell at the time t?1 (P(s.sub.t|s.sub.t-1)); and what is referred to as a static inverse model at the time t(P(s.sub.t|w.sub.t)) corresponding to a probability of knowing that the cell is occupied by a static tangible body at the time t from the pair of occupancy grids at the time t?1 and at the time t; and/or S40) Generating a free space grid at the time t (FG.sub.t), each cell (FG.sub.t(i)) of the free space grid at the time t having a subsequent probability of said cell being free at the time t P(f.sub.t|w.sub.1:t)), said subsequent probability being computed for each cell by way of a binary Bayesian filter from: the subsequent probability of said cell being free at the time t?1 (P(f.sub.t-1|w.sub.1:t-1)), said subsequent probability of said cell being free at the time t?1 (P(f.sub.t-1|w.sub.1:t-1)) being injected directly at input of the binary Bayesian filter; what is referred to as a free prediction model corresponding to a probability of the cell being free at the time t as a function of the state of the cell at the time t?1 (P(f.sub.t|f.sub.t-1)); and what is referred to as a free inverse model at the time t (P(f.sub.t(w.sub.t)) corresponding to a probability of knowing that the cell is free at the time t from the pair of occupancy grids at the time t?1 and at the time t.

2. The method according to claim 1, wherein step S30) of generating a static space grid and step S40) of generating a free space grid are implemented concomitantly.

3. The method according to claim 2, comprising a step S50) of generating a combined grid (CG.sub.t) resulting from the combination of the static space grid (SG.sub.t) and the free space grid (FG.sub.t).

4. The method according to claim 3, wherein each cell i of the combined grid (CG.sub.t) is computed by way of the following Bayesian fusion: ${\mathrm{CG}}_t\left(i\right)\stackrel{?}{=}F\left({\mathrm{SG}}_t\left(i\right),1-{\mathrm{FG}}_t\left(i\right)\right)$ wherein F(,) is the Bayesian fusion function, CG.sub.t(i) corresponds to a cell i of the combined grid at the time t, SG.sub.t(i) corresponds to a cell i of the static space grid at the time t, and FG.sub.t(i) corresponds to a cell i of the free space grid at the time t, And according to the value of CG.sub.t(i): if CG.sub.t(i)>?, the cell i is probably static given the sequence of pairs of occupancy grids (w.sub.1:t) if CG.sub.t(i)<?, the cell is probably free, if CG.sub.t(i)=?, the cell is neither free nor static.

5. The method according to claim 1, wherein: the subsequent probability of the cell being occupied by a static tangible body at the time t (P(s.sub.t|w.sub.1:t)) and the static inverse model at the time t (P(s.sub.t|w.sub.t)) are approximated by values belonging to a set of finite cardinality, the values being identified respectively by a probability index n(s.sub.t|w.sub.1:t) and by a static inverse model index n(s.sub.t|w.sub.t); the subsequent probability of the cell being free at the time t (P(f.sub.t|w.sub.1:t)) and the free inverse model at the time t (P(f.sub.t|w.sub.t)) are approximated by values belonging to a set of finite cardinality, the values being identified respectively by a probability index n(f.sub.t|w.sub.1:t) and by a free inverse model index n(f.sub.t|w.sub.t).

6. The method according to claim 5, wherein the static inverse model index n(s.sub.t|w.sub.t) is computed as follows: $n\left(s_t.Math.w_t\right)=\{\begin{array}{cc}g\left(w_t\right)>0& \mathrm{if}n\left(o_{i,t-1}.Math.z_{t-1}\right)>0\mathrm{and}n\left(o_{i,t}.Math.z_t\right)>0\\ 0& \mathrm{otherwise}\end{array}$ the function g(w.sub.t) returning a positive value, n(o.sub.i,t-1|z.sub.t-1) corresponding to the occupancy index of the cell i of the occupancy grid OG.sub.t-1 at the time t?1, and n(o.sub.i,t|z.sub.t) corresponding to the occupancy index of the cell i of the occupancy grid OG.sub.t at the time t.

7. The method according to claim 5, wherein the free inverse model index n(f.sub.t|w.sub.t) is computed as follows: $n\left(f_t.Math.w_t\right)=\{\begin{array}{cc}h\left(w_t\right)>0& \mathrm{if}n\left(o_{i,t}.Math.z_t\right)<0\\ 0& \mathrm{otherwise}\end{array}$ and n(o.sub.i,t|z.sub.t) corresponding to the occupancy index of the cell i of the occupancy grid OG.sub.t at the time t, the function h(w.sub.t) returning a positive value.

8. The method according to claim 6, wherein the positive value of the function g(w.sub.t) and the positive value of the function h(w.sub.t) are constant values (?.sub.SG, ?.sub.FG).

9. The method according to claim 6, wherein the positive value returned by the function g(w.sub.t) is equal to max(n(o.sub.i,t-1|z.sub.t-1), n(o.sub.i,t|z.sub.t).

10. The method according to claim 7, wherein the positive value returned by the function h(w.sub.t) is equal to ?n(o.sub.i,t|z.sub.t).

11. The method according to claim 5, wherein the free inverse model index n(f.sub.t|w.sub.t) is computed as follows: $n\left(f_t.Math.w_t\right)=\{\begin{array}{cc}\max \left(-n\left(o_{i,t-1}.Math.z_{t-1}\right),-n\left(o_{i,t}.Math.z_t\right)\right)& \mathrm{if}n\left(o_{i,t-1}.Math.z_{t-1}\right)<0\\ -n\left(o_{i,t}.Math.z_t\right)& \mathrm{otherwise}\end{array}$ n(o.sub.i,t|z.sub.t) corresponding to the occupancy index of the cell i of the occupancy grid OG.sub.t at the time t, and n(o.sub.i,t-1|z.sub.t-1) corresponding to the occupancy index of the cell i of the occupancy grid OG.sub.t-1 at the time t?1.

12. The method according to claim 5, wherein step S30) of generating a static space grid and step S40) of generating a free space grid are implemented concomitantly, and comprising a step S50) of generating a combined grid (CG_t) resulting from the combination of the static space grid (SG_t) and the free space grid (FG_t), wherein the index n(s.sub.t|w.sub.1:t-1) corresponding to the prediction component of the binary Bayesian filter of the static space grid is obtained using a look-up table comprising a finite set of probability indices, and the filtered index n(s.sub.t|w.sub.1:t) is obtained by adding integer probability indices, and wherein the index n(f.sub.t|w.sub.1:t-1) corresponding to the prediction component of the binary Bayesian filter of the free space grid is obtained using a look-up table comprising a finite set of probability indices, and the filtered index n(f.sub.t|w.sub.1:t) is obtained by adding integer probability indices.

13. The method according to claim 5, wherein each cell i of the combined grid (CG.sub.t) is computed by way of the following Bayesian fusion: ${\mathrm{CG}}_t\left(i\right)\stackrel{?}{=}{\mathrm{SG}}_t\left(i\right),1-{\mathrm{FG}}_t\left(i\right)$ CG.sub.t(i) corresponds to a cell i of the combined grid at the time t, SG.sub.t(i) corresponds to a cell i of the static space grid at the time t, and FG.sub.t(i) corresponds to a cell i of the free space grid at the time t, and according to the value of CG.sub.t(i): if CG.sub.t(i)>0 the cell i is probably static given the sequence of pairs of occupancy grids (w.sub.1:t) if CG.sub.t(i)<0, the cell is probably free, if CG.sub.t(i)=0, the cell is neither free nor static.

14. The method for avoiding a tangible body moving around a mobile device, implementing the method according to claim 1 to characterize the environment of a mobile device, and in that it sends a command to an actuator of the mobile device in order to avoid said tangible body.

15. A device for characterizing the environment of a mobile device, the characterization device comprising: at least one input port for receiving a plurality of signals representative of a time series of distance measurements from one or more distance sensors, and a data processor configured to receive said signals at input and to generate a free space grid or a static space grid from said signals by applying a method according to claim 1.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0065] Other features, details and advantages of the invention will become apparent on reading the description provided with reference to the appended drawings, which are given by way of example.

[0066] FIG. 1 is a block diagram illustrating the various steps of the method according to the invention.

[0067] FIG. 2 is a diagram illustrating the binary Bayesian filter.

[0068] FIG. 3 is a diagram illustrating the integer binary Bayesian filter.

[0069] FIG. 4 is a diagram illustrating the integer binary Bayesian filter, wherein the prediction model is constant.

[0070] FIG. 5 is a diagram illustrating the method for characterizing the environment according to the invention by generating a static space grid.

[0071] FIG. 6 is a diagram illustrating the method for characterizing the environment according to the invention by generating a free space grid.

[0072] FIG. 7 is a diagram illustrating the method for characterizing the environment according to the invention by generating a combined grid.

[0073] FIG. 8 is a diagram illustrating the way in which the method according to the invention differs from an algorithm for estimating the displacement of a tangible body known to a person skilled in the art.

[0074] The various steps of the method according to the invention are illustrated in FIG. 1.

DETAILED DESCRIPTION

[0075] The method operates iteratively: in each iteration corresponding to a time t, a new series of measurements is carried out (step S10). Carrying out the same computations with measurements from multiple sensors does not pose any difficulty for a person skilled in the art.

[0076] The set of measurements z.sub.t from one or more sensors at the time t makes it possible to determine the probability of occupancy of a cell i from among the N.sub.c cells of an occupancy grid as described above. Each cell is thus identified by an index i ranging from 1 to N.sub.c.

[0077] The reference z.sub.t actually denotes a set of measurements when the system consists of multiple sensors or when a sensor produces multiple measurements in each iteration. For example, a lidar scan produces a point cloud consisting of a finite number of points.

Generation of the Pair of Occupancy Grids

[0078] The second step S20 consists in generating a pair w.sub.t of occupancy grids. At each time t, an occupancy grid OG.sub.t fuses the measurements produced by all of the sensors of the system in the same iteration.

[0079] It will be recalled that, for an occupancy grid OG.sub.t, a cell has a binary state: it is or is not occupied by an obstacle. In the context of occupancy grids, it is commonly assumed that not occupied means free.

[0080] At each time t, the probability of a cell being occupied is thus calculated taking into account all of the sensor measurements produced at the same time t. P(o.sub.i,t|z.sub.t) represents the probability of occupancy of a cell i given the measurements z.sub.t.

[0081] A new occupancy grid OG.sub.t is thus generated at the time t, and the occupancy grid OG.sub.t-1, generated at the time t?1, is stored in memory in order to be reused for the pair w.sub.t of occupancy grids. w.sub.1:t denotes the sequence (w.sub.1, . . . , w.sub.t) in the present application.

Generation of the Static Space Grid

[0082] In a third step S30, a static space grid SG.sub.t is generated at the time t. The static space grid SG.sub.t is an array of N.sub.c elements, in which:

[00006]$?i?\left\{1,.Math.,N_c\right\},{\mathrm{SG}}_t\left(i\right)=P\left(s_t.Math.w_{1:t}\right)$

[0083] Each cell SG.sub.t(i) of the static space grid has a subsequent probability, at the time t, of the cell being occupied by a static tangible body P(s.sub.t|w.sub.1:t) given the sequence of pairs of occupancy grids w.sub.1:t.

[0084] Said subsequent probability P(s.sub.t|w.sub.1:t) is computed for each cell of the static space grid SG.sub.t by way of a binary Bayesian filter, the principle of which is recalled in FIG. 2.

[0085] Binary Bayesian filtering consists in recursively estimating a hidden state (this being the case if certain cells are obstructed by an obstacle, meaning that the distance measurement is unknown) in the light of observations.

[0086] P(s.sub.t|z.sub.1:t) is called subsequent probability, since it depends on the specific value of the observations z.sub.1:t. As illustrated in FIG. 2, the subsequent probability is reinjected at input of the filter for the following iteration.

[0087] The binary Bayesian filter essentially comprises two steps, namely a prediction step, which depends on the state of the pairs at the previous times 1: t?1 (subsequent probability at the time t?1, and prediction model at the time t) and a step of updating the measurement, which takes into account the inverse model at the time t and the output of the prediction.

[0088] Advantageously, it may be considered that the static prediction model (probability of the cell being occupied by a static tangible body at the time t as a function of the state of the cell at the time t?1) is equal to a constant value ?.

[0089] With this hypothesis, the prediction equation may be written:

[00007]$P\left(s_t.Math.w_{1:t-1}\right)=P\left(s_{t-1}.Math.w_{1:t-1}\right).Math.?+\left(1-P\left(s_{t-1}.Math.w_{1:t-1}\right)\right).Math.\left(1-?\right)$

[0090] Thus, the value of ? influences the prediction as follows:

[0091] If ?=1, the result of the prediction is P(s.sub.t|w.sub.1:t-1)=P(s.sub.t-1|w.sub.1:t-1), this meaning that s.sub.t keeps the same value as the previous estimate of s.sub.t-1.

[0092] If ?=?, the result of the prediction is P(s.sub.t|w.sub.1:t-1)=?, this meaning that the prediction of s.sub.t from s.sub.t-1 results from a completely uncertain estimate of s.sub.t.

[0093] A value of ? between ? and 1 expresses the degree of uncertainty between the previous scenarios.

[0094] In the context of the present invention, the inverse model at the time t is what is referred to as a static inverse model P(s.sub.t|w.sub.t) that comprises a probability of knowing that the cell is occupied by a tangible body at the time t?1 and at the time t from the pair of occupancy grids at the time t?1 and at the time t. A person skilled in the art may refer to the detailed definition of the inverse model in patent application FR3041451.

[0095] At each time t, the static inverse model is computed from the pair w.sub.t of occupancy grids. Using a binary Bayesian filter with an inverse model comprising the last two occupancy grids (at the time t?1 and at the time t) thus makes it possible to determine, for each cell, whether it is occupied by a static tangible body. This modus operandi differs from the method disclosed in patent application FR3116640, which estimates the movement of a tangible body using an inverse model that depends only on a single series of temporal observations at a time t. In patent application FR3116640, movement is estimated using an inconsistency grid that is generated in response to detection, between two iterations, of a change of occupancy state in the feature grids.

[0096] As illustrated in FIG. 2, the subsequent probability P(s.sub.t-1|w.sub.1:t-1) of the cell being occupied by a static tangible body at the time t?1 is injected directly at input of the binary Bayesian filter, thereby considerably simplifying the method disclosed in patent application FR3116640. Indeed, in that document, the iterative method for estimating the movement of a tangible body implements a step of propagating the probability indices before they are reinjected at input of the filter.

[0097] The method according to the invention thus makes it possible to characterize the cells occupied by static obstacles, in the environment of a mobile device, with lower computational complexity compared to known methods.

Generation of the Free Space Grid

[0098] In a step S40, the same principle may be applied to generate a free space grid FG.sub.t at the time t.

[0099] Each cell FG.sub.t(i) of the free space grid at the time t thus has a subsequent probability P(f.sub.t|w.sub.1:t)) of the cell being free at the time t. The subsequent probability is computed for each cell by way of a binary Bayesian filter from: [0100] the subsequent probability of said cell being free at the time ?1 (P(f.sub.t-1|w.sub.1:t-1)), said subsequent probability of said cell being free at the time t?1 (P(f.sub.t-1|w.sub.1:t-1)) being injected directly at input of the binary Bayesian filter; [0101] what is referred to as a free prediction model comprising a probability of the cell being free at the time t as a function of the state of the cell at the time t?1 (P(f.sub.t|f.sub.t-1)); and [0102] what is referred to as a static inverse model at the time t (P(f.sub.t|w.sub.t)) that comprises a probability of knowing that the cell is free at the time t?1 and at the time t from the pair of occupancy grids at the time t?1 and at the time t.

[0103] The method according to the invention thus makes it possible to characterize the free cells, in the environment of a mobile device, also with lower computational complexity compared to known methods.

[0104] According to one embodiment, the method according to the invention comprises only generating a static space grid (that is to say without generating a free space grid) or, conversely, only generating a free space grid (that is to say without generating a static space grid). Indeed, the two grids are independent, and the method may iterate the steps S10-S20-S30 or the steps S10-S20-S40 in a loop.

Generation of the Combined Grid

[0105] As a variant, the static space grid and the free space grid are implemented concomitantly. Thus, in each iteration, a static space grid SG.sub.t and a free space grid FG.sub.t are generated, from the same distance measurements, with the same pairs w.sub.t of occupancy grids.

[0106] Advantageously, in each iteration, the static space grid SG.sub.t and the free space grid FG.sub.t are combined with one another (cell-by-cell combination), so as to obtain a combined grid CG.sub.t (step S50, FIG. 1).

[0107] Each cell i of the combined grid CG.sub.t may be computed by way of the following Bayesian fusion:

[00008]${\mathrm{CG}}_t\left(i\right)\stackrel{?}{=}F\left({\mathrm{SG}}_t\left(i\right),1-{\mathrm{FG}}_t\left(i\right)\right)$ [0108] F (,) represents the Bayesian fusion function.

[0109] Thus, according to the sign of CG.sub.t(i): [0110] if CG.sub.t(i)>?, the cell i is probably static given the sequence of pairs of occupancy grids w.sub.1:t [0111] if CG.sub.t(i)<?, the cell is probably free, [0112] if CG.sub.t(i)=?, the cell is neither free nor static.

[0113] The estimate that prevails between the estimate of the static space grid SG.sub.t and the estimate of the free space grid FG.sub.t is thus looked at.

[0114] The method thus described uses the model of the binary Bayesian filter. One way to improve the implementation and the integration of the method in a microprocessor would be to apply an integer binary Bayesian filter, as illustrated in FIG. 3. The case where the static prediction model is equal to a constant value ? is illustrated by FIG. 4.

[0115] For this purpose, the subsequent probability P(s.sub.t|w.sub.1:t) of the cell being occupied by a static tangible body at the time t is identified by a probability index n(s.sub.t|w.sub.1:t). The subsequent probability P(s.sub.t-1|w.sub.1:t-1) of the cell being occupied by a static tangible body at the time t?1 is identified by a probability index n(s.sub.t-1|w.sub.1:t-1). Similarly, the static inverse model P(s.sub.t|w.sub.t) at the time t is identified by a static inverse model index n(s.sub.t|w.sub.t). Moreover, it is considered that the static prediction model has a constant value a over time.

[0116] These indices belong to a set of finite cardinality of probability classes, and the prediction and update steps benefit from the integer fusion function for the filtering function, using only integer arithmetic, as described in patent application FR3116640. Indeed, the set of finite cardinality of probability classes is formed by combining one or more subsets such that, in the step of updating the measurement, fusion of two probability classes belonging to one and the same subset provides a result also belonging to said subset.

[0117] The index n(s.sub.t|w.sub.1:t-1) corresponding to the prediction component of the integer binary Bayesian filter of the static space grid is obtained using a look-up table comprising a finite set of probability indices, and the filtered index n(s.sub.t|w.sub.1:t) is obtained by adding integer probability indices.

Algorithm of the Integer Binary Bayesian Filter of the Static Space Grid SG.SUB.t..

[0118] The integer binary Bayesian filter IBBF.sub.SG of the static space grid SG.sub.t is an algorithm comprising an initialization function for the filter, and an iterative application function for the filter, with direct feedback from the output of the filter. The prediction step, in the initialization function for the filter, is computed using a look-up table, and the measurement update is computed using a sum of integer indices, as indicated below.

[0119] The initialization function depends on the following input parameters: ?.sub.GFSE, ?.sub.GFSE and ?.sub.SG

[0120] ?.sub.GFSE is a constant that corresponds to the approximation parameter of the sequence (q.sub.n).sub.n??.sub.GFSE of real numbers between 0 and 1 used in the integer Bayesian fusion function, whose parameters x and y are probability values, and defined as:

[00009]$F\left(x,y\right)=\frac{x.Math.y}{x.Math.y+\left(1-x\right).Math.\left(1-y\right)}$${\left(q_n\right)}_{n??}=\{\begin{array}{cc}\frac{1}{2}& \mathrm{if}n=0\\ \frac{1}{2}+{?}_{\mathrm{GFSE}}& \mathrm{if}n=1\\ \frac{1}{2}-{?}_{\mathrm{GFSE}}& \mathrm{if}n=-1\\ F\left(q_{n-1},q_1\right)& \mathrm{if}n>1\\ F\left(q_{n-1},q_{-1}\right)& \mathrm{if}n<-1\end{array}$

[0121] The set of indices ?.sub.GFSE is a subset of for defining the sequence (q.sub.n).sub.n??.sub.GFSE. Thus, rather than working on an infinite sequence (q.sub.n).sub.n?, work is carried out only in a finite sequence (q.sub.n).sub.n??.sub.GFSE. For example, to decode the indices n in 8 bits only, ?.sub.GFSE={?128, . . . , 127} is adopted.

[0122] ?.sub.SG is a constant for the initialization function, with ???.sub.SG?1, and that corresponds to the numerical value of the static prediction model P(s.sub.t|s.sub.t-1).

[0123] The first step of the initialization function consists in determining each entry in the look-up table predLUT starting with an empty vector of size ?.sub.GFSE, and then, for each n in ?.sub.GFSE, the element predLUT(n) is a probability index computed as follows:

[00010]$\mathrm{predLUT}\left(n\right)=m\mathrm{where}{\mathrm{approx}}_{\mathrm{policy}}\left(q_n.Math.{?}_{\mathrm{SG}}+\left(1-q_n\right).Math.\left(1-{?}_{\mathrm{SG}}\right)\right)=q_m.$

[0124] The function approx_policy approximates the result of the operation (q.sub.n.Math.?.sub.SG+(1?q.sub.n).Math.(1??.sub.SG)) by an element q.sub.m of the sequence (q.sub.n).sub.n??.sub.CFSE. It is the index m of q.sub.m that is stored in the element predLUT(n) of the look-up table predLUT.

[0125] The application function for the integer binary Bayesian filter IBBF.sub.SG ApplyFilter(n(s.sub.t-1|w.sub.1:t-1), n(s.sub.t|w.sub.t)) is defined as follows: [0126] Prediction: n(s.sub.t|w.sub.1:t-1)?predLUT(n(s.sub.t-1|w.sub.1:t-1)) [0127] Measurement update: n(s.sub.t|w.sub.1:t)?n(s.sub.t|w.sub.1:t-1)+n(s.sub.t|w.sub.t)

[0128] The method according to the invention advantageously computes the static inverse model index n(s.sub.t|w.sub.t) as follows, illustrated by FIG. 5 (block OG to SIM):

[00011]$n\left(s_t.Math.w_t\right)=\{\begin{array}{cc}g\left(w_t\right)>0& \mathrm{if}n\left(o_{i,t-1}.Math.z_{t-1}\right)>0\mathrm{and}n\left(o_{i,t}.Math.z_t\right)>0\\ 0& \mathrm{otherwise}\end{array}$

[0129] If the cell is probably occupied both at the time t?1 and at the time t, the value of the index of the static inverse model is defined by the function g(w.sub.t) that returns a positive index. Otherwise, the value of the index of the static inverse model is equal to zero.

[0130] n(o.sub.i,t|z.sub.t) corresponds to the probability index in the occupancy grid of the cell i: OG (i)=n(o.sub.i,t|z.sub.t)

[0131] According to one embodiment, the function g(w.sub.t) returns a constant value ?.sub.SG>0.

[0132] As a variant, it is possible to define g(n(w.sub.t)=max(n(o.sub.i,t-1|z.sub.t-1), n(o.sub.i,t|z.sub.t).

[0133] Algorithm of the Integer Binary Bayesian Filter of the Free Space Grid FG.sub.t

[0134] The integer binary Bayesian filter IBBF.sub.FG of the free space grid FG.sub.t is based on the same principle as the integer binary Bayesian filter IBBF.sub.SG of the static space grid SG.sub.t.

[0135] The subsequent probability of the cell being free at the time t (P(f.sub.t|w.sub.1:t)) is identified respectively by a probability index n(f.sub.t|w.sub.1:t) and the free inverse model at the time t (P(f.sub.t|w.sub.t)) is identified by a free inverse model index n(f.sub.t|w.sub.t).

[0136] As illustrated in FIG. 6, the integer binary Bayesian filter IBBF.sub.FG of the free space grid FG.sub.t computes the probability index n(f.sub.t|w.sub.1:t) iteratively, based on the probability index n(f.sub.t-1|w.sub.1:t-1).

[0137] The initialization function for the filter depends on the following input parameters: ?.sub.GFSE, ?.sub.GFSE and ?.sub.FG

[0138] The constant ?.sub.GFSE and the set of indices ?.sub.GFSE are identical to those used for the integer binary Bayesian filter IBBF.sub.SG of the static space grid SG.sub.t.

[0139] ?.sub.FG is a constant, with ???.sub.FG?1, and that corresponds to the numerical value of the free prediction model P(f.sub.t|f.sub.t-1).

[0140] The details of the computations explained above for the integer binary Bayesian filter IBBF.sub.SG of the static space grid SG.sub.t apply, in the same way, to the integer binary Bayesian filter IBBF.sup.FG of the free space grid FG.sub.t; they are therefore not repeated here.

[0141] The inputs of the application function for the filter IBBF.sup.FG are the probability index n(f.sub.t-1|w.sub.1:t-1) that is computed recursively, with direct feedback from the output of the filter, and the free inverse model index n(f.sub.t|w.sub.t).

[0142] Advantageously, the free inverse model index n(f.sub.t|w.sub.t) is computed as follows (block OG to FIM, FIG. 6):

[0143] If the cell is probably free at the time t based on the occupancy grid at the time (OG.sub.t), the value of the free inverse model index is determined by way of the function h(w.sub.t) that returns a positive value. The index of the free inverse model is equal to zero in the other cases, that is to say:

[00012]$n\left(f_t.Math.w_t\right)=\{\begin{array}{cc}h\left(w_t\right)>0& \mathrm{if}n\left(o_{i,t}.Math.z_t\right)<0\\ 0& \mathrm{otherwise}\end{array}$ [0144] n(o.sub.i,t|z.sub.t) corresponds to the probability index in the occupancy grid of the cell i:OG.sub.t(i)=n(o.sub.i,t|z.sub.t)

[0145] According to one embodiment, the function h(w.sub.t) returns a constant value ?.sub.FG>0.

[0146] As a variant, it is possible to define h(w.sub.t)=?n(o.sub.i,t|z.sub.t)

[0147] Or else, according to another variant:

[00013]$n\left(f_t.Math.w_t\right)=\{\begin{array}{cc}\max \left(-n\left(o_{i,t-1}.Math.z_{t-1}\right),-n\left(o_{i,t}.Math.z_t\right)\right)& \mathrm{if}n\left(o_{i,t-1}.Math.z_{t-1}\right)<0\\ -n\left(o_{i,t}.Math.z_t\right)& \mathrm{otherwise}\end{array}$

[0148] The generation of a combined grid resulting from the combination of the static space grid SG.sub.t and of the free space grid FG.sub.t may be implemented using the integer binary Bayesian filters, as illustrated in FIG. 7, the combination in this case taking place between the probability indices n(s.sub.t|w.sub.1:t) and n(f.sub.t|w.sub.1:t), so as to obtain an index n(?.sub.t|w.sub.1:t) for each cell of the combined grid.

[0149] In this case, using the integer binary Bayesian filters, each cell i of the combined grid CG.sub.t may be calculated by the following Bayesian fusion:

[00014]${\mathrm{CG}}_t\left(i\right)\stackrel{?}{=}{\mathrm{SG}}_t\left(i\right)-{\mathrm{FG}}_t\left(i\right)$

[0150] Thus, according to the sign of CG.sub.t(i): [0151] if CG.sub.t(i)>0, the cell i is probably static given the sequence of pairs of occupancy grids w.sub.1:t [0152] if CG.sub.t(i)<0, the cell is probably free, [0153] if CG.sub.t(i)=0, the cell is neither free nor static.

[0154] The estimate that prevails between the estimate of the static space grid SG.sub.t and the estimate of the free space grid FG.sub.t is thus looked at.

[0155] As a variant, it is possible to apply a maximum value criterion. Each cell i of the combined grid CG.sub.t may thus be computed as follows:

[00015]${\mathrm{CG}}_t\left(i\right)\stackrel{?}{=}\{\begin{array}{cc}-{\mathrm{FG}}_t\left(i\right)& \mathrm{if}{\mathrm{FG}}_t\left(i\right)>{\mathrm{SG}}_t\left(i\right)\\ 0& \mathrm{if}{\mathrm{FG}}_t\left(i\right)={\mathrm{SG}}_t\left(i\right)\\ {\mathrm{SG}}_t\left(i\right)& \mathrm{in}\mathrm{other}\mathrm{cases}\end{array}$

[0156] By virtue of using integer binary Bayesian filters, the movement estimate may be carried out in microprocessors, for example with ARM (registered trademark) architectures, whereas in the prior art the estimate is very intensive in terms of computing resources, and usually requires graphics processing units (GPUs).

[0157] FIG. 8 illustrates the complementarity between the method according to the invention and that described in patent application FR3116640. A plurality of sensors (sensor 1, . . . , sensor n). The measurements are fused by implementing the method as described in patent application FR3041451, thereby making it possible to obtain occupancy grids OG (a probability of occupancy per cell). The occupancy grids may be used either to generate the static space and free space grids according to the present invention, or to generate the movement grid described in patent application FR3116640. Nevertheless, the computations to arrive at the movement grid are fundamentally different from those used to arrive at the static space and free space grids, as indicated above.

[0158] The method according to the invention may be implemented by at least one distance sensor, for example a lidar, a radar or even a sonar, or by a camera able to extract distance information from a scene acquired by the sensor.

[0159] The feature grids are established from the distance measurements carried out by the sensor.

[0160] The sensor may be housed on board a mobile device, such as a vehicle, in particular an autonomous vehicle, or else a non-autonomous vehicle, and in this case the method according to the invention makes it possible to assist the driver in detecting obstacles.

[0161] The mobile device may also be any device able to move autonomously, for example a household appliance such as an autonomous vacuum cleaner, or else a gardening appliance such as an autonomous lawnmower.

[0162] The mobile device moreover comprises actuators able to correct the trajectory of the autonomous mobile device on the basis of the characterization of the environment of a mobile device that has been carried out by way of the method according to the invention.

[0163] The invention has essentially been described by discretizing the set of probabilities into a set of finite cardinality, so as not to have to carry out computations using floating-point arithmetic. This provision makes it possible in particular to implement the method according to the invention in an embedded system having severe integration constraints.

[0164] The method according to the invention could also use floating-point arithmetic, in particular if the computational capabilities of the device implementing the method make it possible to carry out the characterization of the environment in real time.