# From Probabilistic Occupancy Grids to versatile Collision Avoidance using Predictive Collision Detection

Thomas Genevois, Lukas Rummelhard, Anne Spalanzani, Christian Laugier

► To cite this version:

Thomas Genevois, Lukas Rummelhard, Anne Spalanzani, Christian Laugier. From Probabilistic Occupancy Grids to versatile Collision Avoidance using Predictive Collision Detection. ITSC 2023 - IEEE International Conference on Intelligent Transportation Systems, IEEE, Sep 2023, Bilbao, Spain. pp.1-7. hal-04225028

HAL Id: hal-04225028

https://inria.hal.science/hal-04225028v1

Submitted on 2 Oct 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# From Probabilistic Occupancy Grids to versatile Collision Avoidance using Predictive Collision Detection

Thomas Genevois<fnref n="1" />, Lukas Rummelhard<fnref n="1" />, Anne Spalanzani<fnref n="1" /> and Christian Laugier<fnref n="1" />

**Abstract**— As robots are spreading in diverse environments, new collision avoidance challenges arise. Real world collision avoidance often includes dynamic, complex, unstructured and uncertain environments. While these constraints are rarely considered all together in perception and navigation research works, we present a broad integration from perception to navigation in a versatile collision avoidance approach that is designed to operate under these constraints. Our solution relies on a new Predictive Collision Detector that we propose as an interface between state-of-art grid-based perception and sampling-based planners. Unlike most other approaches, ours operates only on elementary spatial occupancy and does not use the concept of objects such that it captures the richness and versatility of modern occupancy grid perception. With simulated and experimental results on 2 robots, including a robotic car, we show that our solution generates advanced driving behaviors that compare with the related state-of-art and comply with safety standards even in complex scenarios. With this contribution, we hope to facilitate the use of probabilistic occupancy grids for collision avoidance and to enhance the connectivity of the state-of-art of perception and navigation.

## I. INTRODUCTION

Previously limited to isolated, controlled and specifically-tailored environments, robots are now reaching real-world situations, from autonomous cars merging with traffic, to domestic mobile robots or space exploratory rovers, implying new perception and navigation challenges. Robotics must deal with complex and unstructured environments, often populated by non-cooperative agents, with limited observability, uncertain, partial and noisy observations, and predict future states of the scene. While this domain expansion has been opened by impressive progress in both perception and navigation, their respective internal representation and methods, few attention in comparison seem to be focused on their interconnection, considering jointly the constraints of the dynamic, complex, unstructured and uncertain environments.

The chosen model to represent the environment is a key conception choice, imposing restrictions on the available perception and navigation techniques. [1] categorizes the common environment representations in 4 classes : raw sensor data, grids, features and graphs. In perception, Occupancy grids are a great option for accurate and versatile representation of complex scenes, while being able to model uncertainty. Based on [2] and [3], their use remains circumstantial in navigation (Fig. 1), mainly with global planners and rarely with local planners. Recent sampling-based local planners such as [4], [5] or [6] perform well and provide robust and reliable collision avoidance in dynamic

environments. They also allow to use complex ego-motion models, but rely on sampling the configuration space to generate a graph and assess its connectivity. These promising techniques then remain limited, the configuration space not being directly observable. To combine the benefits of state-of-art grid-based perception and sampling-based planning, an interface software dedicated to the configuration space exploration upon request of sampling-based planners, a *Collision Detector* as defined in [1], could be introduced. Contrary to isolated risk estimators [7] [8], limited to the current trajectory, all potential future states of the robot have to be investigated.

We present a collision avoidance approach that interfaces grid-based perception and sampling-based planners thanks to a Collision Detector. Integrating modern occupancy grid probabilistic description of space and motion in a particle-based approach, the Collision Detector operates probabilistic predictions of the scene motion. It allows then avoidance under uncertainty in unstructured environments. We demonstrate that it is versatile and robust to complex environments compared to the related state-of-art. Despite heavy computations, the use of GPGPU<fnref n="1" /> programming [9] enables real-time performances on embedded devices.

The contributions of this paper are :

* a new Predictive Collision Detector and its GPGPU implementation.

* a collision avoidance solution using this detector.

* simulated and experimental results of the method.

