1Department of Engineering Mathematics, University of Bristol, BS8 1UB, UK
2Research Technology and Innovation, Thales UK

# Distributed Possibilistic Learning in Multi-Agent Systems

Jonathan Lawry1 Michael Crosscombe1† and David Harvey2

###### Abstract

Possibility theory is proposed as an uncertainty representation framework for
distributed learning in multi-agent systems and robot swarms. In particular,
we investigate its application to the best-of-$n$ problem where the aim is for
a population of agents to identify the highest quality out of $n$ options
through local interactions between individuals and limited direct feedback
from the environment. In this context we claim that possibility theory
provides efficient mechanisms by which an agent can learn about the state of
the world, and which can allow them to handle inconsistencies between what
they and others believe by varying the level of imprecision of their own
beliefs. We introduce a discrete time model of a population of agents applying
possibility theory to the best-of-$n$ problem. Simulation experiments are then
used to investigate the accuracy of possibility theory in this context as well
as its robustness to noise under varying amounts of direct evidence. Finally,
we compare possibility theory in this context with a similar probabilistic
approach.

###### keywords:

Possibility theory, best-of-n, distributed learning

This work was presented at the 3rd International Symposium on Swarm Behavior
and Bio-Inspired Robotics (SWARM 2019), Okinawa, Japan, November 16–22, 2019.

##  1 Introduction

There is growing evidence that providing agents with a way of explicitly
representing uncertainty in their beliefs can help to facilitate robust
distributed learning for multi-agent systems operating in noisy environments.
For example, [3] shows that robot swarms which use a third truth-value to
represent “unknown” when solving best-of-$n$ problems [19] are more robust to
noise and malfunction than those using binary belief models. In a similar
context, [12] investigates the use of epistemic sets to represent an agents’
belief, corresponding to the set of states of the world which they deem to be
possible. Extensive multi-agent simulations were then employed to test the
scalability of such an approach when applied to large state spaces and varying
numbers of agents. Here we extend this idea by introducing possibility theory
[20, 6] to capture graded possibilities, whereby instead of simply classifying
states as being either possible or impossible, an agent can allocated a degree
of possibility between $0$ and $1$ to any given state. In particular, we
explore the application of possibility theory to distributed multi-agent
learning and more specifically to the best-of-$n$ problem in which a
population of agents aims to identify the best out of $n$ possible choices
(states) on the basis of feedback from the environment and local interactions
between individuals.

The best-of-$n$ is a class of distributed learning and decision making
problems with clear relevance to a range of applications including search and
rescue [15], pollution treatment swarms and distributed task allocation [9].
Common approaches to best-of-$n$ in swarm robotics are often biologically
inspired, for example by the behaviour of honeybees and Temnothorax ants when
searching for nest sites [2, 18, 16]. However, it can also be tackled by using
a combination of belief fusion between agents together with evidential
updating by individuals based on, for example, sensor readings. The
epistemological importance of this approach to distributed learning has been
highlighted by [4] and has been studied using probabilistic models of belief
in [13]. In the sequel we employ this combined approach in a possibility
theory setting. Furthermore, in this context we will argue that the
combination of fusion and evidential updating is more effective and robust to
noise than evidential updating alone.

Possibility theory [5] is a computationally efficient framework for reasoning
about uncertainty which allows for a distinction to be made between
uncertainty and ignorance. At a representational level there are clear
analogies with probability theory. For instance, subjective belief is
represented by a possibility distribution which allocates a degree of
possibility between $0$ and $1$ to each state of the world. The calculus for
possibilities is maxitive in contrast to that for probabilities which is
additive. In particular, the degree of possibility of a proposition, as
represented by a set of states, is given by the maximum of the possibility
values of those states. Possibility theory can also be understood as a special
case of Dempster-Shafer theory [5] and consequently also of imprecise
probability theory. From the latter perspective, possibility theory provides
both an upper bound (possibility) and a lower bound (necessity) on the
probability of any proposition, with the difference between these providing a
measure of ignorance. This capacity to quantify ignorance then provides
additional flexibility when fusing highly inconsistent beliefs, whereby any
such combination will lead to an increase in overall ignorance. In the
following we will exploit these properties for distributed learning to help
facilitate consensus across a population of agents.

An outline of the remainder of the paper is as follows. Section 2 gives an
overview of the basic concepts from possibility theory including a proposed
approach to fusing possibility distributions. In Section 3 we described a
discrete time agent-based model for possibility theory applied to the best-
of-$n$ problem. Simulation experiment results are then described for this
model at different levels of noise and for different evidence rates. In this
context the possibilistic approach is compared with a probabilistic approach
similar to that outlined in [13]. Finally, Section 4 gives some conclusions.

##  2 Possibility Theory

