Thierry Denoeux
email: thierry.denoeux@utc.fr

Distributed combination of belief functions

Keywords: Dempster-Shafer theory, evidence theory, consensus, information fusion, uncertain reasoning

We consider the problem of combining belief functions in a situation where pieces of evidence are held by agents at the node of a communication network, and each agent can only exchange information with its neighbors. Using the concept of weight of evidence, we propose distributed implementations of Dempster's rule and the cautious rule based, respectively, on average and maximum consensus algorithms. We also describe distributed procedures whereby the agents can agree on a frame of discernment and a list of supported hypotheses, thus reducing the amount of data to be exchanged in the network. Finally, we show the feasibility of a robust combination procedure based on a distributed implementation of the random sample consensus (RANSAC) algorithm.

Introduction

Since its development by Shafer [START_REF] Shafer | A mathematical theory of evidence[END_REF] following Dempster's seminal work on statistical inference [START_REF] Dempster | Upper and lower probabilities induced by a multivalued mapping[END_REF], Dempster-Shafer (DS) theory has been widely used as a formal framework for uncertain reasoning [START_REF] Denoeux | 40 years of Dempster-Shafer theory[END_REF][START_REF] Denoeux | Representations of uncertainty in artificial intelligence: Beyond probability and possibility[END_REF]. In the past thirty years, it has been used extensively in a large number of applications including information fusion [START_REF] Dan | A robust D-S fusion algorithm for multi-target multi-sensor with higher reliability[END_REF][START_REF] Pichon | Quality of information sources in information fusion[END_REF][START_REF] Xiao | Multi-sensor data fusion based on the belief divergence measure of evidences and the belief entropy[END_REF], classification [START_REF] Denoeux | Classification using belief functions: the relationship between the case-based and model-based approaches[END_REF][START_REF] Denoeux | A new evidential k-nearest neighbor rule based on contextual discounting with partially supervised learning[END_REF],

clustering [START_REF] Denoeux | Calibrated model-based evidential clustering using bootstrapping[END_REF], scene perception [START_REF] Xu | Multimodal information fusion for urban scene understanding[END_REF], etc. DS theory is essentially a theory of evidence: it consists in representing elementary pieces of evidence pertaining to a question of interest using belief functions, i.e., completely monotone set functions [START_REF] Shafer | A mathematical theory of evidence[END_REF][START_REF] Denoeux | Representations of uncertainty in artificial intelligence: Beyond probability and possibility[END_REF], and pooling them using some appropriate combination rule. Dempster's rule, also referred to as the product-intersection rule, occupies a central position in DS theory; it allows us to combine pieces of evidence that are both reliable and independent [START_REF] Shafer | A mathematical theory of evidence[END_REF]. However, in real-world applications, it is not always possible to break down the available evidence into independent pieces, and the complete reliability that is called for in the basic theory is often an idealization. For that reason, alternative combination rules have been developed over the years to handle highly conflicting [START_REF] Dubois | Representation and combination of uncertainty with belief functions and possibility measures[END_REF][START_REF] Lefèvre | Belief function combination and conflict management[END_REF][START_REF] Smets | Analyzing the combination of conflicting belief functions[END_REF][START_REF] Bronevich | The contradiction between belief functions: Its description, measurement, and correction based on generalized credal sets[END_REF] or dependent pieces of evidence [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by non distinct bodies of evidence[END_REF][START_REF] Destercke | Idempotent conjunctive combination of belief functions: Extending the minimum rule of possibility theory[END_REF][START_REF] Cattaneo | Belief functions combination without the assumption of independence of the information sources[END_REF][START_REF] Bronevich | The choice of generalized Dempster-Shafer rules for aggregating belief functions[END_REF].

Most implementations of Dempster's rule assume a centralized fusion scheme in which a single agent receives pieces of evidence from several sources and combines them. There are, however, a growing number of applications in which several agents independently collect evidence and exchange information via a static or dynamic communication network. In this case, no single agent holds the totality of the evidence, and agents typically can only access the information held by their neighbors in the communication graph. As typical applications, we can mention target classification in sensor networks [START_REF] Hall | Distributed Data Fusion for Network-Centric Operations[END_REF] and information fusion in multirobot systems [START_REF] Montijano | Distributed Consensus with Visual Perception in Multi-Robot Systems[END_REF]. For instance, El Zoghby et al. [START_REF] Zoghby | Evidential distributed dynamic map for cooperative perception in VANets[END_REF] describe a collaborative perception application in which a fleet of intelligent vehicles is equipped with sensors and communicates through an ad hoc network (see also, e.g. [START_REF] Kim | Multivehicle cooperative driving using cooperative perception: Design and experimental validation[END_REF]). The overall objective of this application is to enhance each vehicle's perception and situation awareness of a complex dynamic traffic scene through the multiplicity of sensors and the communication capabilities of the agents.

Typically, each agent perceives a number of objects and collects sensor information about them. Object association and classification then have to be performed using distributed algorithms, which allow the agents to exchange information locally with their neighbors in the network and to construct, collectively, a shared representation of the environment.

Distributed algorithms for object association are described in [START_REF] Montijano | Distributed Consensus with Visual Perception in Multi-Robot Systems[END_REF]. Here, we assume that the agents have already agreed on some questions of interest (such as the class of matched objects) and we focus on the distributed combination of evidence assumed to be represented by belief functions.

A first approach to this problem has been proposed in [START_REF] Kanjanatarakul | Distributed data fusion in the Dempster-Shafer framework[END_REF], in which the authors proposed a distributed implementation of Dempster's rule based on the combination of commonality functions, an alternative representation of belief functions. However, a problem with this approach is that the quantity of information to be exchanged in the network grows exponentially with the number of hypotheses. Furthermore, this approach does not easily extend to other combination rules. In this paper, we propose an alternative approach based on the combination of weights of evidence. As opposed to commonalities, weights of evidence are usually specified for a small number of hypotheses, which considerably reduces the amount of communications as well as the complexity of computations at each node. Furthermore, the same approach can be used to develop a distributed implementation of the cautious rule, an alternative to Dempster's rule making it possible to combine dependent items of evidence.

Finally, we propose a distributed RANSAC algorithm allowing the robust combination of belief functions to account, for instance, for wrong associations or faulty sensors.

The rest of this paper is organized as follows. The necessary background on DS theory is first recalled in Section 2. The distributed implementations of the product-intersection and cautious rules are then described in Section 3. Finally, the robust combination procedure is presented in Section 4, and Section 5 concludes the paper. 2

Background on belief functions

In this section, background knowledge on DS theory is summarized to make the paper self-contained. Basic notions are first recalled in Section 2.1. Weights of evidence and the cautious rule of combination are then introduced, respectively, in Sections 2.2 and 2.3.

Basic notions

We consider a question of interest having one and only one answer in a finite set Ω called the frame of discernment. A mass function on Ω is a mapping m ∶ 2 Ω → [0, 1] such that A⊆Ω m(A) = 1.

If m(∅) > 0, mass function m is said to be subnormal, otherwise it is said to be normalized.

A subnormal mass function such that m(∅) < 1 can be transformed to a normalized one m * defined by m * (∅) = 0 and

m * (A) = m(A) 1 -m(∅) (1)
for all nonempty subset A ⊆ Ω. This operation is called normalization. for all A ⊆ Ω. The quantity Bel(A) is interpreted as the total degree of support given to the proposition that the truth lies in A, taking into account the support given to A and to all of its subsets. Obviously, Bel(∅) = 0 and Bel(Ω) = 1. A related notion is that of plausibility function, defined as

P l(A) = B∩A≠∅ m * (B) = 1 -Bel(A),
where A denotes the complement of A. The quantity P l(B) reflects the lack of support given to the proposition that the truth does not lie in A.

Two mass functions m 1 and m 2 on Ω representing independent items of evidence can be combined by the conjunctive sum operation ⩀ [START_REF] Smets | The combination of evidence in the Transferable Belief Model[END_REF] defined as

(m 1 ⩀ m 2 )(A) = B∩C=A m 1 (B)m 2 (C) (2)
for all subset A of Ω. Obviously, m 1 ⩀ m 2 may be subnormal, even if m 1 and m 2 are normalized. The quantity

κ(m 1 , m 2 ) = (m 1 ⩀ m 2 )(∅)
is called the degree of conflict between m 1 and m 2 . Normalizing m 1 ⩀ m 2 yields a normalized mass function m 1 ⊕ m 2 , called the orthogonal sum of m 1 and m 2 and defined as

