| 講演名 | 2019-05-11 視界に制限のあるライト付きモバイルロボットによるリング探索 長濵 将太(奈良先端大), 大下 福仁(奈良先端大), 井上 美智子(奈良先端大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 本稿では，能力の低い自律モバイルロボットによるリング型グラフの探索アルゴリズムについて検討する．各ロボットは定数距離の範囲内のノードを観測することができ，定数個の色を持つライトを使って通信しながらリングを探索する．主な成果として，ノードを観測可能な距離が2以上の定数，ライトが2色という条件のもと，次の2点を証明する．(1)全てのロボットが全てのノードを無限回訪問する探索である永続探索を達成するには，2体のロボットが必要十分である．(2)各ノードを少なくとも1体のロボットが訪問したうえで全てのロボットが移動を終える探索である停止探索を達成するには，3体のロボットが必要十分である．これらの結果は，先行研究よりロボットが観測可能な距離を延ばすことで，探索に必要なロボット数を削減できることを示している．また，同じ条件のもと，提案したロボット2体での永続探索アルゴリズムが万能である，つまり，可解な初期状況のどれから探索を開始しても永続探索を達成することを示す．一方，停止探索に対しては，ロボット3体での万能なアルゴリズムが存在しないことを示す． |
| 抄録(英) | In this paper, we investigate ring exploration algorithms for autonomous mobile robots. The robots are myopic, that is, they observe nodes within a certain fixed distance, and luminous, that is, they have light devices that can emit a constant number of colors. We consider the constraint that the visible distance is any constant of at least two and the number of colors of lights is two. As a main contribution, we prove that 1) two robots are necessary and sufficient to achieve perpetual exploration, and 2) three robots are necessary and sufficient to achieve terminating exploration. These results show that the number of robots required for exploration can be reduced by extending their visibility compared to the previous work. We also show that the proposed perpetual exploration algorithm is universal, that is, the algorithm achieves perpetual exploration from any solvable initial configuration with two robots. On the other hand, we show that no universal algorithm exists for terminating exploration with three robots. |
| キーワード(和) | 自律モバイルロボット / 探索問題 / 離散的環境 |
| キーワード(英) | autonomous mobile robots / exploration problem / discrete environments |
| 資料番号 | COMP2019-7 |
| 発行日 | 2019-05-03 (COMP) |
| 研究会情報 | |
| 研究会 | COMP / IPSJ-AL |
|---|---|
| 開催期間 | 2019/5/10(から2日開催) |
| 開催地（和） | 熊本大学 |
| 開催地（英） | Kumamoto University |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | 藤戸 敏弘(豊橋技科大) / 瀧本 英二(九州大学) |
| 委員長氏名（英） | Toshihiro Fujito(Toyohashi Univ. of Tech.) / 瀧本 英二(九州大学) |
| 副委員長氏名（和） | 中野 眞一(群馬大) |
| 副委員長氏名（英） | Shinichi Nakano(Gunma Univ.) |
| 幹事氏名（和） | 玉置 卓(京大) / 大舘 陽太(熊本大) / 河村 彰星(九州大学) / 垣村 尚徳(慶應義塾大学) / 泉 泰介(名古屋工業大学) |
| 幹事氏名（英） | Suguru Tamaki(Kyoto Univ.) / Yota Otachi(Kumamoto Univ) / 河村 彰星(九州大学) / 垣村 尚徳(慶應義塾大学) / 泉 泰介(名古屋工業大学) |
| 幹事補佐氏名（和） | 脊戸 和寿(成蹊大) |
| 幹事補佐氏名（英） | Kazuhisa Seto(Seikei Univ.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Theoretical Foundations of Computing / Special Interest Group on Algorithms |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 視界に制限のあるライト付きモバイルロボットによるリング探索 |
| サブタイトル（和） | |
| タイトル（英） | Ring Exploration Algorithms for Myopic Luminous Robots with Larger Visibility |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 自律モバイルロボット / autonomous mobile robots |
| キーワード(2)（和/英） | 探索問題 / exploration problem |
| キーワード(3)（和/英） | 離散的環境 / discrete environments |
| 第 1 著者 氏名（和/英） | 長濵 将太 / Shota Nagahama |
| 第 1 著者 所属（和/英） | 奈良先端科学技術大学院大学(略称：奈良先端大) Nara Institute of Science and Technology(略称：NAIST) |
| 第 2 著者 氏名（和/英） | 大下 福仁 / Fukuhito Ooshita |
| 第 2 著者 所属（和/英） | 奈良先端科学技術大学院大学(略称：奈良先端大) Nara Institute of Science and Technology(略称：NAIST) |
| 第 3 著者 氏名（和/英） | 井上 美智子 / Michiko Inoue |
| 第 3 著者 所属（和/英） | 奈良先端科学技術大学院大学(略称：奈良先端大) Nara Institute of Science and Technology(略称：NAIST) |
| 発表年月日 | 2019-05-11 |
| 資料番号 | COMP2019-7 |
| 巻番号（vol） | vol.119 |
| 号番号（no） | COMP-21 |
| ページ範囲 | pp.83-90(COMP), |
| ページ数 | 8 |
| 発行日 | 2019-05-03 (COMP) |