ENVIRONMENT SENSING METHOD AND APPARATUS USING A WIDE-ANGLE DISTANCE SENSOR

Abstract

An environment sensing method includes the following steps, carried out by a data processor a) defining an occupancy grid comprising a plurality of cells; b) acquiring at least one measurement result from a distance sensor, representative of the distance of one or more nearest targets; and c) computing an occupation probability of the cells of the occupancy grid by applying to the measurement an inverse sensor model stored in a memory device in the form of a data structure representing a plurality of model grids associated to respective distance measurement results, at least some cells of a model grid corresponding to a plurality of contiguous cells of the occupancy grid belonging to a same of a plurality of angular sectors into which the field of view of the distance sensor is divided, and associating a same occupation probability to each one of the plurality of cells. An apparatus programmed or configured for carrying out the environment sensing method and a computer-implemented method of computing an inverse sensor model suitable for carrying out the environment sensing method are also provided.

Claims

1. An environment sensing method comprising the following steps, carried out by a data processor: a) defining an occupancy grid on a region including a field of view of a distance sensor, the grid comprising a plurality of cells, each having a quantized distance from the sensor; b) acquiring at least one measurement result from the distance sensor, said measurement result being representative of the distance of one or more nearest targets from the sensor; and c) computing an occupation probability of the cells of the occupancy grid by applying to the target distance measurement an inverse sensor model stored in a memory device cooperating with the data processor; wherein the inverse sensor model is stored in the memory device in the form of a data structure representing a plurality of grids, called model grids, associated to respective possible distance measurement results, at least some cells of a model grid corresponding to a plurality of contiguous cells of the occupancy grid belonging to a same of a plurality of angular sectors into which the field of view of the distance sensor is divided, and associating a same occupation probability to each one of said plurality of cells.

2. The method of claim 1, wherein at least some cells of at least one model grid correspond to a plurality of contiguous cells of the occupancy grid belonging to the same angular sector and having different quantized distances from the distance sensor.

3. The method of claim 1, wherein the model grids have a polar geometry and the occupancy grid a Cartesian geometry.

4. The method of claim 1, wherein the inverse sensor model is derived by considering as equivalent all configurations of the occupancy grid comprising at least an occupied cell belonging to a same angular sector and having a same quantized distance from the sensor.

5. The method of claim 4, wherein the inverse sensor model is further derived under the assumption that a detection probability of a target by the sensor depends on the angular position and the angular cross-section of the target as seen from the sensor.

6. The method of claim 1, wherein steps b) and c) are carried out a plurality of times, for a plurality of separate distance measurements, with a same or with different sensors, further comprising: d) computing a consolidated occupancy grid comprising a plurality of cells, each having an occupation probability, by fusing the occupation probabilities computed from said plurality of separate distance measurements.

7. The method of claim 6, wherein at least some of said separate distance measurements correspond to different orientations of a same sensor, two consecutive orientations being separated by less than one half of the angular width of the field of view of the sensor.

8. The method of claim 1, wherein the field of view of the sensor includes at least two cells of the occupancy grid having a same distance from the sensor.

9. An environment sensing apparatus comprising: an input port for receiving at a signal representative of a target distance measurement from a distance sensor; a memory device storing an inverse sensor model; and a data processor configured for receiving said signal and using it for computing an occupation probability of the cells of an occupancy grid defined on a region including a field of view of said distance sensor by applying said or one said inverse sensor model to the signal; wherein the inverse sensor model is stored in the memory device in the form of a data structure representing a plurality of grids, called model grids, associated to respective possible distance measurement results, each cell of a model grid corresponding to a plurality of contiguous cells of the occupancy grid belonging to a same of a plurality of angular sectors into which the field of view of the distance sensor is divided, and associating a same occupation probability to each one of said plurality of cells.

10. The apparatus of claim 9, wherein at least some cells of at least one model grid of the inverse sensor model stored in the memory device correspond to a plurality of contiguous cells of the occupancy grid belonging to the same angular sector and having different quantized distances from the distance sensor.

11. The apparatus of claim 9, wherein the model grids have a polar geometry and the occupancy grid a Cartesian geometry.

12. The apparatus of claim 9, wherein the inverse sensor model is derived by considering as equivalent all configurations of the occupancy grid comprising at least an occupied cell belonging to a same angular sector and having a same quantized distance from the sensor.

13. The apparatus of claim 12, wherein the inverse sensor model is further derived under the assumption that a detection probability of a target by the sensor depends on the angular position and the angular cross-section of the target as seen from the sensor.

14. The apparatus of claim 9, wherein the data processor is configured for receiving a plurality of said signals from a same or from different sensors and for computing a consolidated occupation probability of the cells of the occupancy grid by fusing the occupation probabilities computed from said plurality of signals.

15. A computer-implemented method of computing an inverse sensor model of distance sensor configured for generating a signal representative of the distance of a nearest target, the method comprising the steps of: i. defining an occupancy grid on a region including a field of view of the distance sensor, the occupancy grid comprising a plurality of cells, each having a quantized distance from the sensor; ii. decomposing the field of view of the sensor in a plurality of angular sectors, each comprising a plurality of cells of the occupancy grid having a same quantized distance from the sensor; iii. for every cell of the occupancy grid, computing the probability density of the value taken by the signal generated by the sensor, conditioned by an occupied state of the cell, said probability density being expressed by a sum of contributions corresponding to different states of the occupancy grid for which the cell is occupied; iv. for every cell of the occupancy grid, computing the probability density of the value taken by the signal generated by the sensor, conditioned by an empty state of the cell, said probability density being expressed by a sum of contributions corresponding to different states of the occupancy grid for which the cell is empty; and v. computing the inverse sensor model from the probability densities computed at steps iii. and iv.; and vi. storing the inverse sensor model in a memory device in the form of a data structure representing a plurality of grids, called model grids, associated to respective possible distance measurement results, each cell of a model grid corresponding to a plurality of contiguous cells of the occupancy grid belonging to a same angular sector, and associating a same occupation probability to each one of said plurality of cells; wherein steps iii. and iv. are carried out by considering as equivalent all the configuration of the grid comprising at least an occupied cell belonging to a same angular sector and having a same quantized distance from the distance sensor.

16. The method of claim 15, wherein step v. comprises computing a discrete model associating to each said plurality of cells of the occupancy grid a discrete probability value for each possible measurement result, whereby each cell of each model grid corresponds to a plurality of cells of the occupancy grid belonging to a same angular sector and to which a same discrete probability value is associated.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0035] Additional features and advantages of the present invention will become apparent from the subsequent description, taken in conjunction with the accompanying drawings, wherein:

[0036] FIG. 1, already described, shows an autonomous vehicle equipped with a wide-angle distance sensor suitable for carrying out the invention;

[0037] FIGS. 2 to 6, reproduced from WO2017/050890, illustrate the concept of inverse sensor model, its application to an occupancy grid and its quantification;

[0038] FIGS. 7A-7C, 8A-8C, 9A-9C, 10A-10C and 11A-11C illustrate the direct model of a wide-angle distance sensor;

[0039] FIG. 12 illustrates the decomposition of the field of view of the sensor into angular sectors, allowing the efficient computation of the inverse sensor model;