<figure><img src="image_2.png" /><figcaption>Fig. 1. Non-exhaustive graphical representation of common associations between perception, world modeling and collision avoidance techniques. We propose a new Collision Detector in order to compute the collision risk in configuration space graphs, widely used in local planning, from modern occupancy grid representation, observable via several perception techniques.</figcaption></figure>

<footnote n="1">¹Univ. Grenoble Alpes, INRIA, 38000 Grenoble, France.
e-mail: firstname.lastname@inria.fr</footnote>

<footnote n="1">¹GPGPU : global purpose use of graphics processing unit</footnote>
## II. APPROACH AND RELATED WORKS

### A. *Dynamic Occupancy grids*

Most state-of-art grid-based perception techniques, such as [10], [11], [12] or [8], produce a dynamic probabilistic occupancy grid, a discrete 2D representation of the likelihood of space to be occupied by obstacles, and their estimated speed, with the advantage of being independent of semantic classification and object segmentation, and retaining dense information, explicitly representing free spaces. This provides a unique versatile and accurate description of the environment and its complexity does not depend on the complexity of the environment, neither on the number or types of obstacles. Also dynamic probabilistic occupancy grids offer a rich representation of the uncertainties that may come from noise in sensing or localization, partial observation of the scene, conflictual detections or prediction. Finally such grid-based perception techniques also give an estimation of the speed of the detected motion and its confidence. Depending on the technique, it may be provided as a list of speed particles or as a grid of velocities. Fig. 2 presents an example of occupancy and velocity grids. Dynamic probabilistic occupancy grids appear then as an excellent model of the environment for a versatile collision avoidance system and we choose this to be the input data of the proposed Collision Detector.

<figure><img src="image_3.png" /><figcaption>Fig. 2. On the left is an example of a dynamic occupancy grid. It represents a urban scene where the ego vehicle, a car, is observing an intersection that 2 other vehicles will cross, at different times, speeds and orientations. There are also static objects on the side of the road. The image on the right is the corresponding velocity grid. Its colors refer to motion direction.</figcaption></figure>

### B. *Related works*

Several recent research works already use dynamic occupancy grids to achieve collision avoidance. [13] used dynamic occupancy grid maps with artificial potential fields and velocity synthesis to navigate a robot in an environment with static obstacles and humans. [14] makes use of evidential grids and clothoid sampling of trajectories to achieve collision avoidance in urban road scenarios. [15] and [16] are both using Predictive Occupancy Maps for collision avoidance in structured road environments. The former samples trajectories in acceleration, the latter uses RRT* as local planner. Unfortunately these methods do not consider uncertainties in the dynamic part of the environment. Only [17] considers probability of existence of dynamic obstacles. This work uses Bayesian dynamic occupancy grid with a MPPI planner to mitigate the collision damage in road scenarios. However, as the previously mentioned works, it uses a

simple prediction of the motion of the obstacles and does not consider uncertainty of the prediction. [18] is one of the rare works that relies on advanced probabilistic prediction of the motion of obstacles. It combines a probabilistic occupancy grid with a list of moving obstacles whose motion prediction is done with Hidden Markov Models and local planning has been done with RRT. Yet it is limited to simple shapes and motion models of the ego-vehicle and the obstacles. All these methods propose a broad integration of perception and collision avoidance under realistic observability constraints. They perform well in the avoidance scenarios for which they have been designed but rely on strong assumptions on the structure of the environment, on the ego-vehicle model or on the scenarios, hence they can not be regarded as versatile. Also they use objects to model the dynamic part of the environment, whereas the object segmentation may not be feasible in complex unstructured scenes or under limited sensing capabilities.

### C. *Approach*

In order to preserve the benefits of the rich dynamic occupancy grid environment representation at the elementary occupancy level, we push it forward with a particle-based approach to occupancy prediction, collision detection and provide it to the local planner. Our method achieves generic probabilistic collision prediction, detection and avoidance directly on cells of the grid and motion particles, without using the concept of objects. To our best knowledge, no other research work in collision avoidance operates at this microscopic level. This rich description of the environment enables our approach to operate without making any assumption, neither on the environment nor on the moving elements in it. This allows our approach to handle a wide diversity of scenarios. Moreover it can handle advanced probabilistic occupancy prediction models and accurate probabilistic collision detection with complex ego-motion and collision models. For these reasons, the proposed approach is versatile in the sense that it could apply to a wide range of applications. This is also a matter of robustness since it guarantees that the software can operate under most circumstances. In section IV, we show that our particle-based approach does not prevent our solution from generating advanced macroscopic driving behaviors, that it compares with the state-of-art of section II-B while being more versatile and handling complex scenarios.

