地図を持つエージェントの平均的に高速なランデブーアルゴリズム

• Item type: SIG Technical Reports(1)
• 公開日: 2019-11-21
• タイトル: 地図を持つエージェントの平均的に高速なランデブーアルゴリズム
• タイトル / 言語: en
• タイトル: Average Fast Rendezvous Algorithm for Agents with Maps
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 名古屋工業大学大学院工学研究科
• 著者所属: 名古屋工業大学大学院工学研究科
• 著者所属: 名古屋工業大学大学院工学研究科
• 著者名: 柿澤, 一輝; 北村, 直暉; 泉, 泰介
• 著者名(英): Kazuki, Kakizawa; Naoki, Kitamura; Taisuke, Izumi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: n 頂点から構成される頂点ラベル付き連結無向グラフと，その上を移動する複数のエージェントから成る系を考える．ランデブー問題とは，異なる頂点に配置された 2 体以上のエージェントを，単一の頂点上に集合させる問題である．本研究では同期システムにおける，地図を持つ 2 体のエージェントによるランデブー問題を考える．このシステムにおいて，各エージェントは事前に地図と呼ばれるグラフ全体のトポロジ情報を把握しており，その中における自身の初期位置についても知識を持つものとするが，他方のエージェントの初期位置は知らないものとする．各ラウンドでエージェントは，現在滞在している頂点に留まるか，接続辺を辿って隣接頂点へ移動するという動作を行う．グラフにおける 2 エージェントの初期位置間の距離をdとすると，Ω(d) ラウンドがランデブーアルゴリズムの自明な下界となる．本研究では，2 エージェントの初期位置が距離 d 以下のすべての頂点対から一様ランダムに選ばれるとしたとき，平均 O(d logloglog n log n) ラウンドでランデブーを達成するアルゴリズムを提案する．
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2019-AL-175, 号 24, p. 1-7, 発行日 2019-11-21
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会