11 Search Results for "Yamashita, Masafumi"


Document
Deterministic Self-Stabilising Leader Election for Programmable Matter with Constant Memory

Authors: Jérémie Chalopin, Shantanu Das, and Maria Kokkou

Published in: LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024)


Abstract
The problem of electing a unique leader is central to all distributed systems, including programmable matter systems where particles have constant size memory. In this paper, we present a silent self-stabilising, deterministic, stationary, election algorithm for particles having constant memory, assuming that the system is simply connected. Our algorithm is elegant and simple, and requires constant memory per particle. We prove that our algorithm always stabilises to a configuration with a unique leader, under a daemon satisfying some fairness guarantees (Gouda fairness [Mohamed G. Gouda, 2001]). We use the special geometric properties of programmable matter in 2D triangular grids to obtain the first self-stabilising algorithm for such systems. This result is surprising since it is known that silent self-stabilising algorithms for election in general distributed networks require Ω(log n) bits of memory per node, even for ring topologies [Shlomi Dolev et al., 1999].

Cite as

Jérémie Chalopin, Shantanu Das, and Maria Kokkou. Deterministic Self-Stabilising Leader Election for Programmable Matter with Constant Memory. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{chalopin_et_al:LIPIcs.DISC.2024.13,
  author =	{Chalopin, J\'{e}r\'{e}mie and Das, Shantanu and Kokkou, Maria},
  title =	{{Deterministic Self-Stabilising Leader Election for Programmable Matter with Constant Memory}},
  booktitle =	{38th International Symposium on Distributed Computing (DISC 2024)},
  pages =	{13:1--13:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-352-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{319},
  editor =	{Alistarh, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.13},
  URN =		{urn:nbn:de:0030-drops-212395},
  doi =		{10.4230/LIPIcs.DISC.2024.13},
  annote =	{Keywords: Leader Election, Programmable Matter, Self-Stabilisation, Silent, Deterministic, Unique Leader, Simply Connected, Gouda fair Daemon, Constant Memory}
}
Document
Brief Announcement
Brief Announcement: Optimal Uniform Circle Formation by Asynchronous Luminous Robots

Authors: Caterina Feletti, Debasish Pattanayak, and Gokarna Sharma

Published in: LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024)


Abstract
We study the Uniform Circle Formation (UCF) problem for a swarm of n autonomous mobile robots operating in Look-Compute-Move (LCM) cycles on the Euclidean plane. We assume our robots are luminous, i.e. equipped with a persistent light that can assume a color chosen from a fixed palette, and opaque, i.e. not able to see beyond a collinear robot. Robots are said to collide if they share positions or their paths intersect within concurrent LCM cycles. To solve UCF, a swarm of n robots must autonomously arrange themselves so that each robot occupies a vertex of the same regular n-gon not fixed in advance. In terms of efficiency, the goal is to design an algorithm that optimizes (or provides a tradeoff between) two fundamental performance metrics: (i) the execution time and (ii) the size of the color palette. In this paper, we develop a deterministic algorithm solving UCF avoiding collisions in O(1)-time with O(1) colors under the asynchronous scheduler, which is asymptotically optimal with respect to both time and number of colors used, the first such result. Furthermore, the algorithm proposed here minimizes for the first time what we call the computational SEC, i.e. the smallest circular area where robots operate throughout the whole algorithm.

Cite as

Caterina Feletti, Debasish Pattanayak, and Gokarna Sharma. Brief Announcement: Optimal Uniform Circle Formation by Asynchronous Luminous Robots. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 46:1-46:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{feletti_et_al:LIPIcs.DISC.2024.46,
  author =	{Feletti, Caterina and Pattanayak, Debasish and Sharma, Gokarna},
  title =	{{Brief Announcement: Optimal Uniform Circle Formation by Asynchronous Luminous Robots}},
  booktitle =	{38th International Symposium on Distributed Computing (DISC 2024)},
  pages =	{46:1--46:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-352-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{319},
  editor =	{Alistarh, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.46},
  URN =		{urn:nbn:de:0030-drops-212748},
  doi =		{10.4230/LIPIcs.DISC.2024.46},
  annote =	{Keywords: Uniform Circle Formation, Robots with Lights, Autonomous Robots, Rank Encoding, Time and Color Complexities, Computational SEC}
}
Document
Brief Announcement
Brief Announcement: Distinct Gathering Under Round Robin

Authors: Fabian Frei and Koichi Wada

Published in: LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024)


Abstract
We resolve one of the longest-standing questions about autonomous mobile robots in a surprising way. Distinct Gathering is the fundamental cooperation task of letting robots, initially scattered across the plane in distinct locations, gather in an arbitrary single point. The scheduler Round Robin cyclically activates the robots one by one in a fixed order. When activated, a robot perceives all robot locations and moves wherever it wants based only on this information. For n = 2 robots, the task is trivial. What happens for n ≥ 3 has remained an open problem for decades by now. The established conjecture declares the task to be impossible in this case. We prove that it is indeed impossible for n = 3 but, to great surprise, possible again for any n ≥ 4. We go beyond the standard requirements by providing a very robust algorithm that does not require any consistency or self-consistency for the local Cartesian maps perceived by the robots and works even for non-rigid movement, that is, if robots may be unpredictably stopped and deactivated during a movement.

Cite as

Fabian Frei and Koichi Wada. Brief Announcement: Distinct Gathering Under Round Robin. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 48:1-48:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{frei_et_al:LIPIcs.DISC.2024.48,
  author =	{Frei, Fabian and Wada, Koichi},
  title =	{{Brief Announcement: Distinct Gathering Under Round Robin}},
  booktitle =	{38th International Symposium on Distributed Computing (DISC 2024)},
  pages =	{48:1--48:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-352-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{319},
  editor =	{Alistarh, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.48},
  URN =		{urn:nbn:de:0030-drops-212768},
  doi =		{10.4230/LIPIcs.DISC.2024.48},
  annote =	{Keywords: Autonomous mobile robots, Distinct Gathering, Round Robin}
}
Document
Brief Announcement
Brief Announcement: Self-Stabilizing Graph Exploration by a Single Agent

Authors: Yuichi Sudo, Fukuhito Ooshita, and Sayaka Kamei

Published in: LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024)


Abstract
In this paper, we present two self-stabilizing algorithms that enable a single (mobile) agent to explore graphs. The agent visits all nodes starting from any configuration, i.e., regardless of the initial state of the agent, the initial states of all nodes, and the initial location of the agent. We evaluate the algorithms using two metrics: cover time, which is the number of moves required to visit all nodes, and memory usage, which includes the storage needed for the state of the agent and the state of each node. The first algorithm is randomized. Given an integer c = Ω(n), the cover time of this algorithm is optimal, i.e., O(m) in expectation, and the memory requirements for the agent and each node v are O(log c) and O(log (c+δ_v)) bits, respectively, where n and m are the numbers of nodes and edges, respectively, and δ_v is the degree of v. The second algorithm is deterministic. It requires an input integer k ≥ max(D,δ_max), where D and δ_max are the diameter and the maximum degree of the graph, respectively. The cover time of this algorithm is O(m + nD), and it uses O(log k) bits both for agent memory and each node.

Cite as

Yuichi Sudo, Fukuhito Ooshita, and Sayaka Kamei. Brief Announcement: Self-Stabilizing Graph Exploration by a Single Agent. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 55:1-55:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{sudo_et_al:LIPIcs.DISC.2024.55,
  author =	{Sudo, Yuichi and Ooshita, Fukuhito and Kamei, Sayaka},
  title =	{{Brief Announcement: Self-Stabilizing Graph Exploration by a Single Agent}},
  booktitle =	{38th International Symposium on Distributed Computing (DISC 2024)},
  pages =	{55:1--55:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-352-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{319},
  editor =	{Alistarh, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.55},
  URN =		{urn:nbn:de:0030-drops-212832},
  doi =		{10.4230/LIPIcs.DISC.2024.55},
  annote =	{Keywords: mobile agents, self-stabilization, graph exploration}
}
Document
The Recurrence/Transience of Random Walks on a Bounded Grid in an Increasing Dimension

Authors: Shuma Kumamoto, Shuji Kijima, and Tomoyuki Shirai

Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)


Abstract
It is celebrated that a simple random walk on ℤ and ℤ² returns to the initial vertex v infinitely many times during infinitely many transitions, which is said recurrent, while it returns to v only finite times on ℤ^d for d ≥ 3, which is said transient. It is also known that a simple random walk on a growing region on ℤ^d can be recurrent depending on growing speed for any fixed d. This paper shows that a simple random walk on {0,1,…,N}ⁿ with an increasing n and a fixed N can be recurrent depending on the increasing speed of n. Precisely, we are concerned with a specific model of a random walk on a growing graph (RWoGG) and show a phase transition between the recurrence and transience of the random walk regarding the growth speed of the graph. For the proof, we develop a pausing coupling argument introducing the notion of weakly less homesick as graph growing (weakly LHaGG).

Cite as

Shuma Kumamoto, Shuji Kijima, and Tomoyuki Shirai. The Recurrence/Transience of Random Walks on a Bounded Grid in an Increasing Dimension. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 22:1-22:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{kumamoto_et_al:LIPIcs.AofA.2024.22,
  author =	{Kumamoto, Shuma and Kijima, Shuji and Shirai, Tomoyuki},
  title =	{{The Recurrence/Transience of Random Walks on a Bounded Grid in an Increasing Dimension}},
  booktitle =	{35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)},
  pages =	{22:1--22:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-329-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{302},
  editor =	{Mailler, C\'{e}cile and Wild, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.22},
  URN =		{urn:nbn:de:0030-drops-204577},
  doi =		{10.4230/LIPIcs.AofA.2024.22},
  annote =	{Keywords: Random walk, dynamic graph, recurrence, transience, coupling}
}
Document
Engineering Weighted Connectivity Augmentation Algorithms

Authors: Marcelo Fonseca Faraj, Ernestine Großmann, Felix Joos, Thomas Möller, and Christian Schulz

Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)


Abstract
Increasing the connectivity of a graph is a pivotal challenge in robust network design. The weighted connectivity augmentation problem is a common version of the problem that takes link costs into consideration. The problem is then to find a minimum cost subset of a given set of weighted links that increases the connectivity of a graph by one when the links are added to the edge set of the input instance. In this work, we give a first implementation of recently discovered better-than-2 approximations. Furthermore, we propose three new heuristics and one exact approach. These include a greedy algorithm considering link costs and the number of unique cuts covered, an approach based on minimum spanning trees and a local search algorithm that may improve a given solution by swapping links of paths. Our exact approach uses an ILP formulation with efficient cut enumeration as well as a fast initialization routine. We then perform an extensive experimental evaluation which shows that our algorithms are faster and yield the best solutions compared to the current state-of-the-art as well as the recently discovered better-than-2 approximation algorithms. Our novel local search algorithm can improve solution quality even further.

Cite as

Marcelo Fonseca Faraj, Ernestine Großmann, Felix Joos, Thomas Möller, and Christian Schulz. Engineering Weighted Connectivity Augmentation Algorithms. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 11:1-11:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{faraj_et_al:LIPIcs.SEA.2024.11,
  author =	{Faraj, Marcelo Fonseca and Gro{\ss}mann, Ernestine and Joos, Felix and M\"{o}ller, Thomas and Schulz, Christian},
  title =	{{Engineering Weighted Connectivity Augmentation Algorithms}},
  booktitle =	{22nd International Symposium on Experimental Algorithms (SEA 2024)},
  pages =	{11:1--11:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-325-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{301},
  editor =	{Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.11},
  URN =		{urn:nbn:de:0030-drops-203768},
  doi =		{10.4230/LIPIcs.SEA.2024.11},
  annote =	{Keywords: weighted connectivity augmentation, approximation, heuristic, integer linear program, algorithm engineering}
}
Document
Forming Large Patterns with Local Robots in the OBLOT Model

Authors: Christopher Hahn, Jonas Harbig, and Peter Kling

Published in: LIPIcs, Volume 292, 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)


Abstract
In the arbitrary pattern formation problem, n autonomous, mobile robots must form an arbitrary pattern P ⊆ R². The (deterministic) robots are typically assumed to be indistinguishable, disoriented, and unable to communicate. An important distinction is whether robots have memory and/or a limited viewing range. Previous work managed to form P under a natural symmetry condition if robots have no memory but an unlimited viewing range [Masafumi Yamashita and Ichiro Suzuki, 2010] or if robots have a limited viewing range but memory [Yukiko Yamauchi and Masafumi Yamashita, 2013]. In the latter case, P is only formed in a shrunk version that has constant diameter. Without memory and with limited viewing range, forming arbitrary patterns remains an open problem. We provide a partial solution by showing that P can be formed under the same symmetry condition if the robots' initial diameter is ≤ 1. Our protocol partitions P into rotation-symmetric components and exploits the initial mutual visibility to form one cluster per component. Using a careful placement of the clusters and their robots, we show that a cluster can move in a coordinated way through its component while "drawing" P by dropping one robot per pattern coordinate.

Cite as

Christopher Hahn, Jonas Harbig, and Peter Kling. Forming Large Patterns with Local Robots in the OBLOT Model. In 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 292, pp. 14:1-14:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{hahn_et_al:LIPIcs.SAND.2024.14,
  author =	{Hahn, Christopher and Harbig, Jonas and Kling, Peter},
  title =	{{Forming Large Patterns with Local Robots in the OBLOT Model}},
  booktitle =	{3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)},
  pages =	{14:1--14:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-315-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{292},
  editor =	{Casteigts, Arnaud and Kuhn, Fabian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2024.14},
  URN =		{urn:nbn:de:0030-drops-198924},
  doi =		{10.4230/LIPIcs.SAND.2024.14},
  annote =	{Keywords: Swarm Algorithm, Swarm Robots, Distributed Algorithm, Pattern Formation, Limited Visibility, Oblivious}
}
Document
Oblivious Permutations on the Plane

Authors: Shantanu Das, Giuseppe A. Di Luna, Paola Flocchini, Nicola Santoro, Giovanni Viglietta, and Masafumi Yamashita

Published in: LIPIcs, Volume 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)


Abstract
We consider a distributed system of n identical mobile robots operating in the two dimensional Euclidian plane. As in the previous studies, we consider the robots to be anonymous, oblivious, dis-oriented, and without any communication capabilities, operating based on the Look-Compute-Move model where the next location of a robot depends only on its view of the current configuration. Even in this seemingly weak model, most formation problems which require constructing specific configurations, can be solved quite easily when the robots are fully synchronized with each other. In this paper we introduce and study a new class of problems which, unlike the studied formation problems, cannot always be solved even in the fully synchronous model with atomic and rigid moves. This class of problems requires the robots to permute their locations in the plane. In particular, we are interested in implementing two special types of permutations - permutations without any fixed points and permutations of order n. The former (called Move-All) requires each robot to visit at least two of the initial locations, while the latter (called Visit-All) requires every robot to visit each of the initial locations in a periodic manner. We provide a characterization of the solvability of these problems, showing the main challenges in solving this class of problems for mobile robots. We also provide algorithms for the feasible cases, in particular distinguishing between one-step algorithms (where each configuration must be a permutation of the original configuration) and multi-step algorithms (which allow intermediate configurations). These results open a new research direction in mobile distributed robotics which has not been investigated before.

Cite as

Shantanu Das, Giuseppe A. Di Luna, Paola Flocchini, Nicola Santoro, Giovanni Viglietta, and Masafumi Yamashita. Oblivious Permutations on the Plane. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 24:1-24:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{das_et_al:LIPIcs.OPODIS.2019.24,
  author =	{Das, Shantanu and Di Luna, Giuseppe A. and Flocchini, Paola and Santoro, Nicola and Viglietta, Giovanni and Yamashita, Masafumi},
  title =	{{Oblivious Permutations on the Plane}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{24:1--24:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-133-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{153},
  editor =	{Felber, Pascal and Friedman, Roy and Gilbert, Seth and Miller, Avery},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2019.24},
  URN =		{urn:nbn:de:0030-drops-118103},
  doi =		{10.4230/LIPIcs.OPODIS.2019.24},
  annote =	{Keywords: Distributed Algorithms, Mobile Robots, Fully synchronous, Oblivious, Permutations, Chirality, Sequence of configurations}
}
Document
Gathering and Election by Mobile Robots in a Continuous Cycle

Authors: Paola Flocchini, Ryan Killick, Evangelos Kranakis, Nicola Santoro, and Masafumi Yamashita

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)


Abstract
Consider a set of n mobile computational entities, called robots, located and operating on a continuous cycle C (e.g., the perimeter of a closed region of R^2) of arbitrary length l. The robots are identical, can only see their current location, have no location awareness, and cannot communicate at a distance. In this weak setting, we study the classical problems of gathering (GATHER), requiring all robots to meet at a same location; and election (ELECT), requiring all robots to agree on a single one as the "leader". We investigate how to solve the problems depending on the amount of knowledge (exact, upper bound, none) the robots have about their number n and about the length of the cycle l. Cost of the algorithms is analyzed with respect to time and number of random bits. We establish a variety of new results specific to the continuous cycle - a geometric domain never explored before for GATHER and ELECT in a mobile robot setting; compare Monte Carlo and Las Vegas algorithms; and obtain several optimal bounds.

Cite as

Paola Flocchini, Ryan Killick, Evangelos Kranakis, Nicola Santoro, and Masafumi Yamashita. Gathering and Election by Mobile Robots in a Continuous Cycle. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 8:1-8:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{flocchini_et_al:LIPIcs.ISAAC.2019.8,
  author =	{Flocchini, Paola and Killick, Ryan and Kranakis, Evangelos and Santoro, Nicola and Yamashita, Masafumi},
  title =	{{Gathering and Election by Mobile Robots in a Continuous Cycle}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{8:1--8:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.8},
  URN =		{urn:nbn:de:0030-drops-115044},
  doi =		{10.4230/LIPIcs.ISAAC.2019.8},
  annote =	{Keywords: Cycle, Election, Gathering, Las Vegas, Monte Carlo, Randomized Algorithm}
}
Document
Plane Formation by Synchronous Mobile Robots without Chirality

Authors: Yusaku Tomita, Yukiko Yamauchi, Shuji Kijima, and Masafumi Yamashita

Published in: LIPIcs, Volume 95, 21st International Conference on Principles of Distributed Systems (OPODIS 2017)


Abstract
We consider a distributed system consisting of autonomous mobile computing entities called robots moving in the three-dimensional space (3D-space). The robots are anonymous, oblivious, fully-synchronous and have neither any access to the global coordinate system nor any explicit communication medium. Each robot cooperates with other robots by observing the positions of other robots in its local coordinate system. One of the most fundamental agreement problems in 3D-space is the plane formation problem that requires the robots to land on a common plane, that is not predefined. This problem is not always solvable because of the impossibility of symmetry breaking. While existing results assume that the robots agree on the handedness of their local coordinate systems, we remove the assumption and consider the robots without chirality. The robots without chirality can never break the symmetry consisting of rotation symmetry and reflection symmetry. Such symmetry in 3D-space is fully described by 17 symmetry types each of which forms a group. We extend the notion of symmetricity [Suzuki and Yamashita, SIAM J. Compt. 1999] [Yamauchi et al., PODC 2016] to cover these 17 symmetry groups. Then we give a characterization of initial configurations from which the fully-synchronous robots without chirality can form a plane in terms of symmetricity.

Cite as

Yusaku Tomita, Yukiko Yamauchi, Shuji Kijima, and Masafumi Yamashita. Plane Formation by Synchronous Mobile Robots without Chirality. In 21st International Conference on Principles of Distributed Systems (OPODIS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 95, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{tomita_et_al:LIPIcs.OPODIS.2017.13,
  author =	{Tomita, Yusaku and Yamauchi, Yukiko and Kijima, Shuji and Yamashita, Masafumi},
  title =	{{Plane Formation by Synchronous Mobile Robots without Chirality}},
  booktitle =	{21st International Conference on Principles of Distributed Systems (OPODIS 2017)},
  pages =	{13:1--13:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-061-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{95},
  editor =	{Aspnes, James and Bessani, Alysson and Felber, Pascal and Leit\~{a}o, Jo\~{a}o},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2017.13},
  URN =		{urn:nbn:de:0030-drops-86337},
  doi =		{10.4230/LIPIcs.OPODIS.2017.13},
  annote =	{Keywords: Autonomous mobile robots, plane formation problem, symmetry breaking, group theory}
}
Document
Meeting in a Polygon by Anonymous Oblivious Robots

Authors: Giuseppe A. Di Luna, Paola Flocchini, Nicola Santoro, Giovanni Viglietta, and Masafumi Yamashita

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)


Abstract
The Meeting problem for k>=2 searchers in a polygon P (possibly with holes) consists in making the searchers move within P, according to a distributed algorithm, in such a way that at least two of them eventually come to see each other, regardless of their initial positions. The polygon is initially unknown to the searchers, and its edges obstruct both movement and vision. Depending on the shape of P, we minimize the number of searchers k for which the Meeting problem is solvable. Specifically, if P has a rotational symmetry of order sigma (where sigma=1 corresponds to no rotational symmetry), we prove that k=sigma+1 searchers are sufficient, and the bound is tight. Furthermore, we give an improved algorithm that optimally solves the Meeting problem with k=2 searchers in all polygons whose barycenter is not in a hole (which includes the polygons with no holes). Our algorithms can be implemented in a variety of standard models of mobile robots operating in Look-Compute-Move cycles. For instance, if the searchers have memory but are anonymous, asynchronous, and have no agreement on a coordinate system or a notion of clockwise direction, then our algorithms work even if the initial memory contents of the searchers are arbitrary and possibly misleading. Moreover, oblivious searchers can execute our algorithms as well, encoding information by carefully positioning themselves within the polygon. This code is computable with basic arithmetic operations (provided that the coordinates of the polygon's vertices are algebraic real numbers in some global coordinate system), and each searcher can geometrically construct its own destination point at each cycle using only a compass. We stress that such memoryless searchers may be located anywhere in the polygon when the execution begins, and hence the information they initially encode is arbitrary. Our algorithms use a self-stabilizing map construction subroutine which is of independent interest.

Cite as

Giuseppe A. Di Luna, Paola Flocchini, Nicola Santoro, Giovanni Viglietta, and Masafumi Yamashita. Meeting in a Polygon by Anonymous Oblivious Robots. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 14:1-14:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{diluna_et_al:LIPIcs.DISC.2017.14,
  author =	{Di Luna, Giuseppe A. and Flocchini, Paola and Santoro, Nicola and Viglietta, Giovanni and Yamashita, Masafumi},
  title =	{{Meeting in a Polygon by Anonymous Oblivious Robots}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{14:1--14:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.14},
  URN =		{urn:nbn:de:0030-drops-79833},
  doi =		{10.4230/LIPIcs.DISC.2017.14},
  annote =	{Keywords: Meeting problem, Oblivious robots, Polygon, Self-stabilization}
}
  • Refine by Author
  • 4 Yamashita, Masafumi
  • 3 Flocchini, Paola
  • 3 Santoro, Nicola
  • 2 Das, Shantanu
  • 2 Di Luna, Giuseppe A.
  • Show More...

  • Refine by Classification
  • 4 Theory of computation → Distributed algorithms
  • 1 Computer systems organization → Fault-tolerant network topologies
  • 1 Computer systems organization → Robotic autonomy
  • 1 Computer systems organization → Robotics
  • 1 Computing methodologies → Self-organization
  • Show More...

  • Refine by Keyword
  • 2 Autonomous mobile robots
  • 2 Oblivious
  • 1 Autonomous Robots
  • 1 Chirality
  • 1 Computational SEC
  • Show More...

  • Refine by Type
  • 11 document

  • Refine by Publication Year
  • 7 2024
  • 1 2017
  • 1 2018
  • 1 2019
  • 1 2020

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail