Distributed Data Storage and Fusion for Collective Perception
in Resource-Limited Mobile Robot Swarms

The first goal of our work is to distribute object annotation data across robots in a way that makes efficient use of the collective memory. Each robot can hold a defined number of data items specified by its memory capacity $M_{i}$. Besides memory constraints, we want to account for communication-related costs.

Since we want to pack data items into bins (robots) with different properties, we formulate the distributed storage problem as a heterogeneous bin packing optimization problem. In particular, we consider the variant known as the Variable Cost and Size Bin Packing Problem (VCSBPP) [25].

Given a set of items $\mathcal{T}$ with different volumes $v_{\tau}$ to be loaded into a set of available bins $\mathcal{I}$ with different capacities $M_{i}$ and costs $c_{i}$, we aim to minimize the total cost of the bins selected to store items:

Our second goal is to improve the map annotation accuracy by using at least $V$ votes for each object to identify in the environment. We seek to derive the ensemble probability of success in predicting the correct class $p_{ens}(V,\,p)$ as a non-decreasing function of $V$ that is always at least as large as the accuracy $p$ of the correct class.

Figure 1 shows the interconnection between the different components of the collective semantic annotation application with label consolidation. Robots move in an environment with objects to annotate. Upon detecting an object and deciding to record an annotation, each robot assigns an uncertain class annotation for the location. The robots writes the annotation into the shared memory as described in Section IV-B. Upon storing multiple annotations from the same location, robots query the shared memory for all data from that location to retrieve all the related annotations. If they receive enough annotations back from the query, the robots write the most frequent label for that location into the shared memory as a consolidated annotation. The exact consolidation mechanism and the resulting ensemble accuracy are formalized in Section IV-C. Over time, as robots explore the environment, the shared memory stores an increasingly more complete map of the annotated objects in the form of consolidated annotations. Section IV-D explains the local routine run by the robots to perform the various actions across components.

We implement a shared memory to enable distributed storage across the robots. For this purpose we used SwarmMesh [26], a decentralized data structure for mobile swarms. As part of the work in this paper, we also provide a generic, open-source C++ implementation of this data structure.¹¹1https://github.com/NESTLab/SwarmMeshLibrary SwarmMesh is based on a distributed online heuristic solution to the Bin Packing problem formulated in Section III-B, Eqs. (1)-(2).

SwarmMesh stores data in the form of tuples (key-value pairs). The tuple key k is used for both storing and addressing tuples. It consists of two parts: (i) a unique tuple identifier $\tau$ and (ii) a tuple hash $\rho_{\tau}$ that depends on the tuple value v to be stored. When a robot $i$ creates a new tuple, the unique tuple identifier $\tau$ is calculated as the concatenation of the binary representations of $i$ and of the count of tuples created so far by the robot. The tuple value v contains the annotation $\lambda_{\nu}$, the box center, the box orientation and the vector from the center of the box to the front right corner of the box. These variables fully describe an annotated 3D bounding box.

Each robot calculates a so-called NodeID, $\delta_{i}$, which determines which tuples can be stored on a robot and which cannot. The robots compute their NodeIDs at each time step as follows:

Intuitively, the NodeID encodes how willing a robot is to store a new tuple, but also how desirable it is to store a tuple on that robot. In Eq. (3), the NodeID increases linearly with the amount of available memory (more room for tuples) and the number of neighbors of a robot (better connectivity, lower likelihood of disconnections, better routing). As the robots move and store or delete tuples, the NodeIDs change over time.

The NodeIDs form a distribution that defines an hierarchy among robots. To decide which robot eventually stores a tuple, SwarmMesh has an analogous mechanism that imposes an hierarchy among tuples. A tuple is passed from robot to robot until $\delta_{i}(t)>\rho_{\tau}$. Intuitively, we want tuples with a high hash $\rho_{\tau}$ to occupy the best robots in the network. Our insight is that the most uncertain annotations are those that should be mapped to higher values of $\rho_{\tau}$, because this makes them easier to query and route. This makes it more efficient to consolidate uncertain annotations into annotations with a sufficient level of confidence. In contrast, annotations with high levels of certainty need a less critical placement. To formalize this notion, we calculate $\rho_{\tau}=R(\lambda_{\nu})$, where $R(\cdot)$ is a staircase function increasing with the uncertainty of annotation $\lambda_{\nu}$.

