Maxime Chaveroche
email: maxime.chaveroche@gmail.com

Franck Davoine
email: franck.davoine@hds.utc.fr

Véronique Cherfaoui
email: veronique.cherfaoui@hds.utc.fr

Decentralized cooperative perception for autonomous vehicles: Learning to value the unknown ⋆

Keywords:

Deep Learning Reinforcement Learning

A B S T R A C T Recently, we have been witnesses of accidents involving autonomous vehicles and their lack of sufficient information. One way to tackle this issue is to benefit from the perception of different view points, namely cooperative perception. We propose here a decentralized collaboration, i.e. peer-topeer, in which the agents are active in their quest for full perception by asking for specific areas in their surroundings on which they would like to know more. Ultimately, we want to optimize a trade-off between the maximization of knowledge about moving objects and the minimization of the total volume of information received from others, to limit communication costs and message processing time. For this, we propose a way to learn a communication policy that reverses the usual communication paradigm by only requesting from other vehicles what is unknown to the ego-vehicle, instead of filtering on the sender side. We tested three different generative models to be taken as base for a Deep Reinforcement Learning (DRL) algorithm, and compared them to a broadcasting policy and a policy randomly selecting areas. More precisely, we slightly modified a state-of-the-art generative model named Temporal Difference VAE (TD-VAE) to make it sequential. We named this variant Sequential TD-VAE (STD-VAE). We also proposed Locally Predictable VAE (LP-VAE), inspired by STD-VAE, designed to enhance its prediction capabilities. We showed that LP-VAE produced better belief states for prediction than STD-VAE, both as a standalone model and in the context of DRL. The last model we tested was a simple state-less model (Convolutional VAE). Experiments were conducted in the driving simulator CARLA, with vehicles exchanging parts of semantic grid maps. Policies learned based on LP-VAE featured the best trade-off, as long as future rewards were taken into account. Our best models reached on average a gain of 25% of the total complementary information, while only requesting about 5% of the ego-vehicle's perceptual field. We also provided interpretable hyperparameters controlling the reward function, which makes this trade-off adjustable (e.g. allowing greater communication costs).

Introduction

Recently, we have been witnesses of accidents involving autonomous vehicles and their lack of sufficient information at the right time. One way to tackle this issue is to benefit from the perception of different viewpoints, namely collaborative perception. While setting a multitude of sensors in the road infrastructure could be imagined, this would require a lot of investments and limit its usage to some areas in the world. Instead, we focus on the exchange of information between vehicles about their common environment, where they are the only sources available.

These communications can simply be centralized by a server that would gather all information from all vehicles to process it and re-distribute it to all, as suggested in [START_REF] Chen | F-cooper: Feature based cooperative perception for autonomous vehicle edge computing system using 3D point clouds[END_REF]. However, this still consists of Vehicle-to-Infrastructure (V2I) communications, which implies (1) an infrastructure cost and the impossibility to share information with other agents when there is no server available nearby. It also features the disadvantage of (2) making the agents broadcast their entire perception, which can be heavy on the means of communication and computation and give rise to delays.

In contrast, the decentralized Vehicle-to-Vehicle (V2V) approach [START_REF] Kim | Multivehicle Cooperative Driving Using Cooperative Perception: Design and Experimental Validation[END_REF][START_REF] Li | Multivehicle Cooperative Local Mapping: A Methodology Based on Occupancy Grid Map Merging[END_REF][START_REF] Zoghby | Evidential distributed dynamic map for cooperative perception in vanets[END_REF][START_REF] Seeliger | Advisory warnings based on cooperative perception[END_REF][START_REF] Vasic | A system implementation and evaluation of a cooperative fusion and tracking algorithm based on a Gaussian mixture PHD filter[END_REF] does not require any extra infrastructure to work, i.e. does not implies [START_REF] Chen | F-cooper: Feature based cooperative perception for autonomous vehicle edge computing system using 3D point clouds[END_REF]. In this setting, agents directly exchange pieces of information between them. It also comes with new problems such as data incest and lower computation capabilities. We will ignore them here as we already tackled the issue of avoiding data incest using Dempster-Shafer Theory (DST) [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF] in spite of low computation capabilities with two conference papers [START_REF] Chaveroche | Calcul exact de faible complexité des décompositions conjonctive et disjonctive pour la fusion d'information[END_REF][START_REF] Chaveroche | Efficient Möbius transformations and their applications to DS theory[END_REF] and a journal paper [START_REF] Chaveroche | Focal points and their implications for möbius transforms and dempster-shafer theory[END_REF]. But V2V communications bring a potentially heavier communication burden as well, due to redundancies. In fact, (2) is worse in this setting than in the centralized one if agents are passive, meaning if they simply broadcast their perception for the others to know, without filtering it beforehand. Nevertheless, this decentralized approach offers the possibility to make the agents active in their quest for full perception, i.e. making the agents ask for specific areas in their surroundings on which they would like to know more, instead of always broadcasting everything. This is impossible in the centralized setting, as the server decides and thus needs to gather all perceptions beforehand.

Here, we propose such a system, where each agent builds its own local top-down semantic grid and sends specific requests to others in the form of bounding boxes described in the global reference frame. We choose local grid maps for their ability to map an agent's knowledge and to deduce its uncertainties in space.

Related Works

Since not all uncertain areas are relevant, Active Exploration [START_REF] Stachniss | Information gain-based exploration using rao-blackwellized particle filters[END_REF][START_REF] Clemens | An evidential approach to SLAM, path planning, and active exploration[END_REF] is not enough; a truly efficient collaboration policy requires some understanding of the scenery [START_REF] Wang | Semantic-Aware Informative Path Planning for Efficient Object Search Using Mobile Robot[END_REF], extracted from the spatial arrangement of grid cells and their classes. What could lie in the shadows and how to best discover it? If a pedestrian is heading towards an occluded area, we expect the agent to request for this area, as a tracking system. If the agent has no idea of what could be in the unknown, maybe it could ask for some key points to understand the layout of the environment. If an area on the road is near a crowd of people or in the continuity of a pedestrian crossing, ask for it as some unseenbefore pedestrians could be crossing, etc. More generally, we would like the agent to know as much as possible about moving objects in its vicinity, while avoiding to request too much information from others. This represents a complex bounding box selection policy to be learned from pixels.

Given the long-lasting successes of Deep Learning in such ordeals, it seems natural to consider neural networks for our problem. But, while it is theoretically possible (but practically challenging) to learn our policy in an end-toend fashion with Model-free Deep Reinforcement Learning (DRL), we choose to first learn a deep generative model to pre-process our inputs. Indeed, training deep neural networks is easier, faster and more stable when the loss on the output is in the form of a well-justified derivable function, which is hard to achieve with reward signals from a RL environment. Building this generative model also allows for more control and insights on what is learned, and reduces the size of the neural networks that are supposed to be trained through model-free DRL. As demonstrated in World Models [START_REF] Ha | Recurrent world models facilitate policy evolution[END_REF], learning a policy on top of a model can even be achieved with simple heuristics such as Evolution Strategies (ES), with performances equivalent to RL algorithms.

Our model needs to be generative, for inference in unknown areas. In addition, we want it to be predictive, in order to make it understand latent dynamics, anticipating disappearances or inferring hidden road users from the behavior of visible ones. Doing so, it could even eventually compensate for communication latencies. Such a model would be useful in itself for other tasks as well, e.g. autonomous driving.

Several existing works [START_REF] Wirges | Evidential occupancy grid map augmentation using deep learning[END_REF][START_REF] Sugiura | Probable Multi-hypothesis Blind Spot Estimation for Driving Risk Prediction[END_REF][START_REF] Hoermann | Dynamic occupancy grid prediction for urban autonomous driving: A deep learning approach with fully automatic labeling[END_REF][START_REF] Everett | Planning Beyond The Sensing Horizon Using a Learned Context[END_REF][START_REF] Shrestha | Learned map prediction for enhanced mobile robot exploration[END_REF]] employed generative models with convolutional networks in a U-Net architecture in order to augment instantaneous individual grid maps. Some used deterministic networks such as Generative Adversarial Networks (GAN). Others tried to incorporate stochasticity with Monte Carlo Dropout or simply using a Variational Auto-Encoder (VAE). Most used occupancy grids as input, but some chose semantic grid maps or DOGMa (occupancy grid with velocities). These inputs were either expressed in a static global reference frame or given to a system that had no prediction capability. Doing so, it appears that none of these approaches really modeled the long-term dynamics of the environment that would be necessary to learn our desired policy. On the other hand, a kind of recurrent generative model inspired by the VAE, namely Temporal Difference VAE (TD-VAE) [START_REF] Gregor | Temporal difference variational auto-encoder[END_REF], was designed with the specific intent of being taken as base for a reinforcement learning algorithm. It puts an emphasis on the learning of belief states for long-term predictions, which are important for the development of complex strategies. It has been proven in [START_REF] Gregor | Shaping Belief States with Generative Environment Models for RL[END_REF] that explicitly predicting future states enhances data-efficiency in a number of RL tasks, though they train their model jointly with the policy and do not use the loss defined in [START_REF] Gregor | Temporal difference variational auto-encoder[END_REF]. Appealed by the theoretical justifications of TD-VAE, its decoupling regarding specific RL tasks (which simplifies the search for good RL hyperparameters) and its demonstrated ability to predict plausible sequences of images in a 3D world at different time horizons and from a variable number of observations, we have implemented and adapted this TD-VAE to our problem. However, correcting some of its weaknesses regarding its actual prediction capability, we finally proposed our own model, called Locally Predictable VAE (LP-VAE). To learn our communication policy based on this model, we chose the widely used Proximal Policy Optimization (PPO) algorithm [START_REF] Schulman | Proximal Policy Optimization Algorithms[END_REF], which is a fairly stable and simple policy-gradient based DRL algorithm with few hyperparameters.