In this section we give a brief introduction to possibility theory and propose
a parameterised family of fusion operators as an effective method for
combining partially inconsistent beliefs. The underpinning concept is that of
a _possibility distribution_ which allocates a degree of possibility to each
of a set of possible states of the world, denoted by
${\mathbb{S}}=\\{s_{1},\ldots,s_{n}\\}$, as follows:

###### Definition 1

Possibility Distribution
A possibility distribution on ${\mathbb{S}}$ is a function
$\pi:{\mathbb{S}}\rightarrow[0,1]$ such that
$\max\\{\pi(s):s\in{\mathbb{S}}\\}=1$. Let ${\mathbb{D}}$ denote the set of
all possibility distributions on $\mathbb{S}$.

A possibility distribution characterises a possibility and necessity measure
defined over propositions as represented by sets of states. Intuitively, in a
context in which knowledge is graded, the possibility measure of a proposition
quantifies the degree to which it is consistent with an agent’s knowledge,
while the necessity quantifies the degree to which it is entailed by that
knowledge.

###### Definition 2

Possibility and Necessity Measures
A possibility distribution $\pi$ on ${\mathbb{S}}$ generates a possibility and
a necessity measure on $2^{{\mathbb{S}}}$ such that, for
$A\subseteq{\mathbb{S}}$,

$\displaystyle\Pi(A)$ $\displaystyle=\max\\{\pi(s):s\in A\\}\ \text{ and }$
$\displaystyle N(A)$ $\displaystyle=\min\\{1-\pi(s):s\in A^{c}\\}.$

For notational simplicity we use $N(s_{i})$ as shorthand for $N(\\{s_{i}\\})$.

The following properties of possibility and necessity measures are immediate
consequences of Definition 2 [5]: For $A,B\subseteq\mathbb{S}$,

  * •

$\Pi({\mathbb{S}})=N({\mathbb{S}})=1$ and $\Pi(\emptyset)=N(\emptyset)=0$,

  * •

$N(A)\leq\Pi(A)$ and $N(A)=1-\Pi(A^{c})$,

  * •

$N(A\cap B)=\min(N(A),N(B))$ and $\Pi(A\cup B)=\max(N(A),N(B))$.

Possibility and necessity measures can also be interpreted as upper and lower
probabilities respectively in the sense that there is a set of probability
measures on propositions satisfying $N(A)\leq P(A)\leq\Pi(A)$ for all
$A\subseteq{\mathbb{S}}$, and furthermore that $N(A)$ and $\Pi(A)$ are
respectively the infimum and supremum of this set. The level of ignorance
about a proposition $A$ is then given by $\Pi(A)-N(A)$.

We now propose a family of fusion operators for combining possibility
distributions which in the current context represent the beliefs of different
agents in the population. This will require the notion of an intersection
function, or _t-norm_ , as given below. The intuition here is that if we
consider the possibility distributions of two agents as defining two fuzzy
sets of possible states [20] then one approach to fusing them is to take the
intersection of these two sets [7].

###### Definition 3

Intersection Function (t-norm)
An intersection function (t-norm) [10] is a function
$T:[0,1]^{2}\rightarrow[0,1]$ which satisfies the following properties:

  * •

For $x\in[0,1]$, $T(x,1)=x$.

  * •

For $x,y,z\in[0,1]$, if $y\leq z$ then $T(x,y)\leq T(x,z)$.

  * •

For $x,y\in[0,1]$, $T(x,y)=T(y,x)$.

  * •

For $x,y,z\in[0,1]$, $T(x,T(y,z))=T(T(x,y),z)$.

###### Definition 4

Possibility Fusion Function
A possibility fusion function is a function
$c:{\mathbb{D}}^{2}\rightarrow{\mathbb{D}}$. In particular, we propose the
following family of t-norm based pooling functions:

$\displaystyle c(\pi_{1}(s),\pi_{2}(s))$
$\displaystyle=T(\pi_{1}(s),\pi_{2}(s))$
$\displaystyle+1-\max\\{T(\pi_{1}(s),\pi_{2}(s)):s\in\mathbb{S}\\}.$

Definition 4 takes the fusion of two possibility distributions to be their
intersection, normalised so that the maximum possibility of the fused
possibility distribution is $1$ as required by Definition 1. The effect of the
normalisation is to increase the level of ignorance if the two possibility
distributions are highly inconsistent. We can argue that
$\max\\{T(\pi_{1}(s),\pi_{2}(s)):s\in{\mathbb{S}}\\}$ provides a good measure
of the consistency of two possibility distributions $\pi_{1}$ and $\pi_{2}$.
Intuitively, $\pi_{1}$ and $\pi_{2}$ might be considered highly inconsistent
if, for all states, $\pi_{1}$ allocates a high possibility values whenever
$\pi_{2}$ allocates a low possibility value and vice versa. In this case
$T(\pi_{1}(s),\pi_{2}(s))$ will be low for all states since it follows from
Definition 3 that $T(\pi_{1}(s),\pi_{2}(s))\leq\min(\pi_{1}(s),\pi_{2}(s))$
[10]. Consequently, the normalising term in Definition 4 will be high as will
then be the possibility values of all states. Hence, according to Definition 2
in this case the possibility measure of all propositions, i.e. sets of states,
will be close to $1$ and its necessity measure will be close $0$. We now
introduce Frank’s family of t-norms which generate a parameterised family of
fusion operators when used in Definition 4.

