Search

Summary: In this paper, we consider the problem of semi‐uniform deployment for mobile robots in perfect ℓ$$ \ell $$‐ary trees. This problem requires robots to spread in the tree so that, for some positive integer d$$ d $$ and some fixed integer s(0≤s≤d−1)$$ s\left(0\le s\le d-1\right) $$, each node of depth s+dj(j≥0)$$ s+ dj\left(j\ge 0\right) $$ is occupied by a robot. Robots have an infinite visibility range but are opaque, and each robot can emit a light color visible to itself and other robots, taken from a set of κ$$ \kappa $$ colors, at each time step. Then, we clarify the solvability of the semi‐uniform deployment problem, focusing on the number of available light colors. First, we consider robots with κ=1$$ \kappa =1 $$. In this setting, we show that there is no collision‐free algorithm to solve the problem. Next, relax the number of available light colors, that is, we consider robots with κ=2$$ \kappa =2 $$. In this setting, we propose a collision‐free algorithm that can solve the problem. From these results, we can show that the semi‐uniform deployment problem can be solved when κ≥2$$ \kappa \ge 2 $$, and our proposed algorithm is optimal with respect to the number of used light colors (i.e., 2). [ABSTRACT FROM AUTHOR]

We consider mobile robotic entities that have to cooperate to solve assigned tasks. In the literature, two models have been used to model their visibility sensors: the full visibility model, where all robots can see all other robots, and the limited visibility model, where there exists a limit λ > 0 such that all robots closer than λ are seen and all robots further than λ are not seen. We introduce the uncertain visibility model, which generalizes both models by considering that a subset of the robots further than λ cannot be seen. An empty subset corresponds to the full visibility model, and a subset containing every such robot corresponds to the limited visibility model. Then, we explore the impact of this new visibility model on the feasibility of benchmarking tasks in mobile robots computing: gathering, uniform circle formation, luminous rendezvous, and leader election. For each task, we determine the weakest visibility adversary that prevents task solvability, and the strongest adversary that allows task solvability. Our work sheds new light on the impact of visibility sensors in the context of mobile robot computing, and paves the way for more realistic algorithms that can cope with uncertain visibility sensors. [ABSTRACT FROM AUTHOR]

We consider swarms of asynchronous oblivious robots evolving into an anonymous grid-shaped network. In this context, we investigate optimal (w.r.t. the number of robots) deterministic solutions for the terminating exploration problem. We first show lower bounds in the semi-synchronous model. Precisely, we show that at least three robots are required to explore any grid of at least three nodes, even in the probabilistic case. Then, we show that at least four (resp. five) robots are necessary to deterministically explore a |$\bf(2,2)$| -Grid (resp. a |$\bf(3,3)$| -Grid). We then propose deterministic algorithms in the asynchronous model. This latter being strictly weakest than the semi-synchronous model, all the aforementioned bounds still hold in that context. Our algorithms actually exhibit the optimal number of robots that is necessary to explore a given grid. Overall, our results show that except in two particular cases, three robots are necessary and sufficient to deterministically explore a grid of at least three nodes and then terminate. The optimal number of robots for the two remaining cases is four for the |$\bf(2,2)$| -Grid and five for the |$\bf(3,3)$| -Grid, respectively. [ABSTRACT FROM AUTHOR]

We study verification problems for autonomous swarms of mobile robots that self-organize and cooperate to solve global objectives. In particular, we focus in this paper on the model proposed by Suzuki and Yamashita of anonymous robots evolving in a discrete space with a finite number of locations (here, a ring). A large number of algorithms have been proposed working for rings whose size is not a priori fixed and can be hence considered as a parameter. Handmade correctness proofs of these algorithms have been shown to be error-prone, and recent attention had been given to the application of formal methods to automatically prove those. Our work is the first to study the verification problem of such algorithms in the parameterized case. We show that safety and reachability problems are undecidable for robots evolving asynchronously. On the positive side, we show that safety properties are decidable in the synchronous case, as well as in the asynchronous case for a particular class of algorithms. Several other properties of the protocol can be decided as well. Decision procedures rely on an encoding in Presburger arithmetics formulae that can be verified by an SMT-solver. Feasibility of our approach is demonstrated by the encoding of several case studies. [ABSTRACT FROM AUTHOR]

We deal with a team of autonomous robots that are endowed with motion actuators and visibility sensors. Those robots are weak and evolve in a discrete environment. By weak, we mean that they are anonymous, uniform, unable to explicitly communicate, and oblivious. We first show that it is impossible to solve the terminating exploration of a simple torus of arbitrary size with less than 4 or 5 such robots, respectively depending on whether the algorithm is probabilistic or deterministic. Next, we propose in the SSYNC model a probabilistic solution for the terminating exploration of torus-shaped networks of size ℓ × L , where 7 ≤ ℓ ≤ L , by a team of 4 such weak robots. So, this algorithm is optimal w.r.t. the number of robots. [ABSTRACT FROM AUTHOR]

In mobile robotic swarms, the gathering problem consists in coordinating all the robots so that in finite time they occupy the same location, not known beforehand. Multiplicity detection refers to the ability to detect that more than one robot can occupy a given position. When the robotic swarm operates synchronously, a well-known result by Cohen and Peleg permits to achieve gathering, provided robots are capable of multiplicity detection. We present a new algorithm for synchronous gathering, that does not assume that robots are capable of multiplicity detection, nor make any other extra assumption. Unlike previous approaches, the correctness of our proof is certified in the model where the protocol is defined, using the COQ proof assistant. [ABSTRACT FROM AUTHOR]

