Method for characterizing the environment of a mobile device, producing a static space grid and/or a free space grid

[0001] This application claims priority to foreign French patent application No. FR 2213671, filed on Dec. 16, 2022, the disclosure of which is incorporated by reference in its entirety.

[0002] The invention relates to a method for characterizing the environment of a mobile device (also called a robot hereinafter) using distance sensors. It also relates to a device for implementing such a method.

[0003] The invention may be applied to any type of robot, for example ground robots (autonomous cars), aerial robots (drones), underwater robots, etc.

[0004] A mobile robot navigates through space to carry out a task. To navigate autonomously, the robot has to acquire knowledge about its environment in order to plan a path, avoid collisions and navigate safely. For this purpose, the robot relies on a perception system.

[0005] The perception system retrieves data about the environment through measurements from on-board sensors. A computer model of the environment is then constructed and updated continuously by the perception system based on measurements from sensors. The robot will reason and make navigation decisions based on the environment model.

[0006] Many types of environment model exist in the prior art. One of the most commonly used in robotics is the occupancy grid, initially introduced in the article by H. P. Moravec and A. Elfes “High resolution maps from wide angle sonar”, Proceedings. IEEE ICRA, volume 2, pages 116-121, March 1985. The occupancy grid is a probability grid: each cell has a probability of occupancy, and therefore a value between 0 and 1.

[0007] An occupancy grid is a map of a delimited region of the environment surrounding the robot. The region is subdivided into multiple adjacent sub-regions, called cells.

[0008] A cell may have three dimensions (3D), for example a cube of 10 cm×10 cm×10 cm. It may also be two-dimensional (2D), for example the space delimited by a square of 10 cm×10 cm. The collection of all of the cells forms a grid.

[0009] The objective of the framework defined by the occupancy grid is to compute the probability of a cell being occupied by an obstacle, given the measurements from the on-board sensors. A probability of occupancy of 1 means “the cell is occupied”, 0 means “the cell is free”, and a value between 0 and 1 expresses the uncertainty regarding the occupancy of the cell. In particular, a probability of occupancy of ½ means that the occupancy of the cell is unknown, that is to say that the cell may be free or occupied, without leaning towards one of the two hypotheses.

[0010] Occupancy grids have advantageous properties for a perception system. They constitute a robust method for fusing multiple sensors of various technologies. Patent application FR3041451 provides one example of a multi-sensor fusion method employing integer arithmetic computations.

[0011] Commonly used detection technologies are lidars, radars, cameras and sonars. While cameras give detailed colours and textures, they are limited in darkness. Lidars are able to give a detailed representation of point clouds, but their performance decreases in bad weather (snow, fog or rain).

[0012] Multi-sensor fusion is therefore essential for overcoming the limitation of a given technology. Occupancy grids also make it possible to manage measurement uncertainties and noise through probabilistic approaches.

[0013] Feature grids thus represent free space and the space occupied by one or more tangible bodies. The term “tangible bodies” (or obstacle) denotes any tangible substance or object having individuality and able to be detected and identified by an appropriate sensor.

[0014] Inanimate objects, whether natural or artificial, plants, animals, human beings, but also liquid or solid particles suspended in the air, such as clouds, or even liquid or gaseous masses, are thus considered to be tangible bodies.

[0015] For example, for an autonomous car, common tangible bodies are pedestrians, other cars, buildings, vegetation, cyclists, etc. The tangible bodies may be mobile, that is to say dynamic, or static. The occupancy state of a cell may vary over time. Indeed, a cell may be free for a certain time, and then suddenly occupied by a moving obstacle, and then free again when the obstacle has left. For example, a pedestrian may stand up without moving for a short period and then walk in one direction.

[0016] The standard framework of the feature grids computes the probabilities of occupancy of all of the cells of a grid in each iteration t, taking into account only the instantaneous measurements from the sensors in the same iteration. Let OG_t be the feature grid constructed in iteration t (or at the time t). Let us consider a cell c that has always been estimated as being free by all of the feature grids from OG₁ to OG_t-1.

