視界に制限のあるライト付きモバイルロボットによるリング探索

• Item type: SIG Technical Reports(1)
• 公開日: 2019-05-03
• タイトル: 視界に制限のあるライト付きモバイルロボットによるリング探索
• タイトル / 言語: en
• タイトル: Ring Exploration Algorithms for Myopic Luminous Robots with Larger Visibility
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 奈良先端科学技術大学院大学
• 著者所属: 奈良先端科学技術大学院大学
• 著者所属: 奈良先端科学技術大学院大学
• 著者所属(英): en
• 著者所属(英): Nara Institute of Science and Technology
• 著者所属(英): en
• 著者所属(英): Nara Institute of Science and Technology
• 著者所属(英): en
• 著者所属(英): Nara Institute of Science and Technology
• 著者名: 長濵, 将太; 大下, 福仁; 井上, 美智子
• 著者名(英): Shota, Nagahama; Fukuhito, Ooshita; Michiko, Inoue
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本稿では，能力の低い自律モバイルロボットによるリング型グラフの探索アルゴリズムについて検討する．各ロボットは定数距離の範囲内のノードを観測することができ，定数個の色を持つライトを使って通信しながらリングを探索する．主な成果として，ノードを観測可能な距離が 2 以上の定数，ライトが 2色という条件のもと，次の 2点を証明する．（1) 全てのロボットが全てのノードを無限回訪問する探索である永続探索を達成するには，2体のロボットが必要十分である．(2) 各ノードを少なくとも 1体のロボットが訪問したうえで全てのロボットが移動を終える探索である停止探索を達成するには，3体のロボットが必要十分である．これらの結果は，先行研究よりロボットが観測可能な距離を延ばすことで，探索に必要なロボット数を削減できることを示している．また，同じ条件のもと，提案したロボット 2体での永続探索アルゴリズムが万能である，つまり，可解な初期状況のどれから探索を開始しても永続探索を達成することを示す．一方，停止探索に対しては，ロボット 3体での万能なアルゴリズムが存在しないことを示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2019-AL-173, 号 13, p. 1-8, 発行日 2019-05-03
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会