## III. METHODOLOGY

### A. *Framework overview*

The proposed Predictive Collision Detector makes the interface between a perception system that generates a dynamic occupancy grid, such as [10], [11], [12] or [8], and a sampling-based local planner, such as [19], [4], [5] or [6]. These planners, associated with a motion model of the ego-vehicle, provide a list of configurations {2D position, heading, time} for which they request the probability of collision for the ego vehicle standing in the configuration.
Fig. 3 provides an overview of the proposed collision avoidance framework. The proposed Predictive Collision Detector consists of the 3 following modules:

* The occupancy prediction that projects the current occupancy grid along the motion particles and estimates the evolution of the occupancy grid over the next seconds.

* The collision detection investigates the predicted occupancy grid at the configurations that the planner requests and returns the probability of collision for each configuration.

* The optional TTC<fnref n="2" /> estimation uses the probabilities of collision over sequences of configurations in order to compute the expected TTC on each trajectory. This is used for planners, such as [19], that require a risk estimation over a whole trajectory, but may not be needed with other planners.

<figure><img src="image_4.png" /><figcaption>Fig. 3. Design of the software framework of the proposed collision avoidance system. The different processes are presented along with the data they exchange. The columns refer to the possibilities of parallelization in the implementation of the processes.</figcaption></figure>

As these modules manipulate large arrays of data, massive GPGPU parallelization is mandatory to meet the real-time constraint. Throughout the whole process, the parallelization goes along different data to optimize each computation.

## B. Occupancy prediction

The occupancy prediction is the module that projects the perceived motion over time in order to generate an occupancy grid for each sampled time interval. The perception of motion is represented by a list of motion particles i.e. bits of occupancy that has followed a consistent motion over the

previous frames. The particles do not refer to an object segmentation or instantiation. If the perception provides a velocity grid, it can be regarded as a sparse array and its non zero elements as particles in order to apply the same approach. The occupancy prediction is parallelized over the motion particles. Each particle has a speed vector and carries a probability of occupancy that represents the probability of existence of a moving obstacle in the cell in which is the particle. Let $t_0$ be the current time, $\Delta t$ the time step and $m$ the number of time intervals. Let $\mathcal{P}$ be an initial particle of speed $\vec{v}$ and occupancy probability $p$. In order to represent the deviations from the motion that has been estimated, each initial particle $\mathcal{P}$ is split at $t_0$ into a set of $N$ independent sub-particles $\mathcal{P}_k \in [1,N]$. A deviation that represents a possible evolution of the motion is applied to each sub-particle. The deviation $U_k$ is here a command in acceleration and steering that figures the possible actions of an agent moving according to a dynamic unicycle motion model. The set of deviations may also contain the estimated probability distribution of the motion coming from the perception. We consider the sub-particles to be independent and equally probable then the occupancy probability carried by each is given by (1). This definition guarantees that the occupancy probabilities of all sub-particles are equal and that the combined occupancy probability is equal to the one of the initial particle.

$$ \forall k \in [1,N], p_k = 1 - \sqrt[N]{1-p} \quad (1) $$

Let $(x_k(t), y_k(t))$ be the coordinates of $\mathcal{P}_k$ at time $t$. $(x_k(t), y_k(t))$ are computed from the status at $t_0$ according to $U_k$ and the chosen agent motion model. Let $O(x,y,t)$ be the occupancy probability at time $t$ for the cell in which falls the coordinates $(x,y)$. For each time $t$, $O(x,y,t)$ is first initialized with the static occupancy. Then the occupancy of each cell of the grid is increased with each sub-particle that falls in it at the corresponding time according to (2). This defines that the cell is occupied if there is already an obstacle in it or if a sub-particle brings an obstacle along.

$$ O(x_k(t), y_k(t), t) \leftarrow 1 - (1 - O(x_k(t), y_k(t), t))(1 - p_k) \quad (2) $$