SwarmMesh offers a wide API of operations to handle tuples. In this work, we use the following operations:

• •

  store(k,v) which assigns a tuple to a suitable robot in the data structure;

• •

  get(x,y,r), which returns all the tuples located within a radius $r$ of the point $(x,y)$ expressed in a global reference frame;

• •

  erase_except_tuple(x,y,r,k), which removes from the data structure all tuples located within a radius $r$ around the point $(x,y)$ in the global reference frame, except for the tuples with unique identifier $\tau$ in the list k.

Plurality vote. Upon querying the shared memory for a particular location in space, the querying robot receives class annotations predicted by various robots. If the number of votes $n$ is greater than or equal to the minimum number of votes $V$, the robot aggregates these votes into a consolidated annotation $\bar{\lambda}$ for the object through plurality voting:

where $I$ is the indicator function. In case of ties, the consolidated annotation is selected at random from the tied options.

Without knowing the correct class, we can estimate it from an observed vector as the class with the most votes, whether a majority or plurality. In the case where several classes are tied with the highest number of votes, we select one of those classes at random. Again considering that $z_{1}$ represents the true correct class, we use $z^{*}$ to denote a vector of vote counts for which $z_{1}\geq z_{i}$, for all $i=2,3,\ldots,c$. The probability of identifying the correct class with $n$ total votes is then

since all other vectors $z$ result in a success probability of zero. Because the largest term in $z^{*}$ appears first and all incorrect classes are chosen with equal probability, we can express (4) using integer partitions.

Integer partitions. An integer partition $\xi$ is a nonincreasing sequence of positive integers $\xi_{1}\geq\xi_{2}\geq\cdots\geq\xi_{\omega}$. We say that $\xi$ is a partition of $n$, denoted $\xi\vdash n$, if $\sum_{i=1}^{\omega}\xi_{i}=n$, and we consider the set of all such $\xi$ to be $\mathcal{P}$. The $\xi_{i}$ are called parts of the partition, and we define the length of the partition $\ell(\xi):=\omega$. An alternative formulation is to consider the infinite sequence of multiplicities of each part $\xi=(k_{1},k_{2},\ldots)$ where $k_{j}\in\{0,1,\ldots\}.$ Here, $\xi\vdash n$ if $\sum_{j=1}^{\infty}jk_{j}=n$, and the length $\ell(\xi)=\sum_{j=1}^{\infty}k_{j}=\omega$, since all but a finite number of $k_{j}$ are zero [27]. For example, $\xi=(5,3,2,1,1)$ in part notation and $\xi=(2,1,1,0,1,0,\ldots)$ in multiplicity notation represent the same partition of $n=12$. We will refer to both the parts $\xi_{i}$ and multiplicities $k_{j}$ of the same partition throughout.

Note that we can map each vector $z^{*}$ to an integer partition $g(x^{*})=\xi$, where $\xi_{1}$ represents the number of votes for the correct class, and the other $\xi_{i}$ represent the positive numbers of votes for $\omega-1$ incorrect classes. Since all incorrect classes are equally likely, each $z^{*}$ that maps to a particular $\xi$ yields the same probability of success. Thus,

where $\left|g^{-1}\big{(}\{\xi\}\big{)}\right|$ is the cardinality of the preimage of $\{\xi\}$, i.e., the number of $z^{*}$ that map to $\xi$.

To determine $\left|g^{-1}\big{(}\{\xi\}\big{)}\right|$, we start with the $\binom{c-1}{\omega-1}$ combinations of incorrect classes and count the ways to assign vote counts with multiplicities $k_{j}$ to each. There are

such assignments, where the $k_{\xi_{1}}-1$ derives from the fact that one of the spots for the largest possible vote count is taken by the correct class. Together, we have

