論文の概要: Pairwise Symmetry Reasoning for Multi-Agent Path Finding Search
- arxiv url: http://arxiv.org/abs/2103.07116v1
- Date: Fri, 12 Mar 2021 07:27:35 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-15 13:17:06.936468
- Title: Pairwise Symmetry Reasoning for Multi-Agent Path Finding Search
- Title（参考訳）: 多元経路探索のためのペアワイズ対称性推論
- Authors: Jiaoyang Li, Daniel Harabor, Peter J. Stuckey, Sven Koenig
- Abstract要約: マルチエージェントパス発見(mapf)は,協調エージェントのチームに対して,衝突のないパスを計画することを求める課題である。
MAPFが解決しにくい理由の1つは、ペアワイズ対称性と呼ばれる現象によるものであることを示しています。
対称性の発生を効率的に検出し、特殊な制約を用いて解決する様々な推論手法を提案します。
- 参考スコア（独自算出の注目度）: 43.40580211016752
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Multi-Agent Path Finding (MAPF) is a challenging combinatorial problem that
asks us to plan collision-free paths for a team of cooperative agents. In this
work, we show that one of the reasons why MAPF is so hard to solve is due to a
phenomenon called pairwise symmetry, which occurs when two agents have many
different paths to their target locations, all of which appear promising, but
every combination of them results in a collision. We identify several classes
of pairwise symmetries and show that each one arises commonly in practice and
can produce an exponential explosion in the space of possible collision
resolutions, leading to unacceptable runtimes for current state-of-the-art
(bounded-sub)optimal MAPF algorithms. We propose a variety of reasoning
techniques that detect the symmetries efficiently as they arise and resolve
them by using specialized constraints to eliminate all permutations of pairwise
colliding paths in a single branching step. We implement these ideas in the
context of the leading optimal MAPF algorithm CBS and show that the addition of
the symmetry reasoning techniques can have a dramatic positive effect on its
performance - we report a reduction in the number of node expansions by up to
four orders of magnitude and an increase in scalability by up to thirty times.
These gains allow us to solve to optimality a variety of challenging MAPF
instances previously considered out of reach for CBS.
- Abstract（参考訳）: マルチエージェントパス探索(mapf)は,協調エージェントのチームに対して,衝突のないパスを計画することを求めるコンビネーション問題である。
本研究では, mapf が解くのが難しい理由の1つとして, 2 つのエージェントがそれぞれ異なる経路を持ち, それぞれが有望に見えるが, それらの組み合わせが衝突を生じさせる, ペアワイズ対称性と呼ばれる現象があげられる。
いくつかのペアワイズ対称性のクラスを同定し、各クラスが実際に一般的に発生することを示し、衝突解決の可能な空間において指数的爆発を引き起こすことを示し、現在の最先端(有界)MAPFアルゴリズムに対する受け入れがたいランタイムを生み出す。
単一分岐ステップにおける対衝突経路の全ての置換を排除すべく, 特殊制約を用いて, 対称性の発生を効率的に検出し, 解決する様々な推論手法を提案する。
私たちは、これらのアイデアを最先端のMAPFアルゴリズムCBSの文脈で実装し、対称性推論技術の追加は、その性能に劇的なプラスの効果をもたらすことができることを示しています - 我々は、最大4桁のノード拡張の減少と最大30倍のスケーラビリティの増加を報告します。
これらの利益により、これまでCBSに到達できなかった様々な挑戦的なMAPFインスタンスを最適に解決することができます。
関連論文リスト
- UCB-driven Utility Function Search for Multi-objective Reinforcement Learning [75.11267478778295]
マルチオブジェクト強化学習(MORL)エージェントでは、意思決定行動の最適化を行う。
重みベクトル w でパラメータ化される線型効用関数の場合に焦点を当てる。
学習過程の異なる段階で最も有望な重みベクトルを効率的に探索する上信頼境界に基づく手法を提案する。
論文 参考訳（メタデータ） (2024-05-01T09:34:42Z) - 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) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳（メタデータ） (2023-10-08T23:39:38Z) - Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
マルチエージェントパスフィンディングに適したモンテカルロ木探索(MCTS)のオリジナル版を紹介する。
具体的には,エージェントの目標達成行動を支援するために,個別の経路を用いる。
また,木探索手順の分岐係数を低減するために,専用の分解手法を用いる。
論文 参考訳（メタデータ） (2023-07-25T12:33:53Z) - Fine-Grained Complexity Analysis of Multi-Agent Path Finding on 2D Grids [0.190365714903665]
エージェントを2つのチームに分けた2色MAPFがNPハードのままであることを示す。
フロータイムの目的のために,エージェントの移動数に基づいてトラクタビリティフロンティアを確立する。
この結果は最適解の構造に新たな光を当て、一般的な問題のアルゴリズム設計を導くのに役立つかもしれない。
論文 参考訳（メタデータ） (2023-05-25T17:56:24Z) - MultiZenoTravel: a Tunable Benchmark for Multi-Objective Planning with
Known Pareto Front [71.19090689055054]
多目的AI計画では、既知のPareto Frontsを示すベンチマークが不足している。
提案するベンチマーク生成器と専用ソルバは、結果のインスタンスの真のParetoを確実に計算する。
本稿では,制約された問題に対して最適な計画を示すとともに,制約された問題に対する一般的な問題を減らす方法を示す。
論文 参考訳（メタデータ） (2023-04-28T07:09:23Z) - Decentralised Approach for Multi Agent Path Finding [6.599344783327053]
MAPF (Multi Agent Path Finding) は、空間的に拡張されたエージェントに対する競合のない経路の同定を必要とする。
これらは、Convoy Movement ProblemやTraning Schedulingといった現実世界の問題に適用できる。
提案手法であるDecentralized Multi Agent Path Finding (DeMAPF) は、MAPFを経路計画と割り当ての問題の系列として扱う。
論文 参考訳（メタデータ） (2021-06-03T18:07:26Z) - Loosely Synchronized Search for Multi-agent Path Finding with
Asynchronous Actions [10.354181009277623]
マルチエージェントパス検索(MAPF)は、各開始位置と目標位置の間の複数のエージェントの衝突のないパスのアンサンブルを決定する。
この記事では、エージェントが必ずしも同時に起動および停止しない非同期アクションによるMAPFの自然な一般化を紹介します。
論文 参考訳（メタデータ） (2021-03-08T02:34:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。