Closely related to our goal, other works try to address the problem of efficiently communicating between autonomous vehicles. In [START_REF] Wang | V2vnet: Vehicle-to-vehicle communication for joint perception and prediction[END_REF], they used a joint Perception and Prediction (P&P) model that transforms sensor data into learned features to broadcast to other vehicles. This model also fuses received features with local ones and tries to predict the trajectory of nearby communicating vehicles. This information compression is also present in our work in the form of a Convolutional VAE preprocessing each observation grid. We go one step further in communication efficiency as our system does not broadcast every piece of information, but chooses instead which one it wishes to receive. Sending learned features also forces them to make another neural network learn to spatially and temporally transform all pieces of information received from the vehicular network. Even the fusion operation is done by making a neural network learn how to fuse two learned features, without any guarantee on the result. Instead, here we rely on top-down semantic grids, which are simple discretizations of the space around the ego-vehicle. Doing so, we can transform the content of our transmissions using linear transformations. Furthermore, our system keeps its integrity by only fusing probability distributions.

In [START_REF] Aoki | Cooperative perception with deep reinforcement learning for connected vehicles[END_REF], they used Deep Reinforcement Learning to select only a portion of the perceptive field of an autonomous vehicle to send to others. However, this information filtering is done on the sender side, contrary to our approach that filters on the receiver side. Doing so, their approach still Figure 1: Illustration of our application. CARLA provides a semantic segmentation corresponding to a camera attached to the ego-vehicle hood, as well as its corresponding depth (images taken from [START_REF] Dosovitskiy | CARLA: An open urban driving simulator[END_REF]). This gives us enough information to create a semantic 3D point cloud, i.e. to scatter all pixels in space according to their depth and image coordinates (and the camera deformation). From it, we project these pixels back into a 2D plane (i.e. a grid), but from a top-down point of view (and without camera deformations). In parallel, we get the ego-vehicle motion since the previous time step in order to update a perception memory containing 2D points from previous time steps. We add the current semantic grid to this memory and give the resulting augmented grid to our learned world model (STD-VAE or LP-VAE), along with the ego-motion and driving policy commands. In turn, this model tries to guess what is hidden in occluded areas and provides a belief state about latent dynamics. These outputs are then given to a DRL algorithm that chooses a grid area to request to the world. This area is extracted at the next time step from a grid generated by a camera above the ego-vehicle. Finally, this information is fused at the next time step with the ego-vehicle perception.

consists in broadcasting pieces of information, regardless of the actual needs of others.

The same can be stated for [START_REF] Higuchi | Value-anticipating V2V communications for cooperative perception[END_REF], where they describe a V2V cooperative perception system in which vehicles exchange object detections. They try to reduce redundancies by estimating the value of a piece of information for a potential receiver. The value here is the novelty, i.e. the probability that the potential receiver is not aware of some object of interest.

Section 3 formally introduces our communication problem, justifying the use of a preprocessing generative model. Section 4 formalizes the aforementioned generative model, introducing TD-VAE and LP-VAE. Section 5 presents our deep networks implementing these models. Then, section 6 evaluates and compares the performance of different versions of our models and policy learnings. Finally, we conclude this article with section 7.

Problem formulation

We formulate our communication problem as a Markov Decision Process (MDP). Fig. 1 gives an overview of it, working with the driving simulator CARLA [START_REF] Dosovitskiy | CARLA: An open urban driving simulator[END_REF] for our experiments.

State space

We assume the existence of a driving policy from which we only know the actions taken at each time step: egovehicle controls (acceleration and steering angle, each ranging in [-1, 1]) and global direction (average of the next 10 equally-spaced points the planner set to visit in meters relative to the ego-vehicle's reference). This driving policy influences the road environment in which the ego-vehicle is moving. This is not the case with the communication environment that we consider in this MDP. Each observation is a tuple ( , , ), where is an ego-centered semantic grid, represents the actions taken by the driving policy at a given instant (which influence +1 ) and is the motion of the ego-vehicle between -1 and . Each semantic grid is a top-down 6-channels pseudo-Bayesian mass grid corresponding to the five classes of the frame of discernment Ω = {pedestrian, car, road lines, road, other}. The class car actually contains any type of vehicle, even bikes. The class road lines contains any road marking: road lines, arrows, painted stop signs, etc. The class other contains the rest of the static objects perceivable by the agent, such as vegetation, sidewalks, buildings, etc. The last channel represents ignorance, i.e. the mass put on Ω. This means that ≥ 0 and, for any cell index of , we have Red is for pedestrians, blue is for cars, yellow is for road lines, purple is for road, white is for other and black is for ignorance. The displayed class is the one with the greatest mass. The intensity of its color depends on its mass: the closer to 0, the darker. Notice all the occlusions due to walls or other road users, in addition to the limited distance of perception of the ego-vehicle. Right: Instance of top-down semantic grid corresponding to a complete observation in our model. Actually, this view is obtained with a facing ground camera above the ego-vehicle. Doing so, it contains itself some occlusions due to trees, poles, buildings, etc. Thus, it is rather a hint about the true . This view can also be obtained by the fusion of multiple view points, from autonomous vehicles or infrastructure sensors.

∑ 6 =1 [ ][ ] = 1.
These cells are distributed as a matrix (grid) of 80 rows and 120 columns, i.e.

is analog to a 80 × 120 × 6 image of values in [0, 1]. See Fig. 2 for a visualization of this semantic grid.

These observations constitute a very large and complex space which would be hard to transform into exploitable neural network features without a derivable loss function. Thus, we will first build a generative model of the driving environment (implicitly including the agent's driving policy). Besides, learning this model beforehand will give us more control on the information flow that should be considered by the communication policy. Therefore, the state space of our MDP is made of learned features from this generative model. Several versions of this generative model are proposed in Section 4.

Action space

Our MDP has 4 continuous actions that each ranges in [0, 1], defining a bounding box in the local grid of the ego-vehicle at time : width, height, column and row. This bounding box is supposed to represent an area in the egovehicle's future surroundings.

Transition function

Transitions from a state-action pair to a new state depend also on the driving environment, i.e. CARLA. First, this environment generates a new partial grid +1 and other observations already described. The bounding box described by the action given at time is then translated into an area of +1 filled with complete information. Fig. 3 illustrates this process.

In addition, a visual memory mechanism, specific to our MDP, makes perceptions persist for a few time steps, 2) Send this request in global coordinates to the vehicular network (which may consists of both infrastructure sensors and other autonomous vehicles). 3) At time + 1, we expect some vehicles to transmit their perception of this area. In our implementation, complete perceptions are simply obtained by a camera above the ego-vehicle since we focus on the selection of bounding boxes, i.e. 1). 4) The transmitted partial perception is fused with the one of the ego-vehicle at time + 1. discounted a little more every time. This implements shortterm memory, so that we only consider as unknown what has not been perceived in a long time (or never). This also has the effect of giving consequences to past actions, since bounding boxes in the same area will have close to no potential information gain for a few time steps.

Rewards

Finally, let us define a reward function for our MDP. Let be a reward density, defined for each cell of +1 as:

( ) = -. min + [ ]. 5 ∑ =1 obj [ ]. max 0, +1 [ ][ ] -̃ +1 [ ][ ] (1)
where ∈ ℝ + * , ∈ [0, 1] and ̃ +1 is the grid before fusion with the grid +1 corresponding to +1 . The quantity obj is a nonnegative reward per object pixel (only null for the static class other, i.e. obj [START_REF] Seeliger | Advisory warnings based on cooperative perception[END_REF] = 0) such that obj [ ] ≥ obj [ + 1]. Indeed, pedestrian are the smallest identifiable objects among our classes and so must have the highest reward per pixel. The quantity min is equal to the least positive reward per pixel, i.e. min = obj [START_REF] Zoghby | Evidential distributed dynamic map for cooperative perception in vanets[END_REF]. It is used to discourage the selection of uninteresting cells. The coefficient that multiplies it represents the minimum informational gain that is needed to consider this cell worth to be requested. For some value of , this minimum gain applies to the class with the least reward, while it becomes virtually more and more forgiving as the class has a greater reward per cell. Moreover, notice that max(0 implies that max(0,

, +1 [ ][ ] -̃ +1 [ ][ ]) ∈ [0, 1], which
+1 [ ][ ] -̃ +1 [ ][ ]) ∈ [0, 1]
. This means that only alters the significance of some gain in mass: for

∈ (0, 1), max(0, +1 [ ][ ] -̃ +1 [ ][ ]) will be greater than for = 1, while for ∈ (1, +∞), max(0, +1 [ ][ ] -̃ +1 [ ][ ])
will be less. In other words, if ∈ (1, +∞), then the gain will have to be more important to have an impact on ( ). Finally, represents a spatial filter to account for the fact that we are not equally interested everywhere in discovering road users. For example, a road user very far ahead is not as valuable an information as a road user just around the corner. We defined a forward filter and a lateral filter , such that = . . We set

[ ] = 1 - 1 - . max 0, ( ) max( ) -
where ∈ [0, 1) and ∈ [0, 1]. The quantity ( ) is the forward distance (number of rows from the row in which the center of the ego-vehicle is) corresponding to cell . The greater the parameter , the less the farest cells are valued. The greater the parameter , the farer from the ego-vehicle the decrease in value starts.

The second filter is defined as

[ ] = 1 - . max (0, -|cos (arctan2 ( ( ), ( )))| )
where ∈ (0, 1]. The quantity ( ) is the lateral distance (number of columns from the column in which the center of the ego-vehicle is) corresponding to cell . This filter describes a cone in front of the ego-vehicle (and symmetrically at the back of it) in which the cells are the most valued. The greater the parameter , the narrower this cone. The greater the parameter is, the less the cells outside the cone (i.e. on the sides of the ego-vehicle) are valued. Fig. 4 provides a visualization of .

The reward associated with some action is defined as

( ) = -.(1 -). min + ∑ ∈ ( ) ( ), (2)
where is the minimum number of interesting cells that must be entirely discovered in order to make the request worthwhile, ( ) = [ ( ), ( ) + ℎ( )] × [ ( ), ( ) + ( )] and ( ), ( ), ( ), ℎ( ) are respectively the column index, row index, width and height indicated by some action .

Grid fusion

In order to produce from ̃ and the grid corresponding to in Eq. ( 1), we need to define a fusion procedure. As each cell in both ̃ and is a mass function, we know that:

