2024-03-29T06:50:33Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:002045302023-04-27T10:00:04Z01164:02592:10084:10210
On Memory, Communication, and Synchronous Schedulers for Autonomous Mobile Robots自律分散ロボット群に対してメモリ,通信及びスケジュールが及ぼす影響についてenghttp://id.nii.ac.jp/1001/00204435/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=204530&item_no=1&attribute_id=1&file_no=1Copyright (c) 2020 by the Institute of Electronics, Information and Communication Engineers This SIG report is only available to those in membership of the SIG.オタワ大学カールトン大学法政大学パオラ, フロッチーニニコラ, サントロ和田, 幸一本稿では二次元平面上を LCM (Look-Compute-Move)-サイクルで動作する自律分散ロボット群の計算能力を趨胞する.特にロボットの持つメモリとロボット間の直接通信の能力に無点を当てる.最も一般的なモデルである OBLOT は,メモリを持たず面接通僧を許さないロボット群である.一方,LUMI モデルは,ロボットはライトと呼ばれる定数サイズのメモリをもち,すべてのロボットがそのライトの色を見ることができる.すなわち,LUMI ロボットは各サイクルにおいて,メモリを記憶でき,メモリによって通信可能となる.LUMI ロボットは OBLOT ロボットよりも計算能力は高いので,問題はメモリの記憧能力と直接通信能力のどちらが計算能力が高いかである.本稿では,この問題に対して LUMI の 2 つの部分クラス FSTA と FCOM を考える.FSTA ロボットは定数サイズのメモリを持つが,通信不可である.一方,FCOM は定数ピットの通信能力をもつが,その結果は次のサイクルまで記憧できない.これら 4 つのロボットモデルとロボット間の同期における計算能力に対する完全解を与える.その中で特に,完全同期 (FSYNCH) においては,メモリよりも直接通信の計算能力が真に高く,半同期 (SSYNCH)においては,計算能力に関して比較不能であることがわかった.We investigate the computational power of distributed systems whose autonomous computational entities, called robots, move and operatein the 2-dimensional Euclidean plane in synchronous Look-Compute-Move (LCM) cycles. Specifically, we focus on the power of persistent memory and that of explicit communication, and on their computational relationship. In the most common model, OBLOT, the robots are oblivious (no persistent memory) and silent (no explicit means of communication). In contrast,in the LUMI model, each robot is equipped with a constant-sized persistent memory (called light), visible to all the robots; hence, these luminous robots are capable in each cycle of both remembering and communicating. Since luminous robots are computationally more powerful than the standard oblivious one, immediate important questions are about the individual computational power of persistent memory and of explicit communication. In particular, which of the two capabilities, memory or communication, is more important? in other words, is it better to remember or to communicate ? In this paper we address these questions, focusing on two sub-models of LUMI : FSTA where the robots have a constant-size persistent memory but are silent ; and FCOM, where robots can communicate a constant number of bits but are oblivious. We analyze the relationship among all these models and provide a complete exhaustive map of their computational relationship. Among other things, we prove that communication is more powerful than persistent memory under the fully synchronous scheduler FSYNCH, while they are incomparable under the semi-synchronous scheduler SSYNCH.AN1009593X研究報告アルゴリズム(AL)2020-AL-17810182020-05-022188-85662020-04-30