非同期スケジューラ下のグリッド平面上における自律移動発光ロボットの完全可視化アルゴリズム
Complete Visibility Algorithm for Autonomous Mobile Luminous Robots under an Asynchronous Scheduler on Grid Plane
無限グリッド上に配置された不透明な発光ロボット群が、非同期動作かつ総数未知の状況でも2色のみを用いて全ロボットが互いに見える完全可視状態へ移動するアルゴリズムを提案した。
著者: Yonghwan Kim, Yoshiaki Katayama, Koichi Wada
分類: cs.DC, cs.RO
原文アブストラクト
An autonomous mobile robot system is a distributed system consisting of mobile computational entities (called robots) that autonomously and repeatedly perform three operations: Look, Compute, and Move. Various problems related to autonomous mobile robots, such as gathering, pattern formation, or flocking, have been extensively studied to understand the relationship between each robot's capabilities and the solvability of these problems. In this study, we focus on the complete visibility problem, which involves relocating all the robots on an infinite grid plane such that each robot is visible to every other robot. We assume that each robot is a luminous robot (i.e., has a light with a constant number of colors) and opaque (not transparent). In this paper, we propose an algorithm to achieve complete visibility when a set of robots is given. The algorithm ensures that complete visibility is achieved even when robots operate asynchronously and have no knowledge of the total number of robots on the grid plane using only two colors.