[ ][6] = ̃ [ ][6] . [ ][6],
where 6 is the channel corresponding to the mass on Ω. Furthermore, we can get the contour functions of these pseudo-Bayesian mass functions simply by adding the mass on Ω to the mass on each of our 5 classes. Then, a simple pointwise multiplication of these two contour functions produces the contour function corresponding to . This also implies a mass on ∅, which is caused by conflicting pieces of evidence between the two mass functions. Since we are not interested in this level of conflict, we choose to renormalize masses as in Dempster's combination rule [START_REF] Dempster | A Generalization of Bayesian Inference[END_REF]. Unlike Dempster's rule however, we only distribute this conflict on singletons [ ][1 ∶ 5] and keep the true value [ ] [START_REF] Vasic | A system implementation and evaluation of a cooperative fusion and tracking algorithm based on a Gaussian mixture PHD filter[END_REF], as the distinction between ignorance and conflict is crucial to our communication policy. Algorithm 1 details this procedure.

Algorithm 1: Fusion procedure for two pseudo-Bayesian mass functions 1 and 2 .

Input: Two pseudo-Bayesian mass functions 1 ,

2

Output: The fused mass function 12

← len( 1 );

12 [ ] ← 1 [ ] . 2 [ ]; 12 [1 ∶ -1] ← ( 1 [1 ∶ -1]+ 1 [ ]) . ( 2 [1 ∶ -1] + 2 [ ]) -12 [ ]; ← sum( 12 [1 ∶ -1]); if > 0 then 12 [1 ∶ -1] ← (1 -12 [ ]) . 12 [1∶ -1] ; Return 12 ;

Models

In this section, we will present several versions of the generative model mentioned in section 3.1, namely STD-VAE and LP-VAE. In the end, this generative model will provide us with learned features describing the state of the environment related to the MDP presented in section 3, in order to reduce the size of the network optimized through DRL and to control what is kept in the information flow. We will start by formalizing in section 4.1 a draft of this model that ignores the actions the agent takes at each time step.

Then, we will briefly introduce in section 4.2 the original TD-VAE [START_REF] Gregor | Temporal difference variational auto-encoder[END_REF]. Following that, we will propose in section 4.3 our sequential variant of TD-VAE, i.e. STD-VAE. Inspired by this model, we will then propose LP-VAE in section 4.4. Finally, section 4.5 will demonstrate with LP-VAE how to modify this generative model to incorporate the actions chosen by the agent.

Action-independent modeling

As a vehicle clearly cannot access the complete state of its surroundings through its sole perception, we can model our problem as a Partially Observable Discrete-Time Markov Chain (PO-DTMC), where and denote random variables representing respectively a partial observation and a latent state at time . However, we consider that and are in different spaces, the latent space describing the whole environment and containing information about object dynamics and trajectories allowing for predictions. More precisely, corresponds to the sole perception of the ego-vehicle at time , without memory of the past. We also introduce a third random variable which represents the spatially complete observation corresponding to in the space of . In other words, is a partial observation of which is itself a partial observation of .

So, let be a set containing the parameters of a generative model that projects a latent state onto the observation space as ( , ). We choose to implement this generative model as a deep neural network and we set the following Gaussian distributions as constraints, for numerical stability and simplicity:

• ∼  (0, )

• +1 | (⋅| ; ) =  ( ( ; ), 2 ( ; ). ) • | (⋅| ; ) =  ( ( ; ), . | | ) • | , (⋅| , ; ) =  ( ( , ; ), . | | ) where , ,
and are all deep neural networks taking their parameters in , where is an arbitrary number of dimensions for , where is a realization of for some ∈ [1, ] and where ⋅ ∈ 1 2 , +∞ . This last constraint implies that the generative model recreates independently each dimension of from a latent state with the same fixed precision. Moreover, the PO-DTMC formulation implies that each pair of observations ( , ) is only dependent on , i.e. ... Thus, based on a dataset of independent sequences of partial and complete observations = ( 1∶ , 1∶ ) 1∶ , we want to optimize the parameters so that the probability that the model generates the sequences of is maximal under its constraints. In other words, we want to find the parameters that maximize ( , ) (1) ,…,( , ) ( ) ( ; ), which is the same as finding maximizing log ( , ) (1) ,…,( , ) ( ) ( ; ). We have:

log ( , ) (1) ,…,( , ) ( ) ( ; ) = ∑ ( , )∈ log , ( , ; ) where , ( , ; )
= ∫ , | ( , | ; ) . ( ; ) = ∫ ⋯ ∫ ( 1 ). ∏ =1 , | ( , | ; ) . ∏ =2 +1 | ( | -1 ; ) ∏ =1
which is intractable, due to the fact that , , and are multi-layers neural networks with nonlinearities. This intractability is amplified by the fact that we work with sequences of non-independent continuous latent states, which implies a multiple integral over ℝ × . This means that we cannot evaluate or differentiate the marginal likelihood , ( , ; ). For the same reasons, the posterior distribution

| , (⋅| , ; ) = , | ( , | ⋅ ; ). (⋅ ; ) , ( , ; )
, is intractable, which implies that methods based on the posterior distribution such as the Expectation-Maximization (EM) algorithm cannot be employed either. So, let us adopt the Variational Bayesian (VB) approach by introducing a variational distribution dependent on a parameter set to approximate | , (⋅| , ; ). But, more than just a mathematical trick, we want this variational distribution to actually be a recognition model such that it is able to infer latent states only given past partial observations, in order to infer and to be able to generate plausible next observations.

TD-VAE model

TD-VAE [START_REF] Gregor | Temporal difference variational auto-encoder[END_REF] is a variant of the original VAE [START_REF] Kingma | Auto-Encoding Variational Bayes[END_REF] for temporal sequences which features the particularity to separate belief states from latent states. A belief state is a statistics describing 1∶ such that | 1∶ (⋅| 1∶ ; ) ≈ | (⋅| ; ). The end goal motivating this distinction, aside theoretical accuracy, is to learn a model able to deterministically aggregate observations by updating a statistics that contains enough information to infer some latent state , avoiding the accumulation of estimation errors on 1∶ -1 . Since alone allows for predictions of next latent states, constitutes a belief on plausible latent dynamics that is simply updated with each new observation. This feature is important for model-based RL.

In [START_REF] Gregor | Temporal difference variational auto-encoder[END_REF], they chose additionally to make their model provide jumpy predictions, i.e. directly predicting a latent state + from some where is not precisely known, in order to abstract latent dynamics for the benefit of computational efficiency. Formally, they seek to optimize so that it maximizes the expression

∼ [ , ] ∼ [1, -] log + | + | ; , (3)
where  [ , ] is the uniform distribution on the interval [ , ] and = RNN( , -1 ; ). This cannot be optimized directly, as showed in the previous section. However, we can maximize a lower bound of this expression by introducing a variational distribution.

Let , ( ) = , + | , + (⋅| , + ; ) be this variational distribution, dependent on a parameter set , such that

, + | , + ⋅| , + ; ≈ , + | , + ⋅| , + ;
where it is important to notice that

, + | , + ⋅| , + ; = + , , + | + , ⋅| ; + | + | ; = , ( ) + | + | ;
.

To find the optimal parameters that minimize its approximation error, we can optimize so that it minimizes through gradient descent the following average Kullback-Leibler (KL) divergence:

∼ [ , ] ∼ [1, -] , ( ) | | | | | | | | , ( ) + | + | ; ,
This cannot be optimized directly either. Yet, it can be shown that we can equivalently minimize this divergence, while also maximizing a lower bound of (3), by minimizing the following loss w.r.t. and : .

 TD-VAE ( ; , ) = ∼ [ , ] ∼ [1, -] , ( ) || , ( )
In complement, the authors of [START_REF] Gregor | Temporal difference variational auto-encoder[END_REF] ⋅| ; can be seen as a rough approximation. This abstraction of latent dynamics may be useful in some cases where precision is not needed and the variability of observations ∶ + gathered in a moment can be summarized in latent space by smooth transitions between states corresponding to dataset samples. However, we argue that models of complex environments, in which the observation space is combinatorially extremely large and in which multiple agents interact with each other, require precise learning signals to understand latent dynamics and so to generalize well outside the training set. More importantly, TD-VAE cannot consider the actions taken by the observing agent between and + . Yet, learning the link between actions and observations is central in RL.

Our Sequential variant STD-VAE of the TD-VAE model

The authors of [START_REF] Gregor | Temporal difference variational auto-encoder[END_REF] also proposed a sequential version of their model. Its corresponding Bayesian network is given in Fig. 6. They chose to train its parameters as a particular case of the jumpy one, simply taking = 1. Yet, this would only maximize a lower bound of the probability to observe +1 after , i.e.

∼ [1, -1] log +1 | +1 | ;
, instead of the whole future sequence +1∶ after , i.e.

∼ [1, -1] log +1∶ | +1∶ | ; .
From a practical point of view, this would prove to be computationally heavy if done multiple times per sequence and would not learn from the accumulation of prediction errors: particularly in a stochastic network such as TD-VAE and with a time step small enough, the network will tend to optimize weights such that the predicted next state looks almost identical to the initial state. It is only by chaining these predictions that their errors become significant. Thus, we choose a slightly different variational distribution. Let ...

-1 1 2 -1 1 -1
...

( ) = ∶ | ∶ ⋅| ∶ ;
be this variational distribution, dependent on a parameter set , such that

∶ | ∶ ⋅| ∶ ; ≈ ∶ | , +1∶ ⋅| , +1∶ ;
where it is important to notice that

∶ | , +1∶ ⋅| , +1∶ ; = +1∶ , ∶ | +1∶ , ⋅| ; +1∶ | +1∶ | ; = ( ) +1∶ | +1∶ | ;
.

To find the optimal parameters that minimize its approximation error, we can optimize so that it minimizes through gradient descent the following average Kullback-Leibler (KL) divergence:

∼ [1, -1] ( ) | | | | | | | | ( ) +1∶ | +1∶ | ;
, It can be shown that we can equivalently minimize this divergence, while also maximizing a lower bound of

∼ [1, -1] log +1∶ | +1∶ | ; ,
by minimizing the following loss w.r.t. and :

 STD-VAE ( ; , ) = ∼ [1, -1] ( ) || ( ) where