###### Definition 5

Frank’s Family of t-norms [8]
Frank’s t-norms are a parameterised family of intersection functions of the
form: For $\theta\in{\mathbb{R}}-\\{0\\}$

$\displaystyle T_{\theta}(x,y)=-\frac{1}{\theta}\ln\left(1+\frac{(e^{-\theta
x}-1)(e^{-\theta y}-1)}{(e^{-\theta}-1)}\right).$

Note that

$\displaystyle\lim_{\theta\rightarrow 0}T_{\theta}(x,y)$
$\displaystyle=x\times y,$
$\displaystyle\lim_{\theta\rightarrow\infty}T_{\theta}(x,y)$
$\displaystyle=\min(x,y),$
$\displaystyle\lim_{\theta\rightarrow-\infty}T_{\theta}(x,y)$
$\displaystyle=\max(0,x+y-1).$

Furthermore, Frank’s t-norms are increasing with $\theta$ such that
$\theta\geq\theta^{\prime}$ implies $T_{\theta}\geq T_{\theta^{\prime}}$.

In the case that an agent with possibility distribution $\pi$ needs to make a
choice, for example by selecting a particular state to investigate further,
then one approach is to sample from the pignistic distribution for $\pi$ [17];
the latter is a member of the set of probability distributions bounded above
and below by $\Pi$ and $N$ respectively. Furthermore, it is arguably the least
biased such distribution since it allocates probability proportionately to the
difference between consecutive possibility values [17].

###### Definition 6

Pignistic Distribution
Let $\pi$ be a possibility distribution on $\mathbb{S}$ and let the states be
sorted so that $\pi(s_{i+1})\leq\pi(s_{i})$, then the pignistic distribution
for $\pi$ is the probability distribution on $\mathbb{S}$ given by

$\displaystyle
p_{\pi}(s_{i})=\sum_{j=i}^{n}\frac{\pi(s_{j})-\pi(s_{j+1})}{j}.$

Note that the pignistic distribution is order preserving in the sense that
$\pi(s_{i})\geq\pi(s_{j})$ implies $p_{\pi}(s_{i})\geq p_{\pi}(s_{j})$.

###### Example 7

Let ${\mathbb{S}}=\\{s_{1},s_{2},s_{3}\\}$ and consider the possibility
distribution $\pi$ such that $\pi(s_{1})=1$, $\pi(s_{2})=0.8$ and
$\pi(s_{3})=0.7$. This generates possibility and necessity measures as given
in Definition 2 such that

$\displaystyle\Pi(\\{s_{1},s_{2},s_{3}\\})$ $\displaystyle=\max(1,0.8,0.7)$
$\displaystyle=1$ $\displaystyle\Pi(\\{s_{1},s_{2}\\})$
$\displaystyle=\max(1,0.8)$ $\displaystyle=1,$
$\displaystyle\Pi(\\{s_{1},s_{3}\\})$ $\displaystyle=\max(1,0.7)$
$\displaystyle=1,$ $\displaystyle\Pi(\\{s_{2},s_{3}\\})$
$\displaystyle=\max(0.8,0.7)$ $\displaystyle=0.8,$
$\displaystyle\Pi(s_{1})=1,\hskip 8.00003pt\Pi($ $\displaystyle
s_{2})=0.8,\hskip 8.00003pt\Pi(s_{3})$ $\displaystyle=0.7,$

and

$\displaystyle N(\\{s_{1},s_{2},s_{3}\\})$ $\displaystyle=1,$ $\displaystyle
N(\\{s_{1},s_{2}\\})$ $\displaystyle=1-0.7$ $\displaystyle=0.3,$
$\displaystyle N(\\{s_{1},s_{3}\\})$ $\displaystyle=1-0.8$
$\displaystyle=0.2,$ $\displaystyle N(\\{s_{2},s_{3}\\})$ $\displaystyle=1-1$
$\displaystyle=0,$ $\displaystyle N(s_{1})=\min(1$ $\displaystyle-0.8,1-0.7)$
$\displaystyle=0.2,$ $\displaystyle N(s_{2})=\min(1$ $\displaystyle-1,1-0,7)$
$\displaystyle=0,$ $\displaystyle N(s_{3})=\min(1$ $\displaystyle-1,1-0.8)$
$\displaystyle=0.$

