日本フィジカルAI新聞

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

群制御arXiv:2502.09299

単一アクティブロボットによるタイル配置の効率的再構成

Efficient Reconfiguration of Tile Arrangements by a Single Active Robot

シェア:XThreadsFacebookLINEはてブBluesky

受動的なブロックを並べた2次元グリッド配置を、1台のアクティブロボットで開始配置から目標配置へ再構成する問題を扱い、重み付き移動コスト版のNP困難性を示すとともに、開始・目標の境界ボックスが互いに素な場合に多項式時間の定数近似アルゴリズムを提案した。

著者: Aaron T. Becker, Sándor P. Fekete, Jonas Friemel, Ramin Kosfeld, Peter Kramer, Harm Kube, Christian Rieck, Christian Scheffer, Arne Schmidt

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

原文アブストラクト

We consider the problem of reconfiguring a two-dimensional connected grid arrangement of passive building blocks from a start configuration to a goal configuration, using a single active robot that can move on the tiles, remove individual tiles from a given location and physically move them to a new position by walking on the remaining configuration. The objective is to determine a schedule that minimizes the overall makespan, while keeping the tile configuration connected. We provide both negative and positive results. (1) We generalize the problem by introducing weighted movement costs, which can vary depending on whether tiles are carried or not, and prove that this variant is NP-hard. (2) We give a polynomial-time constant-factor approximation algorithm for the case of disjoint start and target bounding boxes, which additionally yields optimal carry distance for 2-scaled instances.

関連論文

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

PR・アフィリエイト広告

OZ GAMING(GPU搭載BTOゲーミングPC)

OZ GAMING(GPU搭載BTOゲーミングPC)の公式広告バナーOZ GAMINGで完成品PCを見る ↗
PR本紙発行元 EmplifAI