論文の概要: LaCAM: Search-Based Algorithm for Quick Multi-Agent Pathfinding
- arxiv url: http://arxiv.org/abs/2211.13432v1
- Date: Thu, 24 Nov 2022 06:27:18 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-28 18:24:39.354468
- Title: LaCAM: Search-Based Algorithm for Quick Multi-Agent Pathfinding
- Title（参考訳）: LaCAM: 高速マルチエージェントパスフィニングのための検索ベースアルゴリズム
- Authors: Keisuke Okumura
- Abstract要約: MAPF(LaCAM)の遅延制約付加探索という,マルチエージェントパスフィンディング(MAPF)のための新しい完全アルゴリズムを提案する。
LaCAMは2段階の検索を使って、何百ものエージェントでも素早くソリューションを見つける。
実験の結果,LaCAMは様々なシナリオにおいて最先端のMAPFアルゴリズムに匹敵する,あるいは優れることがわかった。
- 参考スコア（独自算出の注目度）: 5.025654873456756
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose a novel complete algorithm for multi-agent pathfinding (MAPF)
called lazy constraints addition search for MAPF (LaCAM). MAPF is a problem of
finding collision-free paths for multiple agents on graphs and is the
foundation of multi-robot coordination. LaCAM uses a two-level search to find
solutions quickly, even with hundreds of agents or more. At the low-level, it
searches constraints about agents' locations. At the high-level, it searches a
sequence of all agents' locations, following the constraints specified by the
low-level. Our exhaustive experiments reveal that LaCAM is comparable to or
outperforms state-of-the-art sub-optimal MAPF algorithms in a variety of
scenarios, regarding success rate, planning time, and solution quality of
sum-of-costs.
- Abstract（参考訳）: 本稿では,MAPF(LaCAM)の遅延制約付加探索という,マルチエージェントパスフィンディング(MAPF)のための新しい完全アルゴリズムを提案する。
MAPFはグラフ上の複数エージェントの衝突のない経路を見つける問題であり、マルチロボット協調の基礎となっている。
lacamは二段階検索を使って、数百以上のエージェントでも素早く解決策を見つける。
低いレベルでは、エージェントの場所に関する制約を検索する。
高レベルでは、低レベルによって指定された制約に従って、すべてのエージェントの位置のシーケンスを検索する。
我々の徹底的な実験により、LaCAMは、成功率、計画時間、コストの総和のソリューション品質など、様々なシナリオにおいて最先端のMAPFアルゴリズムに匹敵する、あるいは優れることがわかった。
関連論文リスト
- Algorithm Selection for Optimal Multi-Agent Path Finding via Graph Embedding [9.831879504969224]
多エージェント経路探索(MAPF)は、衝突しない複数のエージェントの経路を見つける問題である。
MAPFの最適解を見つけることはNP-Hardであるが、現代の最適解法は数百のエージェントにスケールでき、場合によっては数千までスケールできる。
このエンコーディングが既存のエンコーディングと効果的に結合できることを示し、その結果、グラフ埋め込みによるMAPFアルゴリズム選択と呼ばれる新しいASメソッドが実現された。
論文 参考訳（メタデータ） (2024-06-16T07:41:58Z) - Optimal and Bounded Suboptimal Any-Angle Multi-agent Pathfinding [13.296796764344169]
提案手法は,最初の最適非角度マルチエージェントパスフィンディングアルゴリズムである。
我々のプランナーは、Continuous Conflict-based Search (CCBS)アルゴリズムと、Safe Interval Path Planning (TO-AA-SIPP)の最適な任意の角度変種に基づいている。
古典的MAPFから任意の角度設定、すなわち Disjoint Splitting と Multi-Constraint への2つの手法を適用する。
論文 参考訳（メタデータ） (2024-04-25T07:41:47Z) - 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) - Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
マルチエージェントパスフィンディングに適したモンテカルロ木探索(MCTS)のオリジナル版を紹介する。
具体的には,エージェントの目標達成行動を支援するために,個別の経路を用いる。
また,木探索手順の分岐係数を低減するために,専用の分解手法を用いる。
論文 参考訳（メタデータ） (2023-07-25T12:33:53Z) - Improving LaCAM for Scalable Eventually Optimal Multi-Agent Pathfinding [5.025654873456756]
マルチエージェントパスフィンディング(MAPF)のための最近開発されたLaCAMアルゴリズムを拡張した。
LaCAMは、遅延後継生成を用いて計画作業を劇的に削減する、サブ最適検索ベースのアルゴリズムである。
我々は、LaCAM*と呼ばれる任意のバージョンを提案し、最終的にはオプティマに収束する。
論文 参考訳（メタデータ） (2023-05-05T15:43:20Z) - Multi-agent Deep Covering Skill Discovery [50.812414209206054]
本稿では,複数エージェントの結合状態空間の予測被覆時間を最小化し,マルチエージェントオプションを構築するマルチエージェントDeep Covering Option Discoveryを提案する。
また、MARLプロセスにマルチエージェントオプションを採用するための新しいフレームワークを提案する。
提案アルゴリズムは,アテンション機構とエージェントの相互作用を効果的に把握し,マルチエージェントオプションの同定に成功した。
論文 参考訳（メタデータ） (2022-10-07T00:40:59Z) - 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) - MRDet: A Multi-Head Network for Accurate Oriented Object Detection in
Aerial Images [51.227489316673484]
水平アンカーから変換された指向性提案を生成するために、任意指向領域提案ネットワーク(AO-RPN)を提案する。
正確なバウンディングボックスを得るために,検出タスクを複数のサブタスクに分離し,マルチヘッドネットワークを提案する。
各ヘッドは、対応するタスクに最適な特徴を学習するために特別に設計されており、ネットワークがオブジェクトを正確に検出することができる。
論文 参考訳（メタデータ） (2020-12-24T06:36:48Z) - Multi-Goal Multi-Agent Path Finding via Decoupled and Integrated Goal
Vertex Ordering [15.99072005190786]
本稿では,MAPF問題を一般化したマルチゴールマルチエージェントパス探索法(MAPF$MG$)を提案する。
我々は,MAPF$MG$に対処するために,異なるパラダイムを用いた2つの新しいアルゴリズムを提案する。Hamiltonian-CBS (HCBS) と呼ばれる検索ベース検索アルゴリズムと,SMTパラダイムを用いたコンパイルベースアルゴリズムであるSMT-Hamiltonian-CBS (SMT-HCBS) を提案する。
論文 参考訳（メタデータ） (2020-09-10T22:27:18Z) - Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal
Constraints [52.58352707495122]
本稿では,不確実性およびマルチエージェント協調の下での逐次意思決定における重要な計算課題を分離するマルチロボット割当アルゴリズムを提案する。
都市におけるマルチアームコンベヤベルトピック・アンド・プレイスとマルチドローン配送ディスパッチの2つの異なる領域における広範囲なシミュレーション結果について検証を行った。
論文 参考訳（メタデータ） (2020-05-27T01:10:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。