[0017] In iteration t, let us assume that the cell is temporarily hidden from the sensors by a moving obstacle. The occlusion causes the occupancy state of the cell c to suddenly change from free to unknown in iteration t. This means that the previous estimates have been abruptly forgotten, even though it is possible that the cell c remains free in iteration t while it is temporarily occluded.

[0018] The same effect appears for static cells, that is to say cells occupied by fixed obstacles. These cells are estimated as being occupied as long as they are present in the field of view of the sensors. However, their occupancy state suddenly becomes unknown as soon as they are obstructed by an obstacle, even in motion. However, since they are occupied by a static tangible body (an obstacle), it is possible that these cells remain occupied during the occlusion.

[0019] Many approaches exist in the prior art for taking into account the history of measurements in order to estimate free cells and cells occupied by a static tangible body.

[0020] The most promising approaches consist in using particle filters to separate cells occupied by dynamic obstacles from cells occupied by static obstacles.

[0021] Particle filters are described for example in the article by Nuss, D., Reuter, S., Thom, M., Yuan, T., Krehl, G., Maile, M., Dietmayer, K. (2018) “A random finite set approach for dynamic occupancy grid maps with real-time application”, The International Journal of Robotics Research, 37(8), 841-866. The definition of a particle in these algorithms may differ but, in general, particles are a set of points distributed in space. Particles have position coordinates and a velocity vector.

[0022] A particle also has a weight used to estimate velocity distributions. Between successive iterations, a particle moves at its velocity (modulo the introduction of a random error).

[0023] The basic idea of these algorithms is to randomly spread particles in space such that their movement follows the movement of dynamic tangible bodies. The particles are distributed within the grid such that a large number of particles are present in the cells occupied by dynamic tangible bodies.

[0024] These approaches simultaneously estimate where the free cells are, where the static ones are and where the dynamic ones are, leading to a solution with a high computing burden. These approaches therefore require high-performance computing hardware such as GPUs (Graphics Processing Units) to achieve real-time execution, thereby hampering integration thereof into embedded hardware having more limited computing performance and lower energy consumption, such as microcontrollers.

[0025] The invention therefore aims to provide a method that takes into account the history of measurements in order to estimate free cells and cells occupied by a static tangible body, and which may be integrated into embedded microcontroller hardware.

[0026] One subject of the invention is therefore a method for characterizing the environment of a mobile device, wherein, for each iteration at a time t, the following steps are implemented:

• • [0027] S10) Acquiring a plurality of distance measurements in the environment by way of at least one sensor;
  • [0028] S20) Generating a pair of occupancy grids at the time t−1 and at the time, each grid fusing the distance measurements into a discretized spatial representation of the environment;
  • [0029] S30) Generating a static space grid at the time SG_t, each cell 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, said subsequent probability being computed for each cell by way of a binary Bayesian filter from:
  • [0030] the subsequent probability of said cell being occupied by a static tangible body at the time t−1, said subsequent probability of said cell being occupied by a static tangible body at the time t−1 being injected directly at input of the binary Bayesian filter; what is referred to as a static prediction model comprising 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; and
  • [0031] what is referred to as a static inverse model at the time t that comprises 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;
  • [0032] or
  • [0033] S40) Generating a free space grid at the time, each cell of the free space grid at the time t having a subsequent probability of said cell being free at the time t, said subsequent probability being computed for each cell by way of a binary Bayesian filter from:
  • [0034] the subsequent probability of said cell being free at the time t−1, said subsequent probability of said cell being free at the time t−1 being injected directly at input of the binary Bayesian filter;
  • [0035] 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; and
  • [0036] what is referred to as a free inverse model at the time t that comprises 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.

[0037] Advantageously, step S30) of generating a static space grid and step S40) of generating a free space grid are implemented concomitantly.