[0040] FIGS. 13A and 13B illustrate the concept of model grid, used by the inventive environmental sensing method;

[0041] FIG. 14A comprises a flow-chart of an environment sensing method according to an embodiment of the invention and a block diagram of an environment sensing apparatus according to another embodiment of the invention, and FIG. 14B a representation of a model grid illustrating some symbols used in FIG. 14A;

[0042] FIGS. 15A and 15B illustrates a method according to an embodiment of the invention, wherein an angular scanning is performed using a wide-angle distance sensor; and

[0043] FIGS. 16 to 21 are plots illustrating some technical results of the invention.

DETAILED DESCRIPTION

[0044] Before describing the inventive methods and apparatus, it will be expedient to recall some fundamental notions on inverse sensor models and occupancy grids.

[0045] Let d be the real distance between a target and a distance sensor, and z the output of the sensor. Due to unavoidable measurement incertitude, for a given value of d, the value of z will be a random variable characterized by the conditional probability density function p(z|d) which models the relationship between the real position of a target and its estimation seen by the sensor (direct model). FIG. 2 presents an exemplary direct model SM of a sensor; a linear space 50 m long is considered and it is assumed that a target is situated at d=25 m from the sensor. For a sensor with an error which may be modeled by a Gaussian function, the most probable response z will be close to 25 m, but other values will be possible, with a probability density defined by the curve. In the case of an ideal sensor, p(z|d)=(zd), where is a Dirac Delta function, and the measurement would always be equal to the true distance. The direct model of a sensor can be determined in an experimental manner; typically it can be constructed on the basis of data provided by the constructor (in the Gaussian case, the value of the standard deviation suffices to characterize the model).

[0046] An occupancy grid OG is a partition of a continuous and bounded region of space into a number N of parts, called cells and designated by an index i[0, N1]. The cell of index i is indicated by c.sub.i. Only for illustrating the concepts of direct and inverse models, the present discussion will be limited to the case of a one-dimensional occupancy grid observed by a single distance sensor DS (or a plurality of co-located sensors), the index i increasing as the sensors get further away (c.sub.0 therefore being the cell closest to the sensor and c.sub.N-1 the one furthest away). This configuration is illustrated by FIG. 3. The one-dimensional hypothesis is ill-suited to wide-angle sensorsindeed, in a more formal way, a sensor may be considered to be wide angle when more than one cell of the associated occupancy grid are at a same distance from it. Therefore, this limitation will be removed later.

[0047] A target T is a bounded continuous subset of the region of space on which the occupancy grid is defined. A cell c.sub.i is said to be occupied by a target T if Tc.sub.i, to be not occupied by T if Tc.sub.i=. Stated otherwise, if the target covers the cell even partially, the latter is considered to be occupied. Other conventions are possible, but in any event a cell must be either free, or occupied.

[0048] For each of the cells of the grid, one considers the binary random experiment state which can have one of the two outcomes {occupied; vacant} consisting in knowing whether or not the cell contains a target. The state s(c.sub.i) of cell c.sub.i can therefore take two values, o(c.sub.i)cell c.sub.i occupiedand e(c.sub.i)cell c.sub.i empty.

[0049] In a grid, it is considered that all the cells are independent, so that

i,j[0,N1],P(o(c.sub.i)o(c.sub.j))=P(o(c.sub.i)).Math.P(o(c.sub.j))(1)

where is the logical operator and and P() denotes the probability of an event (not to be confused with a probability density, designated by a lower case p).

[0050] A measurement z arising from a sensor makes it possible to determine the probability of occupancy P(o(c.sub.i)|z) of a cell c.sub.i. For a given measurement z, the set of probabilities P(o(c.sub.i)|z)i[0, N1] constitutes the inverse model of the sensor on the grid. Whilst the direct model of the sensor advises regarding the response of the sensor as a function of the material world, the inverse model expresses the impact of the measurement on the occupancy grid which is the model of the material world that is adopted, thereby justifying the term inverse model.

[0051] FIG. 4 presents a typical example of (one dimensional) inverse model ISM.sub.c (index c means that the model is represented by a continuous function) of a distance sensor, in a case where z=25 m. It may be verified that the occupancy probability is quasi-zero for the cells which are situated a distance of less than 24.25 m from the sensor and attains a peak for a distance of 25 m (corresponding to the measurement provided by the sensor). Beyond 25 m, the occupancy probability decreases until it stabilizes at a value of 0.5, indicative of a total ignorance of the occupancy state of the cells which, being situated beyond the target, are masked by the latter and therefore inaccessible to the sensor.

[0052] In accordance with the usage which prevails in the literature, FIG. 4 represents the inverse model by means of a smoothed curve ISM.sub.c. A more correct representation would be to display only the points corresponding to the limits of the cells of the grid: indeed, it is not possible to distinguish a partially occupied cell from another which would be totally occupied, in all cases the distance to the target will be estimated as being the distance to the corresponding cell. This is the spatial error introduced by the grid.

[0053] A more apposite version of the inverse model of FIG. 4, taking account of this spatial quantification induced by the grid is presented in FIG. 5 (line ISM.sub.SD, where SD stands for spatially discretized).

[0054] It should be stressed that the notions of occupancy and of target distance are not entirely equivalent. Indeed, saying that a target is at a sensor distance z does not signify only that a certain cell is occupied, but also that all the other cells of the grid that are closer to the sensor are free (otherwise, the first target would have been seen at a distance of less than z). In the aforementioned FIG. 3, the target A is situated in the cell of index i (black); the cells of index less than i are represented as white to indicate that they are free, those of index greater than i are represented as gray to indicate that their occupancy state is unknown.

[0055] Computing the inverse sensor model for a given occupancy grid starting from the direct sensor model is not a trivial task. A nave algorithm, disclosed by reference [1], has a computational complexity which is exponential in the number of cells of the occupancy grid. This approach relies on Bayes' theorem:

[00001]$\begin{array}{cc}P\left(o\left(c_i\right)|z\right)=\frac{p\left(z|o\left(c_i\right)\right).Math.P\left(o\left(c_i\right)\right)}{p\left(z\right)}& \left(3\right)\end{array}$

[0056] From the decomposition on the two complementary events o(ci) and e(ci), equation (3) becomes:

[00002]$\begin{array}{cc}P\left(o\left(c_i\right)|z\right)=\frac{p\left(z|o\left(c_i\right)\right).Math.P\left(o\left(c_i\right)\right)}{p\left(z|o\left(c_i\right)\right).Math.P\left(o\left(c_i\right)\right)+p\left(z|e\left(c_i\right)\right).Math.P\left(e\left(c_i\right)\right)}& \left(4\right)\end{array}$

Where P(o(c.sub.i)) and P(e(c.sub.i)) evaluate the prior information about the occupancy of cell c.sub.i.

[0057] Equation (4) requires the computation of p(z|o(c.sub.i)) and p(z|e(c.sub.i))i.e. p(z|s.sub.i) for both possible value of s.sub.ifrom the (direct) sensor model.

[0058] Applying the total probability law over all possible grid configurations:

[00003]$\begin{array}{cc}p\left(z|s_i\right)={.Math.}_{G_k^{s_i}}.Math.p\left(z|G_k^{s_i}.Math.s_i\right)& \left(5\right)\end{array}$

