Fugu-MT 論文翻訳(概要): Bidirectional Temporal Plan Graph: Enabling Switchable Passing Orders for More Efficient Multi-Agent Path Finding Plan Execution

論文の概要: Bidirectional Temporal Plan Graph: Enabling Switchable Passing Orders for More Efficient Multi-Agent Path Finding Plan Execution

arxiv url: http://arxiv.org/abs/2401.00315v2
Date: Sun, 7 Jan 2024 01:23:49 GMT
ステータス: 処理完了
システム内更新日: 2024-01-09 21:37:29.424252
Title: Bidirectional Temporal Plan Graph: Enabling Switchable Passing Orders for More Efficient Multi-Agent Path Finding Plan Execution
Title（参考訳）: bidirectional temporal plan graph: より効率的なマルチエージェントパス発見計画実行のための切り替え可能なパスオーダの実現
Authors: Yifan Su, Rishi Veerapaneni, Jiaoyang Li
Abstract要約: BTPG(Bidirectional Temporal Plan Graph)と呼ばれる新しいグラフィカルな表現を導入し,実行中の注文を切り替えることで,不要な待ち時間を回避する。実験の結果, BTPG は TPG に順調に優れ, 不要待ち時間が 8-20% 減少することがわかった。
参考スコア（独自算出の注目度）: 7.2988406091449605
License: http://creativecommons.org/licenses/by/4.0/
Abstract: The Multi-Agent Path Finding (MAPF) problem involves planning collision-free paths for multiple agents in a shared environment. The majority of MAPF solvers rely on the assumption that an agent can arrive at a specific location at a specific timestep. However, real-world execution uncertainties can cause agents to deviate from this assumption, leading to collisions and deadlocks. Prior research solves this problem by having agents follow a Temporal Plan Graph (TPG), enforcing a consistent passing order at every location as defined in the MAPF plan. However, we show that TPGs are overly strict because, in some circumstances, satisfying the passing order requires agents to wait unnecessarily, leading to longer execution time. To overcome this issue, we introduce a new graphical representation called a Bidirectional Temporal Plan Graph (BTPG), which allows switching passing orders during execution to avoid unnecessary waiting time. We design two anytime algorithms for constructing a BTPG: BTPG-na\"ive and BTPG-optimized. Experimental results show that following BTPGs consistently outperforms following TPGs, reducing unnecessary waits by 8-20%.
Abstract（参考訳）: マルチエージェントパス探索(mapf)問題は、共有環境で複数のエージェントの衝突のない経路を計画することである。 MAPFソルバの大多数は、エージェントが特定のタイミングで特定の場所に到着できるという仮定に依存している。しかし、現実の実行の不確実性はエージェントをこの仮定から逸脱させ、衝突やデッドロックを引き起こす可能性がある。先行研究は、エージェントが時間計画グラフ(tpg)に従い、mapfプランで定義されたすべての場所で一貫した通過順序を強制することでこの問題を解決する。しかし,tpgが過度に厳しいのは,ある状況ではパス順序を満たすためにはエージェントが不必要に待つ必要があるため,実行時間が長くなるためである。この問題を克服するために,双方向時間計画グラフ(bidirectional temporal plan graph, btpg)と呼ばれる新しいグラフィカル表現を導入する。 BTPGを最適化したBTPG-na\iveとBTPG-optimizedの2つのアルゴリズムを設計する。実験の結果, BTPG は TPG に順調に優れ, 不要待ち時間が 8-20% 減少することがわかった。

関連論文リスト

