| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2020-05-09 17:26 On Memory, Communication, and Synchronous Schedulers for Autonomous Mobile Robots Paola Flocchini（UoO）・Nicola Santoro（CU）・○Koichi Wada（HU）  COMP2020-3 |
|
| 抄録 | （和） | 本稿では二次元平面上を$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 / / / / | |
| 文献情報 | 信学技報, vol. 120, no. 13, COMP2020-3, pp. 17-24, 2020年5月. | |
| 資料番号 | COMP2020-3 | |
| 発行日 | 2020-05-02 (COMP) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2020-3 |
|
| 研究会情報 | |
| 研究会 | COMP IPSJ-AL |
| 開催期間 | 2020-05-09 - 2020-05-09 |
| 開催地（和） | オンライン開催 |
| 開催地（英） | Online |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2020-05-COMP |
| 本文の言語 | 英語 |
| タイトル（和） | |
| サブタイトル（和） | |
| タイトル（英） | 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 |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | パオラ フロッチーニ / Paola Flocchini / |
| 第1著者 所属（和/英） | オタワ大学 (略称： オタワ大) University of Ottawa (略称： UoO) |
| 第2著者 氏名（和/英/ヨミ） | 二コラ サントロ / Nicola Santoro / |
| 第2著者 所属（和/英） | カールトン大学 (略称： カールトン大) Carleton University (略称： CU) |
| 第3著者 氏名（和/英/ヨミ） | 和田 幸一 / Koichi Wada / ワダ コウイチ |
| 第3著者 所属（和/英） | 法政大学 (略称： 法政大) Hosei University (略称： HU) |
| 第4著者 氏名（和/英/ヨミ） | / / |
| 第4著者 所属（和/英） | (略称： ) (略称： ) |
| 第5著者 氏名（和/英/ヨミ） | / / |
| 第5著者 所属（和/英） | (略称： ) (略称： ) |
| 第6著者 氏名（和/英/ヨミ） | / / |
| 第6著者 所属（和/英） | (略称： ) (略称： ) |
| 第7著者 氏名（和/英/ヨミ） | / / |
| 第7著者 所属（和/英） | (略称： ) (略称： ) |
| 第8著者 氏名（和/英/ヨミ） | / / |
| 第8著者 所属（和/英） | (略称： ) (略称： ) |
| 第9著者 氏名（和/英/ヨミ） | / / |
| 第9著者 所属（和/英） | (略称： ) (略称： ) |
| 第10著者 氏名（和/英/ヨミ） | / / |
| 第10著者 所属（和/英） | (略称： ) (略称： ) |
| 第11著者 氏名（和/英/ヨミ） | / / |
| 第11著者 所属（和/英） | (略称： ) (略称： ) |
| 第12著者 氏名（和/英/ヨミ） | / / |
| 第12著者 所属（和/英） | (略称： ) (略称： ) |
| 第13著者 氏名（和/英/ヨミ） | / / |
| 第13著者 所属（和/英） | (略称： ) (略称： ) |
| 第14著者 氏名（和/英/ヨミ） | / / |
| 第14著者 所属（和/英） | (略称： ) (略称： ) |
| 第15著者 氏名（和/英/ヨミ） | / / |
| 第15著者 所属（和/英） | (略称： ) (略称： ) |
| 第16著者 氏名（和/英/ヨミ） | / / |
| 第16著者 所属（和/英） | (略称： ) (略称： ) |
| 第17著者 氏名（和/英/ヨミ） | / / |
| 第17著者 所属（和/英） | (略称： ) (略称： ) |
| 第18著者 氏名（和/英/ヨミ） | / / |
| 第18著者 所属（和/英） | (略称： ) (略称： ) |
| 講演者 | 第3著者 |
| 発表日時 | 2020-05-09 17:26:00 |
| 発表時間 | 1分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2020-3 |
| 巻番号（vol） | vol.120 |
| 号番号（no） | no.13 |
| ページ範囲 | pp.17-24 |
| ページ数 | 8 |
| 発行日 | 2020-05-02 (COMP) |
[研究会発表申込システムのトップページに戻る]