Rong Li
email: selirong@mail.scut.edu.cn

Anh-Quan Cao
email: anh-quan.cao@inria.fr

Raoul De Charette
email: raoul.de-charette@inria.fr

COARSE3D: Class-Prototypes for Contrastive Learning in Weakly-Supervised 3D Point Cloud Segmentation

Annotation of large-scale 3D data is notoriously cumbersome and costly. As an alternative, weakly-supervised learning alleviates such a need by reducing the annotation by several order of magnitudes. We propose COARSE3D, a novel architecture-agnostic contrastive learning strategy for 3D segmentation. Since contrastive learning requires rich and diverse examples as keys and anchors, we leverage a prototype memory bank capturing class-wise global dataset information efficiently into a small number of prototypes acting as keys. An entropy-driven sampling technique then allows us to select good pixels from predictions as anchors. Experiments on three projection-based backbones show we outperform baselines on three challenging real-world outdoor datasets, working with as low as 0.001% annotations.

Introduction

Semantic segmentation is the holy task of any scene understanding system. For driving, this is of utmost importance, because driving requires a fine-grained 3D understanding for navigation and planning. Subsequently, in recent years, 3D semantic segmentation attracted a plethora of works [START_REF] Cortinhal | Salsanext: Fast, uncertaintyaware semantic segmentation of lidar point clouds[END_REF][START_REF] Hu | Randla-net: Efficient semantic segmentation of largescale point clouds[END_REF][START_REF] Wu | Squeezeseg: Convolutional neural nets with recurrent crf for real-time road-object segmentation from 3d lidar point cloud[END_REF][START_REF] Zhu | Cylindrical and asymmetrical 3d convolution networks for lidar segmentation[END_REF]. However, the vast majority of the literature relies on supervised learning -thus assuming dense point-wise semantic labels -which are laborious and costly to acquire. A striking example is the popular urban dataset SemKITTI [START_REF] Behley | Semantickitti: A dataset for semantic scene understanding of lidar sequences[END_REF], which took more than 1700 hours to label by human operators.

To alleviate this cost, weakly-supervised 3D segmentation uses several orders of magnitude fewer labels [START_REF] Hu | Sqn: Weakly-supervised semantic segmentation of large-scale 3d point clouds with 1000x fewer labels[END_REF][START_REF] Liu | One thing one click: A self-training approach for weakly supervised 3d semantic segmentation[END_REF][START_REF] Wei | Multi-path region mining for weakly supervised 3d semantic segmentation on point clouds[END_REF][START_REF] Wu | Redal: Region-based and diversity-aware active learning for point cloud semantic segmentation[END_REF]. Still, researches are mostly focused on point-based backbones which are efficient but often slow at inference. Conversely, projection-based methods [START_REF] Erdal Aksoy | Salsanet: Fast road and vehicle segmentation in lidar point clouds for autonomous driving[END_REF][START_REF] Cortinhal | Salsanext: Fast, uncertaintyaware semantic segmentation of lidar point clouds[END_REF][START_REF] Milioto | Rangenet ++: Fast and accurate lidar semantic segmentation[END_REF][START_REF] Xu | Squeezesegv3: Spatially-adaptive convolution for efficient point-cloud segmentation[END_REF] were shown to operate at high speed with competitive performance [START_REF] Cortinhal | Salsanext: Fast, uncertaintyaware semantic segmentation of lidar point clouds[END_REF].

In this work, we propose an architecture-agnostic contrastive learning framework for weakly-supervised semantic segmentation. Since our approach does not alter the backbone segmentation, we demonstrate its usage on a lightweight projection backbone, thus enabling both efficient trainings with extreme scarce labels and fast inference. Of paramount importance, contrastive learning needs abundant representative examples [START_REF] Chen | Improved baselines with momentum contrastive learning[END_REF][START_REF] He | Momentum contrast for unsupervised visual representation learning[END_REF][START_REF] Wu | Unsupervised feature learning via non-parametric instance discrimination[END_REF] which is non-trivial to get in weakly-supervised settings. To solve this we introduce two mechanisms. First, we propose a prototype memory bank that stores the global dataset per-class information into a small number of rich and compact prototypes. Second, we employ an entropydriven sampling to select sufficiently good anchors from inaccurate predictions. Experiments show that our method outperform existing weakly-supervised baselines on three real-world outdoor datasets SemKITTI [START_REF] Behley | Semantickitti: A dataset for semantic scene understanding of lidar sequences[END_REF], SemPOSS [START_REF] Pan | Semanticposs: A point cloud dataset with large quantity of dynamic instances[END_REF], and nuScenes [START_REF] Caesar | nuscenes: A multimodal dataset for autonomous driving[END_REF]. On SemKITTI we also show that we on par with full-supervision (i.e., 100% labels) performance, using only 1% of the labels. Our code is released at: https://github.com/cv-rits/COARSE3D.

In brief, our contributions can be summarized as follows:

• We propose an architecture-agnostic framework for weakly-supervised 3D point cloud segmentation and, to the best of our knowledge, first, demonstrate its usage on a lightweight projection backbone. • We introduce a prototype memory bank that captures per-class dataset information with an entropy-driven sampling technique to sample more confident pixels as anchors. • Our strategy significantly outperforms all comparable baselines on three real-world outdoor datasets, with as few labels as 0.001% -roughly corresponding to a single labelled point per frame.

Related Work

Label-efficient 3D Semantic Segmentation. With the abundant annotated large-scale 3D datasets [START_REF] Behley | Semantickitti: A dataset for semantic scene understanding of lidar sequences[END_REF][START_REF] Caesar | nuscenes: A multimodal dataset for autonomous driving[END_REF][START_REF] Dai | Scannet: Richly-annotated 3d reconstructions of indoor scenes[END_REF][START_REF] Liao | KITTI-360: A novel dataset and benchmarks for urban scene understanding in 2d and 3d[END_REF][START_REF] Pan | Semanticposs: A point cloud dataset with large quantity of dynamic instances[END_REF], point cloud semantic segmentation advanced rapidly. The methods can be categorized into point-based [START_REF] Cheng | 2-s3net: Attentive feature fusion with adaptive feature selection for sparse semantic segmentation network[END_REF][START_REF] Hu | Randla-net: Efficient semantic segmentation of largescale point clouds[END_REF][START_REF] Landrieu | Large-scale point cloud semantic segmentation with superpoint graphs[END_REF][START_REF] Radu Alexandru Rosu | Latticenet: Fast point cloud segmentation using permutohedral lattices[END_REF][START_REF] Su | Splatnet: Sparse lattice networks for point cloud processing[END_REF][START_REF] Tang | Searching efficient 3d architectures with sparse point-voxel convolution[END_REF][START_REF] Tatarchenko | Tangent convolutions for dense prediction in 3d[END_REF] and projection-based [START_REF] Erdal Aksoy | Salsanet: Fast road and vehicle segmentation in lidar point clouds for autonomous driving[END_REF][START_REF] Cortinhal | Salsanext: Fast, uncertaintyaware semantic segmentation of lidar point clouds[END_REF][START_REF] Milioto | Rangenet ++: Fast and accurate lidar semantic segmentation[END_REF][START_REF] Wu | Squeezeseg: Convolutional neural nets with recurrent crf for real-time road-object segmentation from 3d lidar point cloud[END_REF][START_REF] Wu | Squeezesegv2: Improved model structure and unsupervised domain adaptation for road-object segmentation from a lidar point cloud[END_REF][START_REF] Xu | Squeezesegv3: Spatially-adaptive convolution for efficient point-cloud segmentation[END_REF] approaches. To learn from fewer labels, various strategies were proposed with point-based methods: enforcing geometric prior [START_REF] Xu | Weakly supervised semantic point cloud segmentation: Towards 10x fewer labels[END_REF], local neighborhood propagation [START_REF] Hu | Sqn: Weakly-supervised semantic segmentation of large-scale 3d point clouds with 1000x fewer labels[END_REF][START_REF] Liu | One thing one click: A self-training approach for weakly supervised 3d semantic segmentation[END_REF], for smarter use of the rare labels some used active learning [START_REF] Wu | Redal: Region-based and diversity-aware active learning for point cloud semantic segmentation[END_REF], pseudo labelling [START_REF] Li | Hybridcr: Weakly-supervised 3d point cloud semantic segmentation via hybrid contrastive regularization[END_REF][START_REF] Shi | Weakly supervised segmentation on outdoor 4d point clouds with temporal matching and spatial graph propagation[END_REF][START_REF] Wei | Multi-path region mining for weakly supervised 3d semantic segmentation on point clouds[END_REF], graph propagation [START_REF] Liu | One thing one click: A self-training approach for weakly supervised 3d semantic segmentation[END_REF][START_REF] Shi | Weakly supervised segmentation on outdoor 4d point clouds with temporal matching and spatial graph propagation[END_REF], self-training [START_REF] Li | Hybridcr: Weakly-supervised 3d point cloud semantic segmentation via hybrid contrastive regularization[END_REF][START_REF] Zhang | Perturbed self-distillation: Weakly supervised large-scale point cloud semantic segmentation[END_REF], temporal matching [START_REF] Shi | Weakly supervised segmentation on outdoor 4d point clouds with temporal matching and spatial graph propagation[END_REF][START_REF] Unal | Scribble-supervised lidar semantic segmentation[END_REF].