AlphaZeroES: Direct score maximization outperforms planning loss minimization [61.17702187957206]
実行時の計画では、シングルエージェントとマルチエージェントの両方の設定でエージェントのパフォーマンスが劇的に向上することが示されている。実行時に計画するアプローチのファミリは、AlphaZeroとその変種で、Monte Carlo Tree Searchと、状態値とアクション確率を予測することによって検索をガイドするニューラルネットワークを使用する。複数の環境にまたがって、エピソードスコアを直接最大化し、計画損失を最小限に抑えることを示す。
論文参考訳（メタデータ） (2024-06-12T23:00:59Z)
Decentralized Monte Carlo Tree Search for Partially Observable Multi-agent Pathfinding [49.730902939565986]
マルチエージェントパスフィンディング問題は、グラフに閉じ込められたエージェントのグループに対するコンフリクトフリーパスのセットを見つけることである。本研究では、エージェントが他のエージェントをローカルにのみ観察できる分散MAPF設定に焦点を当てた。 MAPFタスクのための分散マルチエージェントモンテカルロ木探索法を提案する。
論文参考訳（メタデータ） (2023-12-26T06:57:22Z)
Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
マルチエージェントパスフィンディングに適したモンテカルロ木探索(MCTS)のオリジナル版を紹介する。具体的には,エージェントの目標達成行動を支援するために,個別の経路を用いる。また,木探索手順の分岐係数を低減するために,専用の分解手法を用いる。
論文参考訳（メタデータ） (2023-07-25T12:33:53Z)
Robust Multi-Agent Pickup and Delivery with Delays [5.287544737925232]
MAPD(Multi-Agent Pickup and Delivery)は、エージェント群に対する衝突のない経路の計算の問題である。 MAPDの現在のアルゴリズムは、実際のアプリケーションで遭遇する現実的な問題の多くを考慮していない。本稿では,不完全な実行の影響を抑える計画経路によって堅牢性を保証する2つの手法を提案する。
論文参考訳（メタデータ） (2023-03-30T14:42:41Z)
GoRela: Go Relative for Viewpoint-Invariant Motion Forecasting [121.42898228997538]
精度や一般化を犠牲にすることなく、全てのエージェントとマップに対して効率的な共有符号化を提案する。不均一空間グラフにおけるエージェントとマップ要素間の幾何学的関係を表現するために、ペアワイズ相対的な位置符号化を利用する。我々のデコーダは視点非依存であり、レーングラフ上でエージェント目標を予測し、多様かつコンテキスト対応のマルチモーダル予測を可能にする。
論文参考訳（メタデータ） (2022-11-04T16:10:50Z)
Optimal Multi-Agent Path Finding for Precedence Constrained Planning Tasks [0.7742297876120561]
我々は,PC-MAPF (Precedence Constrained Multi-Agent Path Finding) 問題の拡張について検討する。そこで我々は,PC-CBS (Precedence Constrained Conflict Based Search) という新しいアルゴリズムを提案する。本アルゴリズムは, 各種倉庫集合体, マルチエージェントピックアップ, 配送タスクに対して性能をベンチマークし, 最近提案された効率的なベースラインのサブ最適性を評価する。
論文参考訳（メタデータ） (2022-02-08T07:26:45Z)
Symmetry Breaking for k-Robust Multi-Agent Path Finding [30.645303869311366]
k-Robust Conflict-BasedSearch (k-CBS)は、最大k遅延のロバストな座標と衝突のない計画を生成するアルゴリズムです。そこで我々は,k-robust計画に特有な様々な対称性の破れ制約を導入し,矛盾するエージェントのペアに対して,効率よく相反する最適経路を見つける。
論文参考訳（メタデータ） (2021-02-17T11:09:33Z)
A Feedback Scheme to Reorder a Multi-Agent Execution Schedule by Persistently Optimizing a Switchable Action Dependency Graph [65.70656676650391]
複数の自動誘導車両 (AGV) が共通作業空間をナビゲートし, 様々な作業を行う。一つのアプローチは、Action Dependency Graph (ADG)を構築し、そのルートに沿って進むとAGVの順序を符号化する。ワークスペースが人間やサードパーティロボットのような動的障害によって共有されている場合、AGVは大きな遅延を経験することができる。本稿では,各AGVの経路完了時間を最小限に抑えるために,非循環ADGを繰り返し修正するオンライン手法を提案する。
論文参考訳（メタデータ） (2020-10-11T14:39:50Z)
Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints [52.58352707495122]
本稿では,不確実性およびマルチエージェント協調の下での逐次意思決定における重要な計算課題を分離するマルチロボット割当アルゴリズムを提案する。都市におけるマルチアームコンベヤベルトピック・アンド・プレイスとマルチドローン配送ディスパッチの2つの異なる領域における広範囲なシミュレーション結果について検証を行った。
論文参考訳（メタデータ） (2020-05-27T01:10:41Z)
Optimized Directed Roadmap Graph for Multi-Agent Path Finding Using Stochastic Gradient Descent [33.31762612175859]
我々はODRM(Optimized Directed Roadmap Graph)と呼ばれる新しいアプローチを提案する。 ODRMは、マルチロボットナビゲーションにおける衝突回避を可能にする有向ロードマップグラフを構築する方法である。実験の結果,単純な集中型プランナさえあれば,他のマルチエージェントプランナでは解決できない,多数のエージェントで解決できることがわかった。
論文参考訳（メタデータ） (2020-03-29T02:18:31Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。