( ) || ( ) = ∶ ∼ ( ) log | | ; + -1 ∑ = log | , +1 | , +1 ; -log | | ; - ∑ = +1 log +1 | | -1 ; - ∑ = log | | ; (4)
Fig. 7 visually explains the process of evaluating (4), which is very similar to the original TD-VAE. The belief network aggregates observations such that each belief is assumed to be a sufficient statistics for 1∶ . The smoothing network, knowing what the final latent state is, given observations 1∶ , infers what should have been latent states ∶ -1 . This gives us two different distributions for the inference of : one given only observations 1∶ , and the other given all observations 1∶ . In the learning phase, we measure the divergence between these two distributions as a loss to prompt correct dynamics recognition and consistency in the belief network. Then, the Markovian transition model infers the next state from the current one. We infer the Gaussian parameters of the next state for each latent state inferred by the smoothing network and measure as loss the divergence between the distribution inferred by the smoothing network and the one inferred by the transition model. Finally, for each latent state sampled from the smoothing network, we infer the Gaussian parameters describing the observation with the decoding network and compute the negative log-likelihood of given these parameters as loss.

However, our preliminary experiments on this model with a dataset acquired in CARLA [START_REF] Dosovitskiy | CARLA: An open urban driving simulator[END_REF] revealed very poor prediction quality when is sampled from | (⋅| ; ), while providing very good predictions when is sampled from | (⋅| ∶ ; ), i.e. from the smoothing network. In fact, this seems obvious considering that the prediction part of this model is trained with the latent states sampled from the variational distribution

∶ | ∶ ⋅| ∶ ;
and not

Our Locally Predictable VAE (LP-VAE) model

First, we put a local predictability constraint for the model to be able to predict multiple time steps into the future:

| 1∶ (⋅| 1∶ ; ) ≈ | , (⋅| , ; ) (5)
for any instant ≥ min . This means that there must be some instant min such that the partial observations 1∶ min are sufficient to recognize the latent dynamics of the whole sequence, i.e. such that all observations 1∶ and all subsequent partial observations min +1∶ bring negligible additional information in the recognition of these latent dynamics. Notice that Actually, to achieve both these objectives, we only need to minimize

 LP-VAE ( , ; , ) = ∼  [ min , -1] ( , ) || ( ) (8)
w.r.t. both and . See Appendix A for more details. Developing the KL divergence of Eq. ( 8) to make our recurrent distributions appear, we finally obtain:

( , ) || ( ) = ∼ ( , ) log 1∶ | 1∶ ( 1∶ | 1∶ ; ) + log +1∶ | ( +1∶ | ; ) - ∼ ( , ) log 1∶ ( 1∶ ; ) + log +1∶ | ( +1∶ | ; ) + log , | ( , | ; ) = 1∶ | 1∶ (⋅| 1∶ ; ) || 1∶ (⋅ ; ) - ∼ ( , ) log , | ( , | ; ) (9)
which leads to

( , ) || ( ) = ∼ ( , ) log | | ; + -1 ∑ =1 log | , +1 | , +1 ; -log 1 ; - ∑ =2 log +1 | | -1 ; - ∑ =1 log , | , | ; (10)
Fig. 8 illustrates the process of evaluating [START_REF] Chaveroche | Focal points and their implications for möbius transforms and dempster-shafer theory[END_REF]. We can easily give an interpretation to this loss: we can identify two global objectives in Eq. ( 9) that are reminiscent of the original VAE [START_REF] Kingma | Auto-Encoding Variational Bayes[END_REF] in terms of interpretation: the term is an encoder loss for the recognition model of parameters , while the second term is a decoder loss for the generative model of parameters . It can be viewed as a precision loss (second term) optimized against a regularization (first term) to prevent from overfitting.

We can even go deeper in interpretation to highlight what differs from the original VAE. Contrary to the original VAE, our model generates a sequence of observations instead of an isolated one. Doing so, we have a Markovian transition model that predicts a latent state from the previous one with its own set of parameters separated from the decoder ones. Therefore, it seems natural to have a third loss term for prediction. We can make it appear by splitting the second term of Eq. ( 9), i.e.:

( , ) || ( ) = 1∶ | 1∶ (⋅| 1∶ ; ) || 1∶ (⋅ ; ) - ∼ ( , ) log ( , ) 1∶ | 1∶ (( , ) 1∶ | 1∶ ; ) - ∼ ( , ) log ( , ) +1∶ | +1∶ (( , ) +1∶ | +1∶ ; )
The first term is an encoder loss. The second term is a decoder loss. The third term is a prediction loss. This prediction loss can also be viewed as a loss optimized against a regularization since the term affects the inference of by the recognition model from which the next latent states are predicted.

LP-VAE with actions

The models we described up to this point represents the environment evolving around the observing agent. However, our agent also acts on this environment and influences the observations gathered to train our model. Thus, we need to modify it in order to integrate this subtlety.

Let be the action applied at time on perceptions. This action describes a mask on the information contained in . This partial information is then transmitted to the observing agent, influencing . It has no influence on the environment evolving around the agent, only on its perception of it. This means that and are not affected by . Moreover, we will now consider that the random variable is the ego-vehicle perception at time , eventually augmented with information from , in accordance with , and combined with the discounted memory of the previous partial observations 1∶ -1 . Fig. 9 provides the corresponding Bayesian network.

We set the following constraints:

• ∼  (0, )

• +1 | (⋅| ; ) =  ( ( ; ), 2 ( ; ). ) • | (⋅| ; ) =  ( ( ; ), . | | ) • | -1 , , , (⋅| -1 , , , ; ) =  ( ( -1 , , , ; ), .
| | ) where all parameters ⋅ and ⋅ are deep neural networks taking their parameters in , and ⋅ ∈ 1 2 , +∞ . Our dataset is composed of independent sequences of partial and complete observations with a randomly chosen bounding box , i.e.

= ( 1∶ , 1∶ , 2∶ ) 1∶ . Fortunately, Eq. ( 7) still holds in this new model. Moreover, we know that the environment does not depend on the actions 2∶ taken on its perception of it and that the actions only mask regions of while not altering the remaining. Finally, since contains the information transmitted from in accordance with , the actions 2∶ do not bring any information for the inference of the latent states 1∶ . Given the Bayesian network in Fig. 9, the actions without knowing ...

-1 1 2 -1 1 -1 ... 2 -1 ... +1 2 -1
... ...

-1 1 -1
... +1∶ do not bring any information for the inference of the latent states +1∶ either. We have:

| 1∶ , (⋅| 1∶ , ; ) = | 1∶ (⋅| 1∶ ; ) Thus, we keep the LP-VAE variational distributions 1 ( ) = | 1∶ (⋅| 1∶ ; ), 2 ( ) = | 1∶ , +1 (⋅| 1∶ , +1 ; ), ( , ) ≈ | 1∶ (⋅| 1∶ ;
). Then, for our local predictability constraint (See Eq. ( 5)), we consider | , , (⋅| , , ; ) instead of | , (⋅| , ; ). Notice that

| , , (⋅| , , ; ) = , , | ( , , ⋅ | ; ) , | ( , | ; ) = ( ) , | ( , | ; )
We take as loss function  LP-VAE ( , | ; , ) instead of  LP-VAE ( , ; , ), where

 LP-VAE ( , | ; , ) = ∼  [ min , -1] ( , ) || ( ) (11)
This loss maximizes a lower bound of

, | ( , | ; ).
Developing the KL divergence of Eq. ( 11) in accordance with our new model, we get: ,,; -log

( , ) || ( ) = ∼ ( , ) log 1∶ | 1∶ 1∶ | 1∶ ; + log +1∶ | +1∶ | ; -log 1∶ 1∶ ; -log +1∶ | +1∶ | ; -log | ( | ; ) -log | , , ( | , , ; ) = ∼ ( , ) log 1∶ | 1∶ 1∶ | 1∶ ; -log 1∶ 1∶ ; -log | ( | ; ) -log | , , ( | , , ; ) which leads to ( , ) || ( ) = ∼ ( , ) log | | ; -log 1 ; + -1 ∑ =1 log | , +1 | , +1 ; - ∑ =2 log +1 | | -1 ; - ∑ =1 log | | ; - ∑ =2 log | -1 , , , | -1 ,
1 | 1 , 1 1 | 1 , 1 ; (12)
In practice however, we will neglect the term -log

1 | 1 , 1 1 | 1 , 1 ;
for several reasons. First, it avoids to optimize parameters that would only be used in the learning phase, while not corresponding to an important component (the complete observation 1 being already considered and containing 1 ). But maybe more importantly, since keeps a memory of past observations in this formulation of the LP-VAE, 1 may also contain information on actions preceding 2∶ that should be given as well if 1 is actually not the start of an episode of interactions in the environment. Not generating 1 allows us to start the inference of latent states at any point of the episode, independently from the previous actions and observations that produced 1 . This means that we can re-use different subsequences of the same training sequence in the learning phase, without having to make sure that 1 do not contain information related to past observations and actions.

Implementation as neural networks

Belief state computation

The grids introduced in section 3.1 are not directly taken as input of our LP-VAE. Beforehand, we train a Convolutional VAE (CVAE) to learn a compressed, essentialized representation of these observations in which spatial features have been extracted. This CVAE is itself separated into 4 independent parts in order to preserve the semantics of these features: a CVAE for the pedestrian channel, another for the car channel, another for static elements (road lines, road, other) and a last one for the ignorance. The projection of into the latent space of this Convolutional VAE is the taken by our LP-VAE. Then, we feed , -1 and the ego-motion to a Multilayer perceptron (MLP) in order to extract features about the motion of road users around the ego-vehicle. The output of this MLP serves as input to a Recurrent Neural Network (RNN) composed of Long Short-Term Memory (LSTM) cells to form and update a belief over the dynamics of other road users. The concatenation of the hidden state of this RNN with and the driving controls represents the belief state at time . Fig. 10 visually sums up this procedure.

Inference of Gaussian parameters

