論文の概要: WinkTPG: An Execution Framework for Multi-Agent Path Finding Using Temporal Reasoning
- arxiv url: http://arxiv.org/abs/2508.01495v1
- Date: Sat, 02 Aug 2025 21:33:08 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-08-05 18:25:21.904441
- Title: WinkTPG: An Execution Framework for Multi-Agent Path Finding Using Temporal Reasoning
- Title（参考訳）: WinkTPG:テンポラル推論を用いたマルチエージェントパス探索のための実行フレームワーク
- Authors: Jingtian Yan, Stephen F. Smith, Jiaoyang Li,
- Abstract要約: エージェントの大規模なグループに対する衝突のない経路の計画は、多くの現実世界のアプリケーションにおいて難しい問題である。
我々は,MAPFプランをキノダイナミックに実現可能なプランに効率的に洗練するマルチエージェント速度最適化アルゴリズムである,キノダイナミック時空間グラフ計画(kTPG)を提案する。
kTPGをベースとしたMAPF実行フレームワークであるWindowed kTPG(WinkTPG)を提案する。
- 参考スコア（独自算出の注目度）: 7.2069924323665235
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Planning collision-free paths for a large group of agents is a challenging problem with numerous real-world applications. While recent advances in Multi-Agent Path Finding (MAPF) have shown promising progress, standard MAPF algorithms rely on simplified kinodynamic models, preventing agents from directly following the generated MAPF plan. To bridge this gap, we propose kinodynamic Temporal Plan Graph Planning (kTPG), a multi-agent speed optimization algorithm that efficiently refines a MAPF plan into a kinodynamically feasible plan while accounting for uncertainties and preserving collision-freeness. Building on kTPG, we propose Windowed kTPG (WinkTPG), a MAPF execution framework that incrementally refines MAPF plans using a window-based mechanism, dynamically incorporating agent information during execution to reduce uncertainty. Experiments show that WinkTPG can generate speed profiles for up to 1,000 agents in 1 second and improves solution quality by up to 51.7% over existing MAPF execution methods.
- Abstract（参考訳）: エージェントの大規模なグループに対する衝突のない経路の計画は、多くの現実世界のアプリケーションにおいて難しい問題である。
MAPF(Multi-Agent Path Finding)の最近の進歩は有望な進歩を示しているが、標準的なMAPFアルゴリズムは単純化されたキノダイナミクスモデルに依存しており、エージェントが生成されたMAPF計画に直接従わない。
このギャップを埋めるため,キノダイナミック・テンポラル・プラン・グラフ・プランニング(kTPG)を提案する。
kTPG 上に構築した Windowed kTPG (WinkTPG) は,ウィンドウベース機構を用いてMAPF プランを漸進的に洗練し,実行中にエージェント情報を動的に組み込んで不確実性を低減する MAPF 実行フレームワークである。
実験の結果、WinkTPGは1秒で最大1000のエージェントの速度プロファイルを生成でき、既存のMAPF実行方法よりも51.7%高いソリューション品質を向上できることがわかった。
関連論文リスト
- Budget Allocation Policies for Real-Time Multi-Agent Path Finding [11.050047263054985]
リアルタイムMAPFは、計画と実行がインターリーブされる現実的なMAPFセットアップを具現化する。
RT-MAPFの既存のソリューションは、計画期間毎にMAPFアルゴリズムのウィンドウバージョンを反復的に呼び出す。
標準MAPFアルゴリズムのウィンドウ化バージョンにおける計画予算の配分について検討する。
論文 参考訳（メタデータ） (2025-07-22T08:32:55Z) - Advancing Learnable Multi-Agent Pathfinding Solvers with Active Fine-Tuning [46.35418789518417]
マルチエージェントパスフィンディング(MAPF)は、マルチロボット軌道計画問題の共通の抽象化である。
本稿では,機械学習を活用した分散化サブ最適化MAPFソルバMAPF-GPT-DDGを紹介する。
本実験は,MAPF-GPT-DDGが既存の学習型MAPF解法を超えることを示した。
論文 参考訳（メタデータ） (2025-06-30T12:34:31Z) - PGPO: Enhancing Agent Reasoning via Pseudocode-style Planning Guided Preference Optimization [58.465778756331574]
本稿では,効果的なエージェント学習のためのPGPOと呼ばれる疑似コード型計画優先最適化手法を提案する。
2つの計画指向の報酬により、PGPOは、高品質なPコードプランを生成するLLMエージェントの能力をさらに強化する。
実験により、PGPOは代表エージェントベンチマークよりも優れた性能を示し、現在のリードベースラインより優れていることが示された。
論文 参考訳（メタデータ） (2025-06-02T09:35:07Z) - Speedup Techniques for Switchable Temporal Plan Graph Optimization [7.478072166004144]
MAPF (Multi-Agent Path Finding) は、複数エージェントの衝突のない経路を計画することに焦点を当てている。
MAPF計画の実行中、エージェントは予期せぬ遅延に遭遇し、非効率性、デッドロック、さらには衝突に至る可能性がある。
本稿では,グラフベーススイッチブルエッジサーチ(GSES)を4つの高速化手法により大幅に高速化する改良GSESを提案する。
論文 参考訳（メタデータ） (2024-12-20T13:59:15Z) - Transient Multi-Agent Path Finding for Lifelong Navigation in Dense Environments [9.000023855628958]
ライフロングMAPF(英: Lifelong MAPF、LMAPF)は、エージェントが現在のターゲットに到達すると新たなターゲットを受信するMAPFのオンライン版である。
そこで本研究では,LMAPF問題に対して,各エージェントが最終的にターゲットを訪問することを目的とした修正MAPF問題の系列を解くことで,LMAPF問題を解くことを提案する。
本稿では、このMAPF変種をTransient MAPF (TMAPF) と呼び、既存のMAPFアルゴリズムに基づいたいくつかのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-12-05T15:37:29Z) - Scalable Mechanism Design for Multi-Agent Path Finding [87.40027406028425]
MAPF (Multi-Agent Path Finding) は、複数のエージェントが同時に移動し、与えられた目標地点に向かって共有領域を通って衝突しない経路を決定する。
最適解を見つけることは、しばしば計算不可能であり、近似的な準最適アルゴリズムを用いることが不可欠である。
本稿では、MAPFのスケーラブルな機構設計の問題を紹介し、MAPFアルゴリズムを近似した3つの戦略防御機構を提案する。
論文 参考訳（メタデータ） (2024-01-30T14:26:04Z) - Bidirectional Temporal Plan Graph: Enabling Switchable Passing Orders
for More Efficient Multi-Agent Path Finding Plan Execution [7.2988406091449605]
BTPG(Bidirectional Temporal Plan Graph)と呼ばれる新しいグラフィカルな表現を導入し,実行中の注文を切り替えることで,不要な待ち時間を回避する。
実験の結果, BTPG は TPG に順調に優れ, 不要待ち時間が 8-20% 減少することがわかった。
論文 参考訳（メタデータ） (2023-12-30T20:23:27Z) - Decentralized Monte Carlo Tree Search for Partially Observable
Multi-agent Pathfinding [49.730902939565986]
マルチエージェントパスフィンディング問題は、グラフに閉じ込められたエージェントのグループに対するコンフリクトフリーパスのセットを見つけることである。
本研究では、エージェントが他のエージェントをローカルにのみ観察できる分散MAPF設定に焦点を当てた。
MAPFタスクのための分散マルチエージェントモンテカルロ木探索法を提案する。
論文 参考訳（メタデータ） (2023-12-26T06:57:22Z) - Robust Multi-Agent Pickup and Delivery with Delays [5.287544737925232]
MAPD(Multi-Agent Pickup and Delivery)は、エージェント群に対する衝突のない経路の計算の問題である。
MAPDの現在のアルゴリズムは、実際のアプリケーションで遭遇する現実的な問題の多くを考慮していない。
本稿では,不完全な実行の影響を抑える計画経路によって堅牢性を保証する2つの手法を提案する。
論文 参考訳（メタデータ） (2023-03-30T14:42:41Z) - Collaborative Intelligent Reflecting Surface Networks with Multi-Agent
Reinforcement Learning [63.83425382922157]
インテリジェント・リフレクション・サーフェス(IRS)は将来の無線ネットワークに広く応用されることが想定されている。
本稿では,エネルギー収穫能力を備えた協調型IRSデバイスを用いたマルチユーザ通信システムについて検討する。
論文 参考訳（メタデータ） (2022-03-26T20:37:14Z) - Covert Model Poisoning Against Federated Learning: Algorithm Design and
Optimization [76.51980153902774]
フェデレーテッド・ラーニング(FL)はパラメータ伝達中にFLモデルに対する外部攻撃に対して脆弱である。
本稿では,最先端の防御アグリゲーション機構に対処する有効なMPアルゴリズムを提案する。
実験の結果,提案したCMPアルゴリズムは,既存の攻撃機構よりも効果的で,かなり優れていることが示された。
論文 参考訳（メタデータ） (2021-01-28T03:28:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。