The parallel implementation of (2) must be done carefully because the threads of different sub-particles that fall in the same cell are likely to attempt to modify the value of this cell simultaneously, the modification should be done in a manner that avoids concurrency. Fig. 4 presents an example of predicted occupancy grid. This approach of dividing initial particles into sub-particles that spread acts similarly to a Monte-Carlo filter. It tends to filter out lonely initial particles that spread little occupancy probability in a large area while it reveals consensual motion of groups of particles that generates a wide distribution of predicted occupancy. The dynamic unicycle model that we use to predict the motion of agents leads to a conservative prediction since it considers all actions from maximum braking to maximum acceleration within the whole steering range. We use $N = 100$ to ensure a fine sampling of the deviations. Our approach suits well with the probabilistic occupancy paradigm and achieves great

<footnote n="2">²TTC : time to collision</footnote>
real-time performances although it is not as accurate as state-of-art of occupancy prediction such as [20] or [21].

<figure><img src="image_5.png" /><figcaption>Fig. 4. This grid represents the occupancy which is predicted with the proposed method. It has been computed from the grids of Fig. 2. The colors attempt to represent the time dimension of the predicted occupancy grid which is actually a 3D array (x,y,t). As the probability of occupancy gets much lower when it spreads, it is represented via a logarithm scale on the value component of the colors. Static elements are represented in white.</figcaption></figure>

### C. Collision detection

The Collision Detector is the module that investigates the predicted occupancy grid at the configurations that the local planner requests. Then the Collision Detector returns the probability of a collision if the ego vehicle happens to be in that configuration at the corresponding time. The computations of the Collision Detector are parallelized over this list of configurations. Let $X$ be a configuration, it is defined by the 2D coordinates, a heading and a time. The shape of the ego vehicle is discretized, at the same resolution than the occupancy grid. Let $\mathcal{S}$ be the set of vectors that define the discretized shape of the ego vehicle with respect to its reference frame. Let $T(X)$ be the transformation matrix from the absolute frame to the ego vehicle reference frame for a given $X$. Let $O(x,y,t)$ be the occupancy probability of a cell at the given position and time. Then we use $T(X)$ to perform the forward projection of $\mathcal{S}$ on the grid. The probability of a collision if the ego is in $X$, $P_{\text{coll}}(X)$, is defined by (3) as the probability that there is no obstacle in none of the equivalent cells of the shape.

$$P_{\text{coll}}(X) = 1 - \prod_{\vec{v} \in \mathcal{S}} 1 - O(T(X)\vec{v}, t) \quad (3)$$

The definition of $O$ depends on the type of occupancy grid which is used. In the case of Bayesian occupancy grid as provided by [10], the grid defines the probability of having observed a cell and the probability of existence of an obstacle inside it given that it has been observed. $O$ is the combination of these probabilities, unobserved state resulting in a prior distribution. Although the prior has to be specified carefully. Applying a prior of 0.5 probability of occupancy per cell would lead to $P_{\text{coll}}(X) = 1 - 0.5|\mathcal{S}| \approx 1$ if $X$ is in an unknown area, unknown would be perceived almost as occupied areas. The prior value should be normalized for a given area so that the uncertainties do not depend on the resolution of the grid.

This method allows to use even complex shapes of the ego vehicle. The massive parallelization over $X$ leads to a very efficient computation. As the collision detection is done on the predicted occupancy grid, it takes into account the

estimated motions in the environment. Then the output of this module, the collision probability associated to each $X$, is the required input for most sampling-based planners.

### D. Optional Time To Collision estimation

Planners like [19] require an estimation of collision risks over trajectories. For this, our method provides the expected TTC on each trajectory. Let $\mathcal{T}_{[0,n]}$ be a trajectory i.e. a sequence of configurations. The probability that a collision occurs in the $i$ first configurations of $\mathcal{T}_{[0,n]}$ is given by (4).

$$P_{\text{coll}}(\mathcal{T}_{[0,i]}) = 1 - \prod_{j=0}^{i} 1 - P_{\text{coll}}(\mathcal{T}_j) \quad (4)$$