In [START_REF] Gregor | Temporal difference variational auto-encoder[END_REF], they proposed to use what they called D maps1 to infer the Gaussian parameters of any of the distributions over the latent state . It is a part of a LSTM cell (new features multiplied by the input gate), as indicated in Fig. 11, where the output is passed to two fully connected (FC) layers in parallel without activation function, one to determine and the other to determine log( ). Yet, in our sequential setting, this D map becomes a truly recurrent unit, chaining itself multiple times from 1 to 1 in the smoothing network and from 1 to 2 in the prediction network. As for any recurrent network, this poses the issue of vanishing gradients. Furthermore, it lacks the semantics of a transition model: some components could disappear from the frame (forget gate) and some other could become visible or simply move from their initial state (input gate, followed by an addition to the initial components). These are exactly the transformations applied to the cell state of a LSTM cell. Thus, using the cell state of a LSTM cell as latent state mean as in Fig. 11, where ℎ = +1 and input = , solves both the vanishing gradient issue and the lack of model semantics. Giving ℎ as both hidden and cell states also has the effect of implementing peephole connections [START_REF] Gers | Recurrent nets that time and count[END_REF], giving the cell state some control over the input, forget and output gates (the three sigmoïd layers), which better captures sporadic events. In addition, uncertainty should be encoded within the latent state to be self-sufficient for a transition model. This encourages the computation of the standard deviation from with some filtering gate (output gate), which is exactly what a LSTM cell does to output a quantity based on its cell state. Similarly, we use this LSTM cell in the prediction network for +1 | (⋅| ; ), where ℎ = and input = ∅. For the belief network, we keep this D map as there is no propagation in time.

Decoding

So far, we determined the networks outputting distribution parameters describing the latent states used in the evaluation of  LP-VAE , both for the generative model and the recognition model. It remains to propose the decoding network that is part of the generative model and produces and . Given the conditional distributions appearing in  LP-VAE , we need a decoder inferring from and another one inferring from -1 , , and . However, since and are not given in the original space but in a learned compressed one, extracting features from according to the bounding box is not directly possible. One has to decode , extract features according to , decode and then fuse it with the leaked features from . For the sake of efficiency, we will learn to directly extract these features that we denote by the random variable in the learned compressed space and to fuse them with . Thus, in parallel to  LP-VAE , we minimize an extra loss term

- ∑ =2 log | , | , ; , -1 × + tanh × tanh × × + tanh × × + tanh ×

Decoder

Figure 12: Illustration of our decoding architecture. The decoder block infers the partial observation, the spatially complete observation and the masked (as dictated by the bounding box ). It takes as inputs a latent state , a previous partial observation -1 and a bounding box . A rectangle indicates a fully connected layer, while the symbol at its center indicates the activation function applied to its output ( for sigmoid, tanh for hyperbolic tangent and nothing for the identity function). Each updating network is composed of a forget gate (first ) and a D map, i.e. input features (tanh), an input gate (last ) and a fully connected layer.

where corresponds to masked in accordance with and compressed by the same CVAE as for . Note that our dataset becomes = ( 1∶ , 1∶ , 2∶ , 2∶ ) 1∶ . We choose to infer from through a D map as introduced in section 5.2. All other inferences are done through an updating module that is inspired by the updating of a LSTM cell state. The masking of is orchestrated by , producing by filtering. Finally, -1 is updated in two steps. The first update is assumed to change its reference frame and to determine which parts of are visible to the ego-vehicle. This implicitly produces the corresponding to the null action, i.e. the action that consists in doing nothing. We consider this transformation deterministic, given and . The second update transmits the excerpt from to this prior perception, producing the actual influenced by . Fig. 12 depicts these networks. In addition, Fig. 13 illustrates the decoding of by the decoder of the Convolutional VAE.

Experiments

Data acquisition & RL Environment

To conduct our experiments, we chose to work with the open-source driving simulator CARLA [START_REF] Dosovitskiy | CARLA: An open urban driving simulator[END_REF]. Our semantic grids are computed online from a frontal 320 × 480 depth camera with FOV of 135 • and its corresponding pixelwise semantic classification. These simulated sensors are attached to a simulated vehicle autonomously wandering in a city with other vehicles, bikes and pedestrians (see Fig. 2). More precisely, is obtained by counting the number of occurrences of each class in each possible configuration of 4 × 4 consecutive pixels. All classes corresponding to static objects are merged into the class other. Then, in each cell of the resulting 80 × 120 × 5 grid, these numbers are divided by 16 and we add a channel representing ignorance (i.e. Ω) to store the quantity needed to make the sum on all channels equal to 1. We also discount the resulting mass functions by a factor of 0.01 to simulate noise, i.e. all masses are multiplied by 0.99 and 0.01 is added to the mass on ignorance. Finally, thanks to the depth and information about the camera, we create a 3D point cloud of this frontal perception. Thus, to get the 2D grid , we ignore points higher than 2.5 meters and we take the highest of the remaining ones (if more than one point at the same ground coordinates). For this reason, it sometimes happens that the ground under a vehicle is perceived, but not its top, leading to road cells surrounded by car cells, as can be observed in Fig. 2 Left. An important road elevation may also conflict with the threshold of 2.5 meters. This view can be obtained by a LIDAR and a 3D semantic classifier [START_REF] Li | Deep learning for LiDAR point clouds in autonomous driving: a review[END_REF] as well.

Our top-down semantic grids corresponding to complete observations in our model are obtained with a facing ground camera above the ego-vehicle. Doing so, it contains itself some occlusions due to trees, poles, buildings, etc. Thus, it is rather a hint about the true . This grid can also be obtained by the fusion of multiple view points, from a fleet of autonomous vehicles or infrastructure sensors, which can be acquired in the real world. A drone may be able to acquire this information as well. In any case, this ground truth grid is in fact itself uncertain and so is computed as with an ignorance channel.

We created a dataset composed of 1560 sequences of 50 timesteps (5 seconds) each, where each perception is 80×120×6. There are 30 runs in each of four cities available in CARLA, including small towns, big towns and fast lanes. Each run is 35 seconds long and a sequence is recorded every 2.5 seconds, leading to 13 sequences per run, hence the size of our dataset. This dataset provides the grids corresponding to and in the action-independent model of section 4.1. To provide the grids corresponding to as defined in the full model of section 4.5, we created a second dataset from the first one by choosing random regions of to be given to . We also added a visual memory that keeps a buffer of grid cells, transforms their coordinates according to the given motion of the ego-vehicle, discounts their mass functions to account for information ageing and fuses them with the current perception grid, resulting in this . In fact, the first dataset combined with our visual memory and our fusion procedure of Algorithm 1 for ̃ and constitutes the environment in which our agent will learn a communication policy.

Models

During training, we give between 8 and 10 timesteps of observations (i.e. between 0.8 and 1 second) and it is asked to predict between 5 and 10 timesteps ahead, i.e. between 0.5 and 1 second. We use the Mean Squared Error (MSE) loss function to compute the Gaussian negative log likelihoods of observing the grids corresponding to and given latent states. Indeed, this is analog to taking = 1 2 and ignoring the constant term log √ 2 . For the negative log likelihoods on the grid corresponding to , we binarize it by taking the class with maximum mass and use a cross-entropy loss. To account for the fact that the instances of in our dataset are not perfect, we simply do a pointwise multiplication between this loss and the complement to 1 of its ignorance channel (last channel). That way, if does not have any information about a cell, no loss on is actually back-propagated. Furthermore, we weight this cross-entropy loss differently from one channel to another to account for class imbalance. We used the weight vector [100, 10, 1, 0.2, 0.1, 1]. Indeed, on average, there are far less cells containing pedestrians than cells containing the road or any other static class. Doing so, without weights, the network would consider pedestrian as noise and neglect them.

In the following, we compare STD-VAE and LP-VAE for complete grid inference and prediction.

Grid completion

In this experiment, we use the decoder network described in Fig. 12 on the current latent state inferred from to retrieve . Then, we use the network described in Fig. 13 to transform into the complete mass grid . To compare STD-VAE and LP-VAE, we employed two metrics: binary classification accuracy per class and a mass score. Our Mass score metric is computed as the mean of . ̂ over all cells in the grid, where is the true binary complete grid classification and ̂ is a mass grid inferred by some model. Since is binary, it acts as an indicator function for the correct class and the mass score represents the mean mass given to the right class by the model generating ̂ . Results are showed in Table 1.

Prediction

In this experiment, we compare prediction accuracy between LP-VAE and STD-VAE. For this, we study mass variations on the super-class {road, road line}, i.e. the sum of the road and road line grid channels. Indeed, this superclass represents the road layout. Its absence in a cell indicates either road users or the other class. Thus, its mass variations accounts for the dynamics of the whole scene, independently of classification accuracy.

In practice, for each model, we infer a prediction sequence of 10 complete grids ̂ 1∶10 (i.e. 1 second in the future), based on 10 observations (i.e. the past second). From it, we compute the corresponding sequence of 9 grid variations ̂ ′ = ̂ +1 -̂ . We execute the same process with the true complete grids, which produces grids ′ 1∶9 of values ranging in {-1, 0, 1}. We test separately the accuracy on positive and negative changes. For the former, we do a pointwise multiplication between the true complete positive grids max(0, ′ 1∶9 ) and the inferred positive ones max(0, ̂ ′ 1∶9 ). For the latter, we do a pointwise multiplication between the true complete negative grids max(0, -′ 1∶9 ) and the inferred negative ones max(0, -̂ ′ 1∶9 ). We then sum all cells of each grid in the sequence, over 4992 sequences, i.e. 49 920 inferred grids and compare it to the separate sums of positive and negative true changes. Results are displayed in the first two columns of Table 2.

However, note that this binary mask can be quite hard to match, as both the exact location of these changes and their amplitude must be correct. To alleviate this constraint, we repeat this test with blurring filters applied to each grid of ′ 1∶9 . The resulting grids, noted ̃ ′ 1∶9 , are then renormalized so that ∑ max(0, ′ 1∶9 ). max(0,

̃ ′ 1∶9 ) = ∑ max(0, ′ 1∶9 ) and ∑ max(0, -′ 1∶9 ). max(0, -̃ ′ 1∶9 ) = ∑ max(0, -′ 1∶9 )
. This allows for slight misplacements of cells in predicted grids. We repeated this test twice with Gaussian filters, with kernels 5x5 and 11x11. These experiments correspond to the last 4 columns of Table 2. Our LP-VAE outperforms STD-VAE in every of these tests, no matter how hard the constraint on change location is. This means that the predicted changes of LP-VAE are not just better located, but also better shaped than the ones of STD-VAE, as expected by design. Fig. 14 illustrates this experiment.

Policy learning

Here, we finally compare different policies learned with PPO, with and without model to test the benefits of using belief states in our case. Each policy is the best found among iterations of training with 3000 transitions amounting to 500 000 time steps in total. We used a batch size of 60, with 10 epochs on each transition dataset, with a learning rate of 0.0003 and an entropy coefficient of 0.01. We also made the time horizon vary, i.e. we made the hyperparameter vary from 0 to 0.7, in order to see if a medium/long term strategy performs better.