For the conditional probability $P(\mathrm{success}\,|\,\xi)$, when $\xi_{1}$ is the strictly largest part, it is chosen with probability 1; otherwise, there is a $k_{\xi_{1}}$-way tie, from which a class is chosen at random. In both cases, the correct class is chosen with probability $P(\mathrm{success}\,|\,\xi)=1/k_{\xi_{1}}$. Substituting into (5) and simplifying gives

Robots each run a local procedure in a loop. We refer to this procedure as the control step and outline it from the perspective of robot $i$ in Algorithm 1. Every time step, the robot performs one iteration of this loop.

At the beginning of the procedure, the robot receives and deserializes messages from its neighbors. Certain messages are meant for specific recipients only (point-to-point) and get discarded by any other receiving robot during deserialization. The robot then computes and performs a motion increment according to a diffusion policy [21].

Next, the robot checks the output of its perception module if it is not in recording timeout. The recording timeout is a delay imposed to avoid making successive observations of the same object. If the perception module has detected an object, the robot creates a tuple and starts a store() operation on the shared memory. The payload of the tuple contains the object annotation and the bounding box location and dimensions.

If the robot is not in a querying timeout, it reviews the tuples stored in its memory by bounding box location. If the robot finds multiple tuples with the same location in its own local memory, it starts a get() query on SwarmMesh to retrieve all the tuples currently stored with that bounding box location. It then saves the meta data for the started query.

The robot goes through the queries it has started and checks whether it has not received replies for a period longer than a time threshold. If the number of tuples is larger than the minimum number of votes, the robot creates and writes a tuple into SwarmMesh with the consolidated annotation. It also start an erase_except_tuple() request of all tuples with the given location except for the newly created tuple.

SwarmMesh routing at line 30 of Alg. 1 decides which requests and replies need to be routed and to which robot. A robot may have to send a reply to a request and continue propagating the request or route a neighbor’s reply or discard the request or reply. The details of the routing process are reported in [26].

Robots and environment. We study the influence of the number of robots $N$ by running experiments with 30, 60 and 90 robots. The robots have a communication range $C$ of 2 m and move at a forward speed of 5 cm/s. The robots diffuse and avoid obstacles in an $8\times 8\,\mathrm{m^{2}}$ environment. Given these settings, the robot density is such that robots are within communication range most of the time, but a significant number of intermittent disconnections occur. We do not consider line-of-sight obstructions.

In order to run experiments representative of collective annotation in an indoors environment, we import 40 objects of 13 types from the SceneNN dataset. Therefore, the objects are non-uniformly distributed in space. We made the following adjustments when importing scene 005 of the dataset: (i) we limited physical dimensions to fit in the viewing frustum; (ii) we lowered objects to the ground level; (iii) we rotated them to face towards the center of each “room”; (iv) we removed overlapping objects; (v) we re-labelled “unknown” objects by drawing from the list of object classes at random. Figure 3 shows the imported environment with these modifications.

Classifier. We simulate the statistical behavior of the BGA-DGCNN classifier using data from the SceneNN dataset [24, 10]. The procedure to generate a posterior distribution is described in Section III-A3. Each observed annotation $\lambda_{\nu}$ in the simulation is given by drawing from this distribution.

Ensemble accuracy. In order to set $V$ according to a desired range of probabilistic accuracy, we compute the ensemble accuracy $p_{ens}(n,p)$ for each class of objects for a given number of votes $n$ using Equation 6. We use the per-class accuracy $p$ for BGA-DGCNN shown in Table I, as reported in [10]. Figure 4 is the resulting curve. In our experiments, we vary the threshold $V$ in the range between the two vertical lines in Figure 4.

SwarmMesh parameters. We select the data structure parameters so as to maintain a reasonable load factor, i.e., the ratio of data to store over the available storage capacity. We set the memory capacity of robots $M_{i}$ to 20 tuples with a target of 10 tuple for storage and an allowance of 10 for the routing queue. We set the step size in the hashing function $R(\lambda_{\nu})$ to 5 (see Section IV-B).