(4) must be considered carefully. It is valid only if $P_{\text{coll}}(\mathcal{T}_j)$ is defined as the probability of a collision to occur within the corresponding time interval and possibly normalized as such otherwise the definition of $P_{\text{coll}}(\mathcal{T}_{[0,i]})$ would depend on the time step. Then we define the TTC, $\tau(\mathcal{T}_{[0,n]})$ as the expectancy of the time of the first collision in (5).

$$\tau(\mathcal{T}_{[0,n]}) = t_0 P_{\text{coll}}(\mathcal{T}_0) + \sum_{i=1}^{n} t_i P_{\text{coll}}(\mathcal{T}_{[0,i]}) (1 - P_{\text{coll}}(\mathcal{T}_{[0,i-1]})) \quad (5)$$

As it is convenient for the planner to fix an upper bound on the TTC, we added a final virtual configuration to each trajectory with a probability of collision of 1. This estimation of TTC relies on a probabilistic approach and considers the measure of uncertainty that the perception and the prediction use. This module also achieves great real-time performances thanks to a parallelization over the set of trajectories.

## IV. IMPLEMENTATION AND EXPERIMENTAL RESULTS

The proposed method has been deployed on an experimental robotic car which is equipped with 5 LiDAR sensors and 1 camera. An accurate localization is computed from an IMU and a RTK GPS. The CMCDOT perception suite [10] generates dynamic occupancy grids and a sampling-based MPC planner [19] combines path following and obstacle avoidance. We run the computations on a NVIDIA GeForce GTX 1080. The occupancy grid contains 350000 cells and the planner investigates a total of 25960 configurations. Despite this large amount of data, the occupancy prediction is executed in a maximum of 15ms, the collision detection in 14ms and the TTC estimation in 1ms while the whole collision avoidance is executed at 15Hz. This allows to meet the real-time constraints. For this validation, a SiL<fnref n="3" /> simulation framework is used, it means that the software uses only information given by the emulated sensors but also that these tests could be executed in actual experiments. For these tests, the planner is guided by a given path but can leave the path for avoidance. Realistic and interactive crowd behavior is simulated with SPACiSS [22]. In several urban scenarios, the safety distances will be evaluated with respect to the Responsibility-Sensitive Safety recommendations [23]. The RSS<fnref n="4" /> defines safety distances depending on the road

<footnote n="3">³SiL: software-in-the-loop</footnote>

<footnote n="4">⁴RSS: Responsibility-Sensitive Safety [23]</footnote>
topology, relative positions, speeds and dynamic capabilities of the actors. As this approach considers dynamically feasible worst cases, it is pessimistic and more conservative than most human drivers.

A first simple example, in fig. 5 and 6, illustrates a behavior that is induced by the Predictive Collision Detector. As a pedestrian is about to cross the road ahead, the probabilistic risk assessment provides the clues for the planner to identify the risk of intercepting the trajectory of the pedestrian and to decide whether to safely cross before or to yield smoothly. This behavior of our avoidance system qualitatively compares with what has been presented in [13], [17] and [18].

<figure><img src="image_6.png" /><figcaption>Fig. 5. In a SiL simulation, the ego vehicle approaches a footpath that a pedestrian is about to cross. The predicted occupancy and the set of evaluated trajectories with the estimated collision risk are displayed. The Predictive Collision Detector is able to clearly identify the sets of trajectories that lead to a collision and the actions that lead to safe trajectories. In this example, the planner chose to cross safely before the pedestrian, without disturbing him.</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Fig. 6. Repeating the scenario of Fig. 5 with a 1s delay in the arrival of the car leads to a different outcome. The collision avoidance predicts early that there is no safe option to pass before the pedestrian so it adopts a smooth deceleration and yields. The image and speed graph illustrate this experiment. $t_0$ represents the first collision risk detection.</figcaption></figure>

A second example in a SiL simulation, in fig. 7, demonstrates that our Predictive Collision Detector identifies all collision risks that arise during an overtaking maneuver. Moreover the observed forward, lateral and rear safety distances that our avoidance respects match with the RSS recommendations. This illustrates the accuracy of the predictive collision risk estimation. This is an expectable result since our avoidance encapsulates, in our particle-based prediction, kinodynamic worst cases that are similar to those of RSS. This behavior of our avoidance system qualitatively com-

pares with what has been presented in [14], [15] and [16].