We investigate exploration algorithms for autonomous mobile robots evolving in uniform ring-shaped networks. Unlike previous works, we consider myopia (each robot can only observe its neighboring nodes) and luminosity (each robot can use only two colors for its light) properties for the robots. As a main contribution, we prove that (i) in the FSYNC model, two (resp. three) myopic robots are necessary and sufficient to achieve perpetual (resp. terminating) exploration, and (ii) in the SSYNC and ASYNC models, three (resp. four) myopic robots are necessary and sufficient to achieve perpetual (resp. terminating) exploration. We also show that, in all execution models, our perpetual exploration algorithm is universal. That is, the algorithm solves perpetual exploration from any solvable initial configuration with two (resp. three) myopic robots and two colors in the FSYNC model (resp. the SSYNC and ASYNC models). On the other hand, we provide impossibility results for universal terminating exploration. [ABSTRACT FROM AUTHOR]

We consider a swarm of mobile robots evolving in a bidimensional Euclidean space. We study a variant of the crash-tolerant gathering problem: if no robot crashes, robots have to meet at the same arbitrary location, not known beforehand, in finite time; if one or several robots crash at the same location, the remaining correct robots gather at the crash location to rescue them. Motivated by impossibility results in the semi-synchronous setting, we present the first solution to the problem for the fully synchronous setting that operates in the vanilla Look-Compute-Move model with no additional hypotheses: robots are oblivious, disoriented, have no multiplicity detection capacity, and may start from arbitrary positions (including those with multiplicity points). We furthermore show that robots gather in a time that is proportional to the initial maximum distance between robots. [ABSTRACT FROM AUTHOR]

The paper details the first successful attempt at using model checking techniques to verify the correctness of distributed algorithms for robots evolving in a continuous environment. The study focuses on the problem of rendezvous of two robots with lights. There exist many different rendezvous algorithms that aim at finding the minimal number of colors needed to solve rendezvous in various synchrony models (e.g. , FSYNC, SSYNC, ASYNC). While these rendezvous algorithms are typically very simple, their analysis and proof of correctness tend to be extremely complex, tedious, and error-prone as impossibility results are based on subtle interactions between the activation schedules of the robots. The paper presents a generic verification model that can be concretely expressed in available software model-checkers. In particular, we explain the subtle design decisions that allow to keep the search space finite and tractable, as well as prove several important theorems that support them. As a sanity check, we use the model to verify several known rendezvous algorithms in six different models of synchrony. In each case, we find that the results obtained from the model checker are consistent with the results known in the literature. The model checker outputs a counter-example execution in every case that is known to fail. In the course of developing and proving the validity of the model, we identified several fundamental theorems, including the ability for a well chosen algorithm and ASYNC scheduler to produce an emerging property of memory in a system of oblivious mobile robots, and why it is not a problem when robots executing the gathering algorithms are equipped with lights. [Display omitted] • We describe a model to verify mobile robot gathering algorithms that evolve in a Euclidean continuous space. • We show that positive results obtained for the model extend to the initial system model. • We model check all known mobile robot gathering algorithms and verify previous pen-and-paper results. • We obtain new insights about key system hypotheses about problem solvability. • We introduce weaker models of consistency (inspired by regular registers). • We derive a new algorithm that solves mobile robot gathering in such a model. [ABSTRACT FROM AUTHOR]

We consider the rendezvous problem of two autonomous robots with very weak capacities. This problem is notoriously impossible to solve in the semi-synchronous execution model when robots are deterministic, oblivious, and their ego-centered coordinate system is fully symmetric. We show that if the robots disagree on the unit distance of their coordinate system, it becomes possible to solve rendezvous and agree on a final common location, without additional assumptions. We also generalize our scheme to solve gathering (that is, rendezvous of n ≥ 2 robots) in the same setting, possibly starting from a bivalent configuration. • We introduce new techniques that take advantage of different unit distances. • We design and prove a solution to the rendezvous problem of oblivious and disoriented robots in SSYNC. • We generalize our design to solve gathering from any arbitrary initial configuration. [ABSTRACT FROM AUTHOR]

Abstract: Given a set of robots with arbitrary initial location and no agreement on a global coordinate system, convergence requires that all robots asymptotically approach the exact same, but unknown beforehand, location. Robots are oblivious–they do not recall the past computations–and are allowed to move in a one-dimensional space. Additionally, robots cannot communicate directly, instead they obtain system related information only via visual sensors. Even though convergence and the classical distributed approximate agreement problem (that requires correct processes to decide, for some constant , values distance apart and within the range of initial proposed values) are similar, we provide evidence that solving convergence in robot networks requires specific assumptions about synchrony and Byzantine resilience. In more detail, we prove necessary and sufficient conditions for the convergence of mobile robots despite a subset of them being Byzantine (i.e. they can exhibit arbitrary behavior). Additionally, we propose two deterministic convergence algorithms for robot networks and analyze their correctness and complexity in various atomicity and synchrony settings. The first algorithm tolerates Byzantine robots for -sized robot networks in fully synchronous ATOM networks, while the second proposed algorithm tolerates Byzantine robots for -sized robot networks in non-atomic CORDA networks. The resilience of these two algorithms is proved to be optimal. [Copyright &y& Elsevier]