Contrastive Learning for 3D. Contrastive learning [START_REF] Chen | A simple framework for contrastive learning of visual representations[END_REF][START_REF] Chen | Improved baselines with momentum contrastive learning[END_REF][START_REF] He | Momentum contrast for unsupervised visual representation learning[END_REF], initially designed for 2D, was extended to 3D using similar points from different views in [START_REF] Hou | Exploring data-efficient 3d scene understanding with contrastive scene contexts[END_REF][START_REF] Lal | Coconets: Continuous contrastive 3d scene representations[END_REF][START_REF] Xie | Pointcontrast: Unsupervised pre-training for 3d point cloud understanding[END_REF][START_REF] Zhang | Self-supervised pretraining of 3d features on any point-cloud[END_REF]. Limited training data is considered in [START_REF] Hou | Exploring data-efficient 3d scene understanding with contrastive scene contexts[END_REF]. Invariant representation is learned from spatio-temporal cues in [START_REF] Chen | 4dcontrast: Contrastive learning with dynamic correspondences for 3d scene understanding[END_REF][START_REF] Huang | Spatio-temporal selfsupervised representation learning for 3d point clouds[END_REF][START_REF] Liang | Exploring geometry-aware contrast and clustering harmonization for self-supervised 3d object detection[END_REF]. Pairs of point and pixels regions were matched in [START_REF] Sautier | Image-to-lidar self-supervised distillation for autonomous driving data[END_REF] while point-pixel pairs are regarded as a whole in [START_REF] Liu | P4contrast: Contrastive learning with pairs of point-pixel pairs for rgb-d scene understanding[END_REF]. We focus the literature on crucial aspects for our work. Sampling Strategy is crucial for constrastive learning that requires many good examples [START_REF] Chen | Improved baselines with momentum contrastive learning[END_REF][START_REF] He | Momentum contrast for unsupervised visual representation learning[END_REF][START_REF] Kaya | Deep metric learning: A survey[END_REF][START_REF] Wu | Unsupervised feature learning via non-parametric instance discrimination[END_REF]. Prior knowledge is used to guide sampling in [START_REF] Bell | Learning visual similarity for product design with convolutional neural networks[END_REF][START_REF] Hadsell | Dimensionality reduction by learning an invariant mapping[END_REF]. Multiple pairs of positive and negative data are sampled in [START_REF] Bucher | Improving semantic embedding consistency by metric learning for zero-shot classiffication[END_REF][START_REF] Sohn | Improved deep metric learning with multi-class n-pair loss objective[END_REF]. To improve convergence, hard negative sampling is exploited in [START_REF] Bucher | Hard negative mining for metric learning based zero-shot classification[END_REF][START_REF] Kalantidis | Hard negative mixing for contrastive learning[END_REF][START_REF] Khosla | Supervised contrastive learning[END_REF][START_REF] Robinson | Contrastive learning with hard negative samples[END_REF][START_REF] Schroff | Facenet: A unified embedding for face recognition and clustering[END_REF][START_REF] Simo-Serra | Discriminative learning of deep convolutional feature point descriptors[END_REF] and point proxies serve as examples in [START_REF] Movshovitz-Attias | No fuss distance metric learning using proxies[END_REF]. To avoid local minima, semi-hard negative sampling is proposed in [START_REF] Cai | Are all negatives created equal in contrastive instance discrimination?[END_REF][START_REF] Schroff | Facenet: A unified embedding for face recognition and clustering[END_REF][START_REF] Xie | Delving into inter-image invariance for unsupervised visual representations[END_REF]. In [START_REF] Cui | Fine-grained categorization and dataset bootstrapping using deep metric learning with humans in the loop[END_REF], false positive images are used as hard negative examples. Since noisy samples were shown to deteriorate performance [START_REF] Chao-Yuan | Sampling matters in deep embedding learning[END_REF], hard positive/negative examples sampling is applied in [START_REF] Khosla | Supervised contrastive learning[END_REF] while highquality anchors are sampled by considering correct prediction in [START_REF] Wang | Exploring cross-image pixel contrast for semantic segmentation[END_REF]. We instead propose entropy-driven anchors sampling techniques to learn more robust representations. Memory Bank introduced in [START_REF] Wu | Unsupervised feature learning via non-parametric instance discrimination[END_REF] allows storing many examples, e.g. pixels in 2D, typically sampled per image [START_REF] Chaitanya | Contrastive learning of global and local features for medical image segmentation with limited annotations[END_REF][START_REF] Wang | Dense contrastive learning for self-supervised visual pre-training[END_REF][START_REF] Xie | Propagate yourself: Exploring pixel-level consistency for unsupervised visual representation learning[END_REF] or mini-batch [START_REF] Wang | Exploring cross-image pixel contrast for semantic segmentation[END_REF] to increase variety. However, such storage comes at the cost of large memory and asynchronous updates. These issues are mitigated using momentum encoder [START_REF] Chen | Improved baselines with momentum contrastive learning[END_REF][START_REF] He | Momentum contrast for unsupervised visual representation learning[END_REF] or keeping examples in recent batches [START_REF] Chen | Improved baselines with momentum contrastive learning[END_REF][START_REF] He | Momentum contrast for unsupervised visual representation learning[END_REF][START_REF] Wang | Cross-batch memory for embedding learning[END_REF]. Pixels

Constrative learning training

Segmentation module

Keys

Entropy-driven sampling are selected randomly [START_REF] Wang | Exploring cross-image pixel contrast for semantic segmentation[END_REF] or selectively [START_REF] Alonso | Semi-supervised semantic segmentation with pixel-level contrastive learning from a class-wise memory bank[END_REF] from each image. Still, only a few pixels are stored due to memory constraints, losing full dataset content. Moreover, using pixels embeddings is redundant [START_REF] Wang | Exploring cross-image pixel contrast for semantic segmentation[END_REF]. Regions [START_REF] Hu | Region-aware contrastive learning for semantic segmentation[END_REF][START_REF] Wang | Exploring cross-image pixel contrast for semantic segmentation[END_REF] can be employed as more compact representation but not with label sparsity settings due to the need of per-pixel annotation. Hence, we propose an efficient memory bank, storing prototypes (instead of pixels) that can capture the class-wise dataset-wise information using only a small number of prototypes.

Prototype Learning aims to represent the embedding space as a set of prototypes. It is used for many tasks like classification [START_REF] Cover | Nearest neighbor pattern classification[END_REF][START_REF] Garcia | Prototype selection for nearest neighbor classification: Taxonomy and empirical study[END_REF][START_REF] Goldberger | Neighbourhood components analysis[END_REF][START_REF] Guerriero | Deepncm: Deep nearest class mean classifiers[END_REF][START_REF] Mettes | Hyperspherical prototype networks[END_REF][START_REF] Salakhutdinov | Learning a nonlinear embedding by preserving class neighbourhood structure[END_REF][START_REF] Wu | Improving generalization via scalable neighborhood component analysis[END_REF][START_REF] Yang | Robust classification with convolutional prototype learning[END_REF], few-/zero-shot [START_REF] Bucher | Hard negative mining for metric learning based zero-shot classification[END_REF][START_REF] Jetley | Prototypical priors: From improving classification to zero-shot learning[END_REF][START_REF] Snell | Prototypical networks for few-shot learning[END_REF], regression [START_REF] Mettes | Hyperspherical prototype networks[END_REF], unsupervised learning [START_REF] Wu | Unsupervised feature learning via non-parametric instance discrimination[END_REF][START_REF] Xu | Attribute prototype network for zero-shot learning[END_REF], explanability [START_REF] Li | Deep learning for case-based reasoning through prototypes: A neural network that explains its predictions[END_REF], and semantic segmentation [START_REF] Dong | Few-shot semantic segmentation with prototype learning[END_REF][START_REF] Vinyals | Matching networks for one shot learning[END_REF][START_REF] Wang | Panet: Few-shot image semantic segmentation with prototype alignment[END_REF][START_REF] Zhou | Rethinking semantic segmentation: A prototype view[END_REF]. Different from the literature, we use prototypes as a memory bank to gather the rich class-wise global context information from the whole dataset efficiently.

Proposed approached

We address the problem of 3D semantic segmentation of point clouds and propose, a novel architecture-agnostic training strategy for weakly-supervised learning coined 'COARSE3D'.

To learn efficient semantic representation from scarce labels, we leverage a custom contrastive learning module whose originality resides in a lightweight memory footprint and sparse embedding optimization. Results show our methodology is efficient with as little as 0.001% of the labelled data -stepping ahead of prior works [START_REF] Hu | Sqn: Weakly-supervised semantic segmentation of large-scale 3d point clouds with 1000x fewer labels[END_REF][START_REF] Xu | Weakly supervised semantic point cloud segmentation: Towards 10x fewer labels[END_REF][START_REF] Zhang | Weakly supervised semantic segmentation for large-scale point cloud[END_REF][START_REF] Zhang | Self-supervised pretraining of 3d features on any point-cloud[END_REF]. COARSE3D, depicted in Fig. 1, uses a custom contrastive module (Sec. 3.1) that projects features of the segmenter encoder into a different embedding space. As for the segmenter backbone, we employ the fast and memory efficient SalsaNext [START_REF] Cortinhal | Salsanext: Fast, uncertaintyaware semantic segmentation of lidar point clouds[END_REF] which processes 3D point cloud as 2D range images. Rather than the greedy pixel-wise memory [START_REF] Wang | Exploring cross-image pixel contrast for semantic segmentation[END_REF], our projected features are clustered into a prototype memory bank (Sec. 3.2) that captures compact class-wise semantic embeddings. This enables preserving the dataset context in a significantly lighter fashion. In each iteration, we optimize only a small subset of pixels (i.e. anchors) sampled with an entropy-based strategy (Sec. 3.3) considering prototypes as positive/negative samples (i.e. keys). Our training strategy (Sec. 3.4) combines standard segmentation and contrastive losses, along with a simple labels propagation strategy.

Contrastive Learning Pipeline

We leverage a contrastive learning scheme since prior works have shown its effectiveness to learn from limited labels [START_REF] Hou | Exploring data-efficient 3d scene understanding with contrastive scene contexts[END_REF][START_REF] Rozenberszki | Language-grounded indoor 3d semantic segmentation in the wild[END_REF][START_REF] Xie | Pointcontrast: Unsupervised pre-training for 3d point cloud understanding[END_REF]. We build on the standard InfoNCE pixel-wise contrastive loss [START_REF] Gutmann | Noise-contrastive estimation: A new estimation principle for unnormalized statistical models[END_REF][START_REF] Van Den Oord | Representation learning with contrastive predictive coding[END_REF] but apply the latter between our class-wise representations, hereafter prototypes (Sec. 3.2), and a subset of sampled pixels (Sec. 3.3).

More specifically, at each training iteration we select a set of pixels, called anchors having features A={a j , ..., a N a }. For each anchor, we select the corresponding prototypes of similar semantic class, i.e. positive keys with features P + ={p + 1 , ..., p + N + }, or different semantic class, i.e. negative keys with features P -={p - 1 , ..., p - N -}. The InfoNCE optimization objective is to simultaneously pull the embedding of anchors towards positive keys while pushing them away from the negative keys. Formally, it writes:

L Pix2Proto = 1 N a ∑ a i ∈A -log ∑ p + j ∈P + exp a i • p + j /τ ∑ p + j ∈P + exp a i • p + j /τ + ∑ p - j ∈P -exp a i • p - j /τ , ( 1
)
where τ is the temperature hyperparameter. All feature vectors are extracted by first linearly interpolating multi-scale features to the full image size. Then, they are concatenated and mapped to 256-dim using two 1×1 2D convolutional layers. Finally, they are 2 -normalized. Following previous works [START_REF] Kaya | Deep metric learning: A survey[END_REF][START_REF] Wang | Exploring cross-image pixel contrast for semantic segmentation[END_REF] that demonstrated the benefit of a custom selection of keys and anchors, we consider a set of anchors sampled using the entropy of the segmentation output and keys from a newly introduced prototype memory bank, that we describe next.

Prototype Memory Bank

