We consider programmable matter that consists of computationally limited devices (which we call particles) that are able to self-organize in order to achieve some collective goal without the need for central control or external intervention. We use the geometric amoebot model to describe such self-organizing particle systems, which defines how particles can actively move and establish or release bonds with one another. Under this model, we investigate the feasibility of solving fundamental problems relevant to programmable matter. In this paper, we present an efficient local-control algorithm which solves the leader election problem in O(n) asynchronous rounds with high probability, where n is the number of particles in the system. Our algorithm relies only on local information (e.g., particles do not have unique identifiers, any knowledge of n, or any sort of global coordinate system), and requires only constant memory per particle.
In the area of , it is usually assumed that there is a collection of autonomous robots that can move freely in a given area and have limited sensing, vision, and communication ranges. They are used in a variety of contexts, including graph exploration (e.g., @cite_4 ), gathering problems (e.g., @cite_33 @cite_1 ), and shape formation problems (e.g., @cite_35 @cite_12 ). Surveys of recent results in swarm robotics can be found in @cite_14 @cite_36 ; other samples of representative work can be found in @cite_30 @cite_28 @cite_27 @cite_9 @cite_37 @cite_22 @cite_26 . While the analytic techniques developed in swarm robotics and natural swarms are of some relevance to this work, the individual units in those systems have more powerful communication and processing capabilities than in the systems we consider.
@cite_30 @cite_35 @cite_37 @cite_14 @cite_4 @cite_33 @cite_22 @cite_26 @cite_36 @cite_28 @cite_9 @cite_1 @cite_27 @cite_12
2782960731 2074713499 2963730940 1569673105
Swarms of mobile robots recently attracted the focus of the Distributed Computing community. One of the fundamental problems in this context is that of exploration: the robots must coordinate to visit all locations that are reachable from their initial positions. Despite its apparent simplicity, this problem proved quite hard to characterise fully, due to many model variants, leading to informal error-prone reasoning. Over the past few years, a significant effort permitted to set up a formal framework, relying on the Coq proof assistant, which was used to provide certified results when robots evolve in a continuous bi-dimensional Euclidean space. However, the most challenging issues with exploration arise in the discrete setting (a.k.a. graph), where locations are modeled as vertices and where edges between vertices denote the ability for a robot to move from one location to the next. We present a formal model to tackle problems and reason about robot algorithms arising in the discrete setting. Our approach extends and generalises previous research efforts focusing on the continuous model. As case studies, we consider fundamental impossibility results for exploration with stop in the discrete model. To our knowledge, those are the first certified results in this context. This framework paves the way for a general certification workflow dedicated to mobile robots on graphs. This paper presents a machine vision based ap- proach for human operators to select individual and groups of autonomous robots from a swarm of UAVs. The angular distance between the robots and the human is estimated using measures of the detected human face, which aids to determine human and multi-UAV localization and positioning. In turn, this is exploited to effectively and naturally make the human select the spatially situated robots. Spatial gestures for selecting robots are presented by the human operator using tangible input devices (i.e., colored gloves). To select individuals and groups of robot we formulate a vocabulary of two-handed spatial pointing gestures. With the use of a Support Vector Machine (SVM) trained in a cascaded multi-binary-class configuration, the spatial gestures are effectively learned and recognized by a swarm of UAVs. I. INTRODUCTION Without the use of teleoperated and hand-held interaction devices, human operators generally face difficulties in select- ing and commanding individual and groups of robots from a relatively large group of spatially distributed robots (i.e., a swarm). However, due to the widespread availability of cost effective digital cameras onboard UGVs and UAVs, it is increasing the attention towards developing uninstrumented methods (i.e., methods that do not use sophisticated hardware devices from the human side) for human-swarm interaction (HSI). In previous work, we focused on learning efficient features incrementally (online) from multi-viewpoint images of multiple gestures that were acquired by a swarm of ground robots (1). In this paper, we present a cascaded supervised machine learning approach to deal with the machine vision problem of selecting 3D spatially-situated robots from a networked swarm based on the recognition of spatial hand gestures. These are a natural, easy recognizable, and device- less way to enable human operators to easily interact with external artifacts such as robots. Inspired by natural human behavior, we propose an ap- proach that combines face engagement and pointing gestures to interact with a swarm of robots: standing in front of a population of robots, by looking at them and pointing at them with spatial gestures, a human operator can designate individual or groups of robots of determined size. Robots cooperate to combine their independent observations of the human's face and gestures to cooperatively determine which robots were addressed (i.e., selected). While state of the art computer vision techniques pro- vide excellent face detection, human skeleton, and gesture recognition in ideal conditions, there are often occlusions, Consider a set of n finite set of simple autonomous mobile robots (asynchronous, no common coordinate system, no identities, no central coordination, no direct communication, no memory of the past, non-rigid, deterministic) initially in distinct locations, moving freely in the plane and able to sense the positions of the other robots. We study the primitive task of the robots arranging themselves on the vertices of a regular n-gon not fixed in advance (Uniform Circle Formation). In the literature, the existing algorithmic contributions are limited to conveniently restricted sets of initial configurations of the robots and to more powerful robots. The question of whether such simple robots could deterministically form a uniform circle has remained open. In this paper, we constructively prove that indeed the Uniform Circle Formation problem is solvable for any initial configuration in which the robots are in distinct locations, without any additional assumption (if two robots are in the same location, the problem is easily seen to be unsolvable). In addition to closing a long-standing problem, the result of this paper also implies that, for pattern formation, asynchrony is not a computational handicap, and that additional powers such as chirality and rigidity are computationally irrelevant. This paper considers a system of asynchronous autonomous mobile robots that can move freely in a two-dimensional plane with no agreement on a common coordinate system. Starting from any initial configuration, the robots are required to eventually gather at a single point, not fixed in advance (gathering problem). Prior work has shown that gathering oblivious (i.e., stateless) robots cannot be achieved deterministically without additional assumptions. In particular, if robots can detect multiplicity (i.e., count robots that share the same location) gathering is possible for three or more robots. Similarly, gathering of any number of robots is possible if they share a common direction, as given by compasses, with no errors. Our work is motivated by the pragmatic standpoint that (1) compasses are error-prone devices in reality, and (2) multiplicity detection, while being easy to achieve, allows for gathering in situations with more than two robots. Consequently, this paper focusses on gathering two asynchronous mobile robots equipped with inaccurate compasses. In particular, we provide a self-stabilizing algorithm to gather, in a finite time, two oblivious robots equipped with compasses that can differ by as much as π 4.