Hence, for the possibility distribution $\pi$ the degree of ignorance
associated with the states $s_{1}$, $s_{2}$ and $s_{3}$ is

$\displaystyle\Pi(s_{1})-N(s_{1})$ $\displaystyle=1-0.2\ $
$\displaystyle=0.8,$ $\displaystyle\Pi(s_{2})-N(s_{2})$ $\displaystyle=0.8-0$
$\displaystyle=0.8,$ $\displaystyle\Pi(s_{3})-N(s_{3})$ $\displaystyle=0.7-0$
$\displaystyle=0.7,$

respectively. The pignistic distribution for $\pi$ is generated according to
Definition 6 as follows:

$\displaystyle p_{\pi}(s_{3})=\frac{0.7}{3}=0.2333,$ $\displaystyle
p_{\pi}(s_{2})=\frac{0.8-0.7}{2}+\frac{0.7}{3}=0.2833,$ $\displaystyle
p_{\pi}(s_{1})=\frac{1-0.8}{1}+\frac{0.8-0.7}{2}+\frac{0.7}{3}=0.4833.$

Now consider a second possibility distribution $\pi^{\prime}$ such that
$\pi^{\prime}(s_{1})=0.4,\pi^{\prime}(s_{2})=0.9,\pi^{\prime}(s_{3})=1$. We
can fuse $\pi$ and $\pi^{\prime}$ by applying the operator in Definition 4.
Taking $\theta=10$ and applying the Frank’s t-norm as in Definition 5 we
obtain

$\displaystyle T_{\theta}(\pi(s_{1}),\pi^{\prime}(s_{1}))\ $ $\displaystyle=\
T_{\theta}(1,0.4)\ $ $\displaystyle=\ 0.4,$ $\displaystyle
T_{\theta}(\pi(s_{2}),\pi^{\prime}(s_{2}))\ $ $\displaystyle=\
T_{\theta}(0.8,0.9)\ $ $\displaystyle=\ 0.7791,$ $\displaystyle
T_{\theta}(\pi(s_{3}),\pi^{\prime}(s_{2}))\ $ $\displaystyle=\
T_{\theta}(0.7,1)\ $ $\displaystyle=\ 0.7.$

In this case the normalising term is
$1-\max(\\{0.4,0.7791,0.7\\})=1-0.7791=0.2209$. Hence, the fused possibility
distribution is such that

$\displaystyle c(\pi,\pi^{\prime})(s_{1})\ $ $\displaystyle=\ 0.4+0.2209\ $
$\displaystyle=\ 0.6209,$ $\displaystyle c(\pi,\pi^{\prime})(s_{2})\ $
$\displaystyle=\ 0.7791+0.2209\ $ $\displaystyle=\ 1,$ $\displaystyle
c(\pi,\pi^{\prime})(s_{3})\ $ $\displaystyle=\ 0.7+0.2209\ $ $\displaystyle=\
0.9209.$

Figure 1 shows the possibility distribution values $c(\pi,\pi^{\prime})$ for
varying values of $\theta$. In this example the normalisation term is
$1-T_{\theta}(\pi(s_{2}),\pi^{\prime}(s_{2}))$. Since $T_{\theta}$ is
increasing with $\theta$ then this term decreases with increasing $\theta$. In
other words, the amount of inconsistency generated by the fusion operator
decreases as $\theta$ increases.

$c(\pi,\pi^{\prime})(s_{2})$$c(\pi,\pi^{\prime})(s_{3})$$c(\pi,\pi^{\prime})(s_{1})$Frank’s
parameter $\theta$

Figure 1: The fused possibility distribution values for $c(\pi,\pi^{\prime})$
plotted against the Frank’s parameter $\theta$.

##  3 Agent-Based Experiments

We adopt a discrete time agent-based model in order to study the macro-level
convergence properties of a population of agents each attempting to
individually solve a best-of-$n$ problem formulated using possibility theory.
Let ${\mathbb{A}}=\\{a_{1},\ldots,a_{k}\\}$ denote the set of agents in the
population. Each state $s_{i}\in\mathbb{S}$ has a quality value
$q_{i}\in[0,1]$ which can be sampled with noise from the environment. For
example, in a distributed search and rescue scenario, $s_{i}$ might correspond
to a particular location and $q_{i}$ to the degree of support for there being
casualties at that location. We assume without loss of generality that
$q_{i}<q_{i+1}$ for $i=1,\ldots,n-1$. More specifically, in the experiments
described below we take $q_{i}=\frac{i}{n+1}$ for $i=1,\ldots,n$, so that
quality values are distributed uniformly across the interval $[0,1]$.

Time $t$

(a) $\pi(s_{n})$ and $N(s_{n})$ for fusion and evidential updating.

Time $t$

(b) $\pi(s_{n})$ and $N(s_{n})$ for evidential updating only.

