論文の概要: Windowed MAPF with Completeness Guarantees
- arxiv url: http://arxiv.org/abs/2410.01798v1
- Date: Wed, 2 Oct 2024 17:55:46 GMT
- ステータス: 処理完了
- システム内更新日: 2024-11-04 15:14:33.708555
- Title: Windowed MAPF with Completeness Guarantees
- Title（参考訳）: 完全性保証付きウィンドウ付きMAPF
- Authors: Rishi Veerapaneni, Muhammad Suhail Saleem, Jiaoyang Li, Maxim Likhachev,
- Abstract要約: 完全性を実現するウインドウドMAPFのためのフレームワークWinC-MAPFを紹介する。
また,CBSに新たな変更を加えて,この枠組みを即時化するシングルステップCBS (SS-CBS) も開発した。
単一のステップとアップデートしか計画していないSS-CBSが、既存のウィンドウ化アプローチが失敗する難しいシナリオを効果的に解決できることを示す。
- 参考スコア（独自算出の注目度）: 23.16660963084037
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Traditional multi-agent path finding (MAPF) methods try to compute entire start-goal paths which are collision free. However, computing an entire path can take too long for MAPF systems where agents need to replan fast. Methods that address this typically employ a "windowed" approach and only try to find collision free paths for a small windowed timestep horizon. This adaptation comes at the cost of incompleteness; all current windowed approaches can become stuck in deadlock or livelock. Our main contribution is to introduce our framework, WinC-MAPF, for Windowed MAPF that enables completeness. Our framework uses heuristic update insights from single-agent real-time heuristic search algorithms as well as agent independence ideas from MAPF algorithms. We also develop Single-Step CBS (SS-CBS), an instantiation of this framework using a novel modification to CBS. We show how SS-CBS, which only plans a single step and updates heuristics, can effectively solve tough scenarios where existing windowed approaches fail.
- Abstract（参考訳）: 従来のマルチエージェントパス探索(MAPF)手法は、衝突のないスタートゴールパス全体を計算しようとする。
しかし、エージェントが迅速に再計画する必要があるMAPFシステムでは、パス全体を計算するのに時間がかかりすぎる可能性がある。
この問題に対処する手法は、通常「ウィンドウ化された」アプローチを採用し、小さなウィンドウ化された時間ステップの水平線に対して衝突のない経路を見つけようとするだけである。
この適応には不完全なコストが伴うため、現在のウィンドウ化されたアプローチはすべてデッドロックやライブロックで立ち往生する可能性がある。
我々の主な貢献は、完全性を実現するWinC-MAPF for Windowed MAPFの導入である。
本フレームワークでは,シングルエージェントリアルタイムヒューリスティック検索アルゴリズムからのヒューリスティックな更新洞察とMAPFアルゴリズムからのエージェント独立性を用いた。
また,CBSに新たな変更を加えて,この枠組みを即時化するシングルステップCBS (SS-CBS) も開発した。
単一のステップのみを計画し、ヒューリスティックを更新するSS-CBSは、既存のウィンドウ化アプローチが失敗する難しいシナリオを効果的に解決できることを示す。
関連論文リスト
- Improving Learnt Local MAPF Policies with Heuristic Search [24.06091123268885]
MAPF (Multi-Adnt Path Finding) は、エージェントのチームが目標地点に到達するための衝突のない経路を見つける問題である。
MAPFに対する現在の機械学習アプローチでは、このポテンシャルの表面を掻き傷始めた手法が提案されている。
我々は,学習ポリシーを用いた検索のモデルに依存しないいくつかの方法を示し,政策の成功率とスケーラビリティを著しく向上させる。
論文 参考訳（メタデータ） (2024-03-29T17:16:20Z) - Scalable Mechanism Design for Multi-Agent Path Finding [87.40027406028425]
MAPF (Multi-Agent Path Finding) は、複数のエージェントが同時に移動し、与えられた目標地点に向かって共有領域を通って衝突しない経路を決定する。
最適解を見つけることは、しばしば計算不可能であり、近似的な準最適アルゴリズムを用いることが不可欠である。
本稿では、MAPFのスケーラブルな機構設計の問題を紹介し、MAPFアルゴリズムを近似した3つの戦略防御機構を提案する。
論文 参考訳（メタデータ） (2024-01-30T14:26:04Z) - Decentralized Monte Carlo Tree Search for Partially Observable
Multi-agent Pathfinding [49.730902939565986]
マルチエージェントパスフィンディング問題は、グラフに閉じ込められたエージェントのグループに対するコンフリクトフリーパスのセットを見つけることである。
本研究では、エージェントが他のエージェントをローカルにのみ観察できる分散MAPF設定に焦点を当てた。
MAPFタスクのための分散マルチエージェントモンテカルロ木探索法を提案する。
論文 参考訳（メタデータ） (2023-12-26T06:57:22Z) - Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding [29.76466191644455]
MAPF(Multi-Agent Path Finding)は、ロボット工学における基本的な問題であり、エージェントのチームに対して衝突のない経路の計算を求める。
本稿では,MAPFにエージェントを誘導する手法を提案する。
各エージェントが1つの宛先を持つワンショットMAPFと、エージェントが常に新しい宛先を割り当てる終身MAPFの2つの大規模設定でこのアイデアを評価する。
論文 参考訳（メタデータ） (2023-08-22T07:17:39Z) - Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
マルチエージェントパスフィンディングに適したモンテカルロ木探索(MCTS)のオリジナル版を紹介する。
具体的には,エージェントの目標達成行動を支援するために,個別の経路を用いる。
また,木探索手順の分岐係数を低減するために,専用の分解手法を用いる。
論文 参考訳（メタデータ） (2023-07-25T12:33:53Z) - Green Hierarchical Vision Transformer for Masked Image Modeling [54.14989750044489]
階層型視覚変換器(ViT)を用いたマスク付き画像モデリングのための効率的な手法を提案する。
グループウィンドウのアテンションスキームは,ディバイド・アンド・コンカエ戦略に従って設計する。
グループ化されたパッチに対する注意の全体的なコストを最小限に抑えるため、動的プログラミングアルゴリズムによるグループ化戦略をさらに改善する。
論文 参考訳（メタデータ） (2022-05-26T17:34:42Z) - Conflict-Based Search for Explainable Multi-Agent Path Finding [7.734726150561088]
安全クリティカルなアプリケーションでは、人間の監督者は、この計画が本当に衝突のないものであることを検証したいかもしれない。
MAPF問題は、簡潔な説明を認める非衝突経路のセットを要求する。
従来のMAPFアルゴリズムは、説明可能なMAPFを直接処理するものではない。
我々は、MAPFのためのよく研究されたアルゴリズムである Conflict Based Search (CBS) を適用して、説明可能なMAPFを扱う。
論文 参考訳（メタデータ） (2022-02-20T23:13:14Z) - Loosely Synchronized Search for Multi-agent Path Finding with
Asynchronous Actions [10.354181009277623]
マルチエージェントパス検索(MAPF)は、各開始位置と目標位置の間の複数のエージェントの衝突のないパスのアンサンブルを決定する。
この記事では、エージェントが必ずしも同時に起動および停止しない非同期アクションによるMAPFの自然な一般化を紹介します。
論文 参考訳（メタデータ） (2021-03-08T02:34:17Z) - Probabilistic Case-based Reasoning for Open-World Knowledge Graph
Completion [59.549664231655726]
ケースベース推論(CBR)システムは,与えられた問題に類似した事例を検索することで,新たな問題を解決する。
本稿では,知識ベース(KB)の推論において,そのようなシステムが実現可能であることを示す。
提案手法は,KB内の類似エンティティからの推論パスを収集することにより,エンティティの属性を予測する。
論文 参考訳（メタデータ） (2020-10-07T17:48:12Z) - POMP: Pomcp-based Online Motion Planning for active visual search in
indoor environments [89.43830036483901]
本稿では, 屋内環境におけるオブジェクトのアクティブビジュアルサーチ(AVS)の最適ポリシーを, オンライン設定で学習する問題に焦点をあてる。
提案手法はエージェントの現在のポーズとRGB-Dフレームを入力として使用する。
提案手法を利用可能なAVDベンチマークで検証し,平均成功率0.76,平均パス長17.1とした。
論文 参考訳（メタデータ） (2020-09-17T08:23:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。