[0038] Advantageously, the method comprises a step S50) of generating a combined grid resulting from the combination of the static space grid and the free space grid.

[0039] Advantageously, each cell i of the combined grid is computed by way of the following Bayesian fusion:

[0040] ${\mathrm{CG}}_t\left(i\right)\stackrel{\Delta }{=}F\left({\mathrm{SG}}_t\left(i\right),1-{\mathrm{FG}}_t\left(i\right)\right)$

• • [0041] Wherein F(,) is the Bayesian fusion function, CG_t(i) corresponds to a cell i of the combined grid at the time t, SG_t(i) corresponds to a cell i of the static space grid at the time t, and FG_t(i) corresponds to a cell i of the free space grid at the time t,
  • [0042] And according to the value of CG_t(i):
  • [0043] if CG_t(i)>½, the cell i is probably static given the sequence of pairs of occupancy grids
  • [0044] if CG_t(i)<½, the cell is probably free,
  • [0045] if CG_t(i)=½, the cell is neither free nor static.
    Advantageously:
  • [0046] the subsequent probability of the cell being occupied by a static tangible body at the time t and the static inverse model at the time t are approximated by values belonging to a set of finite cardinality, the values being identified respectively by a probability index n(s_t|w_1:t) and by a static inverse model index n(s_t|w_t);
  • [0047] the subsequent probability of the cell being free at the time t and the free inverse model at the time t are approximated by values belonging to a set of finite cardinality, the values being identified respectively by a probability index n(f_t|w_1:t) and by a free inverse model index n(f_t|w_t).

[0048] Advantageously, the static inverse model index n(s_t|w_t) is computed as follows:

