1,720,984 research outputs found
The geodesic mutual visibility problem: Oblivious robots on grids and trees
Full text linkThe MUTUAL VISIBILITY is a well-known problem in the context of mobile robots. For a set of n robots disposed in the Euclidean plane, it asks for moving the robots without collisions so as to achieve a placement ensuring that no three robots are collinear. For robots moving on graphs, we consider the GEODESIC MUTUAL VISIBILITY (GMV) problem. Robots move along the edges of the graph, without collisions, so as to occupy some vertices that guarantee they become pairwise geodesic mutually visible. This means that there is a shortest path (i.e., a “geodesic”) between each pair of robots along which no other robots reside. We study this problem in the context of trees and (finite or infinite) square grids, for robots operating under the standard Look–Compute–Move model. In both scenarios, we provide resolution algorithms along with formal correctness proofs, highlighting the most relevant peculiarities arising within the different contexts, while optimizing the time complexity
Molecular pattern formation on grids in the MOBLOT model
Full text linkIn the theoretical studies on distributed algorithms for swarm robotics, the complexity and capabilities of the robots are usually reduced to their minimum. Recently, the MOBLOT model has been introduced in order to deal with robots considered silent, anonymous, and oblivious but capable to aggregate into more complex structures, called molecules. We study the case where robots move along a graph based on a square lattice and we formally define the Molecular Pattern Formation (MPF) problem, where a specific configuration of robots assembled into molecules must be reached. As a preliminary general result, we provide a necessary condition for its solvability. Then, we actually show that dealing with molecules can resolve in some cases the symmetry breaking issue on grids where otherwise robots cannot. Finally, we introduce an interesting case study, representative of the MPF problem, in which the molecules can be formed by the set of the seven tetrominoes (aka Tetris blocks). We provide a complete characterization of this specific problem, providing a distributed algorithm able to form a molecular pattern whenever the necessary condition for the solvability of MPF is verified
MOBLOT: Molecular oblivious robots
No full textIn swarm robotics, research mainly follows a theoretical approach that considers robot systems in the abstract, where the complexity and capabilities of the underlying model are often reduced to their minimum. One general and well-investigated model is OBLOT, where the robots are silent, anonymous, and oblivious. In this work, we introduce MOBLOT, a model that extends OBLOT to address a larger spectrum of cases. MOBLOT stands for molecular oblivious robots: like atoms combine themselves to form molecules, in MOBLOT simple robots can move to form more complex computational units, having an extent and different capabilities with respect to robots; like molecules combine themselves to form the matter, in MOBLOT the complex structures can exploit their own capabilities to arrange themselves to form any shape defining an acceptable final structure. In MOBLOT, we formally define the Matter Formation (MF) problem and, as a preliminary general result, we provide a necessary condition for its solvability which relies on symmetricity. Informally, the symmetricity of a configuration measures the amount of symmetries of the robots' disposal. We actually show how dealing with molecules can resolve in some cases the symmetry breaking issue where OBLOT cannot. Finally, we provide a case study for MOBLOT, that is, a representative MF problem along with a resolution distributed algorithm
Arbitrary pattern formation on infinite regular tessellation graphs
No full textGiven a set R of robots, each one located at a different vertex of an infinite regular tessellation graph, we aim to explore the Arbitrary Pattern Formation (APF) problem. Given a multiset F of grid vertices such that |R|=|F|, APF asks for a distributed algorithm that moves robots so as to reach a configuration similar to F. Similarity means that robots must be disposed as F regardless of translations, rotations, reflections. So far, as possible graph discretizing the Euclidean plane only the standard square grid has been considered in the context of the classical OBLOT model. However, it is natural to consider also the other regular tessellation graphs, that are triangular and hexagonal grids. In particular, the former can be considered as the most general in terms of possible symmetries and trajectories. We provide a resolution algorithm for APF when the initial configuration is asymmetric and the considered topology is any regular tessellation graph. The algorithm and its correctness are based on a rigorous methodology
Molecular Oblivious Robots: A New Model for Robots With Assembling Capabilities
Full text linkResearch in theoretical swarm robotics focuses on models that assign to robots a minimal set of capabilities. One of the models well investigated is certainly OBLOT , addressing the case of distributed robots that are, anonymous, without means of communication, and oblivious. Here we propose MOBLOT , an extension of OBLOT that allows to resolve a larger spectrum of cases. {MOBLOT stands for molecular oblivious robots: like atoms combine themselves to form molecules, in {MOBLOT simple robots can bond with each other in order to create possibly bigger computational units with more intrinsic capabilities with respect to robots (called molecules also in the model); like in nature, molecules can further bond to create more complex structures (e.g., the matter), the {MOBLOT version of molecules can exploit their own capabilities to accomplish new tasks or simply to arrange themselves to form any shape defined according to some compositional properties. In order to better understand the potentials of {MOBLOT , we introduce a new problem called matter formation (MF). We do provide a necessary condition for the solvability of MF, in general. This relies on the 'amount of symmetries' arising by the disposal of the robots. In practice, we show how molecules can break certain symmetries that cannot be broken in OBLOT. Finally, as a case study of {MOBLOT , we consider a representative problem derived from the general MF problem along with a distributed resolution algorithm and show its correctness
On the Approximability of Graph Visibility Problems
No full textVisibility problems have been investigated for a long time under different assumptions as they pose challenging combinatorial problems and are connected to robot navigation problems. The mutual-visibility problem in a graph G of n vertices asks to find the largest set of vertices X⊆V(G), also called μ-set, such that for any two vertices u,v∈X, there is a shortest u, v-path P where all internal vertices of P are not in X. This means that u and v are visible w.r.t. X. Variations of this problem are known as total, outer, and dual mutual-visibility problems, depending on the visibility property of vertices inside and/or outside X. The mutual-visibility problem and all its variations are known to be NP-complete on graphs of diameter 4. In this paper, we design a polynomial-time algorithm that finds a μ-set with size Ωn/D, where D is the average distance between any two vertices of G. Moreover, we show inapproximability results for all visibility problems on graphs of diameter 2 and strengthen the inapproximability ratios for graphs of diameter 3 or larger. More precisely, for graphs of diameter at least 3 and for every constant ε>0, we show that mutual-visibility and dual mutual-visibility problems are not approximable within a factor of n1/3-ε, while outer and total mutual-visibility problems are not approximable within a factor of n1/2-ε, unless P=NP. Furthermore, in the extended version of this paper we study the relationship between the mutual-visibility number and the general position number in which no three distinct vertices u, v, w of X belong to any shortest path of G
Molecular Robots with Chirality on Grids
No full textIn the theoretical studies on distributed algorithms for swarm robotics, the complexity and capabilities of the robots are usually reduced to their minimum. Recently, the MOBLOT model has been introduced in order to deal with robots considered silent, anonymous, and oblivious but capable to aggregate into more complex structures, called molecules. We study the case where robots move along a regular square grid and we formally define the Molecular Pattern Formation (MPF) problem where a specific configuration of robots assembled into molecules must be reached. As general result, we provide a necessary condition for its solvability. Then, we actually show that dealing with molecules can resolve in some cases the symmetry breaking issue on grids where otherwise robots cannot. Finally, we introduce and resolve an interesting case study, where molecules are given by tetrominos (aka Tetris blocks)
The Geodesic Mutual Visibility Problem for Oblivious Robots: the case of Trees
Full text linkThe Mutual Visibility is a well-known problem in the context of mobile robots. For a set of n robots disposed in the Euclidean plane, it asks for moving the robots without collisions so as to achieve a placement ensuring that no three robots are collinear. Here we introduce the Geodesic Mutual Visibility problem, a possible counterpart for robots moving in a discrete environment. For a set of robots disposed on the vertices of a graph, it asks for moving the robots so that they are pairwise geodesic mutually visible, that is there is a shortest path (i.e., a "geodesic") between each pair of robots along which no other robots reside. It is known that, for tree topologies, the maximum number of robots that can be disposed by respecting the geodesic mutual visibility equals the number of leaves. Given a tree T with (T) leaves, we consider n ≤ (T) identical, mobile and semi-synchronous robots disposed on n different vertices of T, and we study the problem to make the robots move so as to reach a configuration where the geodesic mutual visibility is achieved. We propose a distributed algorithm, along with its correctness, for configurations not admitting critical vertices. Intuitively, a vertex v is critical if two or more equivalent robots must pass through v in order to reach a leaf, hence potentially collide in v. Furthermore, we provide an extensive discussion about the implications as well as complications arising when admitting critical vertices and/or the synchronous or the asynchronous settings, along with impossibility results or possible strategies of resolution to investigate
- …