The network learned with PPO has two parts: one for inferring the Value of a state, representing the mean of all potential future rewards, and one for inferring the best action from this same state, representing the policy. Each of these networks is composed of two fully connected hidden layers of 128 and 64 neurons.

Different communication behaviors can be obtained by adjusting reward parameters. In particular, increasing in Eq. 2 will make requests bigger, increasing in Eq. 1 will make requests more focused on completely unknown areas, increasing will make requests more focused on pedestrians and cars, less rewarding in general and so less frequent. We chose the following values: = 0.3, = 36 and = 2. We also added a penalty of -15 for no cooperation at all (i.e. choice of a bounding box with no pixel in it, which means no transmission cost either) to force the agent to play the game. Moreover, approximating the top-down dimensions of cars and pedestrians, we took the following reward densities per squared meter: obj = [540∕(0.7 * 1.6), 540∕(3 * 1.8), 20, 20, 0]. Then, we converted them into rewards per squared cell by multiplying them by our grid resolution. More precisely, we set our cameras in CARLA so that the height corresponds to 40 meters. Thus, our reward densities per squared cell are obj = ( 40 80 ) 2 . obj . Our final rewards are obtained by normalizing obj to [0, 1] by dividing it by its maximum. For the spatial filter, we used the parameters of Fig. 4, i.e. = 0.5, = 0.8, = 1 and = 0.01. In order to evaluate and compare the performance of different policy learning schemes, we take as metrics the mean request size and the mean informational gain over all time steps of a test set with same size and characteristics as the training set described Section 6.1. We applied these metrics to 3 class groups: pedestrians (P), cars (C) and {road lines, road} (R). In these conditions, we compared 3 schemes: PPO on top of the LP-VAE belief state , PPO on top of the STD-VAE belief state and PPO on top of alone (i.e. only the features extracted from the current mass grid by a Convolutional VAE). Each of them has been trained with = 0 (i.e. only immediate rewards matter), = 0.35 and = 0.7, to see if we could benefit from medium/long term strategies. We also compare these policies with a simple random policy that has a 50% chance of making a request and chooses uniformly random size and Learned communication policy performances relatively to a broadcasting policy. The information gain is a mean percentage representing the mass actually gained after request, over the total mass that can be gained, at each time step.

position of bounding box when it does. Table 3 presents our results, in percentage relatively to the maximal information gain and request size possible inherent to a broadcasting policy. All of our learned policies only ask for about 5% of the space around the ego-vehicle, while receiving about 25% of the relevant information the agent lacks. Requiring about 2.5 times more information from the vehicular network for about the same relevant information gain or lower, the random policy is vastly less efficient. It only outperforms the others for pedestrians, which is consistent with the highly random behavior of pedestrians in CARLA. However, PPO + alone and = 0 (i.e. greedy policy) is the policy that performs best overall. Surprisingly enough, taking into account future rewards actually harms performance in our case. A lower discounting factor in the memory module (i.e. observations that are kept longer in memory) would probably make policies perform best with > 0. Furthermore, note that LP-VAE always performs better than the other learned policies when > 0. This is consistent with the fact that LP-VAE has better prediction capabilities and thus provides useful information in its belief state for predicting future rewards.

Conclusions

In this paper, we tried to elaborate an efficient peer-topeer communication policy for collaborative perception. For this, we made agents learn what could be hidden in their blind spots through a generative sequence model that we proposed, named Locally Predictable VAE (LP-VAE). We compared its performance with another generative sequence model for RL applications called TD-VAE that we slightly adapted to our problem by making it both jumpy and sequential, referring to it as STD-VAE. We demonstrated that LP-VAE produces better predictions than STD-VAE, which translated into better performance for policies learned on top of its belief state. However, we discovered in the end that our best communication policy was a greedy one, i.e. one that does not need prediction capabilities. Combined with the fact that we augmented each observation with the discounted memories of past observations, it followed that only a state-less Convolutional VAE was needed for this greedy policy. Overall, our best learned policies only require about 5% of the space around the ego-vehicle, while gaining about 25% of the relevant information the agent lacks. Thus, we proved that learning to value the unknown is much more efficient than employing a broadcasting policy. It is also more efficient than blindly asking for random areas around the ego-vehicle since it requires about 13% of the total information, while gaining less than 25% of the relevant information the agent lacks. In addition, we defined interpretable hyperparameters shaping the reward function corresponding to our problem. This makes it possible to obtain various communication policies, with different tradeoffs between request size and information gain, as well as different class valuations, spatial priorities and valuation of ignorance (i.e. more or less emphasis on total ignorance). For future works, it would be interesting to compare LP-VAE and STD-VAE in RL tasks where future rewards are more important. Also, we would like to test our communication policies in a truly multi-agent context, where the agent would need to take into account the availability of nearby communicating vehicles, and with real sensor data.

A. LP-VAE loss

Figure 2 :

 2 Figure 2: Left: Illustration of an instance of top-down semantic gridcorresponding to a partial observation in our model. Red is for pedestrians, blue is for cars, yellow is for road lines, purple is for road, white is for other and black is for ignorance. The displayed class is the one with the greatest mass. The intensity of its color depends on its mass: the closer to 0, the darker. Notice all the occlusions due to walls or other road users, in addition to the limited distance of perception of the ego-vehicle. Right: Instance of top-down semantic grid corresponding to a complete observation in our model. Actually, this view is obtained with a facing ground camera above the ego-vehicle. Doing so, it contains itself some occlusions due to trees, poles, buildings, etc. Thus, it is rather a hint about the true . This view can also be obtained by the fusion of multiple view points, from autonomous vehicles or infrastructure sensors.

Figure 3 :

 3 Figure 3: Illustration of our decision process: 1) Based on what is known at time , select a bounding box where there is high uncertainty and high probability to discover road users.2) Send this request in global coordinates to the vehicular network (which may consists of both infrastructure sensors and other autonomous vehicles). 3) At time + 1, we expect some vehicles to transmit their perception of this area. In our implementation, complete perceptions are simply obtained by a camera above the ego-vehicle since we focus on the selection of bounding boxes, i.e. 1). 4) The transmitted partial perception is fused with the one of the ego-vehicle at time + 1.

Figure 4 :

 4 Figure 4: Heatmap illustrating our spatial filter for = 0.5, = 0.8, = 1 and = 0.01. Deep blue is 0, while deep red is 1, which means that the reward in a cell located in a blue region will be 0, no matter what is inside. The center of the ego-vehicle is in the middle of the first row starting from bottom.

,

  | ( , | ; ) = ∏ =1 , | ( , | ; ), and that the Markovian property holds in latent space, i.e. ( ; ) = ( 1 ). ∏ =2 +1 | ( | -1 ; ).

Fig. 5

 5 Fig.5provides the Bayesian network corresponding to our model.

2

 2

Figure 5 :

 5 Figure 5: Bayesian network of our generative model of parameters in . We have replications of this model, corresponding to the sequences of length in our dataset. The parameter set influences the inference of all variables in the model for the sequences we have.

2

 2

Figure 6 :

 6 Figure 6: Bayesian networks corresponding to STD-VAE. Solid lines represent the Bayesian network of our generative model (without ) of parameters in . Dashed lines represent the Bayesian network of the recognition model of parameters in proposed by TD-VAE. Parameter dependencies are not represented for the sake of clarity. Onlyis not directly influenced by , while only variables at the end of a dashed arrow are influenced by . We have replications of this model, corresponding to the sequences of length in our dataset.

  ∶ | ⋅| ; . This is what motivates the introduction in the next section of a local predictability constraint, allowing us to train our model on samples from ∶ |⋅| ; . This will also allow us to keep the idea of predicting distant latent states from current observations while avoiding the strong assumption that |

1 Figure 7 :

 17 Figure 7: Illustration of the forward computations allowing for the evaluation of the STD-VAE loss (4). A diamond indicates a deterministically inferred variable. A rectangle indicates the deterministic inference of distribution parameters. A circle indicates the deterministic inference of distribution parameters and a sample from this distribution. The blue network is the belief network. The red network is the smoothing network. The black network is the Markovian transition model. The brown network is the decoding network.

Figure 8 :

 8 Figure 8: Illustration of the forward computations allowing for the evaluation of the LP-VAE loss. A diamond indicates a deterministically inferred variable. A rectangle indicates the deterministic inference of distribution parameters. A circle indicates the deterministic inference of distribution parameters and a sample from this distribution. The blue network is the belief network. The red network is the smoothing network. The black network is the Markovian transition model. The brown network is the decoding network.

2 Figure 9 :

 29 Figure 9: Bayesian network of our generative model of parameters in . We have replications of this model, corresponding to the sequences of length in our dataset. The parameter set influences the inference of all variables in the model for the sequences we have.

Figure 10 :Figure 11 :

 1011 Figure 10: Illustration of the process of computing the observation and the belief state from , -1 , and . Four independent Convolutional VAEs are trained to learn a sufficient representation of pedestrian, car, {road lines, road, other} and ignorance. These encodings form . A Multilayer perceptron (MLP) tries to learn features about the motion of road users around the ego-vehicle. The output of this MLP serves as input to a Recurrent Neural Network (RNN) composed of Long Short-Term Memory (LSTM) cells to form and update a belief over the dynamics of other road users. The concatenation of the hidden state of this RNN with and the driving controls represents the belief state at time .

Figure 13 :

 13 Figure 13: Illustration of the decoding of or or by the decoder of the CVAE that gave to get back into the observation space. The CNN blocks are Transposed CNNs.

Figure 14 :

 14 Figure 14: (a) Left column: partial grid corresponding to . Right column: complete grid corresponding to . Top row: true classification grids. Bottom row: classification grids predicted by LP-VAE from alone, 4 time steps in the future. (b) Prediction dynamics. Black represents the absence of variation, white some mass change in the cells of the road and road line channels of the grid in (a). Left column corresponds to the true variations, blurred by a 11x11 Gaussian filter. The central column corresponds to the prediction dynamics of STD-VAE, multiplied by the ones of the first column. Same for the right column but for LP-VAE. The first row represents positive changes, while the second row represents negative ones.

  ⋅| ; as a multivariate normal distribution with diagonal covariance matrix, corresponding to the distribution of latent states at any instants in [ + , + ]. This is in contradiction with our sequential latent model ⋅| ; , which is itself a multivariate normal distribution with diagonal covariance matrix. In this regard,

					had to make the strong
	assumption that	|	⋅| ;	=	|	⋅| ;	for any
	, . They also set