Figure 2: Average $\pi(s_{n})$ (black line) and $N(s_{n})$ (red line) against
time for $k=100$, $n=5$, $\rho=0.05$, $\sigma=0$ and $\theta=20$.

Agents’ beliefs about which is the best or highest quality state are
represented by possibility distributions on ${\mathbb{S}}$, and at time $t=0$
all agents in ${\mathbb{A}}$ are initialised as being completely ignorant so
that $\pi(s_{i})=1$ for all $s_{i}\in{\mathbb{S}}$. At each time step $t$, two
agents are selected at random to combine their beliefs by applying the fusion
operator given in Definition 4. The aim here is to model systems with limited
communications but mostly unconstrained mixing of agents. The type of swarm
robotics or decentralised AI applications on which we are focusing will
involve individuals moving independently through an environment and
encountering a variety of different agents at different times. This can be
modelled by a system where there is free mixing between agents, i.e. a totally
connected interaction graph of agents, but where there are only relatively few
interactions at any given time. The latter is referred to as a ‘well-stirred’
system in [14], corresponding to the assumption that each agent is equally
likely to interact with any other agent in the population and that such
interactions are independent events. Also, within a time step each agent
selects a state to investigate by sampling at random from the pignistic
distribution of their current possibility distribution (Definition 6). There
is then a probability $\rho$, referred to as the evidence rate, that the agent
will succeed in sampling the quality value for their chosen state. $\rho$
provides a simple quantification of the difficulty of obtaining direct
evidence from the environment, or of traversing the environment in order to
reach the chosen state. If evidence is received then it is with normally
distributed noise, so that the agent receives quality $q_{i}+\epsilon$ for
state $s_{i}$ where $\epsilon$ is a normally distributed random variable with
mean $0$ and standard deviation $\sigma$. The agent then updates their belief
as follow. The evidence received is represented by a possibility distribution
such that111Since quality values are assumed to be in the range $[0,1]$ then
we bound noise values so that the sampled quality is taken to be $0$ if
$q_{i}+\epsilon<0$ and $1$ if $q_{i}+\epsilon>1$.

$\displaystyle\pi_{E}(s_{j})=\begin{cases}1&:j=i,\\\
1-q_{i}-\epsilon&:\text{otherwise}.\end{cases}$

The agent then updates their belief by fusing their current possibility
distribution $\pi$ with the evidence to obtain $c(\pi,\pi_{E})$.

In summary then we have outlined a discrete time model of a population of
agents deployed on the best-of-$n$ problem which is comprised of two
decentralised processes both implemented locally by individual agents:
evidential updating and belief fusion. The defining parameters of this model
are $k$ (the number of agents), $n$ (the number of states), $\rho$ (the
evidence rate), $\sigma$ (the noise) and $\theta$ (the Frank’s t-norm
parameter). In the following subsection we present simulation results for this
model for a variety of different parameter values to gain insight into the
accuracy and robustness of the possibility theory based approach.

Frank’s parameter $\theta$

(a) $\pi(s_{n})$ and $N(s_{n})$ for varying $\theta$ and $\sigma=0$.

Frank’s parameter $\theta$

(b) $\pi(s_{n})$ and $N(s_{n})$ for varying $\theta$ and $\sigma=0.3$.

Figure 3: The average values of $\pi(s_{n})$ (black line) and $N(s_{n})$ (red
line) at $t=1500$ for varying $\theta$ both with and without noise for $n=5$
and $\rho=0.05$.

###  3.1 Simulation Results

In the following experiments we simulated the model described above for
$k=100$ agents and $n=5$ states while varying the remaining parameters. Each
experiment, as characterised by a particular set of parameter values, is run
for $1500$ time steps and the results are then averaged over $100$ runs. In
all cases averages are shown together with 10 and 90 percentiles represented
as error bars. Figure 2 shows the average possibility and necessity values of
the best state, i.e. $s_{n}$, plotted against time. In this case we assume a
$5\%$ evidence rate ($\rho=0.05$), no noise and take $\theta=20$. Figure 2(a)
shows the results when both fusion and updating take place as described above.
In this case the population converges to a shared belief for which
$\pi(s_{n})=N(s_{n})=1$ as characterised by a possibility distribution where
$\pi(s_{n})=1$ and $\pi(s_{i})=0$ for $i\neq n$. In other words, agents are
collectively converging on the correct answer with total certainty. Figure
2(b) shows the results when only evidential updating takes place, i.e. when
there is no fusion of beliefs between agents. Here, convergence is much
slower, with the population not having fully converged after $1500$ time steps
and agents still maintaining imprecision in their beliefs, as indicated by
average necessity values being significantly lower than possibility values.
This indicates that fusion can play a positive role in propagating evidence
through the population. Furthermore, we will subsequently show that evidence-
only learning is much less robust to noise. Initially, however, we consider
the sensitivity of the combined model to the value of the Frank’s parameter
$\theta$.