[0049] $n\left(s_t❘w_t\right)=\{\begin{array}{ccc}g\left(w_t\right)>0& \mathrm{if}n\left(o_{i,t-1}❘z_{t-1}\right)>0& \mathrm{and}n\left(o_{i,t}❘z_t\right)>0\\ & 0\mathrm{otherwise}& \end{array}$
The function g(w_t) returning a positive value, n(o_i,t−1|z_t-1) corresponding to the occupancy index of the cell i of the occupancy grid OG_t-1 at the time t−1, and n(o_i,t|z_t) corresponding to the occupancy index of the cell i of the occupancy grid OG_t at the time t.

[0050] Advantageously, the free inverse model index n(f_t|w_t) is computed as follows:

[0051] $n\left(f_t❘w_t\right)=\{\begin{array}{cc}h\left(w_t\right)>0& \mathrm{if}n\left(o_{i,t}❘z_t\right)<0\\ 0& \mathrm{otherwise}\end{array}$
and n(o_i,t|z_t) corresponding to the occupancy index of the cell i of the occupancy grid OG_t at the time t, the function h(w_t) returning a positive value.

[0052] Advantageously, the positive value of the function g(w_t) and the positive value of the function h(w_t) are constant values.

[0053] Advantageously, the positive value returned by the function g(w_t) is equal to max(n(o_i,t−1|z_t-1), n(o_i,t|z_t)).

[0054] Advantageously, the positive value returned by the function h(w_t) is equal to −n(o_i,t|z_t).

[0055] Advantageously, the free inverse model index n(f_t|w_t) is computed as follows:

[0056] $n\left(f_t❘w_t\right)=\{\begin{array}{c}\max \left(-n\left(o_{i,t-1}❘z_{t-1}\right),-n\left(o_{i,t}❘z_t\right)\right)\mathrm{if}n\left(o_{i,t-1}❘z_{t-1}\right)<0\\ -n\left(o_{i,t}❘z_t\right)\mathrm{otherwise}\end{array}$

[0057] Advantageously, the index n(s_t|w_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_t|w_1:t) is obtained by adding integer probability indices, and wherein the index n(f_t|w_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_t|w_1:t) is obtained by adding integer probability indices.

[0058] Advantageously, each cell i of the combined grid (CG_t) is computed by way of the following Bayesian fusion:

[0059] $C{G}_t\left(i\right)\stackrel{\Delta }{=}{\mathrm{SG}}_t\left(i\right),1-F{G}_t\left(i\right)$

• • [0060] CG_t(i) corresponds to a cell i of the combined grid at the time t, SG_t(i) corresponds to a cell i of the static space grid at the time t, and FG_t(i) corresponds to a cell i of the free space grid at the time t,
  • [0061] And according to the value of CG_t(i):
  • [0062] if CG_t(i)>0 the cell i is probably static given the sequence of pairs of occupancy grids (w_1:t)
  • [0063] if CG_t(i)<0, the cell is probably free,
  • [0064] if CG_t(i)=0, the cell is neither free nor static.

[0065] The invention also relates to a method for avoiding a tangible body moving around a mobile body, characterized in that it implements the abovementioned method 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.

[0066] The invention also relates to a device for characterizing the environment of a mobile device, comprising:

• • [0067] 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
  • [0068] 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 the abovementioned method.

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

[0079] 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.

[0080] The set of measurements z_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_c cells of an occupancy grid as described above. Each cell is thus identified by an index i ranging from 1 to N_c.

[0081] The reference z_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

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

[0083] It will be recalled that, for an occupancy grid OG_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”.

[0084] 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_i,t|z_t) represents the probability of occupancy of a cell i given the measurements z_t.

[0085] A new occupancy grid OG_t is thus generated at the time t, and the occupancy grid OG_t-1, generated at the time t−1, is stored in memory in order to be reused for the pair w_t of occupancy grids. w_1:t denotes the sequence (w₁, . . . , w_t) in the present application.

Generation of the Static Space Grid

[0086] In a third step S30, a static space grid SG_t is generated at the time t. The static space grid SG_t is an array of N_c elements, in which:

[0087] $\forall i\in \left\{1,\dots ,N_c\right\},{\mathrm{SG}}_t\left(i\right)=P\left(s_t❘w_{1:t}\right)$

[0088] Each cell SG_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_t|w_1:t) given the sequence of pairs of occupancy grids w_1:t.

[0089] Said subsequent probability P(s_t|w_1:t) is computed for each cell of the static space grid SG_t by way of a binary Bayesian filter, the principle of which is recalled in FIG. 2.

[0090] 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.

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

[0092] 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.

[0093] 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 α.

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

[0095] $P\left(s_t❘w_{1:t-1}\right)=P\left(s_{t-1}❘w_{1:t-1}\right)·\alpha +\left(1-P\left(s_{t-1}❘w_{1:t-1}\right)\right)·\left(1-\alpha \right)$

[0096] Thus, the value of α influences the prediction as follows:

[0097] If α=1, the result of the prediction is P(s_t|w_1:t−1)=P(s_t-1|w_1:t−1), this meaning that s_t keeps the same value as the previous estimate of s_t-1.

[0098] If

[0099] $\alpha =\frac{1}{2},$
the result of the prediction is

[0100] $P\left(s_t|w_{1:t-1}\right)=\frac{1}{2},$
this meaning that the prediction of s_t from s_t-1 results from a completely uncertain estimate of s_t.

[0101] A value of α between ½ and 1 expresses the degree of uncertainty between the previous scenarios.

[0102] 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_t|w_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.

[0103] At each time t, the static inverse model is computed from the pair w_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.

[0104] As illustrated in FIG. 2, the subsequent probability P(s_t-1|w_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.

[0105] 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

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

[0107] Each cell FG_t(i) of the free space grid at the time t thus has a subsequent probability P(f_t|w_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:

• • [0108] the subsequent probability of said cell being free at the time −1 (P(f_t-1|w_1:t−1)), said subsequent probability of said cell being free at the time t−1 (P(f_t-1|w_1:t−1)) being injected directly at input of the binary Bayesian filter;
  • [0109] 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_t|f_t-1)); and
  • [0110] what is referred to as a static inverse model at the time t (P(f_t|w_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.

[0111] 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.

[0112] 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

[0113] As a variant, the static space grid and the free space grid are implemented concomitantly. Thus, in each iteration, a static space grid SG_t and a free space grid FG_t are generated, from the same distance measurements, with the same pairs w_t of occupancy grids.

[0114] Advantageously, in each iteration, the static space grid SG_t and the free space grid FG_t are combined with one another (cell-by-cell combination), so as to obtain a combined grid CG_t (step S50, FIG. 1).

[0115] Each cell i of the combined grid CG_t may be computed by way of the following Bayesian fusion:

[0116] ${\mathrm{CG}}_t\left(i\right)\stackrel{\Delta }{=}F\left({\mathrm{SG}}_t\left(i\right),1-{\mathrm{FG}}_t\left(i\right)\right)$

• • [0117] F (,) represents the Bayesian fusion function.

[0118] Thus, according to the sign of CG_t(i):

• • [0119] if CG_t(i)>½, the cell i is probably static given the sequence of pairs of occupancy grids w_1:t
  • [0120] if CG_t(i)<½, the cell is probably free,
  • [0121] if CG_t(i)=½, the cell is neither free nor static.

[0122] The estimate that “prevails” between the estimate of the static space grid SG_t and the estimate of the free space grid FG_t is thus looked at.

[0123] 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.

[0124] For this purpose, the subsequent probability P(s_t|w_1:t) of the cell being occupied by a static tangible body at the time t is identified by a probability index n(s_t|w_1:t). The subsequent probability P(s_t-1|w_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_t-1|w_1:t−1). Similarly, the static inverse model P(s_t|w_t) at the time t is identified by a static inverse model index n(s_t|w_t). Moreover, it is considered that the static prediction model has a constant value α over time.

[0125] 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.

[0126] The index n(s_t|w_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_t|w_1:t) is obtained by adding integer probability indices.

Algorithm of the Integer Binary Bayesian Filter of the Static Space Grid SG_t.

[0127] The integer binary Bayesian filter IBBF_SG of the static space grid SG_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.

[0128] The initialization function depends on the following input parameters: ϵ_GFSE, Γ_GFSE and α_SG

[0129] ∈_GFSE is a constant that corresponds to the approximation parameter of the sequence (q_n)_n∈Γ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:

[0130] $F\left(x,y\right)=\frac{x·y}{x·y+\left(1-x\right)·\left(1-y\right)}$ ${\left(q_n\right)}_{n\in \mathbb{Z}}=\{\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}$

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

[0132] α_SG is a constant for the initialization function, with ½≤α_SG≤1, and that corresponds to the numerical value of the static prediction model P(s_t|s_t-1).

[0133] 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 Γ_GFSE, and then, for each n in Γ_GFSE, the element predLUT(n) is a probability index computed as follows:

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

[0135] The function approx_policy approximates the result of the operation (q_n·α_SG+(1−q_n)·(1−α_SG)) by an element q_m of the sequence (q_n)_n∈ΓCFSE. It is the index m of q_m that is stored in the element predLUT(n) of the look-up table predLUT.

[0136] The application function for the integer binary Bayesian filter IBBF_SG ApplyFilter(n(s_t-1|w_1:t−1), n(s_t|w_t)) is defined as follows:

• • [0137] Prediction: n(s_t|w_1:t−1)←predLUT(n(s_t-1|w_1:t−1))
  • [0138] Measurement update: n(s_t|w_1:t)←n(s_t|w_1:t−1)+n(s_t|w_t)

[0139] The method according to the invention advantageously computes the static inverse model index n(s_t|w_t) as follows, illustrated by FIG. 5 (block “OG to SIM”):

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

[0141] 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_t) that returns a positive index. Otherwise, the value of the index of the static inverse model is equal to zero.

[0142] n(o_i,t|z_t) corresponds to the probability index in the occupancy grid of the cell i: OG (i)=n(o_i,t|z_t)

[0143] According to one embodiment, the function g(w_t) returns a constant value β_SG>0.

[0144] As a variant, it is possible to define g(n(w_t)=max(n(o_i,t−1|z_t-1), n(o_i,t|z_t).

Algorithm of the Integer Binary Bayesian Filter of the Free Space Grid FG_t

[0145] The integer binary Bayesian filter IBBF_FG of the free space grid FG_t is based on the same principle as the integer binary Bayesian filter IBBF_SG of the static space grid SG_t.

[0146] The subsequent probability of the cell being free at the time t (P(f_t|w_1:t)) is identified respectively by a probability index n(f_t|w_1:t) and the free inverse model at the time t (P(f_t|w_t)) is identified by a free inverse model index n(f_t|w_t).

[0147] As illustrated in FIG. 6, the integer binary Bayesian filter IBBF_FG of the free space grid FG_t computes the probability index n(f_t|w_1:t) iteratively, based on the probability index n(f_t-1|w_1:t−1).

[0148] The initialization function for the filter depends on the following input parameters: ∈_GFSE, Γ_GFSE and α_FG

[0149] The constant ∈_GFSE and the set of indices Γ_GFSE are identical to those used for the integer binary Bayesian filter IBBF_SG of the static space grid SG_t.

[0150] α_FG is a constant, with

[0151] $\frac{1}{2}\le {\alpha }_{\mathrm{FG}}\le 1,$
and that corresponds to the numerical value of the free prediction model P(f_t|f_t-1).

[0152] The details of the computations explained above for the integer binary Bayesian filter IBBF_SG of the static space grid SG_t apply, in the same way, to the integer binary Bayesian filter IBBF^FG of the free space grid FG_t; they are therefore not repeated here.

[0153] The inputs of the application function for the filter IBBF^FG are the probability index n(f_t-1|w_1:t−1) that is computed recursively, with direct feedback from the output of the filter, and the free inverse model index n(f_t|w_t).

[0154] Advantageously, the free inverse model index n(f_t|w_t) is computed as follows (block “OG to FIM”, FIG. 6):

[0155] If the cell is probably free at the time t based on the occupancy grid at the time (OG_t), the value of the free inverse model index is determined by way of the function h(w_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:

[0156] $n\left(f_t❘w_t\right)=\{\begin{array}{cc}h\left(w_t\right)>0& \mathrm{if}n\left(o_{i,t}❘z_t\right)<0\\ 0& \mathrm{otherwise}\end{array}$

• • [0157] n(o_i,t|z_t) corresponds to the probability index in the occupancy grid of the cell i:OG_t(i)=n(o_i,t|z_t)

[0158] According to one embodiment, the function h(w_t) returns a constant value β_FG>0.

[0159] As a variant, it is possible to define h(w_t)=−n(o_i,t|z_t)

[0160] Or else, according to another variant:

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

[0162] The generation of a combined grid resulting from the combination of the static space grid SG_t and of the free space grid FG_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_t|w_1:t) and n(f_t|w_1:t), so as to obtain an index n(κ_t|w_1:t) for each cell of the combined grid.

[0163] In this case, using the integer binary Bayesian filters, each cell i of the combined grid CG_t may be calculated by the following Bayesian fusion:

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

[0165] Thus, according to the sign of CG_t(i):

• • [0166] if CG_t(i)>0, the cell i is probably static given the sequence of pairs of occupancy grids w_1:t
  • [0167] if CG_t(i)<0, the cell is probably free,
  • [0168] if CG_t(i)=0, the cell is neither free nor static.

[0169] The estimate that “prevails” between the estimate of the static space grid SG_t and the estimate of the free space grid FG_t is thus looked at.

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

[0171] ${\mathrm{CG}}_t\left(i\right)\stackrel{\Delta }{=}\{\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}$

[0172] 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).

[0173] 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.

[0174] 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.

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

[0176] 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.

[0177] 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.

[0178] 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.

[0179] 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.

[0180] 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.