# Robot Swarms Decide under Perception Errors in Best-of-N Problems
## 3 The Extended Robot'S Behavioral Model
Differently from the distance-based algorithm, the following two algorithms enable robots to reconstruct the distribution of the quality values of the two sites and by relying on local information. Similarly to the distance-based algorithm, during the period of \(\theta_{classify}\), robot \(i\) collects the quality values measured by its neighbors who have visited the same site. Robot \(i\) then exploits these measurements to predict the quality distribution of that particular site. The two investigated algorithms are as follows:
* **The k-means clustering algorithm:** K-means clustering is a clustering algorithm that aggregate data in k groups based on specific similarities [23]. The parameter \(k\) tells the algorithm in how many clusters to split the data points. In our study, we have three populations; hence, we set \(k=3\) and this piece of information is known by individual robots. The k-means algorithm initializes the means of the three clusters using the data collected during the period of \(\theta_{classify}\). This divides the range of the collected data evenly by using the minimum \(d_{min}\) and the maximum \(d_{max}\) of the collected data as follows. \[\mu_{1} =d_{min}+(d_{max}-d_{min})/2\] \[\mu_{2} =\mu_{1}+(d_{max}-\mu_{1})/2\] \[\mu_{3} =d_{min}+(\mu_{1}-d_{min})/2\] The algorithm loops over the quality values collected by the robot and assigns each value to the cluster for which its mean has the smallest absolute distance to that value. Once the algorithm has looped over all collected values, it recomputes the means of the three clusters by using the average value over the added data. It repeats this procedure until the means of the three clusters stop to change or until a predefined number of iterations is reached. Afterwards, robots use the generated distribution with the three clusters to classify themselves, i.e., accurate if their opinion belongs to the cluster in the middle, overestimating if their opinion belongs to the cluster with the largest mean, and underestimating if their opinion belongs to the cluster with the smallest mean. The one clear downside of the k-mean algorithm is the prerequisite of parameter \(k\)--i.e., robots need to know upfront the number of populations. Additionally, when setting, e.g., \(k=3\), the algorithm will cluster the data in three groups, even when less populations are present. To handle this downside, we introduce in the following--the DBSCAN clustering algorithm. * **The density-based algorithm for discovering clusters (DBSCAN):** This algorithm [24] iterates over all values collected by the robot during the period of \(\theta_{classify}\). For each value, it creates an adjacent list that includes all other values for which its distance to the considered value is less than a configurable parameter \(\rho\). The generated adjacent lists represent potential distribution clusters. Once this is performed, the algorithm iterates over each value that is not classified yet and assigns it--and recursively the members of its adjacent list--to the proper cluster. Values that do not have an adjacent list of at least \(A_{min}\) values are considered as noisy data points and, hence, ignored. Since DBSCAN generates data clusters with no a prior knowledge on the number of clusters, it may output a more accurate number of clusters than the k-mean algorithm. However, when the number of generated clusters is one or two, it becomes challenging for the robots to classify themselves. In case of three clusters, the robots for which its opinions belong in the middle cluster classify themselves as the accurate ones. While robots' whose opinions belong in the cluster with the largest(lowest) mean classify themselves as overestimating(underestimating). When DBSCAN outputs more than three clusters, robots classify themselves as accurate as long as their opinions do not belong in the most-left (cluster with the lowest mean) or most-right(cluster with the largest mean) clusters.