Figure 3 shows the average values of $\pi(s_{n})$ and $N(s_{n})$ at time step
$1500$ when $\rho=0.05$, plotted against $\theta$ as employed in Definition 5.
Figure 3(a) is when $\sigma=0.0$, i.e. when there is no noise, and Figure 3(b)
is when $\sigma=0.3$. In both cases we see that performance broadly increases
with $\theta$. Note that since Frank’s t-norm increases with $\theta$
(Definition 5), increasing $\theta$ decreases the normalisation term
$1-\max\\{T_{\theta}(\pi_{1}(s),\pi_{2}(s)):s\in\mathbb{S}\\}$ in Definition
4. In other words, Figure 3(a) suggests that the population is better at
solving the best-of-$n$ when employing fusion operators that do not themselves
generate significantly higher levels of inconsistency than is inherent to the
two possibility distributions being fused. In light of this, for the remaining
experiments we adopt a value of $\theta=20$.

Noise $\sigma$

Figure 4: Probability that a sampled quality value for $s_{5}$ will be less
than a sampled quality value for $s_{4}$, plotted against $\sigma$.

Noise $\sigma$

(a) $\pi(s_{n})$ and $N(s_{n})$ for varying $\sigma$ for both fusion and
evidential updating

Noise $\sigma$

(b) $\pi(s_{n})$ and $N(s_{n})$ for varying $\sigma$ for evidential updating
only.

Figure 5: The average values of $\pi(s_{n})$ (black line) and $N(s_{n})$ (red
line) after $1500$ iterations for varying levels of noise, when $n=5$,
$\theta=20$ and $\rho=0.05$.

We now investigate the robustness of the possibilistic approach to noise as
represented by the standard deviation of the noise distribution $\sigma$. In
order to give an indication of the effect of noise in this context we can
consider the probability that a sampled quality value for $s_{5}$, the best
state when $n=5$, is less than an independently sampled quality value for the
second best state $s_{4}$. This is shown in Figure 4 and plotted against the
noise standard deviation $\sigma$. For example, when $\sigma=0.3$ the
probability that the order of these two quality values will be reversed is
$0.331$. Figure 5 shows the average values of $\pi(s_{n})$ and $N(s_{n})$ at
time step $t=1500$, plotted against values of $\sigma$ ranging from $0$ to
$0.5$. Figure 5(a) shows the results when both fusion and evidential updating
are combined, while Figure 5(b) shows the results when there is only updating
from direct evidence. These strongly suggest that combining both fusion
between agents and evidential updating results in distributed learning that is
much more robust to noise than learning based only on direct evidence. We
conjecture that this in part due to the inconsistency handling of the fusion
function given in Definition 4. Noise results in variation in quality sampling
which in turn leads to inconsistency between agents. As described in Section
2, applying the fusion function to inconsistent possibility distributions
results in an increase in imprecision, i.e. to a fused possibility
distribution with high possibility values for a number of different states.
The resulting pignistic probability distribution (Definition 6) will then give
higher probability to those states so that their quality values will be more
likely to be re-sampled. In summary, we suggest that sampling from a noisy
environment leads to more inconsistency between different agents’ beliefs, and
fusing those beliefs results in more imprecision which in turn results in more
repeated sampling of a greater variety of states.

###  3.2 Comparison with Probability

In this subsection we directly compare the possibilistic model for best-of-$n$
with a probabilistic version. For the latter we adopt a discrete time model
with the same structure as that of the possibilistic version but where agents’
beliefs are represented by probability distributions which are then combined
using the product fusion operator as introduced in Definition 8 below.

Evidence rate $\rho$

(a) Comparison of possibility and probability for
$\rho\in[0.01,1]$.

Evidence rate $\rho$

(b) Comparison of possibility and probability for
$\rho\in[0.01,0.11]$.

Figure 6: The average values of $\pi(s_{n})$ (black line), $N(s_{n})$ (red
line) and probability $p(s_{n})$ (blue line) for varying evidence rates
$\rho$. These are after $1500$ iterations with $n=5$, $\theta=20$ and
$\sigma=0.3$.

###### Definition 8

Probability Fusion Function
Let ${\mathbb{P}}$ denote the set of all probability distributions on
${\mathbb{S}}$. Then a probability fusion function is a function
$c:{\mathbb{P}}^{2}\rightarrow{\mathbb{P}}$. In particular, we will focus on
the product fusion function given by: for $s_{i}\in{\mathbb{S}}$,

$\displaystyle
c(p_{1},p_{2})(s_{i})=\frac{p_{1}(s_{i})p_{2}(s_{i})}{\sum_{j=1}^{n}p_{1}(s_{j})p_{2}(s_{j})}.$

