The best-of-n problem with dynamic site qualities: Achieving adaptability with stubborn individuals (ANTS2018)

Abstract

Collective decision-making is one of main building blocks of
swarm robotics collective behaviors. It is the ability of individuals to
make a collective decisions without any centralized leadership, but only
via local interactions and communication. The best-of-n problem is one
subclass of collective decision-making, whereby the swarm has to select
the best option among a set of n possible alternatives. Recently, the bestof-
n problems has gathered momentum: a number of decision-making
mechanisms have been studied or proposed focusing both on cases where
there is an explicit measurable difference between the two qualities, as
well as on cases when there are only delay costs in the environment
driving the consensus to one of the n alternatives. To the best of our
knowledge, all the formal studies on the best-of-n problem have focused
on cases where the site quality distribution is stationary and does not
change over time.

In this paper, we perform a study of the best-of-n problems in a dynamic
environment setting. We consider the situation where site qualities can
be directly measured by agents, and we introduce abrupt changes to
these qualities, whereby the two qualities are swapped at a given time
to invert the convenience of the two alternatives.

Using computer simulations, we show that a vanilla application of the
simplest decision-making mechanism, the voter model, does not guarantee
adaptation of the swarm consensus towards the best option after the
swap occurs. Therefore, we introduce the notion of stubborn agents, that
are agents that are not allowed to change their opinion. We show that
the presence of the stubborn agents is enough to achieve adaptability
to dynamic environments, and we study the performance of the system
with respect to a number of key parameters, such as the swarm size,
the difference between the two qualities and the proportion of stubborn
individuals.

Keywords: Swarm Robotics, Collective decision-making, Dynamic environments