The memory bank requires massive data to learn good representation which is traditionally achieved by storing a large number of pixels as in [START_REF] He | Momentum contrast for unsupervised visual representation learning[END_REF][START_REF] Wang | Exploring cross-image pixel contrast for semantic segmentation[END_REF][START_REF] Wang | Cross-batch memory for embedding learning[END_REF][START_REF] Wu | Unsupervised feature learning via non-parametric instance discrimination[END_REF]. Still, this is very costly in terms of memory and computation for contrastive sampling. Furthermore, storing pixels is semantically redundant which can be mitigated by storing semantic regions [START_REF] Wang | Exploring cross-image pixel contrast for semantic segmentation[END_REF]. However, the latter would be poorly reliable given the limited labels. Therefore, we introduce a prototype memory bank that encodes class-wise embedding into compact prototypes. More in-depth, the memory bank stores {P k ∈ R N p ×D } K k=1 prototypes of feature dimension D, corresponding to N p prototypes per class for each of the K semantic classes. For each semantic class k, at each training iteration, we cluster the N k labelled pixels of such class into the corresponding N p class prototypes. We frame this as an optimal transport problem and employ the Sinkhorn algorithm [START_REF] Cuturi | Sinkhorn distances: Lightspeed computation of optimal transport[END_REF], similar to [START_REF] Zhou | Rethinking semantic segmentation: A prototype view[END_REF] because it balances the pixels assignment between all prototypes. Here, note that the prototypes are solely updated from the embeddings of labelled pixels which guarantees reliable information.

In pratice, we compute the optimal transport matrix T ∈ R N k ×N p by unrolling three iterations of the Sinkhorn algorithm on the cost matrix C ∈ R N k ×N p -where C i j is the cosine distance between the feature maps of pixel i and prototype j. The pixel-prototype mapping of pixel p i is obtained with m(p i )=argmax j T i j . In practice, to encourage exploration we use a Gumbel-Softmax (τ=0.5) as differentiable argmax. Given a random initialization, we update each prototype with a σ = 0.999 momentum towards the mean of the clustered pixels embeddings in each training iteration. Hence, j th prototype {P k } j of class k is updated as:

{P k } j = σ {P k } j + (1 -σ ) 1 ∑ N k i=1 m(x i )= j N k ∑ i=1 x i m(x i )= j , (2)
with . the Iverson brackets.

Entropy-driven Anchors Sampling

Prior works have shown the importance of proper sampling in contrastive learning [START_REF] Bucher | Hard negative mining for metric learning based zero-shot classification[END_REF][START_REF] Cai | Are all negatives created equal in contrastive instance discrimination?[END_REF][START_REF] Kalantidis | Hard negative mixing for contrastive learning[END_REF][START_REF] Schroff | Facenet: A unified embedding for face recognition and clustering[END_REF][START_REF] Sohn | Improved deep metric learning with multi-class n-pair loss objective[END_REF][START_REF] Wang | Exploring cross-image pixel contrast for semantic segmentation[END_REF][START_REF] Xie | Delving into inter-image invariance for unsupervised visual representations[END_REF]. However, such strategies are inappropriate in our setup given the limited labels and the need for abundant samples in contrastive learning. Instead, we build on information theory [START_REF] Elwood | A mathematical theory of communication[END_REF] and introduce an entropy-driven sampling technique to select the most appropriate pixels to serve as anchors among the abundant pseudo-labels predictions.

Given an image x processed by the segmentation module, we estimate the quality of the semantic prediction for pixel x i using its Shannon entropy

H(x i ) = -∑ K k=1 f (x i ) log( f (x i ))
, where K is the number of classes and f (x i ) ∈ R K is the softmax prediction. Subsequently, we define the sampling probability as ρ(

x i ) = exp -H(x i ) 2 ∑ x j ∈X exp -H(x j ) 2
where X is set of pixels with the same predicted label as x i . Intuitively, pixels with low entropy will have higher chances to be selected. The power of 2 is used to make the distribution steeper. Finally, we perform weighted sampling to select the N a pixels as a set of anchors A. Unlike standard pixelwise contrastive loss [START_REF] Wang | Exploring cross-image pixel contrast for semantic segmentation[END_REF] requiring thousands of pixels, we start with only one anchor and linearly increase during training -up to 50% pseudo label. This follows the intuition that the segmentation module improves as training progresses.

Training Strategy

To train the method, we first apply a simple voxel propagation scheme to expand labels illustrated in Fig. 1 and detailed in Appendix B.1. We then train with two supervised and one unsupervised loss. First, the focal loss [START_REF] Lin | Focal loss for dense object detection[END_REF] is applied on all labelled points to alleviate classes imbalance:

