| 講演名 | 2020-05-09 On Memory, Communication, and Synchronous Schedulers for Autonomous Mobile Robots パオラ フロッチーニ(オタワ大), 二コラ サントロ(カールトン大), 和田 幸一(法政大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 本稿では二次元平面上を$LCM(Look$-$Compute$-$Move)$-サイクルで動作する自律分散ロボット群の計算能力を議論する．特にロボットの持つメモリとロボット間の直接通信の能力に焦点を当てる．最も一般的なモデルである$OB$は，メモリを持たず直接通信を許さないロボット群からなる．一方，$LU$モデルは，ロボットはライトと呼ばれる定数サイズのメモリをもち，すべてのロボットがそのライトの色を見ることができる．すなわち，$LU$ロボットは各サイクルにおいて，メモリを記憶でき，メモリによって通信可能となる．$LU$ロボットは$OB$ロボットよりも計算能力は高いので，問題はメモリの記憶能力と直接通信能力のどちらが計算能力が高いかである．本稿では，この問題に対して$LU$の2つの部分クラス$FS$と$FC$を考える．$FS$ロボットは定数サイズのメモリを持つが，通信不可である．一方，$FC$は定数ビットの通信能力をもつが，その結果は次のサイクルまで記憶できない．これら4つのロボットモデルとロボット間の同期における計算能力に対する完全解を与える．その中で特に，完全同期(FSY)においては，メモリよりも直接通信が計算能力が真に高く，半同期(SSY)においては，計算能力に関して比較不能であることがわかった． |
| 抄録(英) | We investigate the computational power of distributed systems whose autonomous computational entities, called robots, move and operate in the 2-dimensional Euclidean plane in synchronous $mathit{Look}$-$mathit{Compute}$-$mathit{Move}$ ($mathit{LCM}$) %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, $OB$, the robots are oblivious (no persistent memory) and silent (no explicit means of communication). In contrast, in the $LU$ model, each robot is equipped with a constant-sized persistent memory (called {em 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 $LU$: $FS$ where the robots have a constant-size persistent memory but are silent; and $FC$, 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 FSY, while they are incomparable under the semi-synchronous scheduler SSY. |
| キーワード(和) | LCMサイクル / 無記憶ロボット / ライト付きロボット / メモリ対通信 |
| キーワード(英) | Look-Compute-Move / Oblivious mobile robots / Robots with lights / Memory versus Communication |
| 資料番号 | COMP2020-3 |
| 発行日 | 2020-05-02 (COMP) |
| 研究会情報 | |
| 研究会 | COMP / IPSJ-AL |
|---|---|
| 開催期間 | 2020/5/9(から1日開催) |
| 開催地（和） | 国立情報学研究所 |
| 開催地（英） | National Institute of Informatics |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | 藤戸 敏弘(豊橋技科大) |
| 委員長氏名（英） | Toshihiro Fujito(Toyohashi Univ. of Tech.) |
| 副委員長氏名（和） | 中野 眞一(群馬大) |
| 副委員長氏名（英） | Shinichi Nakano(Gunma Univ.) |
| 幹事氏名（和） | 大舘 陽太(名大) / 玉置 卓(兵庫県立大) |
| 幹事氏名（英） | Yota Otachi(Nagoya Univ) / Suguru Tamaki(Univ. of Hyogo) |
| 幹事補佐氏名（和） | 脊戸 和寿(成蹊大) |
| 幹事補佐氏名（英） | Kazuhisa Seto(Seikei Univ.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Theoretical Foundations of Computing / Special Interest Group on Algorithms |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | |
| サブタイトル（和） | |
| タイトル（英） | On Memory, Communication, and Synchronous Schedulers for Autonomous Mobile Robots |
| サブタイトル（和） | |
| キーワード(1)（和/英） | LCMサイクル / Look-Compute-Move |
| キーワード(2)（和/英） | 無記憶ロボット / Oblivious mobile robots |
| キーワード(3)（和/英） | ライト付きロボット / Robots with lights |
| キーワード(4)（和/英） | メモリ対通信 / Memory versus Communication |
| 第 1 著者 氏名（和/英） | パオラ フロッチーニ / Paola Flocchini |
| 第 1 著者 所属（和/英） | オタワ大学(略称：オタワ大) University of Ottawa(略称：UoO) |
| 第 2 著者 氏名（和/英） | 二コラ サントロ / Nicola Santoro |
| 第 2 著者 所属（和/英） | カールトン大学(略称：カールトン大) Carleton University(略称：CU) |
| 第 3 著者 氏名（和/英） | 和田 幸一 / Koichi Wada |
| 第 3 著者 所属（和/英） | 法政大学(略称：法政大) Hosei University(略称：HU) |
| 発表年月日 | 2020-05-09 |
| 資料番号 | COMP2020-3 |
| 巻番号（vol） | vol.120 |
| 号番号（no） | COMP-13 |
| ページ範囲 | pp.17-24(COMP), |
| ページ数 | 8 |
| 発行日 | 2020-05-02 (COMP) |