日本フィジカルAI新聞

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

経路計画arXiv:2102.05733

単一アクセス通路グラフ上の経路計画の高速化

Speeding up Routing Schedules on Aisle-Graphs with Single Access

シェア:XThreadsFacebookLINEはてブBluesky

片側からしかアクセスできない通路グラフ(畑や倉庫)で、限られたバッテリー内で報酬を最大化する経路計画問題に対し、最適アルゴリズムと高速な近似アルゴリズムを提案した。

著者: Francesco Betti Sorbelli, Stefano Carpin, Federico Coro, Sajal K. Das, Alfredo Navarra, Cristina M. Pinotti

分類: cs.RO, cs.DS

原文アブストラクト

In this paper, we study the Orienteering Aisle-graphs Single-access Problem (OASP), a variant of the orienteering problem for a robot moving in a so-called single-access aisle-graph, i.e., a graph consisting of a set of rows that can be accessed from one side only. Aisle-graphs model, among others, vineyards or warehouses. Each aisle-graph vertex is associated with a reward that a robot obtains when visits the vertex itself. As the robot's energy is limited, only a subset of vertices can be visited with a fully charged battery. The objective is to maximize the total reward collected by the robot with a battery charge. We first propose an optimal algorithm that solves OASP in O(m^2 n^2) time for aisle-graphs with a single access consisting of m rows, each with n vertices. With the goal of designing faster solutions, we propose four greedy sub-optimal algorithms that run in at most O(mn (m+n)) time. For two of them, we guarantee an approximation ratio of 1/2(1-1/e), where e is the base of the natural logarithm, on the total reward by exploiting the well-known submodularity property. Experimentally, we show that these algorithms collect more than 80% of the optimal reward.

関連論文

  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・アフィリエイト広告

MINISFORUM(ミニPC)

MINISFORUM(ミニPC)の公式広告バナーMINISFORUM公式ストアを見る ↗
PR本紙発行元 EmplifAI