L foc i = -α(1 -( f (x i )) γ log( f (x i )) , (3)
where α = {w k | y i = k} is the weight of class k, y i the pseudo label of point i, and

w k = log(1 + 1 freq k
) with freq k is the class frequency before voxel propagation. Second, we use the lovász-softmax loss [START_REF] Berman | The lovász-softmax loss: A tractable surrogate for the optimization of the intersection-over-union measure in neural networks[END_REF] to directly optimize the mean intersection-over-union, defined as:

L lov i = 1 k K ∑ k=1 ∆ J k ( m(c)) , with mi (k) = 1 -f (x i ) if k = y i , f (x i ) otherwise, (4)
where ∆ J s indicates the Lovász extension of the Jaccard index for class k. y i is the label of point x i . Finally, the overall training target is

L = ∑ i λ ce L foc i + λ lov L lov i + λ nce L nce i . (5)

Experiments

We evaluate our proposal by comparing against recent baselines on 3 challenging real-world LiDAR datasets, being SemKITTI [START_REF] Behley | Semantickitti: A dataset for semantic scene understanding of lidar sequences[END_REF], nuScenes [START_REF] Caesar | nuscenes: A multimodal dataset for autonomous driving[END_REF] and SemPOSS [START_REF] Pan | Semanticposs: A point cloud dataset with large quantity of dynamic instances[END_REF] and report main results in Sec. 4.2 and ablations in Sec. 4.3. For memory-efficient processing, we evaluate solely on projection-based backbones but COARSE3D is applicable to any architecture (e.g., point-based). In particular main results use SalsaNext [START_REF] Cortinhal | Salsanext: Fast, uncertaintyaware semantic segmentation of lidar point clouds[END_REF] backbone and we experiment with Rangenet-21 [START_REF] Milioto | Rangenet ++: Fast and accurate lidar semantic segmentation[END_REF] and SqueezeSegV3-21 [START_REF] Xu | Squeezesegv3: Spatially-adaptive convolution for efficient point-cloud segmentation[END_REF] backbones in ablations. Importantly, all our components are removed at inference, leaving the segmenter backbone unchanged.

Experimental Setup

Datasets. SemanticKITTI [START_REF] Behley | Semantickitti: A dataset for semantic scene understanding of lidar sequences[END_REF] has 22 German scenes recorded at 10Hz with an HDL-64E LiDAR. We follow common practice and train on sequences 00 to 10, except 08 for validation. The hidden test set uses sequences 11 to 21. nuScenes [START_REF] Caesar | nuscenes: A multimodal dataset for autonomous driving[END_REF] has 850 scenes from U.S.A./Singapore acquired with a VLP-32 LiDAR, labelled at 2Hz. Again, we follow standards using 700 scenes for training and 150 scenes for validation. SemanticPOSS [START_REF] Pan | Semanticposs: A point cloud dataset with large quantity of dynamic instances[END_REF] recorded Chinese campus scenes with @10Hz 40-layers LiDAR. Though much smaller, the dataset has many pedestrians. We train on sequences 00 to 05, except 02 for validation.

Model Selection. For SemKITTI [START_REF] Behley | Semantickitti: A dataset for semantic scene understanding of lidar sequences[END_REF], we cherrypick the best model after hyperparameter tuning on the validation set. The main evaluation of the chosen model is done using an online official benchmark (hidden test set). Evaluations on SemPOSS [START_REF] Pan | Semanticposs: A point cloud dataset with large quantity of dynamic instances[END_REF] and nuScenes [START_REF] Caesar | nuscenes: A multimodal dataset for autonomous driving[END_REF] use the exact same setting but without any hyperparameters tuning thus reporting only results of the last training model on their validation sets.

Annotation Strategy. To avoid the human labeling efforts of active learning [START_REF] Wu | Redal: Region-based and diversity-aware active learning for point cloud semantic segmentation[END_REF] or onepoint-per-object annotation [START_REF] Liu | One thing one click: A self-training approach for weakly supervised 3d semantic segmentation[END_REF], we apply random subsampling to existing dense ground truths (i.e. 100% annotation) to obtain sparse labels (e.g. 0.01%) as in [START_REF] Hu | Sqn: Weakly-supervised semantic segmentation of large-scale 3d point clouds with 1000x fewer labels[END_REF][START_REF] Xu | Weakly supervised semantic point cloud segmentation: Towards 10x fewer labels[END_REF][START_REF] Zhang | Weakly supervised semantic segmentation for large-scale point cloud[END_REF]. For a given setting, all methods share the same labels.

Implementation and Training. We train on 4 NVIDIA Tesla V100 for 100 epochs, using AdamW with 0.01 learning rate and batch size 16. We balance losses with λ foc = 1.0, λ lov = 1.0 and λ nce = 0.1 and use standard data augmentation as in [START_REF] Cortinhal | Salsanext: Fast, uncertaintyaware semantic segmentation of lidar point clouds[END_REF]. Because early prototypes are too noisy, we apply a 5 epochs warm-up without contrastive learning.

Performance

Quantitative Results. We report performance on SemKITTI 1 [START_REF] Behley | Semantickitti: A dataset for semantic scene understanding of lidar sequences[END_REF] hidden test set in Tab. 1, and on SemPOSS [START_REF] Pan | Semanticposs: A point cloud dataset with large quantity of dynamic instances[END_REF] and nuScenes-Lidarseg [START_REF] Caesar | nuscenes: A multimodal dataset for autonomous driving[END_REF] using their validation sets both in Tab. 2. On all datasets, we consistently outperform other weakly-supervised baselines being projectionbased networks like SalsaNext [START_REF] Cortinhal | Salsanext: Fast, uncertaintyaware semantic segmentation of lidar point clouds[END_REF] or point-based networks like SQN [START_REF] Hu | Sqn: Weakly-supervised semantic segmentation of large-scale 3d point clouds with 1000x fewer labels[END_REF]. Specifically, comparing Ours and SalsaNext -our backbone -the mIoU is +5.6/+3.6 mIoU on SemKITTI (Tab. 1) with only 0.1%/0.01% annotations and +4.1/+3.7 on SemPOSS (Tab. 2a). On nuScenes (Tab. 2b), we get +2.2 mIoU with 0.1% labels but -1.6% in the 0.01% labels case. We argue the drop relates to nuScenes (24x sparser than SemKITTI) having 10 of the 16 classes with less than 20 labels in the 0.01% setting. Subsequently, our clustering fails to associate labels with our 20 prototypes per class and the latter act as noise. Importantly, in Tab. 1 note that despite the projection-based nature of our backbone we significantly outperform SQN, a point-based method. Furthermore, we even beat some recent fully supervised baselines on each dataset despite the fact that we use 1000x or even 10000x fewer labels. This demonstrates our ability to learn robust semantic embeddings with significantly less labels. The ablation in Tab. 4, later discussed, even advocates that 1% of labels is sufficient to perform on par with full supervision.

Qualitative Results. Fig. 2 shows qualitative outputs on SemKITTI [START_REF] Behley | Semantickitti: A dataset for semantic scene understanding of lidar sequences[END_REF] validation set, along with ground truth and SalsaNext [START_REF] Cortinhal | Salsanext: Fast, uncertaintyaware semantic segmentation of lidar point clouds[END_REF] baseline given the absence of public implementation for SQN [START_REF] Hu | Sqn: Weakly-supervised semantic segmentation of large-scale 3d point clouds with 1000x fewer labels[END_REF]. In both 0.1% and 0.01% settings, our method surpasses SalsaNext, especially on thin objects. More qualitative results are in the Appendix C. 1 For fair comparison with our SalsaNext backbone on the hidden test set of SemKITTI we also use the kNN post-processing [START_REF] Milioto | Rangenet ++: Fast and accurate lidar semantic segmentation[END_REF] to mitigate the risk of overlapping points in projection-output having same 3D label.

Ablation Study

We first vary the backbone used and then ablate our method. Unless otherwise mentioned, we employ SalsaNet backbone with 0.1% annotation evaluated on SemKITTI val. set. Choice of Backbones. To demonstrate our approach is architecture-agnostic, Tab. 3 shows experiments on the val. sets of SemKITTI [START_REF] Behley | Semantickitti: A dataset for semantic scene understanding of lidar sequences[END_REF] and SemPOSS [START_REF] Pan | Semanticposs: A point cloud dataset with large quantity of dynamic instances[END_REF] with various backbones, namely: RangeNet-21 [START_REF] Milioto | Rangenet ++: Fast and accurate lidar semantic segmentation[END_REF], SqueezeSegV3-21 [START_REF] Xu | Squeezesegv3: Spatially-adaptive convolution for efficient point-cloud segmentation[END_REF], and SalsaNext [START_REF] Cortinhal | Salsanext: Fast, uncertaintyaware semantic segmentation of lidar point clouds[END_REF] (details in Appendix B.2). For all backbones and datasets, we boost results significantly w.r.t. to the original segmentation backbone, with mIoU difference of [+3.8, +6.3]. The results also advocate for our choice of SalsaNext backbone which performs best over all three. Architectural Components. Tab. 4a shows that all of our designs contribute to the best results. More in depth, 'w/o contrast module' shows that the contrastive module (Sec. 3.1) contributes to the biggest gain. To evaluate the benefit of our anchor sampling (Sec. 3.3), 'w/o anchor sampling' instead uses all pseudo-labels as anchors showing our strategy is indeed beneficial. In 'w/o prototype' we replace our 20 compact prototypes (Sec. 3.2) with 5,000 pixels as in [START_REF] Wang | Exploring cross-image pixel contrast for semantic segmentation[END_REF], showing that our method is lighter and more efficient. Finally, Focal loss (Eq. 3) and Lovasz loss (Eq. 4) are better combined as the two pursue slightly Table 3: COARSE3D with different backbones using 0.01% annotation (val. set).

different objectives since Focal loss mitigates imbalance while Lovasz maximizes IoU. Memory Bank. We now compare other types of memory banks of various per-class sizes. From Tab. 4b, we compare against two variations from [70]: 'Pixel' stores abundant random pixel-wise embeddings and 'Region' which instead stores frame-wise pooled features of semantically consistent regions. Compared to both, our method is more efficient and lighter. The combination of 'Pixel+Region' using 10,000 bank size, proves to be better but still gets outperformed with only 20 of our prototypes. Finally, we also compare against prototypes from mini-batch embeddings [START_REF] Zhuang | Local aggregation for unsupervised learning of visual embeddings[END_REF] -which logically perform worse since they fail at capturing the complete dataset knowledge. In a nutshell, Tab. 4 reveals that more stable contrastive targets -like regions or prototypes -are better and that our momentum update mechanism preserves the dataset context thus reaching better performance. Number of Prototypes. Tab. 4c studies the impact of varying the number of per class prototypes from 1 to 100. With only 1 prototype, each class uses a single high-dimensional embedding which is also referred to as class-wise memory bank [START_REF] Alonso | Semi-supervised semantic segmentation with pixel-level contrastive learning from a class-wise memory bank[END_REF]. Altogether, 20 prototypes are optimal among tested choices since fewer or more prototypes degrade performance.

Choice of Anchors. We study the choice of anchors in Tab. 4d, by varying the basic function used for sampling (col 'Basis') and the strategy for sampling segmentation features (col 'Strategy'). Without any basis function, we tried using all pseudo labels predictions 'All' or a 'Random X' number of X pixels. Results show that more support from pseudo labels boosts performance but the strategy is suboptimal given the prediction inaccuracies. To mitigate this, we evaluate the predictions quality with a basis function: either a 'Softmax' as [START_REF] Nayeem Rizve | In defense of pseudo-labeling: An uncertainty-aware pseudo-label selection framework for semi-supervised learning[END_REF] or our 'Entropy' proposal (Sec. 3.3). For both 'Softmax' and 'Entropy' basis, we consider sampling with a finetuned 'hard-threshold', the 'Top-X' elements, or selection from a random 'Probability' sampling. Our 'Entropy' driven probability sampling performs best.

We relate these results to the fact that Shannon entropy stores joint information distribution [START_REF] Robinson | Contrastive learning with hard negative samples[END_REF][START_REF] Wang | Exploring cross-image pixel contrast for semantic segmentation[END_REF] show the benefit of using smart key sampling strategies which differs to our use of all keys. In Tab. 4e we compare the common key sampling strategies being 'easy', 'hard', 'semi-hard', 'random' or 'All'. Except for the 'All' strategy, we consider 100 prototypes and use the key sampling mentioned to select 20 of these prototypes as keys. In short, 'easy'/'hard' indicates the complexity for anchors to learn with such keys. We refer to [START_REF] Wang | Exploring cross-image pixel contrast for semantic segmentation[END_REF] for details. Intuitively, using semi-hard or hard keys encourage the network to learn more robust representations. However, we denote that using all keys performs in fact better with our prototypes. We conjecture that this relates to the prototype capturing a more robust dataset context which is beneficial to preserve. Effect of Annotation. In Tab. 4f we vary the annotation ratio from 100% (full supervision) to only 0.001% (roughly 1 point label per frame), showing our robustness to the most extreme cases -despite a drastic mIoU drop for 0.001% annotation due to rare classes being absent from labels. In fact, reporting for the latter only mIoU for 'classes in labels', SalsaNext and Ours get respectively, 45.50% and 47.61% which again demonstrates robustness. We further study the effect of random label in Appendix A, showing in a nutshell that variances of 0.1%/0.01% settings are ±0.93/±0.32 -far smaller than the baseline gaps (+4.18/+3.13).

Conclusion

In this paper, we present a weakly supervised LiDAR point cloud semantic segmentation framework. Specifically, we develop a compact class-prototype contrastive learning scheme based on online clustered embeddings and use this prototype as the key to pulling entropydriven sampled anchors. Extensive experiments on three projection-based backbones and three real-world datasets demonstrate the effectiveness of our method.

We study the effect of annotation sampling in Appendix A and report implementation details with new ablation in Appendix B and more qualitative results in Appendix C.

A Effect of Annotations

In weak supervision settings, changing the set of labelled points impact performance. We now study more in depth the effect of sampled labels by randomly resampling labels 3 times on 2 datasets. As it appears in Tab. 5, our method is relatively stable (i.e., std<1). We also measure the gap between random annotations and those of human by asking 2 operators to annotate the entire SemPOSS, labeling roughly 0.01% points per frame. Again, from Tab. 5 our 'human' labels are within 3 std of the mean 0.01% performance (i.e., 29.27 vs 31.48±0.43).

SemKITTI [START_REF] Behley | Semantickitti: A dataset for semantic scene understanding of lidar sequences[END_REF] SemPOSS [START_REF] Pan | Semanticposs: A point cloud dataset with large quantity of dynamic instances[END_REF] Anno

B Implementation Details B.1 Label Voxel Propagation

We replicate SQN [START_REF] Hu | Sqn: Weakly-supervised semantic segmentation of large-scale 3d point clouds with 1000x fewer labels[END_REF] and apply their random grid downsampling with 0.06 voxel size.

Our trivial scheme simply propagates existing labels to all points within the same voxelthus densifying the labels at no extra labelling cost. In the extremely rare case of conflicting labels within a single voxel (e.g. a voxel having two labelled points with different classes), the voxel label will be randomly assigned. We evaluate the effect of this voxel propagation scheme using the SalsaNext backbone on SemKITTI val. set in the 0.1% annotation setting. With/without our scheme we get 57.57/56.26 mIoU. Since baselines do not use our label propagation, it is important to note that the mIoU gap obtained (+1.31 mIoU) is smaller than the gap with the original SalsaNext (+5.14, cf. main paper Tab. 3f) in the same 0.1% setting. This advocates that our method only partly benefits from our voxel propagation scheme and performs best thanks to our overall contrastive learning strategy.

B.2 Segmentation Backbones

SalsaNext [START_REF] Cortinhal | Salsanext: Fast, uncertaintyaware semantic segmentation of lidar point clouds[END_REF]. We use the official implementation2 for the SemKITTI dataset [START_REF] Behley | Semantickitti: A dataset for semantic scene understanding of lidar sequences[END_REF] and applied our best effort to fairly re-implement it for nuScenes [START_REF] Caesar | nuscenes: A multimodal dataset for autonomous driving[END_REF] and SemPOSS [START_REF] Pan | Semanticposs: A point cloud dataset with large quantity of dynamic instances[END_REF]. Specific to SemPOSS [START_REF] Pan | Semanticposs: A point cloud dataset with large quantity of dynamic instances[END_REF], we used an input padding to get a compatible size. When trained with our method, we finetune our contrastive learning hyperparameters.

SqueezeSegV3 [START_REF] Xu | Squeezesegv3: Spatially-adaptive convolution for efficient point-cloud segmentation[END_REF]. We use the lighter SqueezeSegV3-21 from the official implementation3 . To boost performance on weakly supervised tasks, we replaced the multi-layer cross-entropy loss -improper for sparse weak labels due to its downsampling -, with normal cross-entropy loss. When trained with our method, we simply use the contrastive learning hyperparameter found with SalsaNext. RangeNet++ [START_REF] Milioto | Rangenet ++: Fast and accurate lidar semantic segmentation[END_REF]. We use the ligher RangeNet-21 from the official implementation 4 . Inputs are pad to get compatible size. When trained with our method, we simply use the contrastive learning hyperparameter found with

C Additional Results

We report additional qualitative results using SalsaNext on SemKITTI, SemPOSS, and nuScenes in Figs. 3, 4 and 5, respectively, for both 0.1% and 0.01% settings. Overall, our method surpasses SalsaNext, especially in ambiguous and cluttered regions, illustrated in Fig. 3 (sidewalk/parking -row 1; vegetation/building -row 3), in Fig. 4 (car -row 1; rider -row 3; pole/plants -row 4), and in Fig. 5 (terrain/other flat -row 1). Also, SalsaNext makes more mistake regarding classes with close semantical meaning as in Fig. 3 (truck/car -row 1), in Fig. 4 (building/fence -row 5), and in Fig. 5 (bus/trailer/truck -row 2, 3, 4, 5). Furthermore, our method shows superiority in predicting small objects with similar structure or spatial position, demonstrated in Fig. 3 (fence/vegetation -row 4, 5; trunk/traffic sign -row 5), in Fig. 4 (rider/people -row 2, 3, 5; pole/plants -row 4), and in Fig. 5 (terrain/other flat -row 1). Additionally, our method infers better far away, low density regions e.g. Fig. 4 (car -row 1), and Fig. 5 (vegetation/barrier -row 2).

Figure 1 :

 1 Figure 1: Our COARSE3D uses a contrastive learning strategy (Sec. 3.1) to learn high dimensional semantic embeddings from the encoder features, later clustered into a lightweight prototype memory bank (Sec. 3.2). At each step, contrastive learning is applied on a scarce set of 'anchors', selected from an entropy-based sampling (Sec. 3.3), which features are pushed towards (pulled away from) positive (negative) prototypes acting as 'keys'.

Figure 2 :

 2 Figure 2: Sampled predictions on SemKITTI [3] validation set.Method SemPOSS [49] SemKITTI [3] mIoU (%) mIoU (%) Rangenet-21 [46] 25.1 ë 40.7 ë Ours (Rangenet-21) 28.9 +3.8 44.5 +3.8 SqueezeSegV3-21 [83] 30.4 ë 42.5 ë Ours (SqueezeSegV3-21) 36.7 +6.3 48.5 +6.0 SalsaNext [15] 38.9 ë 52.4 ë Ours (SalsaNext) 43.0 +4.1 57.6 +5.2

  SalsaNext (0.01%) (c) SalsaNext (0.1%) bicycle car motorcycle truck other vehicle person bicyclist motorcyclist road parking sidewalk ground building fence vegetation trunk terrain pole traffic sign

Figure 3 :

 3 Figure 3: Additional qualitative results on SemKITTI [3]

Figure 4 :

 4 Figure4: Qualitative results on SemPOSS[START_REF] Pan | Semanticposs: A point cloud dataset with large quantity of dynamic instances[END_REF]

  SalsaNext (0.1%) barrier bicycle bus car construction vehicle motorcycle pedestrian traffic cone trailer truck driveable surface other flat sidewalk terrain manmade vegetation

Figure 5 :

 5 Figure5: Qualitative results on nuScenes[START_REF] Caesar | nuscenes: A multimodal dataset for autonomous driving[END_REF]

Table 1 :

 1 On SemKITTI[START_REF] Behley | Semantickitti: A dataset for semantic scene understanding of lidar sequences[END_REF] hidden test set, our method outperforms all weakly-supervised baselines with either 0.1% or 0.01% labels and some fully supervised methods.

	Anno.(%)	Method	Projection-based	mIoU (%)	road (19.87%)	sidewalk (14.39%)	parking (1.47%)	other-grnd (0.39%)	building (13.26%)	car (4.08%)	truck (0.21%)	bicycle (0.02%)	m.cycle (0.04%)	other-veh. (0.16%)	vegetation (26.68%)	trunk (0.60%)	terrain (7.81%)	person (0.18%)	bicyclist (1.11e-6%)	m.cyclist (5.53e-9%)	fence (7.23%)	pole (0.28%)	traf.-sign (0.06%)
		TangentConv [65]	40.9 83.9 63.9 33.4 15.4 83.4 90.8 15.2 2.7 16.5 12.1 79.5 49.3 58.1 23.0 28.4 8.1 49.0 35.8 28.5
		RandLA-Net [29]	55.9 90.5 74.0 61.8 24.5 89.7 94.2 43.9 47.4 32.2 39.1 83.8 63.6 68.6 48.4 47.4 9.4 60.4 51.0 50.7
		SPVNAS [64]	67.0 90.2 75.4 67.6 21.8 91.6 97.2 56.6 50.6 50.4 58.0 86.1 73.4 71.0 67.4 71.0 50.3 66.9 64.3 67.3
	100	(AF) 2 S3Net [14]	69.7 91.3 72.5 68.8 53.5 87.9 94.5 39.2 65.4 86.8 41.1 70.2 68.5 53.7 80.7 74.3 74.3 63.2 61.5 71.0
		DarkNet53Seg [3]	49.9 91.8 74.6 64.8 27.9 84.1 86.4 25.5 24.5 32.7 22.6 78.3 50.1 64.0 36.2 33.6 4.7 55.0 38.9 52.2
		RangeNet53++ [46]	52.2 91.8 75.2 65.0 27.8 87.4 91.4 25.7 25.7 34.4 23.0 80.5 55.1 64.6 38.3 38.8 4.8 58.6 47.9 55.9
		SqueezeSegV3 [83]	55.9 91.7 74.8 63.4 26.4 89.0 92.5 29.6 38.7 36.5 33.0 82.0 58.7 65.4 45.6 46.2 20.1 59.4 49.6 58.9
		SalsaNext [15]	59.5 91.7 75.8 63.7 29.1 90.2 91.9 38.9 48.3 38.6 31.9 81.8 63.6 66.5 60.2 59.0 19.4 64.2 54.3 62.1
		SQN [30]	50.8 90.5 72.9 56.8 19.1 84.8 92.1 36.7 39.3 30.1 26.0 80.8 59.1 67.0 36.4 25.3 7.2 53.3 44.5 44.0
	0.1	SalsaNext [15]	50.1 87.2 66.0 51.6 18.4 86.2 88.2 31.6 25.3 29.9 31.8 77.0 59.0 60.1 44.6 44.2 15.6 54.9 39.6 41.4
		Ours	55.7 88.4 68.2 57.6 23.4 87.7 89.7 41.0 36.2 36.3 38.3 79.1 62.3 60.2 52.6 45.0 24.6 58.1 49.4 59.9
		SQN [30]	39.1 86.6 66.4 43.0 16.9 80.0 85.5 12.9 4.0 1.4 18.4 72.7 49.6 58.8 16.9 22.3 4.3 42.3 31.7 16.6
	0.01	SalsaNext [15]	42.6 86.0 65.4 43.7 14.5 85.1 83.1 19.5 21.9 14.9 17.6 73.8 45.9 59.7 29.4 23.6 4.2 50.7 32.6 38.1
		Ours	46.2 88.4 68.0 52.7 17.4 87.0 87.3 28.5 25.3 16.0 23.6 79.8 55.5 62.8 28.6 25.3 1.5 55.0 40.3 43.9
		Method			Anno.(%) mIoU%						Method		Anno.(%) mIoU(%)
		RandLA-Net [29]				53.5							RandLA-Net [29]			53.5
		KPConv [66]			100		55.2							PolarNet [90]		100		72.2
		JS3C-Net [86]				60.2							Cylinder3D [93]				76.1
		SqueezeSegV2 [75] SalsaNext [15]	100		29.8 45.0							RangeNet++ [46] SalsaNext [15]	100		65.5 72.2
		SalsaNext [15] Ours		0.1		38.9 43.0							SalsaNext [15] Ours		0.1		56.5 58.7
		SalsaNext [15] Ours		0.01		27.4 31.1							SalsaNext [15] Ours		0.01		44.5 42.9
		(a) SemPOSS											(b) nuScenes

Table 2 :

 2

Performance on SemPOSS

[START_REF] Pan | Semanticposs: A point cloud dataset with large quantity of dynamic instances[END_REF]

(a) and nuScenes

[START_REF] Caesar | nuscenes: A multimodal dataset for autonomous driving[END_REF]

(b) validation sets.

Table 4 :

 4 Ablation study results on SemKITTI[3] validation set. for all class predictions, which makes it more insightful for a proper anchor selection. Choice of Keys. Prior research

Table 5 :

 5 Effect of annotation sampling on SemKITTI and SemPOSS.

	.	0.10%	0.01%	0.10%	0.01%	human (≈ 0.01%)
	run 1	57.57	47.35	43.00	31.10	29.27
	run 2	56.54	47.28	42.88	31.95	-
	run 3	55.71	46.76	42.47	31.38	-
	all	56.61±0.93 47.13±0.32	42.78±0.28 31.48±0.43	-

https://github.com/TiagoCortinhal/SalsaNext

https://github.com/chenfengxu714/SqueezeSegV3

https://github.com/PRBonn/lidar-bonnetal

Acknowledgement. Rong Li was supported by the SMIL lab of South China University of Technolog, received support and advices from Prof. Mingkui Tan, Prof. Caixia Li and Zhuangwei Zhuang. Rong Li was also partly supported by Key-Area Research and Development Program Guangdong Province (2019B010155001). Inria members were partly funded by French project SIGHT (ANR-20-CE23-0016). This work was performed using HPC resources from GENCI-IDRIS (Grant 2021-AD011012808 and 2022-AD011012808R1).


Helene Fargier
email: fargier@irit.fr

Jerome Lang
email: lang@irit.fr

A constraint satisfaction framework for decision under uncertainty

The Constraint Satisfaction Problem (C SP ) framework offers a simple and sound basis for representing and solving simple decision problems, without uncertainty . This paper is devoted to an extension of the CSP frame work enabling us to deal with some decisions problems under uncertainty . This extension relies on a diff eren tiation between the agent-controllable decision vari ables and the uncontrollable parameters whose values depend on the occurrence of uncertain events . The un certainty on the values of the parameters is assumed to be given under the form of a probability distribution . Two algorithms are given , for computing respectively decisions solving the problem with a maximal proba bility , and conditional decisions mapping the largest possible amount of possible cases to actual decisions .

Introduction

Decision making is primarily a matter of choosing between alternatives that most commonly are expressed implicitly.

Thus solving a decision problem amounts to generate the option(s) that is(are) most appropriate with respect to the specification of the decision problem at hand. Different decision problems can be characterized along two discrim inating features:

-decisions are made at a single time point (although they may have a temporal structure i.e., form a plan) or are elaborated in sequence of steps, each being enriched by information resulting from the previous ones; the requirements (constraints, criteria) that implicitly define the alternatives are uncertainty-free or not. Re quirements are uncertain if they vary depending on the circumstances, the occurrence of which is incom pletely known (uncertain).

Sequential decisions and uncertain requirements increase the complexity of the decision problem, the most complex case being the joint situation. This paper is devoted to the case of single-instant decisions and uncertain requirements and proposes an approach of the problem in the framework of constraint satisfaction.

Roger Martin-Ciouaire, Thomas Schiex

INRA, BP27

31326 Castanet Cedex (France) {rmc,tschiex}@toulouse.inra.fr So far the only decision problem tackled within CSP (Con straint Satisfaction Problem) approaches concern the sim plest case: single-instant decision problem with no uncer tainty at all. In order to cast the addressed decision problem in a CSP framework it is essential to distinguish between two types of unknowns that are called parameters and deci sion variables respectively. Parameters are uncontrollable unknowns, i.e. , the value taken by a parameter is a matter of occurrence of an event that cannot be controlled (not even influenced) by the decision maker (also referred to as the agent). The value of a parameter is imposed by the exter nal world and the agent may have only partial knowledge about what this value might be. By contrast, the assignment of the decision variables is what the agent wants to decide upon. Failing to differentiate between parameters and de cision variables may yield nonsensical results in a classical CSP approach because a particular value of a parameter can restrict the range of allowed (satisfactory) values for the de cision variables whereas the converse is physically impossi ble. The key issue is therefore to develop a CSP framework and resolution algorithms that provide for the uncontrol lable/controllable dichotomy in the set of unknowns. This paper addresses an extension of the CSP framework, namely probabilistic CSP, involving both parameters and decision variables, the uncertainty on the values of the pa rameters being represented by a probability distribution. A formal representation framework is defined and two algo rithms relying on an assumption of independence of the parameters are described. In this paper we consider succes sively two assumptions concerning the agent's awareness of the paremeter values (the state of the world) at the time the decision must imperatively be made (deadline for acting):

-(NK) ("no more knowledge"): the agent will never learn anything new about the actual state of the world before the deadline; all it will ever know is already encoded by the probability distribution. For this case we propose an algorithm which gives an actual, un conditional decision, that is most likely to be suitable.

-(CK) ("complete knowledge"): the actual world will be completely revealed before the deadline is reached (possibly, just before), so that it it useful to the agent to compute "off-line" a ready-to-use conditional deci sion, that the agent will be able to instantiate "on-line", as soon as it knows what the actual world is. For this purpose we have developed an "anytime" resolution algorithm that provides a set of decisions with their conditions of applicability, together with the likeli hood of occurrence of these conditions.

The intermediate case where some partial knowledge about the state of the world may be learned is not considered in this paper. See [START_REF] Fargier | A constraint satisfaction framework for de cision under uncertainty[END_REF] for further discussion on this point.

In Section 2 we define probabilistic CSP s and several types of solutions (corresponding to decisions); then we propose algorithms dealing with the problem of computing optimal decisions under the assumptions (NK) (Section 3) and (CK) (Section 4).

2 Probabilistic constraint satisfaction problems

Preliminary definitions and notations

A classical constraint satisfaction problem is a triple P = (X, D, C), where X is a set of variables, each of which has its possible values in a domain (supposed here finite)

D;

(with D = x;D;), and Cis a set of constraints. Each constraint C; E C involves a set of variables noted V ( C;)

and is defined by a subset of the Cartesian product of the domains of the variables in V(C;). This subset, noted C; as the constraint itself, gives the set of all the possible assignments of the variables in V ( C; ): the constraint C; is satisfied by an assignment of the variables in V ( C;) iff this assignment belongs to the set of admissible tuples of C;.

A solution of the CSP is an assignment of values to all the variables such that all the constraints are satisfied. The set of all the solutions of a CSP Pis noted Sol(P). notation) is extended to a set of tuples: the projection R!z on Z of a subset R of the Cartesian product of the domains of the variables of Y is the set of the projections on Z of all the assignments in R.