This is an established probability fusion operator [1] which as been studied
for agent-based models combining fusion and evidential updating in [13], and
in this context has been shown to have strong convergence properties. Figure 6
compares the probabilistic and possibilistic models for $\sigma=0.3$ and for a
range of evidence rates. For the probabilistic model agents are initialised
with the uniform probability distribution, to represent ignorance, and for the
possibilistic model we take Frank’s parameter to be $\theta=20$ as above. For
the probabilistic approach evidence from sampling the quality of state $s_{i}$
is represented by the following probability distribution:

$\displaystyle p_{E}(s_{j})=\begin{cases}\frac{1-q_{i}-\epsilon}{n}&:j\neq
i,\\\ \frac{(n-1)(q_{i}+\epsilon)+1}{n}&:j=i,\end{cases}$

where $p_{E}$ corresponds to the linear combination of the probability
distribution with $p(s_{i})=1$ and the uniform distribution, with weights
$q_{i}+\epsilon$ and $1-(q_{i}+\epsilon)$, respectively. On receiving this
evidence an agent with current probability distribution $p$ updates to the
distribution $c(p,p_{E})$ where $c$ is the product fusion function given in
Definition 8.

Figure 7 shows the average values of $\pi(s_{n})$, $N(s_{n})$ and also the
average probability $p(s_{n})$ obtained from the above probabilistic approach,
plotted against time for $1500$ time steps when $\theta=20$, $\rho=0.05$ and
$\sigma=0.3$. Clearly then, in such a scenario the possibilistic approach
outperforms the probabilistic method in solving the best-of-$n$ problem under
noise. However, the broader picture is somewhat more complex. For example,
Figure 6 shows the average values of $\pi(s_{n})$, $N(s_{n})$ and $p(s_{n})$
at time step $t=1500$ for varying evidence rates. In particular, Figure 6(a)
shows these results for evidence rates between $0.01$ and $1$. These suggest
that the possibilistic approach is more effective for lower evidence rates
below $\rho=0.2$ (see Figure 6(b)). However, the probabilistic approach
performs better for higher evidence rates. While it is not entirely clear why
this is the case we suggest that it might be related to the varying speeds of
convergence of the two different approaches. For instance, Figure 9 shows
average possibility, necessity and probability values plotted against time for
the higher evidence rate of $\rho=0.5$, but in this case for up to $3500$ time
steps. Here we see that under possibilistic fusion and updating the population
eventually converges to the same level of accuracy as obtained using the
probabilistic approach but the former takes around $6$ times as long to
converge as the latter. Given this, a possible explanation the difference in
performance of the two approaches as summarised by Figure 6 is that for very
low evidence rates the probabilistic fusion operators converges before
sufficient evidence has been received to ensure that the highest quality state
is correctly identified.

Time $t$

Figure 7: $\pi(s_{n})$ (black line), $N(s_{n})$ (red line) and $p(s_{n})$
(blue line) plotted against time for $n=5$, $\theta=20$, $\rho=0.05$ and
$\sigma=0.3$.

Average $p(s_{n})$

(a) Distribution of the average population value of $p(s_{n})$ across $100$
runs.

Average $\pi(s_{n})$

(b) Distribution of the average population value of $\pi(s_{n})$ across $100$
runs.

Figure 8: Histograms of simulation outcomes at $t=1500$ across $100$ runs for
both the probabilistic and possibilistic approaches when $\rho=0.05$ and
$\sigma=0.3$.

Time $t$

Figure 9: $\pi(s_{n})$ (black line), $N(s_{n})$ (red line) and $p(s_{n})$
(blue line) plotted against time over $3500$ time steps, for $n=5$,
$\theta=20$, $\rho=0.5$ and $\sigma=0.3$.

This is to some extent confirmed by Figure 8 which is a different presentation
of the results shown in Figure 7. More specifically, Figures 8(a) and 8(b) are
respectively histograms of the average values of $p(s_{n})$ and $\pi(s_{n})$
across the $100$ independent runs of the simulation when $\sigma=0.3$ and
$\rho=0.05$. For the probabilistic approach each run converges to consensus
where all agents have probability values for $s_{n}$ either close to $1$ or
close to $0$. Furthermore, there is significant proportion of runs in which
the population reached consensus at $p(s_{n})$ close to $0$. Note that the
only stable fixed points of the probability fusion function given in
Definition 8 are when both distributions give probability $1$ to the same
state. Hence, there is an inherent tendency for a population of agents
employing this fusion function to converge to one of these distribution.
Evidence will then tend to skew convergence towards the correct distribution
i.e. the distribution for which $p(s_{n})=1$. However, in the case where there
is very limited evidence and fast convergence then this skew may only be
partial as we see in Figure 8(a). On the other hand, slower convergence when
applying the possibility fusion function allows time, at least in the case of
low evidence rates, for the distribution of outcomes across the different runs
to be much more strongly skewed toward $\pi(s_{n})=1$ as can be seen in Figure
8(b). However, there is then the disadvantage for the possibilistic approach
in that, as the evidence rate increases, the convergence time also increases
as more (partially conflicting) evidence becomes available at each time step,
so that $1500$ time steps is no longer sufficient for the population to reach
consensus on what is the best state as shown in Figure 6(a). Although given
more time the population can converge on the correct answer as shown in Figure
9.