+ | +1 | + |

Table 1

 1 Mass score and binary classification accurracy per class. P indicates the pedestrian channel, C the car channel, RL the road lines channel, R the road channel, O the other channel and Ω the complete out-of-sight channel. It is clear that STD-VAE outperforms LP-VAE for simple grid completion, though the total mass score is not so different.

			Binary classification per class		Mass
		P	C	RL	R	O	Ω	score
	LP-VAE	20.5%	68.5%	28.7%	84.3%	77.8%	49.5%	68.3%
	STD-VAE	33.7%	72.7%	30.7%	85.9%	80.6%	46.2%	68.8%

Table 2

 2 Prediction accurracies between STD-VAE and LP-VAE. As expected, LP-VAE significantly outperforms STD-VAE on predictions.

Table 3

 3

In[START_REF] Gregor | Temporal difference variational auto-encoder[END_REF], they used a 16-layer model where the information transits from layer to layer through the states of a LSTM, possibly in place of this D map, in their DeepMind Lab experiment. Note however that it is recurrent through layers, not time. This is different from what is proposed here.

⋆ This work was carried out and co-funded in the framework of the Labex MS2T and the Hauts-de-France region of France. It was supported by the French Government, through the program "Investments for the future" managed by the National Agency for Research (Reference ANR-11-IDEX-0004-02).

( ) || ( ) , which we cannot minimize directly, due to the intractability of , ( , ; ) and | 1∶ (⋅| 1∶ ; ). However, we have:

since the KL divergence is always nonnegative for two probability distributions. So, by optimizing to minimize

( ) || ( ) , we maximize a lower bound of , ( , ; ), which is our primary goal. Thus, we can simply introduce a variational distribution to approximate | 1∶ (⋅| 1∶ ; ) as long as we simultaneously minimize the aforementioned KL divergence. Such a variational distribution corresponds to a recognition model that tries to predict the next latent states in addition to recognizing the current and past ones, which is more useful than one that would directly approximate | , (⋅| , ; ). Notice that:

omitting variable indices in distribution indices for the sake of clarity. Based on this decomposition, let us introduce two variational distributions 1 ( ) = | 1∶ (⋅| 1∶ ; ) and 2 ( ) = | 1∶ , +1 (⋅| 1∶ , +1 ; ) taking their parameters in the parameter set such that:

). We assume that both | 1∶ (⋅| 1∶ ; ) and | 1∶ , +1 (⋅| 1∶ , +1 ; ) have an approximate Gaussian form with an approximately diagonal covariance matrix, i.e.

1 ( ) =  ( ( 1∶ ; ), ( 1∶ ; ). ) 2 ( ) =  ( ( 1∶ , +1 ; ), ( 1∶ , +1 ; ). ), where , , and are deep neural networks taking their parameters in the parameter set . Taking back Eq. ( 7), we get:

, which means that posing our two variational distributions 1 ( ) and 2 ( ) is equivalent to posing the variational distribution ( , ) ≈ | 1∶ (⋅| 1∶ ; ). Therefore, we want to optimize and to minimize ( , ) || ( ) , we maximize a lower bound of , ( , ; ). ■


C Van Geem

T Sim

KCD: a Collision Detector for Path Planning in Factory Models

A critical operation in robot path planning is the veri cation for collision between the robot and the obstacles in its environment. In this contribution we present a new collision detector KCD dedicated to path planning for mechanical devices and robots in industrial-size CAD models. We describe the architecture of KCD and the way in which it is applied in the path planning tool Move3D. We report on experimental results showing its performance.

Introduction

A collision detection algorithm takes as input a soup of possibly moving objects and determines whether or not any of these objects clash. The algorithm may return a boolean result, the minimal distance between the nearest pair of objects, all pairs of colliding objects, or an estimation of penetration in case of collision. Applications may have to feed the algorithm with a particular format or may need particular feedback. Preconditions on the representation of objects can be exploited by an algorithm (e.g. if all objects are convex) resulting in gain of e ciency over loss of generality.

In this paper we will apply collision detection in the frame of path planning with the probabilistic roadmap planning approach (PRM, see 13], 2]). This method constructs a roadmap (or graph) of randomly generated collision-free robot con gurations (nodes) connected by collision-free local paths (edges). A particular path planning problem is then reduced to a graph search. Our goal is to plan motions for mechanical devices (cranes, carts, trucks,...) and robots in complex CAD models of industrial sites (object representation by solids, CSG, and possibly non-convex polyhedra), where most objects do not move. This path planning problem is application oriented and the main topic of the European project Motion for Logistics (MOLOG).

In Section 2 we present a brief overview of the use of collision detectors in path planning and CAD modsupported by the MOLOG project (Esprit IV, LTR 28226), now at KINEO Computer Aided Motion.

elling. Section 3 presents the main contributions of this paper, which are the development of the collision detector KCD -dedicated to path planning for articulated devices in complex CAD models -and the way in which collision detection is used for path planning purposes in the platform Move3D (see 23]). KCD allows e cient planning of guaranteed collision-free paths. We report experimental results in Section 4, before concluding.

Related Work

Extensive and recent surveys on collision detection are published (e.g. 17], 12], 10]). Software of several collision detectors are freely available for research purposes. In this section we concentrate on the observations we made while reading about and experimenting with collision detection algorithms in the frame of path planning applications in industrial models.

Collision Detection Usually the input of a collision detector is a soup of objects, all objects can and do move a priori. Some CDs allow the user to de ne the pairs of objects that have to be tested or ignored; e.g. collision pairs in I Collide [START_REF] Cameron | Enhancing gjk: Computing minimum and penetration distances between convex polyhedra[END_REF]), V Collide [START_REF] Hubbard | Collision Detection for Interactive Graphics Applications[END_REF]).

Computation often falls apart in three stages: preselection of possibly colliding objects, focussing on entities of the selected objects more likely to collide, and precise computation of a collision or of a witness of disjointness. Pre-selection and entity focussing are usually based on computations with bounding volumes (BVs) that approximate the real objects.

The e ciency of a CD depends on the representation of the objects: the convexity in 5] allows ecient entity focussing. The choice of adequate BVs depends on the original objects: spherical shells [START_REF] Klosowski | E cient Collision Detection Using Bounding Volume Hierarchies of k-DOPs[END_REF]) and pie-slices ( 1]) are well-suited BVs for tesselated surfaces whereas oriented bounding boxes (OBBs, 8]) and k-DOPs [START_REF] Kavraki | Towards Planning for Elastic Objects[END_REF]) do better for rather spherical objects. Also, when objects move, their BVs must move or must be recomputed.

Di erent collision detectors use di erent representations and algorithms at the stage of precise computation and return di erent kinds of information. V Collide and RAPID [START_REF] Gilbert | A fast procedure for computing the distance between complex objects in three-dimensional space[END_REF]) test intersection between two triangles, hence only nd collisions between triangularized surfaces. SOLID [START_REF] Simeon | Computer aided motion: Move3d within molog[END_REF]) uses an iterative method to nd a witness of disjointness or a pair of nearest points of two convex solids. V-Clip [START_REF] Lin | Collision Detection between Geometric Models: A Survey[END_REF]) computes the distance between two non-intersecting convex polyhedra or a penetration measure in case of collision.

Path Planning Applications Several collision detection algorithms were used for path planning (e.g. RAPID in 14], I Collide in 22], V Collide in 19], SOLID in 3]). The choice of a particular CD algorithm is often based upon the feed-back given by the CD and needed for the planning algorithm. In 26] V-Clip is used because it returns information on penetration. Usually, whereas the planning problem is di cult to solve for a planning algorithm, the environments have simple geometry.

CAD Applications. Some contributions to the eld of CD are applied to industrial scenes. These include research aimed at the introduction of Virtual Reality techniques for car industry [START_REF] Wilmarth | MAPRM: A Probabilistic Roadmap Planner with Sampling on the Medial Axis of the Free Space[END_REF], 28]) and cooperation with Boeing ( 9], 15]). There exist also some path planning applications in industrial environments [START_REF] Nissoux | Visibility based probabilistic roadmaps[END_REF], 25]). In all these applications unimportant cavities are omitted, models are simpli ed, the number of calls to the CD minimized.

3 KCD for PRM in CAD Models.

Previously we used several of the above mentionned collision detection packages in the motion planning platform Move3D 23], but none of them are designed for the particular application in path planning for devices in CAD models. Therefore we decided to develop our own collision detector. KCD can be seen as a hybrid collision checker that contains pre-selection and entity focussing techniques as in V Collide for handling complex scenes, and precise computation techniques as in SOLID allowing to process composite models made up of possibly concave polyhedra together with volumic primitives (spheres, tubes, cones,...). Furthermore, when no collision is found, KCD can return a distance estimate to the nearest obstacle. In this section we rst indicate the particularities that motivate the architecture, after which follows its description.

KCD and CAD. Collision detection becomes more

time consuming in CAD models due to their high geometrical complexity. Hence we aim for a reduction of the size of the data structures proper to the collision checker without loss of exactness and solvability of the path planning problem. The limitation of the size of the data structures also leads to a faster initialization phase when charging a model.

We observed in experiments with V Collide that the notion of object is important. In a rst stage we dened a V Collide object for each of the polyhedra in the scene. This resulted in too many small axis aligned bounding boxes (AABBs) and most computation time was spent in the pre-selection stage. The OBB-trees on the set of the triangularized facets had an unecient height. Grouping the triangles of several polyhedra in one V Collide object increases performance. However, the notion of object in a CAD system usually groups primitives with the same semantics (e.g. the piping part of the environment) rather than the primitives of one geometrical object, potentially affecting the e cacy of the OBB-trees built on top of the grouped primitives. In the initialization phase of KCD we try to group the primitives automatically in a geometrically meaningful way.

Primitives are simple solids in many CAD systems. Therefore KCD allows a mixture of solids and convex facets. Solids need not to be approximated by polyhedra since in the third stage we apply the GJK algorithm.

The CAD models used in industrial applications may be recycled models, designed for other purposes than path planning. Often objects are more detailed than necessary for path planning. KCD lters away unnecessary details in a conservative way.