Probabilistic CSPs: definitions

Roughly speaking, a probabilistic CSP is a CSP equipped with a partition between (controllable) decision variables and (uncontrollable) parameters, and a probability distribu tion over the possible values of the parameters.

Definition 1 A probabilistic CSP is a 6-uple P = (A, W, X, D, C, pr) where:

-A = { .X1, ... , Ap} is a set of parameters;

-w = wl X ... X Wp. where W; is the domain of >.. ;; -X = { x1, ... , Xn} is a set of decision variables; -D = D1 x • • • x Dn, where D; is the domain of x;; -C is a set of constraints, each of them involving at least one decision variable. -pr : W -[0, 1] is a probability distribution over the parameter assignments.

Constraints are defined in the same way as in classical CSP. We note X(C;) (resp. A(C;)) the set of variables (resp. parameters) involved in a constraint C;.

A complete assignment of the parameters (resp. of the decision variables) will be called a world (resp. a decision) and will be generally denoted by w (resp. by d). A partial world (resp. a partial decision) will be an assignment of a subset of the parameters (resp. of the decision variables).

The subset of C containing the constraints involving no parameters will be denoted by C* ; the other constraints in C

(involving at least a parameter) restrict the allowed values of some decision variables, dependently of the values of some parameters: they will be called parameterized constraints. Obviously, if A = 0, P is a classical CSP.