where G.sub.k.sup.s.sup.i refers to a grid that has no state information for cell c.sub.i, hence G.sub.k.sup.S.sup.is.sub.i represents the configuration of a grid where the state of cell c.sub.i is set to s.sub.i and the state of the other cells are enforced by G.sub.k.sup.s.sup.i.

[0059] Although p(z|G.sub.k.sup.s.sup.is.sub.i) can be derived from the direct sensor model, eq. (5) involves a sum of 2.sup.N-1 terms, N being the number of cells of the occupancy grid. In practice, therefore, the problem may easily become intractable.

[0060] WO2017/050890 has introduced a simplified algorithm having a linear complexity, but only under the single-target hypothesis. One contribution of the present invention, which will be described later, is a linear-complexity algorithm for computing the inverse sensor model under hypothesis which are more general and mode suitable to wide-angle sensors.

[0061] The inverse sensor model of FIG. 5 is spatially discrete, but the conditional probability P(o|z) can take any value out of the continuous interval [0, 1]. In a practical, digital implementation, probability values also need to be quantized. WO2017/050890 shows that some particular, non-uniform, quantification schemes allows a dramatic simplification of the computations required for fusing togetheri.e. combiningthe information provided by several distance measurements issued from a same or different sensors. One of these quantification schemes is based on a countable set S.sub.k of probability values given by the union of the following subsets:

[00004]$\begin{array}{cc}{S}_k^{-}=\left\{\frac{1}{2-k.Math.n},n0\right\}& \left(6.Math.a\right)\\ S_k^{+}=\left\{\frac{k.Math.n+1}{k.Math.n+2},n0\right\}& \left(6.Math.b\right)\end{array}$

where k is a positive integer (k*). S.sub.k quantize the interval [0, 1] in a non-uniform manner, with a quantization spacing which is large near the value 0.5 and smaller and smaller on approaching the values 0 and 1. This is doubly advantageous, since: [0062] a probability of 0.5 indicates uncertain occupancy; it is therefore not useful to be very precise around this value; on the other hand, precision is useful in proximity to the extreme values 0 and 1; [0063] beyond a certain value of Ink, the discrete probability values get extremely close together; the error introduced by truncating the set is therefore negligible.

[0064] Another family of probability quantification scheme is defined by recursion:

[00005]$\begin{array}{cc}{p}_0=0,5;.Math..Math.p_1=p;.Math..Math.p_2=F\left(p,p\right);.Math..Math.p_3=F\left(p_2,p\right);.Math..Math.\mathrm{.Math.}.Math..Math.p_{n+1}=F\left(p_n,p\right).Math..Math.p_{-1}=1-p;.Math..Math.p_{-2}=F\left(p_{-1},p_{-1}\right);.Math..Math.p_{-3}=F\left(p_{-2},p_{-1}\right);.Math..Math.\mathrm{.Math.}.Math..Math.p_{n-1}=F\left(p_n,p_{-1}\right)& \left(6.Math.c\right)\end{array}$

where p is a parameter satisfying 0.5<p<1 and

[00006]$\begin{array}{cc}F\left(p_i,p_j\right)=\frac{p_i.Math.p_j}{p_i.Math.p_j+\left(1-p_i\right).Math.\left(1-p_j\right)}& \left(6.Math.d\right)\end{array}$

[0065] FIG. 6 illustrates two possible ways of quantizing the continuous inverse model of FIG. 5 (curve ISM.sub.c). A first possibility consists in replacing the values of the inverse model with the closest elements of S.sub.k, so as to minimize the quantization error (curve ISM.sub.1) It is seen that this approach may lead to under-estimating the probability of occupancy of a cell, which might not be acceptable in a target detection application. An alternative possibility consists in approximating the values of the theoretical inverse model by the smallest upper bound of S.sub.k (curve ISM.sub.2). Thus the occupancy probability is never under-estimated, which may be an advantage for the detection of targets. In other applications, such as people counting, this type of approximation may on the other hand lead to the generation of false-positives.

[0066] It will be noted that quantizing the probability values has the consequence that several contiguous cells, to which a continuous inverse sensor model would attribute slightly different occupation probability values, take a same quantized occupation probability value. As it will be discussed in greater detail, this is exploited by some embodiments of the present invention.

[0067] In the following, the properties of a direct sensor model (SM for short) suitable for wide-angle distance sensors will be discussed with reference to FIGS. 7A-7C, 8A-8C, 9A-9C, 10A-10C and 11A-11C. The use of such a sensor model for computing an inverse sensor model (ISM) with linear computational complexity will then be described with reference to FIG. 12. Next, the application of this ISM for performing environmental sensing will be described with the help of FIGS. 13A, 13B, 14A and 14B.

[0068] The proposed sensor model makes use of 4 hypotheses, namely: [0069] H.sub.1: a larger Cross Section of target T (CS, see FIGS. 7B, 8B, 9B, 10B, 11B, where the Cross Section is highlighted in grey) leads to a higher probability of detection P.sub.D and in consequence to a smaller probability of Miss-Detection P.sub.MD; [0070] H.sub.2: a target located on the principal axis of the sensor is more likely detected than when it is located towards the sides of the sensor measurement cone [0071] H.sub.3: a maximal probability of detection P.sub.D.sup.max occurs when the Cross Section of the target covers the entire measurement cone width of the sensor; [0072] H.sub.4: P.sub.D.sup.max is used to compute P.sub.D based on equations (11)-(16), see hereafter.

[0073] These hypotheses will be validated in the result section.

[0074] A direct formulation of the Inverse Sensor Model, also called occupancy model; is given based on equations (4) and (5) without any approximation. It is implemented using a sectoral decomposition of the sensor beam. Let us consider, to begin with, the case of a sensor having a wide angle (e.g. >15) field of view FOV, within which several targets may be situated. Under the nearest-target hypothesis, the sensor measurement may be caused:

[0075] either by the nearest target(s),

[0076] or by a missed detection.

[0077] Both cases can be associated to a probability of detection P.sub.D and of missed detection P.sub.MD, respectively.

[0078] Let us now review the factors that influence the SM. First, the angular position is expected to play a role in determining these probabilities. A target T located on the sensor principal beam axis at distance x (see FIG. 9A) will more likely be detected in comparison to the situation where it is located towards the sides at the same distance (FIG. 10A), generating then a higher P.sub.D and a smaller P.sub.MD.

[0079] A second impacting factor is the target Cross Section (CS), which seems neglected in the literature. For example: [0080] the target in FIG. 7A has a larger CS than the one in FIG. 9A even if both targets are identical in shape. Hence, the target in FIG. 7A will more likely reflect the signal emitted by the sensor than the one in FIG. 9A, yielding a higher P.sub.D.

[0081] Targets T.sub.a, T.sub.b, T.sub.c, T.sub.d in FIG. 10A have a larger combined CS=CS.sub.1+CS.sub.2 than the target T in FIG. 9A. However, it cannot be directly stated if they have a higher or lower P.sub.D. In fact, targets in FIG. 10A are located at a poor reflecting area (towards the side of the sensor). On the contrary, the target in FIG. 9Aa is located on the principal beam axis.

[0082] Therefore, it is clear that the CS of an object and its angular position in the sensor FOV interplay on P.sub.D and P.sub.MD.

