抄録/ポイント:
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
本論文では,リングトポロジーにおける移動ロボットの部分収集問題を考察した。部分収集問題は,(坑井調査)全収集問題の一般化であり,ネットワーク中に分散するすべてのkロボットが,非事前決定単一ノードで終了することが必要である。部分収集問題は,与えられた正整数[数式:原文を参照]に対して,各ロボットがノードに移動し,停止するので,少なくともgロボット,あるいはロボットが任意のノードに存在しない。著者らは,いくつかのロボットが同一ノードを共有するかもしれない初期構成から匿名および不活発な移動ロボットに対する問題の可解性を考察した。アルゴリズムがそのような初期構成から問題を解決することができるならば,アルゴリズムは自己安定化と呼ばれる。さらに,部分収集問題に対する要求は,全収集問題に対する要求よりも弱いので,部分収集が(i)全収集に対するよりも弱いモデルで解決可能かどうか,および(ii)全収集に対するよりも厳密に小さい全数の移動において可解であるかどうかを明らかにすることを目的とした。最初に,確率的に自己安定化部分収集アルゴリズムが非同期(ASYNC)モデルに存在するか,あるいは局所-強と大域的-弱多重度検出が利用できるかを示した。驚くべきことに,これらの不可能性結果は総収集の場合と同じである。次に,半同期(SSYNC)と大域的強多重度検出モデル(即ち,解を可能にする最も弱いシステム仮定)において,決定論的および確率的アルゴリズムを考察した。決定論的事例では,まず,非可解な初期構成が存在し,次に,nがノード数である任意の可解な初期構成から動く問題を解くためのアルゴリズムを提案した。確率的事例では,O(gn)を用いた問題を解くためのアルゴリズムを提案して,任意の初期構成(即ち,アルゴリズムが確率的に自己安定化)から期待する。[数式:原文を参照]は保持され,部分(resp.,総)収集問題は[数式:原文を参照](resp.,[数式:原文を参照])移動を必要とする。その結果,提案アルゴリズムは,全収集に対するものより,厳密に小さな全数移動において部分収集を達成することを示した。Copyright Springer Nature Switzerland AG 2020 Translated from English into Japanese by JST.【JST・京大機械翻訳】