Effect of the number of robots. Using more robots distributes sensing spatially and leads to a more densely connected robotic network. As a result, we expect that increasing the number of robots $N$ speeds up the collection and aggregation of data needed to complete the semantic map. In our setting, map coverage refers to the ratio of covered objects to the total number of objects. We make a distinction between two types of coverage: (i) the observation coverage which considers an object covered if at least one robot annotated the object; (ii) the consolidation coverage which considers an object covered if there exists a consolidated annotation $\bar{\lambda}$ for the object in the shared memory. Figure 5 shows the temporal curve of both types of coverage across different values of $N$ and a set threshold of votes $V=3$. The curves of map coverage over time increase faster with a higher number of robots. The consolidation coverage rises slower than the observation coverage since it depends on the consolidation process that queries the shared memory as described in Section IV-D. With $N=90$, the delay for consolidating all the annotations is 14 s from the time all objects have been observed.

Effect of the number of votes. The observation coverage is independent of $V$. Figure 6 shows the map accuracy and the consolidation coverage over time across values of $V$. The experimental map accuracy is the ratio of correct consolidated annotations to the number of consolidated annotations. We observe that the map accuracy increases with $V$ at the cost of a slower coverage.

Distributed storage cost. Figure 7 shows the total storage cost (1a) of the tuples-to-robots assignment realized in practice over time in the simulation, and optimal and worst case curves. At every time step, the tuple set $\mathcal{T}$ and the number of neighbors of each robot $|\mathcal{N}_{i}|$ are updated. In our evaluation, we consider tuples of unit volume ($v_{\tau}=1,\,\forall\tau$) and an homogeneous memory capacity across robots ($M_{i}=M,\,\forall i$). We calculate the cost obtained in simulation using the heuristic tuple-to-robot assignment rule of SwarmMesh. In order to tell apart cases in which tuples are assigned to robots with null $|\mathcal{N}_{i}|$ and/or $m_{i}$, we cap each term in the sum to 1. These cases result in jumps of 1 of the cost in Figure 7.

The VSCBPP problem is NP-hard but our experimental settings ($v_{\tau}=1,\,\forall\tau$) and ($M_{i}=M,\,\forall i$) allow for optimally solving instances of the simulation with $N=30$, $V=3$. We reduce the space of the exhaustive search by noting that permutations of the rows of $(a_{\tau i})$ lead to equivalent solutions in terms of cost. We enumerate integer partitions of $|\mathcal{T}|$ with fewer than $|\mathcal{I}|$ parts and such that all parts are smaller than $M$. For each such partition, we determine the minimal cost using the rearrangement inequality for the product of $1/|\mathcal{N}_{i}|$ and $1/m_{i}$:

where $\sigma(.)$ is an ascending ordering of $|\mathcal{N}_{i}|$, and $\pi(.)$ is a descending ordering of $m_{i}$.

Given $|\mathcal{N}_{i}|$ and $\mathcal{T}$, we compute the worst cost by assigning one tuple to each robot with $|\mathcal{N}_{i}|=0$, filling the memory ($m_{i}=0$) of as many robots as possible given the number of tuples $|\mathcal{T}|$ and placing the remainder of tuples in the robot of lowest non-zero $|\mathcal{N}_{i}|$.

SwarmMesh dimensioning. Figure 8 validates our selection of the SwarmMesh parameters. It shows that the bias of the NodeID distribution is greater than that of the distribution of tuple hashes. This indicates that our insight that uncertain annotations should correspond to higher hash values is appropriate, i.e., it is likely to find a robot of greater NodeID than a given tuple hash. We keep the parameters constant across numbers of robots. This means that with higher swarm size $N$, the collective memory capacity $N\cdot M$ is over-sized and the key partitioning matches tuples to robots randomly. In practice, this means that the robot writing the tuple typically keeps it locally, which leads to reduced communication overhead at greater swarm sizes.

Effect of the number of votes. We find that the number of bytes sent increases with the minimum number of votes $V$ (Figure 9). This indicates that an increase in map accuracy comes at the cost of a higher communication overhead.

Effect of the number of robots. Figure 10 shows the bandwidth usage per robot across different values of $N$ in the configuration with the largest amount of data to be managed ($V=6$). Communication overhead decreases when $N$ increases because we keep the same shared memory parameters across values of $N$. This is consistent with the effect described when discussing the SwarmMesh dimensioning.