[0083] FIGS. 7A-11A show one or more targets at different positions inside the FOV of a distance sensor, FIGS. 7B-11B, the computation of the corresponding cross sections, and FIGS. 7C-11C that of the associated measurement probabilities p(z|x) determined by the sensor model, x being the distance of the nearest target from the sensor and z.sub.max the measurement value corresponding to the maximum measurable distance.

[0084] Let T={t.sub.i; i=1, . . . , N.sub.T} be the set of N.sub.T targets located in the sensor FOV and (T)={t.sub.1, . . . , t.sub.M} the set of the M nearest targets at range r* with:

r*=r(t.sub.1)=r(t.sub.2)= . . . =r(t.sub.M)

r(t.sub.i) being the distance of target t.sub.i from the sensor.

[0085] Here, it will be assumed that M obstacles can be located at the nearest distance r* in the measurement cone, which can happen as the sensor has a large field of view.

[0086] The SM is represented by the probability distribution function p(z|T) where z is the sensor measurement. However, since the nearest-target hypothesis is adopted, the SM is simplified to p(z|(T)). If the two probabilities P.sub.D and P.sub.MD associated to (T) are known, a convenient formulation of the SM is:

[00007]$\begin{array}{cc}p\left(z|\left(T\right)\right)=\frac{P_D}{{}_{r^{*}}.Math.\sqrt{2.Math.}}.Math.e^{\frac{-{\left(z-r^{*}\right)}^2}{2.Math.{}_r*2}}+\frac{P_{\mathrm{MD}}}{\hat{}.Math.\sqrt{2.Math.}}.Math.e^{\frac{-{\left(z-z_{\mathrm{ma}.Math..Math.x}\right)}^2}{2.Math.{\hat{}}^2}}& \left(7\right)\end{array}$

where z.sub.max is the maximum range returned by the sensor when there is a missed detection. Here, the sensor is supposed to have a Gaussian model and .sub.r* and {circumflex over ()} are the standard deviations in the case of detection and missed detection, respectively. Notice that if P.sub.D is known, one can directly deduce P.sub.MD because these probabilities are associated to two complementary events and

P.sub.MD=1P.sub.D(8)

[0087] Thus, only the formulation of P.sub.D is now detailed, taking into account the reasoning that has been introduced above.

[0088] For i{1, . . . , M}, let (t.sub.i) be the CS of target t.sub.i within the sensor cone.

[0089] From now on, and without loss of generality, the study will be restricted to the two dimensional space. Therefore, the CS is restrained between two angular beams .sub.min(t.sub.i) and .sub.max(t.sub.i).

[0090] Let us define:

(t.sub.i)=[.sub.min(t.sub.i),.sub.max(t.sub.i)](9)

that depends at the same time on the CS and the angular position of the target in the sensor cone. ((T)) is also defined as:

[00008]$\begin{array}{cc}\left(\left(T\right)\right)=\underset{t\left(T\right)}{.Math.}.Math.\left(t\right)& \left(10\right)\end{array}$

[0091] If

[00009]$\left(\left(T\right)\right)=\left[-\frac{}{2},\frac{}{2}\right],$

where is the width of the sensor cone, then P.sub.D takes its maximum value, denoted by P.sub.D.sup.max (see FIGS. 11a-c). In fact, in this case the nearest target(s) has (have) the maximum possible CS within the sensor FOV. Therefore, it has (they have) the maximum reflection rate.

[0092] In order to determine the general formulation of P.sub.d, and taking into account the value of P.sub.D.sup.max, it will be proceeded as follows. First, * is defined as the solution over all *.sup.+ verifying the following equation:

[00010]$\begin{array}{cc}{}_{-/2}^{/2}.Math.\frac{1}{.Math.\sqrt{|2.Math.}}.Math.e^{\frac{-{}^2}{2.Math.{}^2}}.Math.d.Math..Math.=P_D^{\mathrm{ma}.Math..Math.x}& \left(11\right)\end{array}$

* can be found by noting that the previous equation is equivalent to:

[00011]$\begin{array}{cc}P\left(.Math..Math.<\frac{}{2}\right)=P_D^{\mathrm{ma}.Math..Math.x}& \left(12\right)\end{array}$

where follows a normal distribution N(0, .sup.2). However, it is known that there exists k* in *.sup.+ verifying:

[00012]$\begin{array}{cc}\frac{}{2}=k^{*}.Math.& \left(13\right)\end{array}$

[0093] It is a known result that:

P(||<k*)=2(k*)1(14)

where () is the cumulative distribution function of the standard normal law. Thus, the problem of finding * is equivalent to finding k**.sup.+ verifying:

2(k*)1=P.sub.D.sup.max(15)

[0094] Then, the value of verifying eq. (13) for the deduced value of k* will be the solution *. Note that the solution k**.sup.+ for the previous equation can be easily found numerically using the quantile function of the standard normal distribution. Therefore, * is deduced.

[0095] Now that * is computed, for

[00013]$\left[-\frac{}{2},\frac{}{2}\right],$

let us define the distribution:

[00014]$\begin{array}{cc}\left(\right)=\frac{1}{{}^{*}.Math.\sqrt{2.Math.}}.Math.e^{-\frac{{}^2}{2.Math.{}^{*2}}}& \left(16\right)\end{array}$

[0096] The () distribution reflects the angular uncertainty of the sensor. Finally, the probability of detection P.sub.D is computed as follows:

[00015]$\begin{array}{cc}{P}_D=\underset{t\left(T\right)}{.Math.}.Math.{}_{\left(t\right)}.Math.\left(\right).Math.d.Math..Math.& \left(17\right)\end{array}$

[0097] In fact, the previous equation sums up the areas between the x-axis and the function over all the intervals (t) for t(T). Thus, this methodology takes into account not only the angular uncertainty but also the CS of the nearest targets.

[0098] A more accurate formulation of the sensor model may be obtaining by taking further types of sensor noise into account, such as specular reflection or cross-talk. Moreover, the decrease of the value of P.sub.D.sup.max when the range increases could also be accounted for. All these improvements fall within the scope of the invention.

[0099] The Sensor Model presented here has been validated in real experiments, as it will be discussed later with reference to FIGS. 15 to 21.

[0100] The ISM formulation for multi-target sensors based on the nearest-target hypothesis is now presented. The aim is to compute the probability of occupancy of each cell in the two-Dimensional (2D) grid G based on equations (4) and (5) and given measurement z.

[0101] To compute p(z|s.sub.i) for i{0, . . . , N1} based on eq. (5), one has to sum up p(z|G.sub.k.sup.s.sup.is.sub.i) over all possible grid configurations G.sub.k.sup.s.sup.i, k=1, . . . , 2.sup.N-1. However, using the nearest-target hypothesis, it can be noticed that different configurations of the grid might share the same value of p(z|G.sub.k.sup.s.sup.i) for a certain value k{1, . . . , 2.sup.N-1}. In fact, two grids having the same set will have the same SM. Thus, the sum in (5) can be reduced by factorizing these grid configurations. This is demonstrated in the sequel.

[0102] Let us first introduce extra notations.

[0103] For i{1, . . . , N1}, denote r(c.sub.i) and (c.sub.i) the distance from cell c.sub.i to the sensor and its CS, respectively. In the present study, the sensor is located at the origin of the grid and its principal axis corresponds to the y axis of the grid.