<figure><img src="image_8.png" /></figure>

The ego vehicle approaches a slower car.

<figure><img src="image_9.png" /></figure>

The ego vehicle is overtaking.

<figure><img src="image_10.png" /></figure>

The ego vehicle concludes the maneuver.

<figure><img src="image_11.png" /></figure>

The occupancy of the other vehicle spreads considering a possible deceleration, inducing an implicit safety distance behind it. So trajectories that deviate from the path provide the best objective-safety compromise.

<figure><img src="image_12.png" /></figure>

The wide distribution of the predicted occupancy also imposes a lateral safety distance. As the ego vehicle is by the side of the other vehicle, the planner is free to accelerate and finds a trajectory that completes the overtaking.

<figure><img src="image_13.png" /></figure>

The planner drives the ego vehicle back on the path. The predicted occupancy of the other vehicle is still spreading and shows that it is about 3s behind. Therefore the trajectories that decelerate are discarded by collision prediction.

<figure><img src="image_14.png" /><figcaption>Fig. 7. Illustration of a driving behavior observed in a simulated overtaking maneuver. Views from simulation are on the top row and the row below shows the predicted occupancy and a visualization of collision risk on sampled trajectories. The graph shows the relative position of the ego vehicle with respect to the other. x is the longitudinal axis and y the lateral one. The collision area is displayed in red, such that the distance from the curve to this area is exactly the safety distance. We notice that our particle-based occupancy prediction leads to the observance of the longitudinal and lateral RSS safety distances that are depicted in green.</figcaption></figure>

Among the state-of-the-art collision avoidance systems that integrate both perception and navigation under uncertainty on dynamic occupancy grids, we have identified on the one hand [13], [18] that handle navigation in human-populated environments, [14], [15] and [16] that operate on structured multiple-lanes road scenarios and [17] that considers collision mitigation in road scenarios. These solution exploit prior knowledge of structure of the environment (some assume a multiple-lanes road structure) and of the obstacles (some assume that all obstacles are humans others that all obstacles are cars). Such simplifications leverage the complexity of computations and the constraints on perception but restrict these avoidance systems to operating domains they have been tailored for. Meanwhile we have shown with examples of fig. 5, 6 and 7 that our proposed collision avoidance qualitatively compares with each of these approaches in their operating domain. This demonstrates the versatility of our solution. The next examples challenge the robustness of our approach in unstructured and complex scenarios that have not been investigated by the presented state-of-the-art.
Fig. 8 presents SiL simulated quantitative experiments of navigation in a crowd of pedestrians using the proposed approach. In this more complex test, we observe that the crowd density makes the navigation more challenging, as a result, the crossing time increases. Yet, despite of this increasing complexity, our avoidance succeeds to maintain a stable level of safety, that we measure with respect to the RSS standards. By the density and the realist behavior of the crowd, the speed and kinodynamic constraints of the ego-vehicle, this test is more challenging that what could handle the other methods that have been presented in the related works because of the simplifying assumptions that limit their operating domain.

<figure><img src="image_15.png" /><figcaption>Fig. 8. The graphs present quantitative results over 50 SiL simulations in which the car crosses a crowd that goes in the opposite direction. Each boxplot displays the median, quartiles, extrema and outliers over 10 simulations. The scene is illustrated on the left image. We define the RSS satisfaction ratio as the minimum realized safety distance divided by the RSS recommended safety distance. The navigation duration increases with the crowd density. However the RSS satisfaction ratio remains stable and mostly above 1. This shows that the proposed method maintains a constant safety level despite the increasing complexity of the navigation task.</figcaption></figure>

The proposed collision avoidance has also been adapted for an industrial logistics application. A light robot is conveying goods in an human-populated indoor environment. It is equipped with a limited set of sensors, 1-layer LiDAR and ultrasonic range sensors. Hardware-in-the-Loop simulated tests have been run on an embedded computer, a NVIDIA Jetson TX2, results are visible in fig. 9. The operational environment contains surfaces that are transparent to LiDAR and observable only to sonars. But the range of sonars is short and they only provide a single range observation over a large angular sector. Also only the legs of humans are visible to LiDAR sensors. Under these constraints, it would not be possible to generate an object-based perception from clustering and object tracking. So the other methods of the state-of-art that we presented could not be applied. Yet our grid-based solution enables the fusion of LiDARs

