日本フィジカルAI新聞

世界のフィジカルAIを、日本語で。

群制御arXiv:1407.7279

動的環境における最優先地点巡回計画

DMVP: Foremost Waypoint Coverage of Time-Varying Graphs

シェア:XThreadsFacebookLINEはてブBluesky

時間変化するグラフ上で複数エージェントが重要地点を迅速に巡回する問題を定式化し、グラフクラスごとの計算困難性と近似可能性を解析した。

著者: Eric Aaron, Danny Krizanc, Elliot Meyerson

分類: cs.CC, cs.DS, cs.RO

原文アブストラクト

We consider the Dynamic Map Visitation Problem (DMVP), in which a team of agents must visit a collection of critical locations as quickly as possible, in an environment that may change rapidly and unpredictably during the agents' navigation. We apply recent formulations of time-varying graphs (TVGs) to DMVP, shedding new light on the computational hierarchy $\mathcal{R} \supset \mathcal{B} \supset \mathcal{P}$ of TVG classes by analyzing them in the context of graph navigation. We provide hardness results for all three classes, and for several restricted topologies, we show a separation between the classes by showing severe inapproximability in $\mathcal{R}$, limited approximability in $\mathcal{B}$, and tractability in $\mathcal{P}$. We also give topologies in which DMVP in $\mathcal{R}$ is fixed parameter tractable, which may serve as a first step toward fully characterizing the features that make DMVP difficult.

関連論文

  1. 1Boston Dynamics、車輪付きAtlasの研究試作機を紹介研究・技術
  2. 2newmoとKDDIが資本業務提携 2028年に堺市で自動運転タクシー商用化目指す提携・買収
  3. 3NVIDIA、CoRLでGR00T 2とIsaac Lab 3.0を発表新製品・発表
  4. 4GXOとApptronik、Apolloの物流現場試験を拡大 最大1,000台の展開を構想量産・展開
  5. 5UC BerkeleyとNVIDIAの研究者、AIエージェントでロボット制御コードを仮想環境で改善研究・技術

PR・アフィリエイト広告

FRONTIER(GPU搭載BTOパソコン)

FRONTIER(GPU搭載BTOパソコン)の公式広告バナーFRONTIERでGPU搭載PCを見る ↗
PR本紙発行元 EmplifAI