[0104] Let r.sub.min be the minimum of {r(c.sub.i)}.sub.i=0.sup.N-1 and r.sub.max its maximum. For each range r[r.sub.min; r.sub.max], let define C(r)={c; c and r(c)=r} representing the cells at range r. Finally, for a set of cells A verifying r(c)=r(A)cA for r(A).sup.+ (i.e. all the cells in A are at the same distance to the sensor denoted by r(A).sup.+), let define G(A) as a configuration grid where (G(A))=A. In other terms, all the cells which have a smaller range than r(A) in G(A) are empty, those having a range r(A) are occupied if and only if they are in A, and the cells having a higher range than r(A) cells can have any state (occupied or empty).

[0105] For a realistic implementation of this ISM, a uniform decomposition of the field of view into B angular sectors (sectoral decomposition) w.sub.i, i=1, . . . , B for B.sup.+ is now considered. FIG. 12 shows the decomposition of the field of view FOV of a sensor into B=5 angular sectors AS.sub.2, AS.sub.1, AS.sub.0, AS.sub.1, AS.sub.2 of a same angular width. It is preferred, but not essential, that B is odd. Also, it is preferred, but not essential, that all the angular sectors have a same width.

[0106] The new formulation of the ISM based on the decomposition of the FOV will be first detailed, then the computational complexity will be discussed.

[0107] The main idea is that, instead of taking into account all the possible cell state combinations at each distance r[r.sub.min; r.sub.max], as in the naf approach, only the state combinations of w.sub.m.sup.r, m=1, . . . , B are considered. Here, w.sub.m.sup.r represents the set of cells at distance r in sector w.sub.m, i.e. w.sub.m.sup.r={c;cw.sub.m and r(c)=r}. w.sub.m.sup.r is considered occupied if there exists at least one occupied cell that belongs to it.

[0108] For m{1, . . . , B} and r[r.sub.min; r.sub.max], let o(w.sub.m.sup.r) be the event that w.sub.m.sup.r is occupied and e(w.sub.m.sup.r) is the event that w.sub.m.sup.r is not occupied (i.e. it is empty). For a given set T.sub.r={s(w.sub.1.sup.r), . . . , s(w.sub.B.sup.r)}, where s(w.sub.m.sup.r){o(w.sub.m.sup.r),e(w.sub.m.sup.r)} for m{1, . . . , B}, let G(T.sub.r) be a configuration grid where (G(T.sub.r))={c;cw.sub.m.sup.r; m{1, . . . , B} and s(w.sub.m.sup.r)=o(w.sub.m.sup.r)}. Using the FOV decomposition into angular sectors, p(z|o(c.sub.i)) is given by:

[00016]$\begin{array}{cc}p\left(z|o\left(c_i\right)\right)=\underset{r_{m.Math..Math.i.Math..Math.n}rr\left(c_i\right)}{.Math.}.Math.\underset{T{}_r^{w\left(c_i\right)}}{.Math.}.Math.p|\left(z|G\left(T\right).Math.o\left(w\left(\left(c_i\right)\right)\right)\right).Math.P\left(G\left(T\right)\right)& \left(18\right)\end{array}$

where .sub.r.sup.w(c.sup.i.sup.) is the set containing all the possible state combinations of w.sub.m.sup.r, m{1, . . . , B} excluding w(c.sub.i), and w(c.sub.i) denotes the sector which contains cell c.sub.i in the following set {w.sub.m.sup.r(c.sup.i.sup.), m{1, . . . , B}}.

[0109] For a fixed distance R[r.sub.min; r(c.sub.i)] and for T.sub.r.sup.w(c.sup.i.sup.), the term p(z|G(T)o(w((c.sub.i)))) in (18) can be directly deduced from the SM:

p(z|G(T)o(w((c.sub.i))))=k(19)

where:

[00017]$\begin{array}{cc}=\frac{P_D^{T,i}}{{}_R.Math.\sqrt{2.Math.}}.Math.e^{\frac{-{\left(z-R\right)}^2}{2.Math.{}_R^2}}+\frac{P_{\mathrm{MD}}^{T,i}}{\hat{}.Math.\sqrt{2.Math.}}|e^{\frac{-{\left(z-z_{\mathrm{ma}.Math..Math.x}\right)}^2}{2.Math.{\hat{}}^2}}& \left(20\right)\end{array}$

[0110] In this case, P.sub.D.sup.T,i is computed as before. The main difference is that the combined CS takes into account all cells in each occupied sector in T if R<r(c.sub.i) and all cells of Tw(ci) if R=r(c.sub.i).

[0111] Besides, P(G(T)) in (18) is equal to the probability of intersection of the following events:

[0112] 1. all the cells at a distance smaller than R are empty. The probability of this event is denoted by P.sub.1.sup.R,T and is equal to:

[00018]$\begin{array}{cc}{P}_1^{R,T}=\underset{c{.Math.}_{r<R}.Math.C\left(r\right)}{.Math.}.Math.P\left(e\left(e\right)\right)& \left(21\right)\end{array}$

[0113] 2. at least one cell is occupied in each occupied sector of T. The probability of this event is denoted by P.sub.2.sup.R,T and is equal to:

[00019]$\begin{array}{cc}{P}_2^{R,T}=\underset{w;o\left(w\right)T}{.Math.}.Math.\left\{1-\underset{cw|}{.Math.}.Math.p\left(e\left(c\right)\right)\right\}& \left(22\right)\end{array}$

[0114] 3. all cells in the empty sectors of T are empty. The probability of this event is denoted by P.sub.3.sup.R,T and is equal to:

[00020]$\begin{array}{cc}{P}_3^{R,T}=\underset{cw;e\left(w\right)T}{.Math.}.Math.P|\left(e\left(c\right)\right)& \left(23\right)\end{array}$

[0115] Thus, in this case P(G(T))=P.sub.1.sup.T,A.Math.P.sub.2.sup.T,A.Math.P.sub.3.sup.T,A. Finally,

[00021]$\begin{array}{cc}p\left(z|o\left(c_i\right)\right)=\underset{r_{m.Math..Math.i.Math..Math.n}rr\left(c_i\right)}{.Math.}.Math.\underset{T{}_r^{w\left(c_i\right)}}{.Math.}.Math.P_1^{r,T}.Math.P_2^{r,T}.Math.P_3^{r,T}.Math.p\left(z|G\left(T.Math.o\left(w\left(\left(c_i\right)\right)\right)\right)\right)& \left(24\right)\end{array}$

[0116] As before, using the sectoral decomposition, p(z|e(c.sub.i)) can be written as:

[00022]$\begin{array}{cc}p\left(z|e\left(c_i\right)\right)=\underset{r_{m.Math..Math.i.Math..Math.n}rr\left(c_i\right)}{.Math.}.Math.\underset{T{\stackrel{.}{}}_r^{w\left(c_i\right)}}{.Math.}.Math.p\left(z|G\left(T\right).Math.e\left(c_i\right)\right).Math.P\left(G\left(T\right)\right)& \left(25\right)\end{array}$

where .sub.r.sup.c.sup.i is the set containing all the possible state combinations of w.sub.m.sup.r, m{1, . . . , B} excluding the effect of the state of c.sub.i.