and sonars, the predicted occupancy grid represents correctly the various obstacles of this scene and their motion. Then, with a map-based global planner and the proposed local collision avoidance, the robot has been able to navigate safely and complete several loops across the whole simulated environment. This demonstrates the versatility of our method in a very different application. It also shows that our solution is robust under the constraints of embedded hardware and limited sensing capabilities.

<figure><img src="image_16.png" /><figcaption>Fig. 9. The proposed method has been tested for indoor navigation of a light robot for industrial logistic applications. (1) displays the simulated environment with the robot at (a). (2) presents the outputs of its LiDAR and sonar sensors. (3) shows the corresponding dynamic occupancy grid. (4) shows the predicted occupancy grid and the current planning output. This grid showcases a global observation of the environment including, transparent walls that are visible only to sonars (b), pedestrian motion (c) and unobserved areas (d). The proposed collision avoidance method is able to consider all these elements to navigate safely in this environment.</figcaption></figure>

Our method has been tested not only in simulation but also in actual vehicle experiments where it demonstrated its collision avoidance capabilities at low speed in diverse scenarios representing urban scenes with static obstacles, pedestrians and other vehicles. Augmented reality on sensor data [24] has been used to safely test scenarios with pedestrians. Fig. 10 illustrates a test with static obstacles. Fig. 11 shows an avoidance in a scene with pedestrian and static obstacles.

<figure><img src="image_17.png" /><figcaption>Fig. 10. Different points of view on the same scene of a test of the collision avoidance system with static obstacles. The occupancy grid and the planner outputs are displayed on the right.</figcaption></figure>
<figure><img src="image_18.png" /><figcaption>Fig. 11. Images from a test of the collision avoidance system with moving obstacles using augmented reality on LiDAR data. This scene has been augmented with virtual pedestrians. On the left is the image of the embedded camera. The predicted occupancy grid and the discretization of the trajectories are shown on the right.</figcaption></figure>

V. CONCLUSIONS

We have presented a Predictive Collision Detector and propose it as an interface between state-of-art grid-based perception and sampling-based planners. The proposed method differs from the state-of-art as it uses only elementary spatial occupancy, at cell and particle level. To illustrate it, a collision avoidance solution has been built around the proposed detector and it has showed advanced driving behaviors involving risk assessment and decision aspects. The navigation safety as been proven according to the well-established standards of RSS. As the proposed avoidance qualitatively compares with the performance of various state-of-art methods in their respective operating domains, we showed that it is more versatile. We also demonstrated the robustness of our approach in scenarios that are more challenging because of their complexity or because of limited sensing capabilities. With this contribution, we hope to facilitate the use of probabilistic occupancy grids for collision avoidance and to enhance the connectivity of the state-of-art of perception and navigation.

Among the possible future works, the occupancy prediction model could be improved, a less conservative policy could increase precision. Also the predictive collision detector should be tested with various perception and planning solutions in order to demonstrate that it can operate as a standard interface between grid-based perception systems and sampling-based planners.

ACKNOWLEDGMENT

This work has been developed within the scope of an "Institut de Recherche Technologique NanoElec" project, founded by the French program "Investissement d'Avenirs" ANR-10-AIRT-05. The authors wish to thank N. Turro for his collaboration and continuous support.

REFERENCES

[1] B. Siciliano and O. Khatib, "Robotics foundations," in Springer Handbook of Robotics. Springer International Publishing, 2016.

[2] E. Yurtsever, J. Lambert, A. Carballo, and K. Takeda, "A survey of autonomous driving: Common practices and emerging technologies," IEEE Access, 2020.

[3] D. González, J. Pérez, V. Milanés, and F. Nashashibi, "A review of motion planning techniques for automated vehicles," IEEE Transactions on Intelligent Transportation Systems (ITSC), 2016.

[4] M. Pivtoraiko and A. Kelly, "Efficient constrained path planning via search in state lattices," in International Symposium on Artificial Intelligence, Robotics, and Automation in Space, 2005.

[5] G. Williams, P. Drews, B. Goldfain, J. M. Rehg, and E. A. Theodorou, "Aggressive driving with model predictive path integral control," in IEEE International Conference on Robotics and Automation (ICRA), 2016.