##  4 Conclusions

We have proposed an approach to distributed learning based on possibility
theory, and shown that it can be effectively applied to the best-of-$n$
problem in a system where agents learn both directly from their environment
and by fusing their beliefs with those of others. In particular, we have
introduced a discrete time agent-based model and carried out a number of
simulation experiments to study its meta-level properties and to gain insight
into the performance of distributed possibilistic learning under varying
evidence rates and levels of noise.

Our results suggest that in a distributed learning context, possibility theory
can provide a useful framework for representing uncertainty. This
representation allows for the imprecision of an agent’s belief to increase as
a result of them encountering other beliefs which are partially inconsistent
with their own. This in turn results in robust performance in the presence of
noise, especially for low evidence rates for which the possibilistic approach
outperforms a similar probabilistic model.

## Acknowledgements

This work was funded and delivered in partnership between the Thales Group,
University of Bristol and with the support of the UK Engineering and Physical
Sciences Research Council, ref. EP/R004757/1 entitled “Thales-Bristol
Partnership in Hybrid Autonomous System Engineering (T-B PHASE).”

## References

  * [1] R. F. Bordley, (1982), A multiplicative formula for aggregating probability assessments, Management Science, 28(10), 1137–1148
  * [2] D. D. R. Burns, A. B. Sendova-Franks, N. R. Franks, The effect of social information on the collective choices of ant colonies, Behavioral Ecology, Volume 27, Issue 4, July-August 2016, 1033–1040
  * [3] M. Crosscombe, J. Lawry, S. Hauert, M. Homer, (2017), Robust distributed decision-making in robot swarms: Exploiting a third truth state, 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 4326-4332
  * [4] I. Douven, C. Kelp, (2011), Truth approximation, social epistemology, and opinion dynamics, Erkenntnis, 75(2), 271-283
  * [5] D. Dubois, H. Prade, (1988), Possibility Theory, Plenum, New York
  * [6] D. Dubois, H. Prade, (2011), Possibility theory and its applications: where do we stand, Mathware and Soft Computing, 18(1), 18-31
  * [7] D. Dubois, W. Liu, J. Ma, H. Prade, (2016), The basic principles of uncertain information fusion. An organised review of merging rules in different representation frameworks, Information Fusion 32, 12-39
  * [8] M. J. Frank, (1979), On the simultaneous associativity of F(x, y) and x+y-F(x, y), aequationes mathematicae, 19(1), 194-226
  * [9] N. Kakalis, Y. Ventikos, (2008), Robotic swarm concept for efficient oil spill confrontation, Journal of Hazardous Material, 32, 12 – 39
  * [10] G. J. Klir, B. Yuan, (1995), Fuzzy Sets and Fuzzy Logic: Theory and Application, Prentice Hall.
  * [11] J. Lawry, (2001), Possibilistic normalisation and reasoning under partial inconsistency, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 9(4), 413-436
  * [12] J. Lawry, M. Crosscombe, D. Harvey, (2019), Epistemic sets applied to best-of-n problems, Proceedings of ECSQARU 2019, to appear
  * [13] C. Lee, J. Lawry, A. Winfield, (2018), Combining opinion pooling and evidential updating for multi-agent Consensus, Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18), 347-353
  * [14] C. Parker, H. Zhang, (2009), Cooperative decision-making in multiple-robot systems: the best-of-n problem, IEEE Transactions on Mechatronics 14, 240–251
  * [15] D. Peleg, (2005), Distributed coordination algorithms for mobile robot swarms, Lecture Notes in Computer Science, 1–12, Springer, Singapore
  * [16] A. Reina, J. Marshall, V. Trianni, T. Bose, (2017), Model of the best-of-n nest-site selection process in honeybees, Physical Review E, 95
  * [17] P. Smets, R. Kennes, (1994) The Transferable Belief Model. Artificial Intelligence, 66, 387–412
  * [18] G. Valentini, E. Ferrante, M. Dorigo, (2014), Self-organized collective decision making: The weighted voter model, Proceeding of AAMAS 14, 45–52
  * [19] G. Valentini, E. Ferrante, M. Dorigo, (2017), The best-of-n problem in robot swarms: Formalization, state of the art, and novel perspectives. Frontiers in Robotics and AI, 4(9).
  * [20] L. A. Zadeh, (1978), Fuzzy sets as a basis for a theory of possibility, Fuzzy Sets and Systems, 100 supplement, 3-28