論文の概要: 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% 減少することがわかった。

関連論文リスト

• Plan-over-Graph: Towards Parallelable LLM Agent Schedule [53.834646147919436]
  大規模言語モデル(LLM)はタスク計画の推論において例外的な能力を示した。 本稿では,まず実生活のテキストタスクを実行可能なサブタスクに分解し,抽象的なタスクグラフを構築する,新しいパラダイムであるプランオーバーグラフを提案する。 モデルはこのタスクグラフを入力として理解し、並列実行計画を生成する。
  論文  参考訳（メタデータ） (2025-02-20T13:47:51Z)
• Hindsight Planner: A Closed-Loop Few-Shot Planner for Embodied Instruction Following [62.10809033451526]
  本研究は,Large Language Models (LLM) を用いた Embodied Instruction following (EIF) タスクプランナの構築に焦点をあてる。 我々は,このタスクを部分観測可能なマルコフ決定プロセス (POMDP) として構成し,数発の仮定で頑健なプランナーの開発を目指す。 ALFREDデータセットに対する我々の実験は、プランナーが数ショットの仮定で競争性能を達成することを示す。
  論文  参考訳（メタデータ） (2024-12-27T10:05:45Z)
• Speedup Techniques for Switchable Temporal Plan Graph Optimization [7.478072166004144]
  MAPF (Multi-Agent Path Finding) は、複数エージェントの衝突のない経路を計画することに焦点を当てている。 MAPF計画の実行中、エージェントは予期せぬ遅延に遭遇し、非効率性、デッドロック、さらには衝突に至る可能性がある。 本稿では,グラフベーススイッチブルエッジサーチ(GSES)を4つの高速化手法により大幅に高速化する改良GSESを提案する。
  論文  参考訳（メタデータ） (2024-12-20T13:59:15Z)
• Loosely Synchronized Rule-Based Planning for Multi-Agent Path Finding with Asynchronous Actions [5.5233853454863615]
  MAPF(Multi-Agent Path Finding)は、各開始地点から各目標地点まで、複数のエージェントの衝突のない経路を求める。 多くのMAPFアルゴリズムは数千のエージェントを処理できるが、エージェントの各アクションが時間単位を必要とするという仮定に依存している。 本稿では,新たなプランナを開発し,スケーラビリティのためのソリューション品質をトレードオフする。
  論文  参考訳（メタデータ） (2024-12-16T11:36:24Z)
• 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)
• 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)

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

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