[0117] For a fixed distance R[r.sub.min; r.sub.max] and for T.sub.R.sup.c.sup.i, the term p(z|G(T)e(c.sub.i)) in (25) can be directly deduced from the SM:

p(z|G(T)e(c.sub.i))=k(26)

where

[00023]$\begin{array}{cc}=\frac{P_D^{T,i}}{{}_R.Math.\sqrt{2.Math.}}.Math.e^{\frac{-{\left(z-R\right)}^2}{2.Math.{}_R^2}}+\frac{P_{\mathrm{MD}}^{T,i}}{\hat{}.Math.\sqrt{2.Math.}}|e^{\frac{-{\left(z-z_{\mathrm{ma}.Math..Math.x}\right)}^2}{2.Math.{\hat{}}^2}}& \left(27\right)\end{array}$ [0118] P.sub.D.sup.T,i and P.sub.MD.sup.T,i are computed following the same reasoning as before. The combined CS takes into account all cells in each occupied sector in T.

[0119] Besides, P(G(T)) in (25) is equal to the probability of intersection of the following events:

[0120] 1. all the cells at a distance smaller than R are empty. The probability of this event is denoted by P.sub.1.sup.R,T and is equal to:

[00024]$\begin{array}{cc}{P}_1^{R,T}=\underset{c{.Math.}_{r<R}.Math.C\left(r\right)}{.Math.}.Math.P\left(e\left(c\right)\right)& \left(28\right)\end{array}$

[0121] 2. at least one cell is occupied in each occupied sector of T. The probability of this event is denoted by P.sub.2.sup.R,T and is equal to:

[00025]$\begin{array}{cc}{P}_2^{R,T}=\underset{w;o\left(w\right)T}{.Math.}.Math.\left\{1-\underset{cw|}{.Math.}.Math.p\left(e\left(c\right)\right)\right\}& \left(29\right)\end{array}$

[0122] 3. all cells in the empty sectors of T are empty. The probability of this event is denoted by P.sub.3.sup.R,T and is equal to:

[00026]$\begin{array}{cc}{P}_3^{R,T}=\underset{cw;e\left(w\right)T}{.Math.}.Math.P|\left(e\left(c\right)\right)& \left(30\right)\end{array}$

[0123] In (28), (29) and (30), the probability P(e(c.sub.i)) is equal to 1 since c.sub.i is known to be empty. Finally, P(G(T))=P.sub.1.sup.T,A.Math.P.sub.2.sup.T,A.Math.P.sub.3.sup.T,A, and p(z|e(c.sub.i)) can be written as:

[00027]$\begin{array}{cc}p\left(z|e\left(c_i\right)\right)=\underset{r_{m.Math..Math.i.Math..Math.n}r{r}_{\mathrm{ma}.Math..Math.x}}{.Math.}.Math.\underset{T{\hat{}}_r^{c_i}}{.Math.}.Math.P_1^{r,T}.Math.P_2^{r,T}.Math.P_3^{r,T}.Math.p\left(z|G\left(T\right).Math.e\left(c_i\right)\right)& \left(31\right)\end{array}$

[0124] Applying the sectoral decomposition, the computation of P(o.sub.i|z), i0, . . . , N1 (respectively, P(e.sub.i|z)) requires less than

[00028]$\frac{N}{B}.Math.2^B$

operations because only the combination of B sectors is considered at each range. Therefore, the complexity is linear with respect to N.

[0125] The sectoral decomposition technique supposes that the Sensor Model generated by considering only one nearest occupied cell in a sector is the same as the one generated by considering that all the nearest cells in the sector are occupied. When B increases, in such a way that only one nearest occupied cell is located in each sector, the sectoral decomposition is equivalent to the exact formulation of equations (4) and (5), and the computational complexity becomes exponential. The interest of the sectoral decomposition lies in the fact that, depending on the degree of detection required, one can tune the number of sectors in order to avoid unnecessarily complex computations. This kind of trade-off can be useful when free space detection is considered. In that case, detection of occupied regions with a high precision is not crucial. As a consequence, one can choose small values of B, leading to a low-complexity computation. This approach also helps keeping the link between the SM and the ISM for multi-target sensors.

[0126] The ISM defines a probability value for each cell of the occupancy grid and for each possible measurement value z. Up to now, it has been considered that z may assume any value out of a continuous range (see FIG. 2), but for digital implementations it is necessary to quantize it. Therefore, the ISM can be represented as a finite set of grids OG, each having the same structure (shape, size and number of cells) as the occupancy grid OG to be determined as a function of actual measurements. It will be noted that the occupancy grid OG preferably has a Cartesian geometry, which is particularly well-suited for application in which the distance sensor may move, while the sensor model is more easily defined in polar coordinates (see FIG. 12).

[0127] This is illustrated on FIG. 13A for a case where the field of view FOV of the sensor fully or partially overlaps with 138 cells of grid OG. The inverse sensor model will therefore consist of 138.Math.M probability values, where M is the number of possible quantized measurement probability values. This may lead to a significant memory occupation, undesirable in embedded applications.

[0128] However, a more convenient representation of the ISM is possible. First of all it will be recalled that, by construction of the ISM, all the cells of the grid situated at a same distance from the sensor and belonging to a same angular sector, have a same conditioned probability P(o|z) for any z. Therefore, these cells may be grouped together and treated as a same entity. Moreover, as discussed above in reference to FIG. 6, several contiguous cells having different distances from the sensor (i.e. having different radial positions, considering that the sensor is at the origin of a polar coordinate system) may be attributed a same occupation probability value due to probability quantization (cf. FIG. 6); therefore, cells can also be grouped together in the radial direction. As a result, the ISM for a given measurement result may be represented by a coarser grid than the occupancy grid OG, only defined over the field of view of the sensor. This coarse grid, called a model grid MG preferably has a polar geometry and is constituted by macrocells, each corresponding to a plurality of cells of the occupancy grid OG. It should be noted that model grids of a same ISM but corresponding to different measurement results will have a somehow different structure, as the merging in the radial direction will be different from a model grid to another (in the azimuthal direction, on the contrary, all model grids will use a same angular sector decomposition).

[0129] FIG. 13B represents a 20-macrocell model grid MG overlap to an occupancy grid OG. Comparison with FIG. 13A allows reducing the number of probability values to be stored for each model grid (in this specific example, from 138 to 20). According to particular embodiments of the invention, the memory occupation may be further reduced. For instance, only data pertaining to the central angular sector AS.sub.0 may be stored, and probability values for macrocells of the other angular sectors (AS.sub.2, AS.sub.1, AS.sub.1, AS.sub.2) be calculatedeven in real timefrom the stored data. Also, the stored data may not directly represent occupation probabilities, but parameters allowing computing them e.g. as a function of environmental conditions (such as visibility) inputted by a user or acquired through a different sensor.

[0130] It will be noted that some cells of the occupancy grid overlap with several macrocells of the model grid, due to the different geometries of the two grids. The simplest way to deal with this situation is to associate each cell of the occupancy grid to the macrocell with which it has the largest overlap. Other possibilities exist, such as computing a weighted average (but a significantly higher computational cost).