We assume that the constraints of C involve at least a de cision variable since the available information about the actual values of parameters is completely encoded by pr if a tuple of parameter assignments is impossible then the probability of any world extending this tuple is 0.

We have not yet discussed how the probability distribution on worlds is specified. Clearly, it is not reasonable to assume that the input contains the explicit specification of pr(w) for each w. Hence, generally pr will be given in a much more concise way. The simplest case occurs when parameters are mutually independent (pr is then specified only by an individual probability distributions p1•,x , for each parameter .X;). A more complex case consists in structuring the parameters in a Bayesian network: the computation of pr requires then the propagation of probabilities through the network. Thus, pr will generally be given implicitly rather than explicitly, and will generally require some computation in order to be available. From now on we choose to ignore this step: the computation of pr is taken for granted.

Definition 2 (possible worlds) A world w of W such that pr( w) > 0 is a possible world. The set of all possible worlds is denoted by Poss(P).

Let a be an assignment of a subset of the variables (where variables is here the general terminology for both parame ters and decision variables). We define the reduction of a constraint C by assignment a as the set of assignments of the unassigned variables compatible with a according to C: This notion of reduction is especially meaningful when a is either a world w or a decision d. The reduction of C by a world w is a set of classical decision constraints (involving decision variables only); it defines the decisions which are suitable if the world is w. Namely, to each world w we as sociate the uncertainty-freedecision problem (X, D, C[w]).

Definition 3 Let C be a constraint of C involving a set V (C) = A( C) U X (C )
Each of these classical CSPs will be called a candidate problem. One of them (and only one) is the actual problem (X, D, C[w*]), corresponding to the actual world w* (but since there is generally more than one possible world, the agent does not know which one is the actual one).

Definition 4 The set of candidate problems induced by P isdefined by Candidates

(P) = {(X,D,C[w]) lw E W)}.
Note that among the CSPs of Candidates(P), some may be inconsistent, which means that the actual problem may be inconsistent.

Dually, the reduction of C by a decision d yields a CSP (A, W, C[d]) involving parameters only, whose solutions are the worlds for which d is a suitable decision. These worlds are said to be covered by d. Note that, obviously,

w is a solution of (A, W, C[d]) iff d is a solution of (X, D, C[w]) iff(w, d) is a solution of (AU X, W x D, C).
Among the possible worlds, those which are covered by at least a decision are called good worldsand the others are called bad worlds.

Equivalently, w is good iff (X, D, C[w ]) is consistent.
Definition S Good(P) = {w E Poss(P) I 3d ED, (w, d) satisfies C)} Bad(P) = Poss(P) \ Good(P)

Now, for each possible decision d we can compute the probability that it is a suitable decision, i.e. that it covers the actual world.

Definition 6 (probability that a decision is a solution)

The probability that a given decision d is a solution of the actual problem is the probability of the set of worlds it covers, i.e. PS(d

) = Pr(Sol((A, W,C[d]))).
Notice that P S is not a probability distribution 1 .

Now, we can compute the probability that the actual world can be covered: this is the probability of consistency of the actual problem.

Definition 7 (probability of consistency) To a proba bilistic CSP P we associate the probability that the actual problem is consistent, i.e.

Pcon•(P) = Pr(Good(P))

If Pcons(P) = 1 then P will be said consistent.

1It is actually a contour function in the sense of Dempster Shafer theory. We omit details due to lack of space (see [START_REF] Fargier | A constraint satisfaction framework for de cision under uncertainty[END_REF]).

