抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
マルチエージェント経路発見(MAPF)の計算複雑性を研究した。グラフGとエージェントのセットを与えられた場合,各スタートとターゲット頂点を持ち,目標は全距離移動を最小化する衝突フリー経路を見つけることである。問題の困難さの源をより良く理解するために,著者らは,それがハードのままである最も簡単で最小の制約付きグラフクラスを研究することを狙った。この目的のために,Gを2Dグリッドに制限し,それは,よく構造化された環境(例えば倉庫)のモデリングを便利に可能にするので,ユビキタス抽象である。以前の硬さ結果は,エージェントによって1つの頂点のみを持つ高度に制約された2D格子を考慮し,一方,多重空頂点が(非格子)平面グラフに対して許容される最も制限された硬度結果であった。したがって,2Dグリッドと多重空頂点の両方を同時に考慮することにより,以前の結果を精密化した。この場合でさえ,距離最適MAPFはNP困難であるが,これはBanfiら(2017)がもたらす未解決問題を沈降することを示している。簡単なガットを用いた3-SATからの直接還元を示し,正結果に対する潜在的進歩に関して,以前の研究よりも,著者らの証明をより有益にする。さらに,この減少は,Gが平面で,最初の関連結果後にほぼ40年現れる場合の最初の線形のものである。これにより,この問題の走行時間に対する指数関数的下限を得るために,さらにステップを前進させ,指数的時間仮説(ETH)を利用した。最後に,著者らの主な結果に向けたステッピング石として,著者らは,エージェントが中間の停止なしで1つずつ移動する単調ケースのNP-硬度を証明した。【JST・京大機械翻訳】
