日本フィジカルAI新聞

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

群制御arXiv:2212.12724

最短経路基準によるボトルネックタスク割り当ての認証

Certification of Bottleneck Task Assignment with Shortest Path Criteria

シェア:XThreadsFacebookLINEはてブBluesky

障害物環境での多ロボットの目標割り当てにおいて、最短経路の不確かさが十分小さくなったときに最適性を保証する認証アルゴリズムを提案し、サンプリングベース経路計画で上下界を求める多項式時間手法を示した。

著者: Tony A. Wood, Maryam Kamgarpour

分類: cs.RO, cs.SY, eess.SY, math.OC

原文アブストラクト

Minimising the longest travel distance for a group of mobile robots with interchangeable goals requires knowledge of the shortest length paths between all robots and goal destinations. Determining the exact length of the shortest paths in an environment with obstacles is NP-hard however. In this paper, we investigate when polynomial-time approximations of the shortest path search are sufficient to determine the optimal assignment of robots to goals. In particular, we propose an algorithm in which the accuracy of the path planning is iteratively increased. The approach provides a certificate when the uncertainties on estimates of the shortest paths become small enough to guarantee the optimality of the goal assignment. To this end, we apply results from assignment sensitivity assuming upper and lower bounds on the length of the shortest paths. We then provide polynomial-time methods to find such bounds by applying sampling-based path planning. The upper bounds are given by feasible paths, the lower bounds are obtained by expanding the sample set and leveraging the knowledge of the sample dispersion. We demonstrate the application of the proposed method with a multi-robot path-planning case study.

関連論文

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

PR・アフィリエイト広告

MINISFORUM(ミニPC)

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