Example: (strongly modified from [START_REF] Rabelais | <Euvres completes, Collection "La plei ade[END_REF]). Cons ider a dinner to be organized , to which each of the three guests (Grandgousier , Gargantua and Pantagruel ) is not sure to come . The problem is to choose a wine and a meal according to four cons traints , among which three depends on the presence of each guest . The probabilistic CSP P corresponding to this problem is defined by:

-Decision variables :

X = {x1, x2 } ; D1 = {White , Red} ; D2 = {Turkey , Beef , Fish} -Parameters : A = {.XI , A2, A3}; W I = w2 = w3 =
{comes , -.comes} (these two values are abbreviated c and -.c in the rest of the paper ) .

-Cons traints : C = {C1,C2,C3,C4};

Cuisine rules Grandgousier (bee[)

Xl X2 w F R B w T R T .X1 X2 c T c F : T -.c -.c F -.c B Gargantua (white wine ) Pantagruel (vegetarian ) .X2 X! c R -.c R -.c w .X 3 X2 c F -.c T -.c F -.c B
The participation of the diff erent guests are mutually independent . The probability that Grandgousier comes is 0.6 and respectively 0. 9 and 0.5 for Gargantua and Pantagruel .

In this example , all worlds are possible ( Poss(P) = W). If There is a number of interesting particular cases of proba bilistic CSPs obtained by some simplifying assumptions. A first assumption, already evoked in Section 2.

Conditional decisions as solutions

A conditional decision will ideally associate to each possi ble world a decision satisfying the corresponding decision problem. Since some possible worlds may induce an in consistent CSP, a weaker request consists in giving a partial conditional decision, i.e., defined on a subset of W (ideally on Good(P)).

Definition 8 (conditional decisions) A complete condi tional decision s is a map from Poss(P) to D. A par tial conditional decision s is a map from a subset W ( s) of Poss(P) to D. A (partial or complete) conditional decision is soundiff V w E W ( s) , s ( w )coversw.

In the rest of the paper, we refer to "conditional decisions" as to partial or complete conditional decisions. Clearly, complete conditional decisions generalize decisions as de fined in Section 2.2 (the latter are called pure decisions as opposed to conditional decisions). Namely, a conditional decision which is constant over Poss(P) corresponds to a (pure) decision. Conditional decisions will play the role of solutions for probabilistic CSPs (ideally, a solution is a complete sound conditional decision). As for (pure) deci sions, a conditional decision has a probability to cover the actual world:

Definition 9 The probability that a conditional decision s will yield a solution to the actual problem is defined by:

PS(s) = L pr•(w)
wEIV(s) s(w) covers w

The following simple results are easy to prove: Proposition 1 (i) fo rany conditional decisions, PS(s) :S Pcons(P).

(ii) there exists as such that PS(s) = P cons(P). (iii) P is consistent iff there exists a s such that P S( s) = 1.

Definition 10 (optimal conditional decisions) A condi tional decision (partial or complete) s is optimal for P iff PS(s) is maximum (or equivalently iff PS(s) = P cons(P)).

Thus, one may compute an optimal conditional decision off line and use it later on, in real time, when the actual world will be known. This assumes that this actual world will be known before the decision has to be taken ((CK)). Clearly, under the other extreme assumption ((NK)), it is useless to look for a conditional decision: consequently, in this case one has to look for a pure decision rather than for a conditional one. A reasonable strategy is then to maximize the probability that this pure decision will work:

Definition 11 (optimal pure decisions) A pure decision d is optimal iff PS(d) is maximum. We let Pspv(P) = P S( d) where dis an optimal pure decision.

Pspv(P) is the maximum probability of success of a Pure Decision. Obviously, Pspv(P) :S P cons (P). The ideal case is when there is a pure decision covering all good worlds: Definition 12 (universal decisions) A pure decision dis a universal decision iff PS(d) = P cons (P) .

Thus, a universal decision will work for any possible world whose associated candidate problem is consistent and thus it is an optimal decision. Clearly, when there exists a universal decision, it is useless to look for a conditional decision.

Definition 13 (strong universal decisions) A pure deci sion dis a strong universal decision ofP iff P S( d) = 1. P is strongly consistent iff it has a strong universal decision.

A strong universal decision is a universal decision covering all possible worlds. The case where P is strongly consistent is the ideal one. Obviously, strong consistency implies consistency .

Example: using the same probabilistic CSP , we may consider the following conditional decisions, which is optimal since P S(s) = Pcons("P) = 0.55. . .

The dectswn ( R , T ) LS the only optimal pure decision( PS((R, T)) = 0.5) but is not univer sal . However , if the probability that Pantagruel ( .X3) comes were 0, ( R , T) would be a strong universal decision .

3 Searching for an optimal pure decision In both Sections 3 and 4 we assume mutual independence of parameters, for the sake of simplicity; however this as-sumption could be relaxed provided that the computation of the probability of a set of worlds is taken for granted.

Furthermore, in this Section (only) we make the assumption (NK) that the agent will never have any further knowledge about the actual world before acting (all it knows is already encoded in pr) and consequently, all it can execute is a pure decision. Now, the best the agent can require from the solver is an optimal pure decision. As it may be computa tionally costly to compute an optimal one, especially if the agent has a deadline, we propose an "anytime" algorithm which computes an approximately optimal pure decision if stopped before its natural stop (the longer the algorithm runs, the better the pure decision), and eventually gives an optimal one if it runs until its natural stop.

Our approach to the problem of maximizing P S( d) consists in using a Depth First Branch and Bound algorithm. For the sake of simplicity, consider that variables are instanti ated in a prescribed order, say ( x 1 , .. . , x") and that all the Each time a new variable decision d; is assigned to variable x;, all the constraints C E C connecting this variable x; to an unassigned decision variable xi or a parameter >.A, will be used as in the classical Forward-checking algorithm [START_REF] Haralick | Increasing tree search efficiency for constraint satisfaction problems[END_REF] to remove all the values incompatible with the assignment After forward-checking, the Cartesian product of the re maining values in the domains of all the parameters define the worlds which are compatible with the current partial de cision: all the worlds that are obviously incompatible have been removed. The cumulated probabilities of the remaining worlds give an upper bound Ps( d) on the probability of the best complete decision among the descendants of the current node since only incompatible worlds have been re moved. This bound is easily computed if independence is assumed: the bound is simply the product on all domains of the sums of the probabilities of the remaining values of each domain. When a complete decision dis reached, since all the constraint have been propagated, the worlds remaining are the worlds covered by the decision: Ps(d) = P S( d).

When does backtrack occur ? First, if the domain of a decision variable or a parameter becomes empty, then we know that no world is covered by our current partial deci sion and we may therefore backtrack, reconsider the value of the last decision variable assigned, restore the domains 3This implies that we are in case (F) since a constraint involves at least one decision variable. The algorithm is easily extended to handle larger arities as long as assumption (F) holds.

modif i ed due to the last assignment to their previous values and go on. Further cutoffs can be obtained using our upper bound and a very simple lower bound on the best proba bility. This lower bound is simply the probability P S( d) associated to the best decision found so far and is embod ied in the algorithm in a threshold a, initialized to 0 and updated each time a decision d such that P S( d) > a is reached. Whenever the two bounds meet, we know that the best probability of any complete decision that can be reached from this node is worse than the best probability found up to now and backtrack occurs, as previously.

The search will stop when no more node can be created. It is successful if a leaf has been reached, and the best decision among those which have been reached is optimal.

Function SEARCH(d1, ... , d;, p;) The functions SAVEDOMAINS and RESTOREDOMAINS save and restore the domains of the the variables (actually, only modif i ed domains have to be saved). One should note that on line 1 of the algorithm vi can be a decision variable or a parameter. On line 3, the current upper bound Pi could easily be incrementally updated by only taking into account the parameters whose domains have been modified: the previous probability p; is simply multiplied by the rela tive decrease of the probability associated to each modified domain. The algorithm is related to existing extensions of Forward checking which have been considered in the context of valued CSP [START_REF] Schiex | Val ued constraint satisfaction problems: hard and easy prob lems[END_REF] and partial CSP [START_REF] Freuder | Partial constraint satisfaction[END_REF].

4 Searching for a conditional decision

Clearly, searching for an optimal conditional decision is computationally costly (since in the worst case, its size equals the number of possible worlds); this leads us to look for an algorithm which gives a conditional decision which tends eventually to an optimal one if we let the algorithm run until it stops naturally (the longer we let it run, the higher the probability associated to the current conditional decision). Intuitively, the algorithm incrementally builds a conditional decision which eventually covers a superset of all good worlds. Repeatedly, (i) we pick a new pure decision d (to be added to the current partial conditional decision) that covers at least one possible world among the worlds which are not covered yet, (ii) we compute the set R of worlds that this decision covers and (iii) we subtract this set from the set of worlds which haven't yet been covered (initially, this set has the value W, i.e. it contains all worlds). In order to easily compute the worlds covered by d and their probabilities, we make the following two assumptions: first, parameters are mutually independent (again), and second, any constraint of C involves at most one parameter (F). Due to assumption {F), the worlds covered by a decision d (i.e., C[d)) form a Cartesian product of subsets of the parameter domains. The successive subtractions of these Cartesian products is performed using a technique recently proposed by Freuder and Hubbe [START_REF] Freuder | Extracting constraint sat isfaction subproblems[END_REF], called subdomain subproblem extraction. Before we describe our algorithm, we first recall this technique of subdomain extraction.

Subdomain extraction

We define an environment E as a set of worlds of the form /1 x • • • x lp. with 'Vk, lk � Wk. An example of envi ronment is (A1 E {c},A2 E {c,-,c},A3 E {..,c}), also c written { c} x {c, -,c} x { -,c} or [ c , � c ) when there is no ambiguity on the order of parameters. The set of all possi ble environments is obviously a lattice (equipped with the inclusion order), whose top is the set of all possible parameter assignments (in the example, [ �: ::: � ] ) and whose c, -.c bottom is the empty set. The probability of an environment

E = /1 x • • • x lp, under the independence assumption, is
Pr(E) = n�=1 LvEik pr(v) .

Given two environments E and R, sub-domain subprob lem extraction technique [START_REF] Freuder | Extracting constraint sat isfaction subproblems[END_REF], decomposes E into a set of disjoint sub-environments Dec(E, R) such that all worlds of E belong either to R or to one of the sub-environments of the decomposition. The decomposition is unique if an ordering on the variables is fixed. We give here a modi fication of Freuder and Robbe's decomposition algorithm, where we also compute incrementally the probability of each environment generated by the decomposition. This function returns the decomposition of E by F and the prob ability of the set of worlds of E that are already in F (used in Algorithm 3).

When actually used, the probability p E of the environment E needed on entry has already been computed since if the procedure DEC is called, either E = W and P E = 1, orE comes from a previous decomposition.

Note that when E n F = 0 we get DEc( E, F) { ( E, pE) }, and when E � F we get DEC( E, F)= 0.

Example: E = W = [ �: ::: � ) , F = [ c,�c ) . c,-,c c c,-,c -.c 2. i = 2; Rest = [ c,-.c ) ; PRest = 0; c,-,c

3. i = 3; Rest = [ c�c ) ; PRest = 0.2, E' = p( E' ) = 0.2; L ist = { ([ �: � � ), 0.6), ( [ c � c ), 0.2) } . EN D [ c�c ] • -.c '

An algorithm for searching a conditional decision

The algorithm is sketched as Algorithm 3. Two steps of the algorithm deserve some comments: first (line 1), the se quences ofCSP (AUX, W x D, CUE), repeatedly solved by the algorithm, define dynamic constraint satisfaction prob lems [START_REF] Dechter | Belief Maintenance inDy namic Constraint Networks[END_REF] and their resolution may be improved by any tech niques developed to solve such problems. Second (line 2), once a new W C is built, it is subtracted from all the await ing environments to avoid some redundant computations. This furthermore guarantees that the computation will stop when the current list Dec is ions defi nes a solution.

Example (continued ) :

1. Env = {(W, 1)}; p900d = 0; Pbad = 0; Decisions= 0 Thus, the set of worlds covered by Decisions grows monotonically (and so does Bad), and the interval [p 9 ood , 1 -Pbad ] shrinks monotonically from its initial value [ 0 , 1] to its final singleton value [Pr(Good(C)), Pr(Good(C))]. Therefore, it is possible to use the algorithm as an "anytime" algorithm: Dec is ions tends to a cover of Good(P) and Bad tends to Bad(P).

So far we have assumed that the applicability of a con ditional decision is taken for granted (since, according to assumption (CK), the actual world will be revealed before the deadline for acting). We could consider more com plex situations where further knowledge about the world can be learned by means of knowledge-gathering actions; another problem consists then in finding a relevant set of knowledge-gathering actions, sufficient to make the agent able to act properly. This is left for further research (see [START_REF] Fargier | A constraint satisfaction framework for de cision under uncertainty[END_REF] for further considerations on this point).

Related work

In the field of constraint satisfaction and automated reason ing: Partial and valued CSP [START_REF] Freuder | Partial constraint satisfaction[END_REF][START_REF] Schiex | Val ued constraint satisfaction problems: hard and easy prob lems[END_REF] define general frame works that extends the traditional CSP framework in a sim ilar direction, but without any distinction between decision variables and parameters. Another related area of research is dynamic constraint satisfaction [START_REF] Dechter | Belief Maintenance inDy namic Constraint Networks[END_REF], where several tech niques are proposed in order to solve a sequence of CSP that differs only in some constraints more efficiently than by naively solving each CSP one after the other. Such improve ments could immediately be incorporated in the algorithm proposed . The computation of a compact representation of (partial) solutions could probably be performed using Fi nite Automata or Ordered Binary Decision Diagrams [START_REF] Bryant | Symbolic Boolean Manipulation with Or dered Binary-Decision Diagrams[END_REF].

OBDD are used to solve problems issued from propositional logic, closely related to CSP. In fact, an OBDD could rep resent -using exponential memory and time in the worst case -all the partial solutions of a probabilistic CSP by shifting to propositional logic.

In the field of decision analysis: Deciding under uncertainty has been studied for long in decision theory and has been applied recently to planning. There is a number of computa tional approaches to decision analysis, which all distinguish in a way or another parameters (subject to probability distri butions) and decision variables, the most common of them include influence diagrams [START_REF] Howard | Infl uence Diagrams, In fl uence Diagrams[END_REF], Markov decision processes and also valuation-based systems [START_REF] Prakash | Valuation-based systems for Bayesian decision analysis[END_REF]. On the one hand, these computational frameworks tackle much more general decision problems since they consider sequences of deci sions (and also utility values), while ours tackles only one step decisions. On the other hand, our framework describes the constraints between dependent variables by means of an elaborate representation language equipped with elaborate computational tools (namely constraint satisfaction prob lems) while influence diagrams and other approaches do not focus on this representation issue and represent these relationships more explicitly. Both kind of approaches are however somewhat complementary, and one could think of extending our framework so as to integrate for instance influence diagrams (for the nice representation of the de pendency structure of the decision problem) and constraint satisfaction (for the representation of the constraints be-tween dependent variables). An interesting particular problem related to our framework is in Qi and Poole [START_REF] Qi | High level path planning with uncertainty[END_REF] who discuss a navigation problem in U-graphs, i.e., graphs where some of the edges are un certain (the probability associated to an uncertain edge is the probability that the connection between two vertices is traversable); the static version of this problem may be encoded by a probabilistic CSP where a parameter is asso ciated to each uncertain edge4•

In the field of knowledge representation: Recently, Boutilier [START_REF] Boutilier | Toward a logic for qualitative decision the ory[END_REF] has proposed a logical, qualitative basis for decision the ory, distinguishing as we did between controllable and un controllable propositions; however, while we look for con ditional decisions, Boutilier's very cautious strategy looks only for a pure decision (the best one maximizing the worst possible outcome). [START_REF] Poole | An abductive framework for decision-theoretic planning[END_REF] also discusses controllability issues in an abduction-based framework for planning.

Concluding remarks

Our contribution was mainly in extending the CSP frame work in order to deal with decision problems under uncer tainty, by distinguishing between controllable variables and uncontrollable parameters and by representing the knowl edge of the world by a probability distribution on the pa rameters. This can be considered as a f i rst step to embed decision theory into constraint satisfaction; two other important steps in this direction will consists in con sidering utilities and sequences of decisions. Utility func tions would enable us to represent flexibility and it should not be significantly harder to embed them in our frame work: in the constraints of C, an extra field is added to each tuple, namely the utility of the corresponding variable assignment. Forbidden tuples have a utility of -oo. Non flexible constraints allow only two utility degrees for the tuples, namely 0 and -oo. Extending our framework to sequences of decisions is significantly harder. The partition of the variables is not sufficient: not only decisions are in fluenced by parameters, but the value of some parameters may also be influenced by some earlier decisions; for this we think of reusing ideas from influence diagrams [START_REF] Howard | Infl uence Diagrams, In fl uence Diagrams[END_REF] or causal networks (e.g [START_REF] Darwiche | Symbolic Causal Net works[END_REF]) by structuring decision variables and parameters in a directed acyclic network (not to be con fused with the undirected constraint graph of the CSP), a link from A; to xi meaning that the allowed values of the decision variable xi depend on ..\;, and a link from x; to ..\ i meaning that the decision of assigning a value to xi has or may have some effects on ..\ i.

An interesting potential application of probabilistic CSP (and its possible extensions) is planning under uncertainty.

A preliminary version of probabilistic CSP has been ap plied to an agricultural planning problem [START_REF] Martin-Clouaire | Crop management plan ning as a fuzzy and uncertain constraint satisfaction problem[END_REF]. Clearly, this problematic needs the notion of controllability, and would certainly gain a lot in being encoded in an extension of the 4However the dynamic version of the problem, where the ac tual presence of an edge can be learned by the agent only when it is at one on its extremities cannot be easily modeled in our framework yet.

CSP framework -since it could benefit from the numer ous advances on the resolution of CSPs. The similarity between our conditional decisions and conditional plans is clear, at least for a single action. For handling sequences of actions, probabilistic constraint satisfaction has to be extended as evoked in the previous paragraph. Actions with probabilistic effects may be encoded by using extra parameters and probability distributions. Lastly, a lot of recent approaches to planning make use of decision the ory; clearly, extending probabilistic CSP with utility values and sequences of decisions goes in this direction; our long term goal is thus to provide a constraint satisfaction based framework to decision-theoretic planning.

  of variables and parameters. The reduction ofC by anassignment aof V' � V(C) is the con straint Reduce(C, a) on V(C)-V' defined by the tuples {bE DJY(C)-V' I (b, a)!V(C) E C}. We note C[a] = {Reduce(C, a), C E C} the reduction of C by a.

  we cons ider world w1 = ( c, -.c, c) whose probability is 0.03, the reduction of the cons traints are : Reduce( C1, w!) = C1, Reduce(C2,w!) = {T, F}, Reduce(C3,w!) = {R, W} and Reduce(C3,wl) = {F} . TheCSP (X,D,C[w1]) that corre sponds to w1 has a single solution (W, F ) and thus w1 is a good world . The decision (W, F ) covers 3 more worlds (( -.c, -.c, c), ( c, -.c, -.c) and ( -.c, -.c, -.c)) which finally give a probability PS((W, F)) = 0.1 (since the worlds covered by (W, f ) are exactly those where Gargantua does not come ) .In the world w2 = ( c, c, c), whose probability is 0.27, the reduction of the cons traints are : Reduce( cl' W2) = cl' Reduce(C 2 ,w2) = { T, F} , Reduce(C3,w2) = {R} and Reduce(C3, w2 ) = {F} which defines an inconsistentCSP . Thus , w2 is a bad world . The only other bad worldisw3 = (-.c, c, c) with probability 0.18. Therefore , Bad(P) = {(c,c,c),(-.c,c,c)}, Pr(Bad(P) = 0.27 + 0.18 = 0.45 and Pcons(P) = 0.55.

  constraint are binary3. The root of the tree is the empty instantiation. Intermediate nodes denote partial decisions ( d 1 , . .. , d;). Leaves represent instantiations of X,i. e. , pure decisions d = ( d 1 , ... , dn)• In a depth f i rst exploration of the tree, we keep track of the leaves d maximizing P S( d).

  x; = d;from the domains of xi (resp. >.k): each domain Di (resp. Wk) is simply replaced by (Dj n Reduce(C, (d;)) (resp (Wk n Reduce(C, (d;) ) if C involves a parameter). Updating the domain of a variable v using constraint C after the assignment of decision d; to x; is performed by the procedure FORWARDCHECK(v, C, d;) in Algorithm 1, line 2.

1 2

 1 if i = n then a := p; {Update upper bound} else Choose a variable x;+1 for d;+l E Di+l do SAVEDOMAINS(A U X) forC E C s.t. Xi+l E V(C) and V(C) C£ {x1, ... , x;+d do L Let {vj} = V(C)-{x;+d FORWARDCHECK(vj, C, d i + l ) 3 Pi+l := flw . LvEW• [pr.x.(v)] if ( P i +l >a) and ('t:/i, D; =f:. 0) then L SEARCH(dl' . .. 'di+l' Pi+l) RESTOREDOMAINS(A U X) Algorithm 1: A Forward-checking-based Depth First Branch and Bound The algorithm is sketched as Algorithm 1. The function SEARCH should initially be called with an empty partial decision and a probability p0 equal to 1, the initial triv ial upper bound on the probability of an optimal decision.

1. i = 1 ; 1 repeat

 11 Rest = [ c, ':,c ) ; PRest = 0.6, E' = [ c�c ) ; C1oC C,•CFunction DEC( ( E, p E), F)List := 0; E' := E ; PE• = PE; i := Rest:= E' Rest!{A;} : = E !{A;}-F !{A;} • -p (Rest I{ >j}) PReot • -PE'• p (E ' ) II>;} {independence} if (Rest ! {A; } # 0) then l Add ( . Rest, PRest ) to List E !{A,} : = E !{A;} n F !{A;} PE' := PE' -PRest i := i + 1 until ((i > p) or (E !{A; } = 0)) return (List, PE' )Algorithm 2: The decomposition algorithm PE' = 0.4; List= { ( [ c, ':, c ) , 0.6) } ;

2 .

 2 (E,pE) = (W, 1); d1 = (R, B); WC = [ c 2c ); Env = { ( [ � • � � ), 0.6), ( [ c ? c ), 0.2) }; ' -.c Decisions = ( {[ c :.., -;, c ), ( R, B))); Pgood = 0.2.

3 .

 3 (E,pE)={[ � : � � ),0.6);d2=(R,T);WC= [ � � � � ); Env = { ( [ c, ; c ), 0.3), ( [ c ? c ), 0.2) }; Decisions = (( [ � � �� ), (R, T)), ( [ c 2c), (R, B))); Pgood = 0.5. c [ �-. c l 4. (E,pE)=([ c . ; c ),o.3;d3=(W,F);WC= c :-:; c J; Env = { {[g), 0.27), {[ g c ), 0.18) }; (( [ :�:), (W, F)) is added to Decisions; Pgood = 0.55; c [ c 5. (E,pE) = ( [g), 0.27); inconsistent ; Bad = { g)};

  corresponding respectively to the relevance and the irrelevance of c; to the actual problem. This simplifying assumption is denoted by ( U). If { c1, ... , c q } denotes the set of these uncertain constraints, then it can be shown that Candi dates ( P) is a relaxation lattice in the sense ofFreuder[START_REF] Freuder | Partial constraint satisfaction[END_REF], equipped with the probability distribution obviously induced by the distri bution on worlds: namely, the set of candidates problems are obtained by taking the union of C* and of any subset of { c;, i = 1 . .. q }. Moreover when the c; 's are independently relevant, P is strongly consistent (see Definition 13) iff the top of the lattice, namely { c;, i = 1 ... q} u C* is consistent in the classical sense. A more general class of probabilistic

	CSPs occurs when each parameterized constraint involves
	exactly one parameter. Each parameterized constraint cor
	responds thus to an disjunctive family of classical decision
	constraints (one for each possible value of the involved pa
	rameter). We denote by (F) this simplifying assumption.
	1, is the mu
	tual independence of parameters: in this case pr is specified
	only by individual probability distributions2•
	Another particular case is illustrated by our previous exam

ple: we have a problem where the relevance of some con straints is uncertain, and every uncertain constraint c; is en coded by a parameterized constraint C; linking the decision 2 Hence, the problem can be stated in such a way that Poss(P) = W, simply by removing impossible values from the domain.

variables of c; to one parameter A;, whose domain has two values (in our example, comes and -.comes),

( ( [ :�:), ( W, F)}, ( ( � �� � ), (R, T )}, ( ( c2c), (R, B))) is the final value of Decisions; from it we may built a conditional decision ; moreover Bad is in Bad. Pgood tends to Pcons(P) and reaches a eventually .

Correctness of the algorithm

Proposition 2 At any point of the algorithm, the fo llowing properties hold:

• VE EBadwe have E � Bad(P);

• V(E and d) E Decisions, Vw E E, d covers w;

• Pgood � Pr( Good(P)) � 1 -Pbad Proposition 3 (Correctness of the algorithm) If run qui etly, the algorithm stops and :

• the final value of Decisions defines an optimal con ditional decision;

• the final values of Pgood and Pbad verify Pgood + Pbad = 1. Pgood = Pr(Good(C)) and Pbad = P1•(Bad(P)).