[0131] FIG. 14A simultaneously represents a block diagram of an apparatus for carrying out the inventive environmental sensing method, and the method itself.

[0132] The apparatus comprises a data processor DP and a memory device MD, and has at least an input port IP for receiving measurement signals from one or more distance sensors DS, typically of the wide-angle type.

[0133] Memory device MD is a memory, such as e.g. a flash memory, storing at least one inverse sensor model in the form of a data structure representing a set of model grids, as described above, each one associated to a possible value of a distance measurement from a distance sensor. As explained above, the data structure may not represent directly the model grids, but data allowing a quick calculation thereof.

[0134] Data processor DP may be a microprocessor associated to a memory storing a suitable program (which may coincide with memory device MD or be distinct from it), an Application Specific Integrated Circuit (ASIC), a suitable programmed Field Programmable Gate Array (FPGA), an electronic board comprising one or more of these devices, etc.

[0135] The data processor is configured (i.e. hardwired) and/or programmed in order to compute the occupation probability of the cells of the occupancy grid by applying the ISM stored in the memory device to the target measurement result received from the distance sensor through the input port. The computation is described here below with reference to FIGS. 14A and 14B.

[0136] When a measurement result z is received from the distance sensor, the data processor extracts from memory device MD the model grid MGz associated to said measurement result, and then identifies the macrocell S00 of its central angular sector AS.sub.0 at distance z from the origin O (i). Then (ii) it updates the probability values of all the cells of the occupancy grid which overlap with macrocell S00. In the following step (iii), the probability values of the cells of the occupancy grid overlapping with macrocells Sa.sub.m0 to Sa.sub.M0 (i.e. the macrocells of peripheral angular sector of the model grid, also at distance z from the origin O) are updated as a function of the probability value associated to S00. These operations are then repeated for macrocells closer to the origin (S0b and Sa.sub.mb to S.sub.aMb for b decreasing from 0 to b.sub.m)step (iv)and then for macrocells farther away from O (step v).

[0137] An interesting feature of this method is that several cells of the occupancy grid (all those which overlap with a same macrocell of the model grid) are updated simultaneously. Advantageously, these simultaneous update may be carried out by direct memory access (DMA) device, freeing computational resources of the processor which may be used for treating other macrocells.

[0138] When the first distance measurement result is received, the cells of the occupancy grid are initialized at a prior occupancy probability value (typically 0.5, expressing complete uncertainty). Updating the occupancy grid simply means associating to each cell the probability value of the corresponding model grid macrocell. In general, however, several successive (or simultaneous) measurement results will be acquired. In this case, updating the occupation probabilities requires fusing the occupation probabilities computed from the separate distance measurements to obtain a consolidated occupancy grid. It will be noted that it is the use of several measurements corresponding to different positions and/or orientations of the sensor which allows taking advantage of the full spatial resolution of the occupancy gridwhich is not the case for a single measurement. For instance, a rotating sensor allows performing an angular scanning, acquiring several successive distance measurement corresponding to different orientations of the sensor. Preferably, two consecutive orientations are separated by less than one half of the angular width of the field of view of the sensor, which allows recovering a better angular (azimuthal) resolution than the width of the angular sectors. For an even finer resolution two consecutive orientations may also be separated by less than one half of the angular width of an angular sector.

[0139] Given two distance measurements z.sub.1 and z.sub.2 from two distance sensors (or from the same sensor at different time) sharing a common occupancy grid, the probability fusion is performed using the following equation:

[00029]$\begin{array}{cc}P\left(o_i|z_1,z_2\right)=\frac{\left[1-P\left(o\left(c_i\right)\right)\right].Math.P\left(o\left(c_i\right)|z_1\right).Math.P\left(o\left(c_i\right)|z_2\right)}{\begin{array}{c}\left[1-P\left(o\left(c_i\right)\right)\right].Math.P\left(o\left(c_i\right)|z_1\right).Math.P\left(o\left(c_i\right)|z_2\right)+\\ P.Math.\left(o\left(c_i\right)\right).Math.P\left(e\left(c_i\right)|z_1\right).Math.P\left(e\left(c_i\right)|z_2\right)\end{array}}& \left(32\right)\end{array}$

[0140] Generalization to more than two sensors is immediateit suffices to consider P(o.sub.i|z.sub.1, z.sub.2) as the inverse model of a virtual sensor and to fuse it with the measurement provided by a third sensor, and so on and so forth.

[0141] Document WO2017/050890 teaches a method of performing probability fusion only using integer arithmetic, provided that a suitable ISM quantification schemes (such as the one of equations 6a-6b or 6c-6d) has been used. This method also applies to the present invention.

[0142] The sectoral decomposition technique has been tested on a 2D uniform square grid of length 5 m composed of cells of length 0.2 m. The ISM was evaluated for a sensor measurement z=3 m coming from a typical 2D sensor having a FOV of 15, .sub.r=0.1+0.01r and {circumflex over ()}=0.15. Thus, only the probability of occupancy of cells located in the sensor beam was evaluated.

[0143] The ISM has been computed for 3 values of B, namely, B=1, 3 and 5, respectively. Note that B=1 corresponds to the case where the sensor beam is not partitioned. The results show that for small values of B, the empty space is well detected while the occupied space is mistaken for an undetermined space. When B increases, the probability of occupancy increases, allowing to derive a stronger opinion about the occupied space. This shows that in order to highlight the occupancy space, one has to choose higher values of B, which comes as well with a higher computational complexity. In fact, when B increases, the sectoral decomposition technique will tend to the exact formulation. However, when empty space assessment is essential (for instance in navigation applications), the sectoral decomposition technique when using small values of B is very efficient from a computational point of view because it will requires a very low number of operations.

[0144] The inventive method was also tested in a configuration with three objects t.sub.1, t.sub.2 and t.sub.3 placed in front of the sensor at different positions with ranges r.sub.1=3 m, r.sub.2=8 m and r.sub.3=5 m, see FIG. 15A for the experimental setup. The objective of this experiment was to demonstrate that the proposed ISM together with sectoral decomposition can be used in conjunction with scanning to precisely localize obstacles in the environment and assess free space. 25 scans were performed with a clockwise shift of 1 of the sensor FOV, starting from the position where the principal axis of the sensor cone is aligned with y.sub.0 of FIG. 15A. In FIG. 15B, the occupancy grid obtained after the first, 6th, 12th and 19th steps of the scan, when B=3 are displayed. The last picture of FIG. 15B is obtained by computing a Bayesian Fusion of all the 25 occupancy grids (see WO2017/050890). Note that the three obstacles can be precisely localized thanks to the scanning.

[0145] The VL53L0X sensor from STMicroelectronics has been considered for validation purpose. This sensor is a new generation Time-of-Flight (ToF) laser ranging module. Its 940 nm VCSEL emitter (Vertical Cavity Surface-Emitting Laser) is eye safe. It can measure an absolute distance till a target up to 2 m. Even if it has not specifically been designed to address Automotive applications, the VL53L0X sensor is considered here because a sensing range of 2 m is of interest for precise positioning applications such as for instance assistance car park. The VL53L0X presents a multi-target behavior with a large Field-of-View of 25. Measurement analyses provided in the sensor datasheet correspond to a complete Field-of-View coverage. However, when targets are angularly separated in the sensor measurement cone, with similar reflectance, the distance provided by the sensor is the one to the nearest obstacle. Note that when two obstacles t.sub.1 and t.sub.2 exhibit close angular positions but with different ranges r.sub.1r.sub.2, the measurement provided by the sensor may be faulty, i.e. zr.sub.1 and zr.sub.2.