[6] S. LaValle and J. Kuffner, "Randomized kinodynamic planning," in IEEE International Conference on Robotics and Automation, 1999.

[7] L. Rummelhard, A. Nègre, M. Perrollaz, and C. Laugier, Probabilistic Grid-Based Collision Risk Prediction for Driving Application. Springer International Publishing, 2016.

[8] J. Laconte, E. Randriamiarintsoa, A. Kasmi, F. Pomerleau, R. Chapuis, C. Debain, and R. Aufrère, "Dynamic lambda-field: A counterpart of the bayesian occupancy grid for risk assessment in dynamic environments," in IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2021.

[9] D. Luebke, "Cuda: Scalable parallel programming for high-performance scientific computing," in IEEE International Symposium on Biomedical Imaging: From Nano to Macro, 2008.

[10] L. Rummelhard, A. Nègre, and C. Laugier, "Conditional monte carlo dense occupancy tracker," in IEEE International Conference on Intelligent Transportation Systems, 2015.

[11] D. Nuss, "A random finite set approach for dynamic occupancy grid maps," Ph.D. dissertation, Universität Ulm, 2017.

[12] M. Schreiber, V. Belagiannis, C. Gläser, and K. Dietmayer, "A multi-task recurrent neural network for end-to-end dynamic occupancy grid mapping," 2022. [Online]. Available: https://arxiv.org/abs/2202.04461

[13] Y. Liu, J. Chen, and X. Bai, "An approach for multi-objective obstacle avoidance using dynamic occupancy grid map," in IEEE International Conference on Mechatronics and Automation (ICMA), 2020.

[14] H. Mouhagir, V. Cherfaoui, R. Talj, F. Aioun, and F. Guillemard, "Using evidential occupancy grid for vehicle trajectory planning under uncertainty with tentacles," in IEEE 20th International Conference on Intelligent Transportation Systems (ITSC), 2017.

[15] K. Lee and D. Kum, "Collision avoidance/mitigation system: Motion planning of autonomous vehicle via predictive occupancy map," IEEE Access, 2019.

[16] D. Shen, Y. Chen, L. Li, and S. Chien, "Collision-free path planning for automated vehicles risk assessment via predictive occupancy map," in IEEE Intelligent Vehicles Symposium (IV), 2020.

[17] L. A. Serafim Guardini, A. Spalanzani, P. Martinet, C. Laugier, T. Genevois, and A.-L. Do, "Minimal injury risk motion planning using active mitigation and sampling model predictive control," in IEEE International Conference on Intelligent Transportation Systems (ITSC), 2022.

[18] C. Fulgenzi, A. Spalanzani, and C. Laugier, "Probabilistic motion planning among moving obstacles following typical motion patterns," in IEEE/RSJ International Conference on Intelligent Robots and Systems, 2009.

[19] D. D. Dunlap, E. G. Collins Jr, and C. V. Caldwell, "Sampling based model predictive control with application to autonomous vehicle guidance," in Florida Conference on Recent Advances in Robotics, 2008.

[20] K. S. Mann, A. Tomy, A. Paigwar, A. Renzaglia, and C. Laugier, "Predicting future occupancy grids in dynamic environment with spatio-temporal learning," in IEEE Intelligent Vehicles Symposium (IV), 2022.

[21] S. Zernetsch, H. Reichert, V. Kress, K. Doll, and B. Sick, "A holistic view on probabilistic trajectory forecasting - case study. cyclist intention detection," in IEEE Intelligent Vehicles Symposium (IV), 2022.

[22] M. Prédhumeau, "Simulating Realistic Pedestrian Behaviors in the Context of Autonomous Vehicles in Shared Spaces," in 20th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2021). IFAAMAS, 2021.

[23] S. Shalev-Shwartz, S. Shammah, and A. Shashua, "On a formal model of safe and scalable self-driving cars," 2017. [Online]. Available: https://arxiv.org/abs/1708.06374

[24] T. Genevois, J.-B. Horel, A. Renzaglia, and C. Laugier, "Augmented reality on lidar data: Going beyond vehicle-in-the-loop for automotive software validation," in IEEE Intelligent Vehicles Symposium (IV), 2022.