m 1 ⊕ m 2 = (m 1 ⩀ m 2 ) * . (3)
The combination rule ⊕ defined by (

m 1 ⊕ . . . ⊕ m n = (m 1 ⩀ . . . ⩀ m n ) * . (4)
Dempster's rule can also be computed using the commonality function. The commonality function Q ∶ 2 Ω → [0, 1] associated to a mass function m is defined by

Q(A) = B⊇A m(B), (5)
for all A ⊆ Ω. Conversely, m can be recovered from Q using the following formula,

m(A) = B⊇A (-1) B -A Q(B) (6)
for all A ⊆ Ω. If Q 1 and Q 2 are the commonality functions associated with two mass functions m 1 and m 2 , then the commonality function

Q 1 ⩀ Q 2 associated with m 1 ⩀ m 2 is the product of Q 1 and Q 2 : Q 1 ⩀ Q 2 = Q 1 ⋅ Q 2 . (7)
Dempster's rule can, thus, be implemented by computing the commonality functions using [START_REF] Cattaneo | Belief functions combination without the assumption of independence of the information sources[END_REF], multiplying them point-wise, converting the result back to a mass function using (6), and renormalizing using (1). However, the complexity of this procedure is O(2 K ), where K is the cardinality of the frame of discernment. In contrast, masses are often assigned to a small number of focal sets, which makes the computation of Dempster's rule using ( 2)-( 3) much more efficient.

Weights of evidence and separability

In practical applications, an elementary piece of evidence about a question of interest often comes as a nonempty set A ⊆ Ω of possible answers, and a degree of support s ∈ [0, 1)

for that set. Mathematically, such a piece of information can be formalized as a simple mass function m of the form

m(A) = s, m(Ω) = 1 -s. (8)
Given two simple mass functions m 1 and m 2 with the same focal set A and degrees of support s 1 and s 2 , their orthogonal sum is

(m 1 ⊕ m 2 )(A) = 1 -(1 -s 1 )(1 -s 2 ) (9a) (m 1 ⊕ m 2 )(Ω) = (1 -s 1 )(1 -s 2 ). (9b)
Denoting the simple mass function (8) by A w , where w = -ln(1-s) is the weight of evidence1

for A as defined by Shafer [35, page 77], Eq. ( 9) becomes

A w 1 ⊕ A w 2 = A w 1 +w 2 ,
i.e., weights of evidence add up when combining simple mass functions with the same focus.

The vacuous mass function can be written as A 0 for any A ⊆ Ω.

A normal mass function m is said to be separable [START_REF] Shafer | A mathematical theory of evidence[END_REF] if it is the orthogonal sum of simple mass functions; it can be written as

m = ⊕ ∅≠A⊂Ω A w(A) , (10)
where w(A) is the weight of evidence for subset A. As a consequence of Theorem 5.2 in [START_REF] Shafer | A mathematical theory of evidence[END_REF],

this decomposition is unique and the weights w(A) are all finite as long as m(Ω) > 0 (m is then said to be nondogmatic). Most mass functions used in practice are separable. This is the case, in particular, for consonant mass functions [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by non distinct bodies of evidence[END_REF].

If m is nondogmatic, the weights in [START_REF] Denoeux | 40 years of Dempster-Shafer theory[END_REF] can be computed from the commonality function by the following equation [START_REF] Smets | The canonical decomposition of a weighted belief[END_REF]:

w(A) = B⊇A (-1) B -A ln Q(B), (11)
for all A ∈ 2 Ω ∖ {∅, Ω}. This equation provides a test to determine if a normalized mass function m is separable: the property holds iff the weights w(A) computed from [START_REF] Denoeux | Representations of uncertainty in artificial intelligence: Beyond probability and possibility[END_REF] are all positive or equal to zero. For an arbitrary nondogmatic mass function, we can still define a corresponding weight assignment as the mapping from 2 Ω ∖ {∅, Ω} to R expressed by [START_REF] Denoeux | Representations of uncertainty in artificial intelligence: Beyond probability and possibility[END_REF].

Let w 1 and w 2 be the weight assignments associated to two mass functions m 1 and m 2 , and let w 1⊕2 be the weight assignment corresponding to m 1 ⊕ m 2 . As a consequence of [START_REF] Dan | A robust D-S fusion algorithm for multi-target multi-sensor with higher reliability[END_REF] and [START_REF] Denoeux | Representations of uncertainty in artificial intelligence: Beyond probability and possibility[END_REF], we have

w 1⊕2 = w 1 + w 2 , (12)
i.e., in the weight representation, Dempster's rule is just addition. Given the weight assignment w, the corresponding mass function can be recovered from [START_REF] Denoeux | 40 years of Dempster-Shafer theory[END_REF], but A w(A) is only a valid simple mass function if w(A) ≥ 0. If w(A) < 0, the notation A w(A) can still be used to designate a "generalized simple mass function" [START_REF] Smets | The canonical decomposition of a weighted belief[END_REF], defined as a mapping that assigns to recover m from w using [START_REF] Denoeux | 40 years of Dempster-Shafer theory[END_REF] for any arbitrary nondogmatic mass function m.

Example 1. Let Ω = {a, b, c} be a frame of discernment with three elements. Table 1 shows two mass functions m 1 and m 2 with their corresponding commonality functions and weight assignments, as well as the result of the combination of m 1 and m 2 by Dempster's rule. We can see that m 1 is separable (the corresponding weights are all positive), whereas m 2 is not (as w 2 ({c}) < 0). A negative weight of evidence can be interpreted as the "retraction" of some evidence [START_REF] Smets | The canonical decomposition of a weighted belief[END_REF][START_REF] Dubois | Prejudice in uncertain information merging: Pushing the fusion paradigm of evidence theory further[END_REF]. The weight assignment w 1⊕2 of m 1⊕2 = m 1 ⊕ m 2 is the sum of the weight assignments w 1 and w 2 . We remark that m 1⊕2 is not separable.

Even though the mass functions of Example 1 are defined over a very small frame, we can already observe that the Q-representation is less parsimonious than the w-representation.

This is due to the fact that the Q-representation is global : if some positive mass m(A) > 0 is assigned to some focal set A, all subsets of A will have a strictly positive commonality. In contrast, the weight-of-evidence representation is local : the combination with a simple mass function focused on a subset A only changes the weight of A. As a consequence, weights of evidence are usually assigned to only a few subsets of the frame of discernment supported by the evidence (called supported sets in the rest of this paper), and the number of nonzero weights typically remains small when combining several mass functions by Dempster's rule.

Cautious rule of combination

In DS reasoning, it is often useful to compare the "information content" of two mass functions. This allows us, in particular, to find the least-committed mass function compatible with a set of constraints induced by the available evidence, a principle known as the Least-Commitment Principle (LCP) [START_REF] Smets | Belief functions: the disjunctive rule of combination and the generalized Bayesian theorem[END_REF]. Several informational orderings generalizing set inclusion have been proposed. For instance, the q-ordering [START_REF] Dubois | A set-theoretic view of belief functions: logical operations and approximations by fuzzy sets[END_REF] is defined by

m 1 ⊑ q m 2 iff ∀A ⊆ Ω, Q 1 (A) ≤ Q 2 (A).
In particular, if there exists a mass function m such that m 1 = m 2 ⊕m and m is not conflicting with m 2 , i.e., κ(m 2 , m) = 0, then m 1 is q-more committed than m 2 ; in this case we have obviously

Q 1 = Q 2 ⋅ Q ≤ Q 2 .
Being the orthogonal sum of m 2 and another mass function m, m 1 then clearly contains more information than m 2 .

Another informational ordering, introduced in [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by non distinct bodies of evidence[END_REF], is based on the comparison between weight assignments: for any two nondogmatic mass functions m 1 and m 2 ,

m 1 ⊑ w m 2 iff ∀A ⊆ Ω, w 1 (A) ≥ w 2 (A),
i.e., m 1 is w-more committed than m 2 if and only if it assigns larger weights of evidence to all hypotheses. An alternative interpretation is as follows: m 1 is w-more committed than m 2 iff there exists a separable mass function m such that m 1 = m 2 ⊕ m.

Let us now assume that we have two mass functions m 1 and m 2 from two sources that are not independent, and we wish to combine them conjunctively. The combined mass function m 12 should be more committed than both m 1 and m 2 . Let S(m 1 ) and S(m 2 )

denote the sets of mass functions that are more committed than, respectively, m 1 and m 2 .

We thus require that m 12 ∈ S(m 1 ) ∩ S(m 2 ). According to the LCP, the least committed mass function in the set S(m 1 ) ∩ S(m 2 ), according to some ordering ⊑ x , should be selected, if it exists. The existence of a least-committed element is not always guaranteed. If m 1 and m 2 are consonant and x = q, then the solution is the consonant mass function m 12 such that P l 12 ({ω}) = P l 1 ({ω}) ∧ P l 2 ({ω}) for all ω ∈ Ω, where ∧ denotes the minimum operator.

However, the consonance condition is quite strict. For the w-ordering, the least-committed mass function in S(m 1 ) ∩ S(m 2 ) exists and is unique for any nondogmatic mass function [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by non distinct bodies of evidence[END_REF]; it is given by

m 1 m 2 = ⊕ ∅≠A⊂Ω A w 1 (A)∨w 2 (A) ,
where ∨ denotes the maximum operator. The operation is called the (normalized) cautious rule of combination [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by non distinct bodies of evidence[END_REF]. Denoting by w 1 2 the weight function corresponding to m 1 m 2 , we thus have

w 1 2 = w 1 ∨ w 2 , (13)
which is to be compared to [START_REF] Denoeux | Optimal object association in the Dempster-Shafer framework[END_REF]. The cautious rule is commutative, associative and idempotent, i.e., m m = m for any nondogmatic mass function m. Also, the orthogonal sum is distributive with respect to : for any nondogmatic mass functions m 1 , m 2 and m 3 , we have

(m 1 ⊕ m 2 ) (m 1 ⊕ m 3 ) = m 1 ⊕ (m 2 m 3 ). (14)
Eq. ( 14) lays bare an important property of the cautious rule: when combining two overlapping pieces of evidence (m 1 ⊕ m 2 and m 1 ⊕ m 3 ), the common part (m 1 ) is not counted twice. This property makes this rule suitable for combining nonindependent pieces of evidence. The cautious rule has shown good performance in many practical applications including classifier combination [START_REF] Quost | Classifier fusion in the Dempster-Shafer framework using optimized t-norm based combination rules[END_REF], visual tracking [START_REF] Klein | Hierarchical and conditional combination of belief functions induced by visual tracking[END_REF], face detection [START_REF] Faux | Theory of evidence for face detection and tracking[END_REF], expert opinion combination [START_REF] Ha-Duong | Hierarchical fusion of expert opinions in the Transferable Belief Model[END_REF][START_REF] Cherfi | Partially supervised independent factor analysis using soft labels elicited from multiple experts: Application to railway track circuit diagnosis[END_REF] and cooperative perception in vehicular networks [START_REF] Zoghby | Evidential distributed dynamic map for cooperative perception in VANets[END_REF].

Example 2. Let us consider again the two mass functions m 1 and m 2 of Example 1. Table 2 shows these mass functions and their weight assignments, together with the result of their combination by the cautious rule. We observe that m 1 2 = m 1 m 2 is separable. More generally, the combination of an arbitrary mass function with a separable mass function by the cautious rule is always separable.

It must be noted that the decision to use Dempster's rule or the cautious rule must be based on the consideration of the evidence on which agents have based the construction of their mass functions, Dempster's rule requiring the bodies of evidence to be entirely distinct [START_REF] Shafer | Constructive probability[END_REF]. Typically, the independence assumption can be considered to hold if agents use distinct sensor data, and it does not hold if they share common information or knowledge. In case of doubt, it may be preferable to use the more conservative cautious rule, which is less likely to yield overconfident conclusions.

Distributed orthogonal-sum and cautious combination

In this section, we show how Dempster's rule and the cautious rule can be implemented in a distributed way. We assume that n agents are located at the nodes of a communication graph G(t) = (V, E(t)), where V = {1, . . . , n} is the set of vertices, E(t) ⊆ V 2 is the set of edges and t is a discrete time index (Figure 1). Each agent i holds a mass function m i and can communicate only with its neighbors in the graph. The communication graph is usually determined by physical constraints such as spatial distance and transmitter power in the case of wireless communication. When agent i can receive information from agent j, it is often the case that agent j can also receive information from agent i, i.e., the communication graph is undirected. While this assumption is not necessary for the subsequent analysis, it is often reasonable and we will adopt it hereafter to simplify the exposition. We wish to design distributed procedures whereby each agent can combine its mass function with those of other agents by any of the combination rules reviewed in Section 2. As a result, a consensus will be reached, each agent having the same mass function

m * = m 1 * . . . * m n , with * = ⊕ or * = .
The key observation is that, as shown in Sections 2.2 and 2.3, combination by Dempster's rule and the cautious rule can be achieved by computing, respectively, the sum and the maximum of the weights of evidence. Consequently, these rules can be implemented in a distributive way using average and maximum consensus algorithms [START_REF] Garin | A survey on distributed estimation and control applications using linear consensus algorithms[END_REF][START_REF] Montijano | Distributed Consensus with Visual Perception in Multi-Robot Systems[END_REF].

We note that, in this paper, we consider only the static consensus problem in which each agent i first constructs a fixed mass function m i based, e.g., on sensor information in a first step, and then combines it with the mass functions of other agents in the network in a second step. A more difficult problem would be to consider situations in which agents continue to update their beliefs by collecting evidence from the outside world while simultaneously exchanging information with other agents in the network. The combination of dynamically changing reference signals in a decentralized fashion is referred to as the dynamic consensus problem [START_REF] Kia | Tutorial on dynamic average consensus: The problem, its applications, and the algorithms[END_REF]. This problem is more complex than the static one; in particular, the convergence of dynamic consensus algorithms can only be guaranteed under some assumptions on the dynamics of the individual reference signals. In practice, static consensus algorithms are applicable and are commonly used when the reference signals (here, individual mass functions) are either fixed, or are updated at a low frequency relative to the convergence time of a static consensus algorithm. This is the case, for instance, in mobile robotics application such as described in [START_REF] Montijano | Distributed Consensus with Visual Perception in Multi-Robot Systems[END_REF] or [START_REF] Zoghby | Evidential distributed dynamic map for cooperative perception in VANets[END_REF].

In the following, static consensus algorithms will first be reviewed in Section 3.1. The application to belief function combination will then be exposed in Section 3.2.

Consensus algorithms

Let us assume that each agent i in the network initially holds a quantity or "state"

x i (0), and agents update their states at discrete times t = 1, 2, . . ., computing x i (t + 1) from

x i (t) using only the information from their neighbors in the communication graph G(t).

The consensus problem is to design an update equation such that the states of all agents converge to the same value ξ, i.e., for all i ∈ {1, . . . , n},

lim t→∞ x i (t) = ξ.
The average and maximum consensus problems correspond, respectively, to the cases where

ξ = 1 n ∑ n i=1
x i (0), and ξ = max 1≤i≤n x i (0). In the following, we focus on the average consensus problem first, and we address the simpler maximum consensus problem at the end of this section. Most of the material in this section is drawn from [START_REF] Garin | A survey on distributed estimation and control applications using linear consensus algorithms[END_REF] and [START_REF] Montijano | Distributed Consensus with Visual Perception in Multi-Robot Systems[END_REF].

Preliminary definitions. Let C = (c ij ) ∈ R n×n be an n × n square matrix. It is said to be stochastic if c ij ≥ 0 for all (i, j), and ∑ n j=1 c ij = 1 for all i, i.e., each row sums to unity. If, additionally, ∑ n i=1 c ij = 1 for all j, i.e., each column also sums to unity, then C is said to be doubly stochastic. Obviously, all symmetric stochastic matrices are doubly stochastic.

The graph G C of stochastic matrix C ∈ R n×n is defined as (V, E C ) with V = {1, . . . , n} and

E C = {(i, j) ∈ V 2 ∶ c ij (t) > 0}. Matrix C is compatible with graph G = (V, E) if its graph G C = (V, E C ) is a subgraph of G, i.e., E C ⊆ E. A graph G = (V, E) is undirected if (i, j) ∈ E implies (j, i) ∈ E.
An undirected graph is connected if there is a path from any node to any other node in the graph. The set of neighbors of vertex i ∈ V in undirected graph G = (V, E) is defined as N (i) = {j ∈ V ∖ {i} ∶ (i, j) ∈ E}. The union of two graphs G 1 = (V, E 1 ) and

G 2 = (V, E 2 )
with the same set of vertices is defined as

G 1 ∪ G 2 = (V, E 1 ∪ E 2 ).
Linear consensus algorithm. We consider the following linear update equation

x(t + 1) = C(t)x(t), (15)
where x(t) = (x 1 (t), . . . , x n (t)) T is the column vector of states at time t and C(t) ∈ R n×n is a stochastic matrix compatible with the communication graph. Eq. ( 15) can be written as:

x i (t + 1) = n j=1 c ij (t)x j (t) = x i (t) + j∈N (i) c ij (t)(x j (t) -x i (t))
for i = 1, . . . , n. Each agent i thus updates its state based on the states on its neighbors in the communication graph.

Several theoretical results guarantee the convergence to the average of the initial quantities x i (0). Let us first consider the case where the communication graph (assumed to be undirected) remains fixed during the execution of the algorithm and C(t) = C is a constant matrix. Then, the following result holds [23, Theorem 3.1].

Proposition 1. If C is symmetric, stochastic and such that c ii > 0 for all i, and if G C is connected, then

lim t→∞ C t = 1 n 1,
where 1 = (1, . . . , 1) T ∈ R n , t is a positive integer and

C t = C . . . C t times
.

Consequently, the linear update equation (15) solves the average consensus problem.

As shown by Xiao and Boyd [START_REF] Xiao | Fast linear iterations for distributed averaging[END_REF], the convergence rate of the linear consensus algorithm [START_REF] Denoeux | Calibrated model-based evidential clustering using bootstrapping[END_REF] with constant weight matrix C(t) = C, defined as

r(C) = sup x(0)≠x lim t→∞ x(t) -x 2 x(t) -x 2 1 t
, where x is the n-vector whose components are the average

(1 n) ∑ n i=1 x i (0), is equal to the spectral radius of matrix C -(1 n)11 T .
A method to design matrix C so as to maximize r(C) is described in [START_REF] Xiao | Fast linear iterations for distributed averaging[END_REF].

If the communication connectivity varies over time, then convergence to the average can still be guaranteed provided the union of the communication graphs G(t) over a time window of given length is connected. This is expressed by the following proposition [23, Theorem When the weight matrix varies, the analysis of the convergence rate has to be based on worst-case analysis [START_REF] Garin | A survey on distributed estimation and control applications using linear consensus algorithms[END_REF]. Bounds on the rate of convergence subject to constraints on the topological properties of the communication graphs and on the numerical values for the entries of C(t) are given in [START_REF] Angeli | Tight estimates for non-stationary consensus with fixed underlying spanning tree[END_REF]. Other theoretical results pertain to the case where matrices {C(t)} are generated randomly. The reader is referred to [START_REF] Garin | A survey on distributed estimation and control applications using linear consensus algorithms[END_REF] for a review of these results.

Design of matrices C(t).

To implement a consensus strategy, we need to design either a single matrix C in the case of a fixed communication network, or a sequence of matrices C(t)

if the connectivity changes. Optimal design methods, maximizing some global performance criterion, often require a centralized mechanism taking into account the topology of the whole network [START_REF] Xiao | Fast linear iterations for distributed averaging[END_REF]. Here, we focus on local design methods, in which each agent can design its consensus update weights using only information provided by its neighbors.

A common choice for the weight matrix C when the network topology is fixed and agents update their state in a synchronized way is the matrix of Metropolis-Hastings weights [START_REF] Xiao | A scheme for robust distributed sensor fusion based on average consensus[END_REF], where d(i) = N (i) is the number of neighbors of node i (called the degree of node i).

c ij = ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ 1 max(d(i),d(j))+1 if (i, j) ∈ E and i ≠ j 1 -∑ n j=1,i≠j c ij if i = j, (16
Clearly, this matrix is symmetric, stochastic and its diagonal elements are strictly positive.

⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ . ( 17
)
Figure 2 shows the convergence of states to the average using the update rule [START_REF] Denoeux | Calibrated model-based evidential clustering using bootstrapping[END_REF] with this weight matrix, starting from the initial condition x(0) = (1, 2, -1, 0, -2).

In some real applications such as, e.g., those involving mobile robots exchanging information through an ad hoc network, the assumptions of fixed communication graph and synchronous communication cannot be made. As an example of a consensus strategy allowing for time-varying graphs and asynchronous communication, we can mention the symmetric gossip scheme [START_REF] Boyd | Randomized gossip algorithms[END_REF][START_REF] Garin | A survey on distributed estimation and control applications using linear consensus algorithms[END_REF], in which at each time step a node i transmits its information to one of its neighbors j, which in turn transmits back its information to i. After this information exchange, both nodes update their state using a consensus scheme. More formally, given a communication graph G = (V, E), assume that at each time t a link (i, j) ∈ E with i ≠ j is selected, and matrix C(t) is defined as

C(t) = C ij = I n - 1 2 (e j -e i )(e j -e i ) T , (18)
where I n is the identity matrix of dimension n, and e i is the n-vector (i.e., column vector of dimension n) containing only zeros except for the i-th entry, which is set to one. Matrices C ij verify the conditions stated in Proposition 2. If there exists an integer T such that all links are selected at least once in every time window of length T , the joint graphs

G(t) = ⋃ i<j C ij
are connected, and the sequence of matrices C(t) solves the average consensus problem.

Example 4. The graph of Figure 1 has four links, with the following corresponding matrices:

C 12 = ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝
0.5 0.5 0 0 0 0.5 0.5 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1

⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ , C 23 = ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝
1 0 0 0 0 0 0.5 0.5 0 0 0 0.5 0.5 0 0 0 0 0 1 0 0 0 0 0 1

⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ , C 34 = ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝
1 0 0 0 0 0 1 0 0 0 0 0 0.5 0.5 0 0 0 0.5 0.5 0 0 0 0 0 1

⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ , C 35 = ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝
1 0 0 0 0 0 1 0 0 0 0 0 0.5 0 0.5 0 0 0 1 0 0 0 0.5 0 0.5

⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠
.

Figure 3 shows the convergence of states to the average using the update rule [START_REF] Denoeux | Calibrated model-based evidential clustering using bootstrapping[END_REF], starting from the same initial condition as in Example 3, and defining C(t) as one of the above four matrices picked in a random order.

Maximum consensus. Solving the maximum consensus problem means ensuring that the states x i (t) of all of the n agents converge to the maximum of the initial states x 1 (0), . . . , x n (0).

This can be achieved by the following nonlinear update rule:

x i (t + 1) = max j∈{i}∪N (i) x j (t), (19)
i.e., at each time step, each agent updates its state by the maximum of its previous state and the states of its neighbors [START_REF] Tahbaz-Salehi | A one-parameter family of distributed consensus algorithms with boundary: From shortest paths to mean hitting times[END_REF][START_REF] Montijano | Distributed Consensus with Visual Perception in Multi-Robot Systems[END_REF]. This algorithm solves the maximum consensus problem in a finite number of iterations under any of the following two conditions, which mirror the conditions of Propositions 1 and 2:

1. The communication graph G is fixed and connected.

2. There exists a positive integer T such that the graphs

G(t) = G(t) ∪ G(t + 1) ∪ . . . ∪ G(t +
T -1) for t = 0, 1, . . . are all connected.

Example 5. Coming back to the network of Figure 1, assume that the initial condition is the initial condition x(0) = (1, 2, -1, 0, -2). Assuming the five agents update their states in a synchronized way, we have x(1) = (2, 2, 2, 0, -1) and x(2) = (2, 2, 2, 2, 2), i.e., the procedure converges in only two iterations.

Application to belief function combination

Let us now assume that agents have collected evidence about some question, and they wish to combine this evidence by exchanging information through the network without any centralized mechanism. To reach this goal, the agents must first agree on the frame of discernment and on a common representation of the available evidence, which can then be combined using the cautious rule or Dempster's rule. These different steps are described below.

Frame of discernment. The first problem to solve is the definition of the frame of discernment Ω. In some applications, this frame is fixed: for instance, in an intrusion detection problem, the frame has only two elements corresponding to the presence or absence of an intruder. In other applications, the frame may potentially be very large, and it may be computationally advantageous to restrict it to as few hypotheses as possible, by discarding hypotheses that are deemed impossible by all agents. For instance, assume that a fleet of mobile robots is searching for a lost object, and the search space is divided into a finite, but large number of cells. If all agents agree that some cells are impossible, then the frame of discernment should include only those cells that are considered possible by at least one agent. Let Θ = {θ 1 , . . . , θ N } be an ordered set containing all hypotheses possible a priori, shared by all agents. Initially, each agent i defines a set Ω i (0) ⊆ Θ containing the hypotheses it considers possible, given its own evidence. Then the update rule can be

Ω i (t + 1) = ⋃ j∈{i}∪N (i) Ω j (t) (20)
for j = 1, . . . , n. This "disjunctive" procedure will converge to Ω = ⋃ n i=1 Ω i in a finite number of iterations. We note that a less conservative approach would be to replace union by intersection in [START_REF] Zoghby | Evidential distributed dynamic map for cooperative perception in VANets[END_REF], which would amount to discarding any hypothesis considered impossible (or maybe only forgotten or neglected) by even a single agent. This "conjunctive" procedure will then converge to ⋂ n i=1 Ω i . While this approach may be preferred in some applications in which the agents' opinions are not expected to be conflicting, it is less robust than the previous one, and the disjunctive approach is arguably safer in many applications.

Evidence representation. After agents have agreed on an ordered frame of discernment Ω = {ω 1 , . . . , ω K }, they can represent their evidence by nondogmatic mass functions m i on Ω corresponding to weight assignments w i ∶ 2 Ω ∖ {∅, Ω} → R. A simple approach would be to represent each weight assignment by a vector of length 2 K -2 but, as mentioned in Section 2.2, most of the weights w(A) will usually be null, except for a small number of supported sets. For large K, agents can limit the amount of communication by first sharing their collections of supported sets, which can be done as follows. Each subset A ⊆ Ω can be represented by a binary vector a = (a 1 , . . . , a K ) ∈ {0, 1} K such that a j = 1 if ω j ∈ A and a j = 0 otherwise. This vector can alternatively be coded as an integer α = ∑

K j=1 a j 2 j-1 . Let F i (0)
denote the set of integers representing the supported sets of agent i, i.e., the subsets A ⊆ Ω such that w i (A) > 0. The consensus algorithm based on the following update rule

F i (t + 1) = ⋃ j∈{i}∪N (i) F j (t) (21)
converges to F = {α 1 , . . . , α r } = ⋃ n i=1 F i (0). Each weight assignment w i can then be coded as an r-vector w i⋅ (0) = (w i1 (0), . . . , w ir (0)) T , where w ij (0) is the weight intially assigned by agent i to subset A j represented by integer α j . After a finite number t of iterations, the consensus algorithm defined by (20) converges to Ω i (t) = Ω = {θ 10 , θ 11 , θ 12 , θ 13 , θ 14 , θ 15 , θ 16 } for i = 1, . . . , 5. Let us rename the elements of Ω as Ω = {ω 1 , . . . , ω 7 }. This is now the common frame of discernment for the five agents. Assume that the agents assess the evidence known to them and represent it by the following separable mass functions:

m 1 = {ω 4 } 0.5 ⊕ {ω 2 , ω 4 } 0.8 , m 2 = {ω 3 } 1 ⊕ {ω 3 , ω 4 } 1.2 m 3 = {ω 3 , ω 4 } 0.3 ⊕ {ω 3 , ω 4 , ω 5 } 0.9 , m 4 = {ω 4 , ω 6 , ω 7 } 0.2 m 5 = {ω 2 , ω 4 } 0.7 ⊕ {ω 2 , ω 4 , ω 6 , ω 7 } 1.1 .
For m 1 , the supported sets are {ω 4 } and {ω 2 , ω 4 }. Their binary representations are, respectively, a 1 = (0, 0, 0, 1, 0, 0, 0) and a 2 = (0, 1, 0, 1, 0, 0, 0), and their corresponding integer The weight assignments can, thus, be represented as vectors of length r = F = 7 as follows:

α j 4 8 10 12 28 104 106 w 1⋅ (0) 0 0.5 0.8 0 0 0 0 w 2⋅ (0) 1 0 0 1.2 0 0 0 w 3⋅ (0) 0 0 0 0.3 0.9 0 0 w 4⋅ (0) 0 0 0 0 0 0.2 0 w 5⋅ (0) 0 0 0.7 0 0 0 1.1

Cautious combination. As explained in Section 2.3, the cautious rule consists in computing the maximum of weights of evidence. This can be done in a distributed way by applying the update rule [START_REF] Dubois | Representation and combination of uncertainty with belief functions and possibility measures[END_REF] to each components of vectors w i in parallel. More precisely, at each time t + 1, each agent i updates its weights w ij (t) as

w ij (t + 1) = max j∈{i}∪N (i)
w ij (t), j = 1, . . . , r.

Each iteration of this maximum consensus algorithm thus requires rd i maximum operations at each node i, where d i = N (i) is the degree of note i. Under the conditions specified in Section 3.1, this algorithm converges in finite number t of iterations to

w 1j (t) = w 2j (t) = . . . = w nj (t) = w ∨j = max i w ij (0), j = 1, . . . , r.

Each agent can then compute the mass function

m = m 1 . . . m n as m = r ⊕ j=1 A w ∨j j , (22)
where A j denotes the subset corresponding to α j . The number of operations needed to compute the orthogonal sum of r mass functions, each having two focal sets in a frame of size K, is bounded upwards by K2 r+1 , but it is often much less, as the number of focal sets of the final combined mass function is often much less than 2 r [START_REF] Wilson | Algorithms for Dempster-Shafer theory[END_REF].

Example 7. Continuing Example 6, let us assume that the five agents update the weight vectors x i (t) synchronously. The sequence of states is as follows:

α j 4 8 10 12 28 104 106 w 1⋅ (1) 1 0.5 0.8 1.2 0.0 0.0 0.00 w 2⋅ (1) 1 0.5 0.8 1.2 0.9 0.0 0.0 w 3⋅ (1) 1 0.0 0.7 1.2 0.9 0.2 1.1 w 4⋅ (1) 0 0.0 0.0 0.3 0.9 0.2 0.0 w 5⋅ (1) 0 0.0 0.7 0.3 0.9 0.0 1.1 α j 4 8 10 12 28 104 106 w 1⋅ (2) 1 0.5 0.8 1.2 0.9 0.0 0.0 w 2⋅ (2) 1 0.5 0.8 1.2 0.9 0.2 1.1 w 3⋅ (2) 1 0.5 0.8 1.2 0.9 0.2 1.1 w 4⋅ (2) 1 0.0 0.7 1.2 0.9 0.2 1.1 w 5⋅ (2) 1 0.0 0.7 1.2 0.9 0.2 1.1 α j 4 8 10 12 28 104 106 w 1⋅ (3) 1 0.5 0.8 1.2 0.9 0.2 1.1 w 2⋅ (3) 1 0.5 0.8 1.2 0.9 0.2 1.1 w 3⋅ (3) 1 0.5 0.8 1.2 0.9 0.2 1.1 w 4⋅ (3) 1 0.5 0.8 1.2 0.9 0.2 1.1 w 5⋅ (3) 1 0.5 0.8 1.2 0.9 0.2 1.1

The network thus converges in only three iterations to the weight assignment vector w ∨ = (1, 0.5, 0.8, 1.2, 0.9, 0.2, 1.1), which corresponds to the following mass function:

m = {ω 3 } 1 ⊕ {ω 4 } 0.5 ⊕ {ω 2 , ω 4 } 0.8 ⊕ {ω 3 , ω 4 } 1.2 ⊕ {ω 3 , ω 4 , ω 5 } 0.9 ⊕ {ω 4 , ω 6 , ω 7 } 0.2 ⊕ {ω 2 , ω 4 , ω 6 , ω 7 } 1.1 , equal to m ({ω 3 }) = 0.1132, m ({ω 4 }) = 0.7697, m ({ω 2 , ω 4 }) = 0.0297 m ({ω 3 , ω 4 }) = 0.0460, m ({ω 3 , ω 4 , ω 5 }) = 0.0118, m ({ω 4 , ω 6 , ω 7 }) = 0.0054 m ({ω 2 , ω 4 , ω 6 , ω 7 }) = 0.0162, m (Ω) = 0.0081.
Combination by Dempster's rule. As shown in Section 2.2, Dempster's rule can be implemented by summing the weight assignment vectors. In order to use the linear average consensus algorithm based on update rule [START_REF] Denoeux | Calibrated model-based evidential clustering using bootstrapping[END_REF] for that purpose, agents need to know the total number n of nodes (vertices) in the network. This number can be set in advance in the case of a fixed communication network, but it needs to be estimated in the case of a dynamic time-varying network. Distributed methods for counting the number of nodes in a network are described in [START_REF] Garin | A survey on distributed estimation and control applications using linear consensus algorithms[END_REF] and [32, pages 61-62]. We only give the former simpler method here.

Assume that the initial conditions are x 1 (0) = 1 and x i = 0 for i = 2, . . . , n (i.e., the initial states are 1 for one agent and 0 for the others). If the state variables x i (t) are updated using the average consensus algorithm, we have lim

t→∞ x i (t) = 1 N n i=1 x i (0) = 1 n .
Denoting ni (t) = 1 x i (t), we thus have lim t→∞ ni (t) = n.

Once the number of nodes has been estimated, the algorithm defined by update equation ( 15) can be used to compute the average weights of evidence assigned to each supported set in a distributed way. After convergence, the average weights will be multiplied by n to obtain the sum of the weights. Let w ⋅j (0) = (w 1j (0), . . . , w nj (0)) T be the n-vector of weights of evidence for supported set A j initially held by the n agents. The partial state vectors w ⋅j (t) for j = 1, . . . , r can be updated in parallel at time t + 1 using linear equations

w ⋅j (t + 1) = Cw ⋅j (t). ( 23
)
Let w(t) = (w ⋅1 (t) T , . . . , w ⋅r (t) T ) T be the rn-vector obtained by concatenating the r vectors w ⋅j (t), j = 1, . . . , r, and let C be the rn × rn matrix C = I r ⊗ C, where I r is the identity matrix of size r and ⊗ is the Kronecker product. Then, the r update equations ( 23) can be written more compactly as

w(t + 1) = C w(t). ( 24
)
Under the conditions of Propositions 1 or 2, we have

lim t→∞ nw ij (t) = n i=1
w ij (0), i.e., each agent i holds after convergence the r-vector of sums w Σ = (∑ n i=1 w i1 , . . . , ∑ n i=1 w ir ), which makes it possible to compute the orthogonal sum

m ⊕ = m 1 ⊕ . . . ⊕ m n = r ⊕ j=1 A w Σj j . (25)
The amount of computation of the distributed Dempster's rule is similar to that of the distributed cautious rule. During the first run of the average consensus to compute the number of nodes, the amount of arithmetic operations at each node i during each iteration is proportional to d i . During the second run to sum up the weights, it is proportional to rd i .

The computation of m ⊕ from the weight vector w Σ requires O(K2 r+1 ) arithmetic operations in the worst case. equations [START_REF] Garin | A survey on distributed estimation and control applications using linear consensus algorithms[END_REF]. The network converges to w Σ = (1.0, 0.5, 1.5, 1.5, 0.9, 0.2, 1.1), corresponding to the orthogonal sum

m ⊕ = {ω 3 } 1 ⊕ {ω 4 } 0.5 ⊕ {ω 2 , ω 4 } 1.5 ⊕ {ω 3 , ω 4 } 1.5 ⊕ {ω 3 , ω 4 , ω 5 } 0.9 ⊕ {ω 4 , ω 6 , ω 7 } 0.2 ⊕ {ω 2 , ω 4 , ω 6 , ω 7 } 1.1 , equal to m ⊕ ({ω 3 }) = 0.0596, m ⊕ ({ω 4 }) = 0.8644, m ⊕ ({ω 2 , ω 4 }) = 0.0329 m ⊕ ({ω 3 , ω 4 }) = 0.0269, m ⊕ ({ω 3 , ω 4 , ω 5 }) = 0.0046, m ⊕ ({ω 4 , ω 6 , ω 7 }) = 0.0021 m ⊕ ({ω 2 , ω 4 , ω 6 , ω 7 }) = 0.0063, m ⊕ (Ω) = 0.0031.

Robust combination

Both Dempster's rule and the cautious rule assume the combined pieces of evidence to be reliable. For this condition to hold, it is necessary, in particular, that the different agents address the same question. There are, however, situations in which this assumption cannot be guaranteed to be verified. Consider, for instance, the data association problem [START_REF] Denoeux | Optimal object association in the Dempster-Shafer framework[END_REF][START_REF] Laghmara | Heterogeneous sensor data fusion for multiple object association using belief functions[END_REF], in which agents collect sensor information about a set of objects. Before this information can be combined, we need to match the objects perceived by each pair of agents. If matching errors occur, then the beliefs held by one agent about some object may be erroneously combined with the beliefs held by the other agent about another object. If the number of agents is large enough and if the matching error probability is small, we can expect to observe consensus among a majority of agents and a few outliers. A robust combination procedure should be able to exclude those outliers and combine only information from consistent sources. In this section, we describe such a procedure based on the RANSAC algorithm [START_REF] Fischler | Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography[END_REF]. The idea of applying a RANSAC-like algorithm to robust combination of belief functions was first proposed by Zair et al. [START_REF] Zair | An evidential RANSAC algorithm and its application to GNSS positioning[END_REF][START_REF] Zair | Evidential framework for robust localization using raw GNSS data[END_REF]. Our proposal is closer to the original RANSAC algorithm and lends itself to distributed implementation using some ideas from [START_REF] Montijano | Distributed Consensus with Visual Perception in Multi-Robot Systems[END_REF]Chapter 4].

In the following, we first recall the RANSAC algorithm and discuss its application to belief function combination in Section 4.1. The distributed implementation is then described in Section 4.2 and an illustrative example is presented in Section 4.3.

RANSAC algorithm and application to evidence combination

The random sample consensus (RANSAC) algorithm [START_REF] Fischler | Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography[END_REF] aims to estimate the parameters of a model from a dataset containing a limited number of outliers. There exist several variants of this algorithm, but the method basically consists in randomly selecting a subsample of the dataset and using it to fit a model. All data items then "vote" for that model if they are well explained by it (i.e., if the model error is less than some threshold). The process is repeated a given number of times, and the model with the largest number of votes is selected. Finally, a better model is fitted by including in the subsample all the observations that voted for the winning model.

The algorithm has three parameters: the size ν of each random subsample, the error threshold τ used in the voting process, and the number N of generated models. In applications such as least-squares estimation, ν is usually chosen as the minimum number of observations to fit a model (i.e., ν = 2 for a straight line). The threshold parameter τ is application-specific and reflects how well the user expects a correct model to explain "inliers". To fix N , Fischler and Bolles [START_REF] Fischler | Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography[END_REF] propose the following line of reasoning. Assume that each observation has a probability p in to be an inlier. The probability that a subsample of size ν is composed of only inliers is p ν in and, consequently, the probability that a sample of size ν contains at least one outlier is 1 -p ν in . If N samples are generated, the probability that at least one of them contains only inliers is, thus, 1 -(1 -p ν in ) N . For this probability to be larger that some predefined value p suc , N has to verify the following inequality:

N ≥ log(1 -p suc ) log(1 -p ν in ) . (26)
When applying the RANSAC approach to evidence combination, the dataset is a set Assuming, as in [START_REF] Zair | An evidential RANSAC algorithm and its application to GNSS positioning[END_REF][START_REF] Zair | Evidential framework for robust localization using raw GNSS data[END_REF], the mass functions to be combined by Dempster's rule, we have

M =
m I = ⊕ i∈I m i (27)
As a measure of discrepancy between a model m I and a mass function m j , we can use the degree of conflict between m j and m I as

κ(m I , m j ) = (m I ⩀ m j )(∅). (28)
In [START_REF] Zair | An evidential RANSAC algorithm and its application to GNSS positioning[END_REF][START_REF] Zair | Evidential framework for robust localization using raw GNSS data[END_REF], the authors do not select a random subset I as in the original RANSAC algorithm, but they search the space 2 M of all models, adding or removing one mass function at a time.

This approach is interesting but it is difficult to implement in a distributed way. For this reason, we stick to the standard RANSAC algorithm in this paper. The centralized (non distributed) procedure is described in Algorithm 1.

Remark 1. When n is small, the random sampling can be replaced by an exhaustive enumeration of all subsets I of {1, . . . , n} of cardinality ν.

Remark 2. The same approach can be used with the cautious rule instead of Dempster's rule. In that case, ( 27) is replaced by

m I = i∈I m i ( 29
)
and the degree of conflict between m I and m j is computed as

κ (m I , m j ) = (m I m j )(∅),
where denotes the unnormalized cautious rule [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by non distinct bodies of evidence[END_REF].

Distributed implementation

The RANSAC procedure described above can be implemented in a distributed way using ideas introduced in [32, Chapter 4]. As in Section 3.2, we assume n agents to be located at the nodes of a network with fixed or time-varying connectivity and verifying the conditions of Propositions 1 or 2, respectively. We assume that the agents have already agreed on the frame of discernement and the list of supported sets using the distributed procedure described in Section 3.2, and that each agent j holds a weight assignment vector w j representing some piece of evidence. We wish to design a robust distributed procedure for combining this evidence using either Dempster's rule or the cautious rule. Dempster's rule will be assumed in the rest of this section for ease of exposition. To this end, the following three steps have to be performed without any centralized mechanism: (1) generation of models from random subsamples, (2) voting process and (3) combination of inliers. These steps are described below. Maybe.Inliers ← Maybe.Inliers ∪ {j} Model generation. This step can be carried out using a random number generation procedure and the maximum consensus algorithm. Initially, each agent i generates a random number

β i . Let β (1) > β (2) > . . . > β (n)
be the n numbers β i (assumed to be distinct) in decreasing order. We need a distributed mechanism for computing the ν largest elements β (1) , . . . , β (ν) . This can be achieved by defining initial sets β j (0) = {β j } and using the following update equation:

β j (t + 1) = max ν ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ β j (t) ∪ ⎛ ⎝ ⋃ k∈N (j) β k (t) ⎞ ⎠ ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ , (30)
where max ν selects the ν largest in a set. By iteratively applying [START_REF] Laghmara | Heterogeneous sensor data fusion for multiple object association using belief functions[END_REF], each β j (t) converges to the set β = {β (1) , . . . , β (ν) }, and the subsample I is defined as I = {j ∶ β j ∈ β}. Each agent knows whether it belongs to I or not. Let

w j (0) = ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ w j if j ∈ I, 0 otherwise,
where 0 = (0, . . . , 0) is a vector of zeros, which is the weight assignment vector of the vacuous mass function m ? . The average consensus algorithm described in Section 3.2 converges to the average 1 n ∑ j∈I w j , which after multiplication by n gives us the weight assignment vector w I = ∑ j∈I w j corresponding to m I = ⊕ j∈I m j . The process can be executed in parallel to generate N subsamples I 1 , . . . , I N and the corresponding combined weight vectors w I 1 , . . . , w I N .

Voting. After the N models have been generated, each agent j votes for them by computing the mass functions m I i and the degrees of conflict κ(m I i , m j ). The votes of agent j may be encoded in the binary N -vector v j (0) = (v j1 (0), . . . , v j N (0)) defined as

v ji (0) = ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ 1 if κ(m I i , m j ) ≤ τ 0 otherwise.
The vote vectors are then updated using the average consensus algorithm, which after convergence allows each agent to compute the score of each of the N models:

score i = n j=1 v ji .
The winning model is the one with the largest of votes and, in case of ties, the smallest index:

i * = min arg max 1≤i≤N score i .
Combination of the inliers. The final step of the RANSAC algorithm is the combination of the inlier mass functions. Each agent knows whether it voted for model i * and thus belongs to the inlier set:

Inliers = {j ∈ {1, . . . , n} ∶ v ji * = 1} .
To combine the mass functions m j for j ∈ Inliers, we initialize the weight assignment vectors as

w j (0) = ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ w j if j ∈ Inliers, 0 otherwise,
and execute one more time the average consensus algorithm. After convergence and multiplication by n, each agent gets the weight vector w = ∑ j∈Inliers w j , from which the mass function m can be computed as

m = r ⊕ k=1 A w k k ,
where A 1 , . . . , A r are the r supported sets identified at the beginning of the process.

Illustrative example

As an example, we consider an idealized distributed classification problem in which each agent observes a feature vector whose distribution depends on the class variable Y ∈ Ω = {ω 1 , ω 2 , . . . , ω K }. Let X i be the feature vector observed by agent i and let f ik be its conditional probability density given Y = ω k . After observing X i = x i , agent i can use the Generalized Bayesian Theorem (GBT) [START_REF] Smets | Belief functions: the disjunctive rule of combination and the generalized Bayesian theorem[END_REF][START_REF] Denoeux | Classification using belief functions: the relationship between the case-based and model-based approaches[END_REF] to derive a mass function m i on Ω defined as

m i = K ⊕ k=1 ({ω k }) -ln γ i f ik (x i ) , (31)
where γ i is a constant such that

γ i ≤ [max k sup x f ik (x)] -1 ,
which ensures that γ i f ik (x i ) ≤ 1 for all k and all x i . The meaning of ( 31) is clear: a small value of the density f ik (x i ) is evidence against ω k or, equivalently, for the complement {ω k } of ω k . The weight assignment function corresponding to m i is, thus,

w i (A) = ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ -ln γ i f ik (x i ) if A = {ω k } 0 otherwise. ( 32
)
It can be represented by a K-vector w i = -(ln f i1 (x i ), . . . , ln f iK (x i )) -ln γ i . Now, assume that the features describe some object but, because of incorrect data association for instance, a minority of agents actually observe a different object belonging to a different class. In that case, the agents' mass functions will be highly conflicting and a robust combination rule must be able to identify and discard outliers. Numerical simulations. We performed simulations with K = 5 classes and n = 20 agents.

Without loss of generality, we assumed that each agent i observes a scalar feature X i whose conditional distribution given class ω k was assumed to be normal with mean µ k ∈ {-2, -1, 0, 1, 2} and standard deviation σ = 1 (Figure 6). We considered a scenario in which the object actually belongs to class ω 1 and 15 agents observe a feature x i drawn for the normal distribution with µ 1 = -2, whereas five agents observe the feature of a class ω 5 object drawn from a normal distribution with mean µ 5 = +2. An example of a dataset x 1 , . . . , x 20 is shown in Figure 6. The mass function m i obtained by the GBT (31) is illustrated in 3 shows the false positive rate (proportion of inliers wrongly labeled as outliers, Table 3a) and the false negative rate (proportion of outliers wrongly labeled as inliers, Table 3b) in percent, averaged over the 100 datasets. Parameter ν seems to have a negligible influence on the performance of the procedure. Larger valued of τ induce smaller false positive rates but larger false negative rates. However, the procedure is not too sensitive to τ and values in the range [0.4, 0.6] appear to yield good results.

Conclusions

The DS theory of belief functions has been widely used for information fusion, due to its ability to represent and combine elementary pieces of information such as provided by sensors or expert judgements. A large body of work has been devoted to the development of procedures making it possible to combine belief functions in a wide range of settings, including conflicting or dependent evidence. Most of these procedures, however, assume that all the belief functions to be combined are available at a single central location. This assumption is not verified in applications such as data fusion in sensor networks or collaborative perception in multi-robot systems. In these applications, information is local, each agent holding only a piece of the available evidence representable by a belief function, and agents can only exchange information with their neighbors in a communication network. We then need distributed fusion procedures allowing the combination of belief functions without any centralized mechanism. Such procedures have been proposed in this paper, based on the notion of weight of evidence. An important observation, already made by Shafer in [START_REF] Shafer | A mathematical theory of evidence[END_REF] but often overlooked, is that evidence can usually be broken down into elementary pieces, each one supporting a single hypothesis to some degree. A mass function can, thus, be represented as a collection of subsets of the frame of discernment, with associated weights of evidence. The weight representation has several advantages: it is sparse (most of the propositions usually have zero weight) and it lends itself to easy calculation, as Dempster's rule boils down to addition in weight space. The cautious rule, an idempotent combination operator suitable for combining dependent evidence, replaces summation by the maximum operation. Adopting the weight representation thus turns the distributed combination problem into the computation of the sum or the maximum of some quantities in a network, which can be solved using existing average and maximum consensus algorithms. Although the amount of communication needed to perform these operations is, in the worst case, exponential in the size of the frame of discernement, we have shown that it is usually much less thanks to the sparsity of the weight representation, and we have described distributed procedures allowing agents to agree on the smallest possible frame and list of supported hypotheses. We have also demonstrated the feasibility of a robust combination procedure based on a distributed implementation of the RANSAC algorithm introduced in [START_REF] Montijano | Distributed Consensus with Visual Perception in Multi-Robot Systems[END_REF].

Although we have focussed on conjunctive combination in this paper, as this is what is mostly needed in applications, the same principles could be applied to disjunctive combination, using the notion of disjunctive weights introduced in [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by non distinct bodies of evidence[END_REF]. Another direction of research is to consider situations in which the agent's beliefs vary in time as they continue to collect sensor information while they exchange information in the communication network. To model such situations, we may need to use dynamic consensus algorithms such as reviewed in [START_REF] Kia | Tutorial on dynamic average consensus: The problem, its applications, and the algorithms[END_REF]. Even more fundamentally, we have only considered the simple situation in which all agents hold evidence pertaining to the same question. While this situation is common in many applications, an interesting extension of this work would be to consider the more complex case in which agents hold evidence about different variables and share common knowledge about the relations between these variables. This knowledge could be assumed to be formalized as a valuation-based system (VBS) [START_REF] Shenoy | A valuation-based language for expert systems[END_REF]. We would then have to combine distributed computation in the communication network with local computation in the VBS hypergraph. This challenging problem is left for further research.

  Mass functions are usually assumed to be normalized, but unnormalized mass functions sometimes appear as intermediate results in calculations (see below). A mass function m represents a piece of evidence, and m(A) represents the probability that the evidence tells us that the truth lies in A, and nothing more specific. The subsets A such that m(A) > 0 are called the focal sets of m. A mass function is said to be consonant if, for any two focal sets A and B, we have either A ⊂ B or B ⊂ A. It is said to be Bayesian if all its focal sets are singletons. Finally, the vacuous mass function m ? verifies m ? (Ω) = 1; it represents complete ignorance. A belief function Bel ∶ 2 Ω → [0, 1] can be computed from a normalized mass function m * as Bel(A) = B⊆A m * (B),

Figure 1 :

 1 Figure 1: Example of a connected graph with five vertices.

Figure 2 :

 2 Figure 2: Convergence of states to the average using Metropolis-Hastings weights (Example 3). Each of the five curves represents the state of one of the five nodes as a function of the number of iterations. All states converge to the average (1 + 2 -1 + 0 -2) 5 = 0 of the initial values.

Furthermore,Example 3 .

 3 G C = G. It thus satisfies the condition of Proposition 1 as long as G is connected, and it ensures average consensus. For the graph of Figure1, the matrix of Metropolis-Hastings weights is

Figure 3 :

 3 Figure 3: Convergence of states to the average using a symmetric gossip scheme (Example 4). Each of the five curves represents the state of one of the five nodes as a function of the number of iterations. All states converge to the average (1 + 2 -1 + 0 -2) 5 = 0 of the initial values.

Example 6 .

 6 Consider again five agents at the nodes of the graph of Figure 1. Assume that Θ = {θ 1 , . . . , θ 100 }. Representing the evidence of each agent by a vector of 2 100 masses or commonalities would obviously be infeasible. Assume that the initial sets of possibilities of the five agents are Ω 1 (0) = {θ 10 , θ 11 , θ 13 , θ 14 }, Ω 2 (0) = {θ 12 , θ 13 , θ 14 , θ 15 } Ω 3 (0) = {θ 11 , θ 12 , θ 13 , θ 14 }, Ω 4 (0) = {θ 12 , θ 13 , θ 15 , θ 16 } Ω 5 (0) = {θ 11 , θ 13 , θ 15 , θ 16 }.

representations are α 1 = 2 3 = 8 and α 2 = 2 1 + 2 3 = 10 .

 1321310 Consequently, F 1 (0) = {8, 10}. Similarly, F 2 (0) = {4, 12}, F 3 (0) = {12, 28}, F 4 (0) = {104} and F 5 (0) = {10, 106}. The consensus algorithm based on update equation (21) converges after a finite number of iterations to the union of the F i (0), i.e., F = {4, 8, 10, 12, 28, 104, 106}.

Example 8 .Figure 4 :

 84 Figure 4: Distributed implementation of Dempster's rule: convergence of nw ij (t) to the sum ∑ n i=1 w ij (0) of initial weights (Example 8). There are n = 5 agents and r = 7 supported sets A j , which makes 5 × 7 = 35 curves. We used separate color for each supported set. The values at convergence are w Σ = (1.0, 0.5, 1.5, 1.5, 0.9, 0.2, 1.1).

  {m 1 , . . . , m n } of n mass functions. Given a subset of indices I ⊂ {1, . . . , n} of cardinality ν, a model is the mass function m I obtained by combining the mass functions {m i ∶ i ∈ I}.

Example 9 .

 9 Figure 5 shows n = 40 mass functions on Ω = {ω 1 , ω 2 } in barycentric coordinates. The bottom left, bottom right and top vertices correspond, respectively, to focal sets {ω 1 }, {ω 2 } and Ω. Thirty "inlier" mass functions support {ω 1 } while 10 outliers (in the lower-left corner) support {ω 2 }. Algorithm 1 was run with τ = 0.3 and ν = 5. Choosing p suc = 0.9999 and p in = 0.75 in (26) gave us N = 34. Figures 5a and 5b show two subsamples I (marked by crosses), with the corresponding sets of outliers (filled circles) and inliers (unfilled circles). The solution of Figure 5a has a score of 30 and is the optimal solution found by the algorithm. In contrast, Figure 5b shows a suboptimal solution with a score of 6. The intermediate mass functions m I and the final mass functions m are shown, respectively, as squares and triangles.

Algorithm 1 4 :i∈I m i 8 :

 148 Centralized RANSAC algorithm for combining belief functions by Dempster's rule. Require: Set of mass functions M = {m 1 , . . . , m n }, subsample size ν, conflict threshold τ , sucess probability p suc , inlier probability p in 1: N ← ⌈ log(1-psuc) log(1-p ν in ) ⌉ 2: best.score ← 0 3: for i = 1 to N do Draw a set I of ν elements from {1, . . . , n} for j = 1 to n do 9: κ(m I , m j ) ← (m I ⩀ m j )(∅) 10: if κ(m I , m j ) ≤ τ then 11: score ← score + 1 12:

Figure 5 :

 5 Figure 5: Mass functions of Example 9 in barycentric coordinates, for two different subsamples I of size ν = 5 shown as crosses. Outliers and inliers are shown, respectively, as filled and unfilled circles. The intermediate mass functions m I and the final mass functions m are shown, respectively, as squares and triangles. The solution on the left-hand side (a) is optimal and has a score of 30. It is the final result of the algorithm. The solution on the right-hand side (b) is suboptimal and has a score of 6.

Figure 6 :

 6 Figure 6: Normal conditional densities of features X i for the five classes, and example of a dataset. Fifteen observations are drawn from N (-2, 1) (unfilled circles) and five are drawn from N (2, 1) (filled circles).

Figure 7 .

 7 Figure 7. The mass assigned to the singletons as well as some of the masses assigned to pairs and triples are shown, respectively, in Figures7a, 7b and 7c, as functions of x. We applied the RANSAC algorithm to 100 datasets. The number N of samples was computed from[START_REF] Kanjanatarakul | Distributed data fusion in the Dempster-Shafer framework[END_REF] with p suc = 0.9999 and p in = 0.75 in[START_REF] Kanjanatarakul | Distributed data fusion in the Dempster-Shafer framework[END_REF], giving us N = 34. We considered values of ν ∈ {3, 5, 10} and τ ∈ {0.2, 0.3, . . . , 0.8}. Table3shows the false positive rate (proportion

Figure 7 :Table 3 :

 73 Figure 7: Mass function obtained by the GBT vs. feature value x: masses assigned to the singletons {ω k }, 1 ≤ k ≤ 5 (a), to the pairs {ω k , ω k+1 } for 1 ≤ k ≤ 4 (b) and to the triples {ω k , ω k+1 , ω k+2 } for 1 ≤ k ≤ 3 (c).The notations ω kl and ω klp stand, respectively, for {ω k , ω l } and {ω k , ω l , ω p }. This figure is better viewed in color.

  3) is called Dempster's rule of combination, or the product-intersection rule. Both the unnormalized conjunctive rule ⩀ and Dempster's rule ⊕ are commutative and associative, and the vacuous element m ? is the neutral element of both operators. An important property is that, to combine several mass functions by Dempster's

rule, we can use the unnormalized combination operator (2) and normalize only at the end, i.e., for n arbitrary mass functions m 1 , . . . , m n ,

Table 1 :

 1 Two mass functions with the corresponding commonality functions and weight assignments, and their orthogonal sum. The weight assignment of the orthogonal sum m 1⊕2 = m 1 ⊕ m 2 is the sum of the weight assignments of m 1 and m 2 .

		∅ {a}	{b} {a, b}	{c}	{a, c} {b, c} {a, b, c}
	m 1	⋅ 0.5	⋅	0.3	⋅	0.1	⋅	0.1
	Q 1	1	1	0.4	0.4	0.2	0.2	0.1	0.1
	w 1		0.22	⋅	1.39	⋅	0.69	⋅
	m 2	⋅	⋅	⋅	⋅	⋅	0.4	0.2	0.4
	Q 2	1 0.8	0.6	0.4	1	0.8	0.6	0.4
	w 2		⋅	⋅	⋅	-0.182 0.69	0.41
	m 1⊕2 ⋅ 0.58 0.067 0.13	0.022	0.13 0.022 0.044
	Q 1⊕2 1 0.89 0.267 0.18	0.222	0.18 0.067 0.044
	w 1⊕2		0.22	⋅	1.39 -0.182 1.39	0.41
	a negative mass s = 1 -e -w(A) to A, and a mass e -w(A) > 1 to Ω. Such mappings are not
	proper mass functions and they do not have a simple interpretation, but they can still be
	formally combined by Dempster's rule using (2)-(3). This notational trick makes it possible

Table 2 :

 2 The two mass functions of Example 1 and their combination by the cautious rule.

		∅ {a} {b} {a, b}	{c}	{a, c} {b, c} {a, b, c}
	m 1	⋅ 0.5	⋅	0.3	⋅	0.1	⋅	0.1
	w 1		0.22	⋅	1.39	⋅	0.69	⋅
	m 2	⋅	⋅	⋅	⋅	⋅	0.4	0.2	0.4
	w 2		⋅	⋅	⋅	-0.182 0.69	0.41
	m 1 2 ⋅ 0.4 0.12 0.24	0.04	0.08	0.04	0.08
	w 1 2		0.22	⋅	1.39	⋅	0.69	0.41

In[START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by non distinct bodies of evidence[END_REF], following[START_REF] Smets | The canonical decomposition of a weighted belief[END_REF], we used the term "weight" for exp(-w), a quantity called "diffidence" in[START_REF] Dubois | Prejudice in uncertain information merging: Pushing the fusion paradigm of evidence theory further[END_REF]. As we will see, the additivity property is central in our analysis: we thus stick to Shafer's terminology and notation in this paper.

Acknowledgment

This research was supported by the Labex MS2T, which was funded by the French Government, through the program "Investments for the future" by the National Agency for Research (reference ANR-11-IDEX-0004-02).