[0146] In the tests performed during the experiments, the obstacles consisted of rectangular card boards having a length of 40 cm with variable widths.

First Experiment: Influence of the Target Angular Position in the Sensor Cone

[0147] The first experiment was conducted using a cardboard having a width of 10 cm. The cardboard was placed in 4 different distances from the sensor, namely, d1=0.5 m, d2=0.75 m, d3=1 m and d4=1.25 m. It was also placed in 5 different angular positions with respect to the principal axis of the sensor measurement cone, namely, .sub.1=0, .sub.2=3, .sub.3=5, .sub.4=9 and .sub.5=12.5. An experimental Probability of Detection was computed for each case based on the following equation:

[00030]$\mathrm{PD}=1-\frac{\mathrm{Number}.Math..Math.\mathrm{of}.Math..Math.\mathrm{missed}.Math..Math.\mathrm{measurements}}{\mathrm{Total}.Math..Math.\mathrm{number}.Math..Math.\mathrm{of}.Math..Math.\mathrm{measurements}}$

[0148] where a measurement is considered to be missed if it is larger than the maximal possible range returned by the sensor, denoted by z.sub.max.

[0149] The results provided in FIG. 16 allowed to evaluate against hypotheses H.sub.1 and H.sub.2. The Probability of Detection obtained with the target at a fixed distance d.sub.i, i{1, 2, 3, 4} was analyzed with respect to its angular position in the sensor FOV. As it can be noticed, this probability decreases when the target reaches an angular position towards the sides of the sensor measurement cone, proving that H.sub.2 is true. On the other hand, when the results related to the four distances for a fixed angular position .sub.i, i{1, 2, 3, 4} are compared, one can notice that when the distance increases (leading to a smaller CS), the probability of detection P.sub.D is decreasing. This proves that hypothesis H.sub.1 is true.

Second Experiment: Influence of Target CS on P.SUB.D

[0150] Hypothesis H.sub.1 is highlighted on FIG. 17, showing results from the second experiment.

[0151] Here, three cardboards with width respectively equal to w1=5 cm, w2=9 cm and w3=18 cm were placed on the principal axis of the sensor FOV (i.e. =0) at four different distances, namely, d1=0.5 m, d2=0.75 m, d3=1 m and d4=1.25 m. Comparing the value of P.sub.D for a fixed distance d.sub.i, i{1, 2, 3, 4} for the three different widths, it can be clearly noticed that when the width increases, generating a larger CS, the probability of detection P.sub.D increases too.

Third Experiment: Maximal Probability of Detection P.SUB.D..SUP.max

[0152] The third experiment was conducted using cardboards occupying the entire section of the sensor measurement cone for different distances ranging from 0.5 m to 2.3 m (see FIG. 18). When the target CS covers the entire conic section at a certain distance d, the probability of detection of the cardboard corresponds to the maximal probability of detection that occurred at the same distance (compared to the previous obtained values). FIG. 18 also shows that this maximum probability depends on the distance. Hypothesis H.sub.3 is therefore verified.

Fourth Experiment: Relation Between P.SUB.D .and P.SUB.D..SUP.Max

[0153] Finally experiments using cardboards of width 5 cm and 10 cm were conducted to check the validity of hypothesis H.sub.4. The values of the experimental probability of detection P.sub.D,real at a distance of 50 cm and 1 m, respectively, are plotted in terms of the theoretical probability of detection P.sub.D,th in FIGS. 19 and 20, respectively. These figures show that the experimental values of the probability of detection P.sub.D,real are sigmoidically dependent on the theoretical value P.sub.D,th computed in equations (11)-(17). In addition, the corresponding sigmoid function expressing the experimental P.sub.D,real in terms of the theoretical P.sub.D,th tends to 0 when the theoretical P.sub.D,th approaches 0. It tends to P.sub.D.sup.max when the theoretical P.sub.D,th approaches P.sub.D.sup.max. Moreover, the shape of the sigmoid function (and therefore its parameter) depends on the distance to the nearest obstacle(s). When this distance increases the bell shape of the sigmoid function becomes smoother.

Fifth Experiment: Detection of Multiple Targets

[0154] The detection of several targets placed in the sensor measurement cone is now considered. This section proves the effectiveness of the occupancy model (i.e. inverse sensor model) proposed here to assess the free space in presence of multiple obstacles placed in the sensor measurement cone. It should be reminded that the occupancy model has been derived under the Nearest-Target hypothesis with hypotheses for the SM that have been validated above for the VL53L0X sensor.

[0155] In this experiment, two identical cardboards having a width of 9 cm were used. They were located at a distance of 30 cm (resp. 70 cm) from the sensor and placed at 7.5 cm on the left of its principle axis (resp. 21 cm on the right of the principle axis). 27 scan steps were made with a clockwise shift of 2 of the sensor FOV, starting from the position where the principal axis of the sensor cone is at 115. The scanning was made using the VL53L0X sensor with the high accuracy mode.

[0156] The sectoral decomposition technique was applied with 3 sectors on a two-dimension (2D) uniform rectangular grid of width 1 m and length 2 m, composed of square cells of length 2 cm. The ISM derived from the SM with hypotheses H.sub.1 to H.sub.4 validated above was used to build the occupancy grid for each scanning angular position.

[0157] FIG. 21 shows the results of the fusion of the 27 occupancy grids obtained for each scan by applying the integer Bayesian Fusion technique from WO2017/050890. This experiment demonstrates that the sectoral decomposition technique can be used in conjunction with a scanning technique to properly assess the free space between the sensor and the obstacles and localize both obstacles, under the Nearest-Target hypothesis.

REFERENCES

[0158] [1] A. Elfes, Occupancy grids: a stochastic spatial representation for active robot perception (Sixth Conference on Uncertainty in Al, 1990) [0159] [2] R. Dia, J. Mottin, T. Rakotovao, D. Puschini, and S. Lesecq, Evaluation of Occupancy Grid Resolution through a Novel Approach for Inverse Sensor Modeling in IFAC World Congress, Toulouse, France, July 2017. [0160] [3] K. Pathak, A. Birk, J. Poppinga, and S. Schwertfeger, 3d forward sensor modeling and application to occupancy grid based sensor fusion in Intelligent Robots and Systems, 2007. IROS 2007. IEEE/RSJ International Conference on. IEEE, 2007, pp. 2059-2064 [0161] [4] E. Kaufman, T. Lee, Z. Ai, and I. S. Moskowitz, Bayesian occupancy grid mapping via an exact inverse sensor model in American Control Conference (ACC), 2016 American Automatic Control Council (AACC), 2016, pp. 5709-5715. [0162] [5] P. Stepan, M. Kulich, and L. Preucil, Robust data fusion with occupancy grid IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), vol. 35, no. 1, pp. 106-115, 2005. [0163] 6] S. Thrun, W. Burgard, and D. Fox, Probabilistic Robotics (Intelligent Robotics and Autonomous Agents). The MIT Press, 2005.