Search Results

Documents authored by Katayama, Yoshiaki

Document
DOI: 10.4230/LIPIcs.OPODIS.2022.14
Gathering of Mobile Robots with Defected Views

Authors: Yonghwan Kim, Masahiro Shibata, Yuichi Sudo, Junya Nakamura, Yoshiaki Katayama, and Toshimitsu Masuzawa

Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)

Abstract
An autonomous mobile robot system consisting of many mobile computational entities (called robots) attracts much attention of researchers, and it is an emerging issue for a recent couple of decades to clarify the relation between the capabilities of robots and solvability of the problems. Generally, each robot can observe all other robots as long as there are no restrictions on visibility range or obstructions, regardless of the number of robots. In this paper, we provide a new perspective on the observation by robots; a robot cannot necessarily observe all other robots regardless of distances to them. We call this new computational model the defected view model. Under this model, in this paper, we consider the gathering problem that requires all the robots to gather at the same non-predetermined point and propose two algorithms to solve the gathering problem in the adversarial (N,N-2)-defected model for N ≥ 5 (where each robot observes at most N-2 robots chosen adversarially) and the distance-based (4,2)-defected model (where each robot observes at most two robots closest to itself), respectively, where N is the number of robots. Moreover, we present an impossibility result showing that there is no (deterministic) gathering algorithm in the adversarial or distance-based (3,1)-defected model, and we also show an impossibility result for the gathering in a relaxed (N, N-2)-defected model.
Cite as

Yonghwan Kim, Masahiro Shibata, Yuichi Sudo, Junya Nakamura, Yoshiaki Katayama, and Toshimitsu Masuzawa. Gathering of Mobile Robots with Defected Views. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 14:1-14:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{kim_et_al:LIPIcs.OPODIS.2022.14,
  author =	{Kim, Yonghwan and Shibata, Masahiro and Sudo, Yuichi and Nakamura, Junya and Katayama, Yoshiaki and Masuzawa, Toshimitsu},
  title =	{{Gathering of Mobile Robots with Defected Views}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{14:1--14:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-265-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{253},
  editor =	{Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.14},
  URN =		{urn:nbn:de:0030-drops-176349},
  doi =		{10.4230/LIPIcs.OPODIS.2022.14},
  annote =	{Keywords: mobile robot, gathering, defected view model}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2022.46
Brief Announcement: Gathering Despite Defected View

Authors: Yonghwan Kim, Masahiro Shibata, Yuichi Sudo, Junya Nakamura, Yoshiaki Katayama, and Toshimitsu Masuzawa

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract
In this paper, we provide a new perspective on the observation by robots; a robot cannot necessarily observe all other robots regardless of distances to them. We introduce a new computational model with defected views called a (N,k)-defected model where k robots among N-1 other robots can be observed. We propose two gathering algorithms: one in the adversarial (N,N-2)-defected model for N ≥ 5 (where N is the number of robots) and the other in the distance-based (4,2)-defected model. Moreover, we present two impossibility results for a (3,1)-defected model and a relaxed (N, N-2)-defected model respectively. This announcement is short; the full paper is available at [Yonghwan Kim and others, 2022].
Cite as

Yonghwan Kim, Masahiro Shibata, Yuichi Sudo, Junya Nakamura, Yoshiaki Katayama, and Toshimitsu Masuzawa. Brief Announcement: Gathering Despite Defected View. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 46:1-46:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kim_et_al:LIPIcs.DISC.2022.46,
  author =	{Kim, Yonghwan and Shibata, Masahiro and Sudo, Yuichi and Nakamura, Junya and Katayama, Yoshiaki and Masuzawa, Toshimitsu},
  title =	{{Brief Announcement: Gathering Despite Defected View}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{46:1--46:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.46},
  URN =		{urn:nbn:de:0030-drops-172377},
  doi =		{10.4230/LIPIcs.DISC.2022.46},
  annote =	{Keywords: mobile robot, gathering, defected view model}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2019.43
Brief Announcement: Neighborhood Mutual Remainder and Its Self-Stabilizing Implementation of Look-Compute-Move Robots

Authors: Shlomi Dolev, Sayaka Kamei, Yoshiaki Katayama, Fukuhito Ooshita, and Koichi Wada

Published in: LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019)

Abstract
In this paper, we define a new concept neighborhood mutual remainder (NMR). An NMR distributed algorithms should satisfy global fairness, l-exclusion and repeated local rendezvous requirements. We give a simple self-stabilizing algorithm to demonstrate the design paradigm to achieve NMR, and also present applications of NMR to a Look-Compute-Move robot system.
Cite as

Shlomi Dolev, Sayaka Kamei, Yoshiaki Katayama, Fukuhito Ooshita, and Koichi Wada. Brief Announcement: Neighborhood Mutual Remainder and Its Self-Stabilizing Implementation of Look-Compute-Move Robots. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 43:1-43:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{dolev_et_al:LIPIcs.DISC.2019.43,
  author =	{Dolev, Shlomi and Kamei, Sayaka and Katayama, Yoshiaki and Ooshita, Fukuhito and Wada, Koichi},
  title =	{{Brief Announcement: Neighborhood Mutual Remainder and Its Self-Stabilizing Implementation of Look-Compute-Move Robots}},
  booktitle =	{33rd International Symposium on Distributed Computing (DISC 2019)},
  pages =	{43:1--43:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-126-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{146},
  editor =	{Suomela, Jukka},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.43},
  URN =		{urn:nbn:de:0030-drops-113504},
  doi =		{10.4230/LIPIcs.DISC.2019.43},
  annote =	{Keywords: neighborhood mutual remainder, self-stabilization, LCM robot}
}
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact