日本フィジカルAI新聞

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

群制御arXiv:2408.09028

競合ベース探索の完全性について:時間的相対的重複枝刈り

On the Completeness of Conflict-Based Search: Temporally-Relative Duplicate Pruning

シェア:XThreadsFacebookLINEはてブBluesky

マルチエージェント経路探索のCBSが解なし問題で停止しない欠陥を、重複状態の検出・除去により解決するTRDPを提案。

著者: Thayne T Walker, Nathan R Sturtevant

分類: cs.AI, cs.RO

原文アブストラクト

Conflict-Based Search (CBS) algorithm for the multi-agent pathfinding (MAPF) problem is that it is incomplete for problems which have no solution; if no mitigating procedure is run in parallel, CBS will run forever when given an unsolvable problem instance. In this work, we introduce Temporally-Relative Duplicate Pruning (TRDP), a technique for duplicate detection and removal in both classic and continuous-time MAPF domains. TRDP is a simple procedure which closes the long-standing theoretic loophole of incompleteness for CBS by detecting and avoiding the expansion of duplicate states. TRDP is shown both theoretically and empirically to ensure termination without a significant impact on runtime in the majority of problem instances. In certain cases, TRDP is shown to increase performance significantly

関連論文

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

PR・アフィリエイト広告

FRONTIER(GPU搭載BTOパソコン)

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