KCD and Path Planning. The pre-selection stage of KCD exploits the fact that in CAD path planning applications most objects of the model are xed. KCD pre-processes the static part of the model at the initialization phase of the internal data structures and thus avoids the general notion of collision pairs at the basis of the nbody mechanism in V Collide for the preselection of possibly colliding object pairs. Probabilistic Roadmap planners make extensive use of collision detection for node and edge veri cation. When the CD only returns a boolean answer, edge veri cation is done by a high number of calls to a static collision detector for con gurations along a chosen path between two nodes. In this case some collisions may not be detected when occuring between two consecutive tested collision-free con gurations. The path planner can bene t of supplementary information like a distance estimate to the nearest obstacle or BV. It allows fewer calls to the CD and guarantees collision-freeness of the paths along the edges of the roadmap. Moreover, path planning applications may require to take into account a user-de ned security distance; an extra reason to require distance estimation.

KCD Architecture.

In order to treat the static part of the model seperately, we introduce the notion of object type: static obstacle and moving object (for each link of a device as well as for a freight). KCD tests each moving object for collision with the obstacles, as well as pairs of moving objects. KCD only allows to de ne the pairs of moving objects to be tested, a necessary feature for articulated devices with adjacent always intersecting links in their geometrical model.

The choice of the bounding volumes (AABBs and OBBs) is also motivated by the observation that since most objects do not move, their bounding volumes must never be re-computed. Furthermore, the placement of OBBs around movable objects can be expressed with the same transformation matrix as for the movable object.

Initialization for pre-selection We rst structurize the static objects. We construct a hierarchy of AABBs and group the objects automatically according to their placement in workspace. We put an AABB around each of the primitives. Pairwize overlapping AABBs belonging to the same CADobject are grouped in an AABB on the next level in the hierarchy and de ne a geometrically meaningful KCD object. For the higher levels of the hierarchy we repeat the grouping of pairwize overlapping AABBs of any of the AABBs in the previous level. The AABB hierarchy is a tree with nodes having multiple child nodes. An AABB is placed around each movable object as well. The AABBs are used in the pre-selection stage.

Initialization for entity focussing We use binary OBB-trees around the KCD-obstacles and around each of the moving objects. The construction of these trees is done in two steps. Firstly an OBB-tree is constructed on each polyhedron and an OBB is places around each solid. Secondly an OBB-tree is constructed on top of these for each KCD-obstacle. The OBB-trees are binary trees constructed in a top-down fashion, starting of with one large OBB around the whole collection of geometrical data and creating two smaller OBBs around half of the geometrical data used for the construction of their parent box. The rst kind of OBB-tree takes as input the convex facets of the polyhedron and the triangles computed by a triangulation algorithm applied to its non-convex facets.

The second kind of OBB-tree takes as input the OBBs around the solids in the KCD-obstacle and the OBB in the root of the OBB-tree of the polyhedra in the KCD-obstacle. The resulting OBB-tree on the KCDobstacle is connected to the OBBs and OBB-trees at its leafs. Each movable object is treated in the same way as a KCD-obstacle for the OBB-tree construction.

Figure 1: object OBB-tree, AABBs of its primitives.

Precise computation As in SOLID, we use the enhanced GJK method ( 7], 4]) on the lowest level: simple solids can be treated as such (see 6]). Since we treat convex facets at the lowest level, we can put an OBB-leaf around a convex facet rather than only a triangle (as required by 8]).

Processing queries It is up to the user to decide whether KCD reports on collision by true or false without further information, or it returns a distance estimate in case of non-collision for each of the movable objects. At each of the three stages faster procedures return only boolean values. The distance estimate is the smallest value computed at one of the levels to decide for non-collision, and therefore is only a conservative estimate. The distance-mode also allows the user to set a safety distance.

The overlap test for AABBs is applied to the AABB hierarchy starting at the root of the tree. When all child boxes intersect an AABB of a movable object, testing is stopped at that level of the tree and the parent AABB is stored. This mechanism results in a collection of AABBs for each of the movable objects. Each AABB contains obstacles that potentially collide. If already at this stage no collision occurs, and if the user asked for a distance estimate, the smallest distance between the AABBs of the movable objects and the visited AABBs of the static environment is returned.

The overlap test for two OBBs limits computations more than the corresponding function in RAPID. The version returning a boolean answer tests at most 15 cases in its quest for a separating axis. A minor modi cation to this algorithm allows to compute the distance between the boxes. The overlap test is called recursively on the OBB-trees of objects in the AABBs selected at the rst stage. Again, if already at this stage no collision occurs, and if the user asked for a distance estimate, the smallest distance between the OBBs of the movable objects and the OBBs of the static environment is returned.

At the lowest level the GJK algorithm is called on the geometrical elements englobed by the leafs of the OBB-trees. As in SOLID, two di erent algorithms deliver two di erent types of answers: a boolean reply or a distance. This test is called when in both of the OBB-trees a leaf is reached.

Omitting details of the scene Another useful feature of KCD is the possibility to lter out details of objects that are useless for path planning purposes. We call a bounding box small when its volume (or the surface of degenerate bounding box around a facet) is smaller than v 3 (or v 2 ) for a given value v. At the initialization of the internal data we stop the top-down construction as soon as the parent bounding box groups only small bounding boxes. When the bounding box of a primitive or a facet is small, we do not call GJK for that primitive or facet. Similar to the ltering technique at the initialization of the internal data structures, the user can demand to omit detailed checking during the queries. Upon request, KCD does not descend any further as soon as a small bounding box is treated, even if this internal data structure exists. The result returned by KCD is thus guaranteed more conservative than without ltering.

Checking path validity For a tested collision-free con guration along a given path, KCD returns a distance estimate for each movable object, hence for each link of an articulated robot. This allows to compute a collision-free interval in the joint-space of the robot, and to cover the path by collision-free intervals around tested con gurations. Also, collisions along trajectories mostly occur somewhat further away from the collision-free initial and goal con gurations. One expects that dichotomic sampling of a path nds a collision sooner than when sampling the path stepwize. Since most local paths are in collision, dichotomy improves performance of the path planner, as our experiments show. Finally, in the case of articulated devices that may self-collide (e.g. some robot arms, humanoids), it is wise to check for self-collision before starting the computation with the rest of the model.

5 Experiments in Move3D.

We used the platform Move3D (see 23]) in order to experiment with KCD and to compare with V Collide. Models: We used the three scenes shown in Figures 2 for our experiments. The complexity of the di erent models is indicated in the table below. The rst line is the total number of polyhedra and solids in the model, the second line is the total number of solids, the third line is the total number of polyhedra. The fourth line is the number of static polyhedra and solids in the model, that is the initial number of AABBs before grouping in KCD objects. The fth line is the number of robot links, hence the number of movable KCD objects in the model. The sixth line is the number of CAD objects in the model, also the number of V Collide objects (both static and movable, since V Collide does not make the di erence). The last line is the number of KCD static objects, after automatic AABB grouping. In the pre-selection stage these are the leafs of the AABB hierarchy. This is also the maximal number of OBB-trees on KCD obstacles tested in the focussing stage against the movable OBB-trees of line 5. In the precise computation phase, KCD will act on solids and the facets of the polyhedra, whereas V Collide acts on the triangulated facets of all primitives (each solid is then approximated by a polyhedron).

Edf Results: The rst table re ects the computation time needed in order to generate 5 nodes of a graph with the PRM-visibility method (see 20]). Grouping several polyhedra in one object improves performance of V Collide due to a better pre-selection. Dichotomy for path veri cation results in less calls to the collision detector. The boolean static collision detecting by KCD is somewhat faster than V Collide. When KCD returns a distance estimate instead of a boolean, the number of calls can be reduced further for path veri cation. This leads to a further gain of e ciency for path planning although the static collision test is more time consuming when a distance must be computed. Note also that the path veri cation is certain when using the distance information. The third table compares the consumption of time and space in the initialization phase. KCD invests more time in the initialization phase but uses less memory than V Collide due to the di erent treatment of solids. When ignoring details, the initialization phase is executed faster and memory usage is further reduced. The last table shows that KCD can take into account a security distance without loss of e ciency. With a higher safety distance more collisions are found in the same amount of time.

CD-along

TPA sd=0.0 sd=50.0 sd=100.0 774/4.1 799/3.9 826/4.1 Safety distance (sd): number of hits/time in sec.

Conclusion.

We presented the new collision detector KCD -dedicated to path planning for articulated devices in complex CAD models. We described the way in which KCD is used for path planning purposes with the platform Move3D. Experiments show that KCD allows efcient planning of guaranteed collision-free paths. In future, it would be useful for path planners if KCD would return a penetration estimate in case of collision.

Figure 2 :

 2 Figure 2: Scenes EDF, Stabilizer and TPA.

  The next table compares the performance for static collision checking. Since a solid in the Stabilizer model are not longer approximated by a polyhedron and its OBB-tree but treated as a solid with just one OBB around it, the proper data structure of KCD is smaller than the one of V Collide and a signi cant gain of performance can be observed.

	CD	obj. path	time answer (sec.) to CD calls
	VCollide pol. stepwise VCollide obj. stepwise VCollide obj. dichotomy bool bool bool KCD obj. dichotomy bool KCD obj. dichotomy dist. Usage for PRM (model: Stabilizer). 2900 14039 118 14039 54 6093 24 6093 11 1822
	Model	hits/ calls	KCD KCD VCollide (bool) (dist.)
	EDF Stabilizer 249/1000 4568/10000 Static collision checking. 3.85 4.87	2.78 1.59	3.90 2.27

  /16sec./44Mb 20.0/21sec./39Mb Initialization (size v of negligable detail/time/memory).The following table shows a gain in performance of KCD when details of the scene (of volume smaller than v 3 or surface smaller than v 2 ) are ignored. Somewhat more collisions are found due to less precision, since we approximate details up to their somewhat larger bounding box.

	Stabilizer	TPA
	VCollide KCD KCD KCD 20.0Value v -/18sec./143Mb 0.0/23sec./96Mb 0.0/27sec./78Mb -/20sec./148Mb 10.0/19sec./61Mb 10.0/24sec./54Mb 0 30 100 300 Collision 250 253 256 256 Time (sec.) 2.11 1.96 1.90 1.85 Initial volume (model: Stabilizer, KCD: 1000 calls).