論文の概要: A Competitive Analysis of Online Multi-Agent Path Finding
- arxiv url: http://arxiv.org/abs/2106.11454v1
- Date: Tue, 22 Jun 2021 00:05:29 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-23 14:44:06.935287
- Title: A Competitive Analysis of Online Multi-Agent Path Finding
- Title（参考訳）: オンラインマルチエージェントパス探索の競合分析
- Authors: Hang Ma
- Abstract要約: オンラインマルチエージェントパス探索(MAPF)について検討し、新しいエージェントが常に時間とともに明らかにされ、すべてのエージェントが与えられた目標地点への衝突のないパスを見つけなければならない。
我々は,オンラインMAPFアルゴリズムを,(1)制御可能性(各時間に経路を計画できるエージェントの集合)と(2)合理性(計画する経路の質)に基づいて,異なるカテゴリに分類し,それらの関係について検討する。
- 参考スコア（独自算出の注目度）: 6.172744281261983
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study online Multi-Agent Path Finding (MAPF), where new agents are
constantly revealed over time and all agents must find collision-free paths to
their given goal locations. We generalize existing complexity results of
(offline) MAPF to online MAPF. We classify online MAPF algorithms into
different categories based on (1) controllability (the set of agents that they
can plan paths for at each time) and (2) rationality (the quality of paths they
plan) and study the relationships between them. We perform a competitive
analysis for each category of online MAPF algorithms with respect to
commonly-used objective functions. We show that a naive algorithm that routes
newly-revealed agents one at a time in sequence achieves a competitive ratio
that is asymptotically bounded from both below and above by the number of
agents with respect to flowtime and makespan. We then show a counter-intuitive
result that, if rerouting of previously-revealed agents is not allowed, any
rational online MAPF algorithms, including ones that plan optimal paths for all
newly-revealed agents, have the same asymptotic competitive ratio as the naive
algorithm, even on 2D 4-neighbor grids. We also derive constant lower bounds on
the competitive ratio of any rational online MAPF algorithms that allow
rerouting. The results thus provide theoretical insights into the effectiveness
of using MAPF algorithms in an online setting for the first time.
- Abstract（参考訳）: オンラインマルチエージェントパス発見(mapf)について検討し,新たなエージェントが時間とともに常に明らかにされ,すべてのエージェントが所定の目標位置への衝突のないパスを見つけなければならない。
我々はMAPFの既存の複雑性結果をオンラインMAPFに一般化する。
我々は,オンラインMAPFアルゴリズムを,(1)制御可能性(各時間に経路を計画できるエージェントの集合)と(2)合理性(計画する経路の質)に基づいて,異なるカテゴリに分類し,それらの関係について検討する。
我々は,オンラインMAPFアルゴリズムの各カテゴリに対して,一般的に使用される目的関数に関する競合分析を行う。
そこで本研究では,新たに開発したエージェントを順次経路づけするナイーブアルゴリズムが,フロータイムとmakespanに対するエージェント数によって,上下から漸近的に境界付けられた競合比を達成することを示す。
その結果,前述したエージェントの再配置が許可されない場合,新たなエージェントの最適経路を計画するオンラインmapfアルゴリズムは,2次元4-neighborグリッドにおいても,naiveアルゴリズムと同じ漸近的競合比を持つことがわかった。
また、合理的オンラインMAPFアルゴリズムの競合比を一定に低くし、リルーティングを可能にします。
その結果, オンライン環境におけるmapfアルゴリズムの有効性に関する理論的知見が得られた。
関連論文リスト
- 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) - 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) - An Efficient Approach to the Online Multi-Agent Path Finding Problem by
Using Sustainable Information [10.367412630626834]
多エージェント経路探索(MAPF)は、衝突せずにエージェントをゴールへ移動させる問題である。
本稿では,持続可能な情報を活用したオンラインMAPFの3段階的解決手法を提案する。
我々のアルゴリズムは、エージェント数の設定が異なる場合、平均1.48倍の速度でSOTAより高速である。
論文 参考訳（メタデータ） (2023-01-11T13:04:35Z) - Learning From Good Trajectories in Offline Multi-Agent Reinforcement
Learning [98.07495732562654]
オフラインマルチエージェント強化学習(MARL)は、事前コンパイルされたデータセットから効果的なマルチエージェントポリシーを学ぶことを目的としている。
オフラインのMARLが学んだエージェントは、しばしばこのランダムなポリシーを継承し、チーム全体のパフォーマンスを脅かす。
この問題に対処するために,共有個人軌道(SIT)と呼ばれる新しいフレームワークを提案する。
論文 参考訳（メタデータ） (2022-11-28T18:11:26Z) - LaCAM: Search-Based Algorithm for Quick Multi-Agent Pathfinding [5.025654873456756]
MAPF(LaCAM)の遅延制約付加探索という,マルチエージェントパスフィンディング(MAPF)のための新しい完全アルゴリズムを提案する。
LaCAMは2段階の検索を使って、何百ものエージェントでも素早くソリューションを見つける。
実験の結果,LaCAMは様々なシナリオにおいて最先端のMAPFアルゴリズムに匹敵する,あるいは優れることがわかった。
論文 参考訳（メタデータ） (2022-11-24T06:27:18Z) - General Cutting Planes for Bound-Propagation-Based Neural Network
Verification [144.7290035694459]
任意の切削平面制約を加えることができるような境界伝搬手順を一般化する。
MIPソルバは、境界プロパゲーションベースの検証器を強化するために高品質な切削面を生成することができる。
本手法は,oval20ベンチマークを完全解き,oval21ベンチマークの2倍のインスタンスを検証できる最初の検証器である。
論文 参考訳（メタデータ） (2022-08-11T10:31:28Z) - Reinforcement Learning for Branch-and-Bound Optimisation using
Retrospective Trajectories [72.15369769265398]
機械学習は分岐のための有望なパラダイムとして登場した。
分岐のための単純かつ効果的なRLアプローチであるレトロ分岐を提案する。
我々は現在最先端のRL分岐アルゴリズムを3～5倍に上回り、500の制約と1000の変数を持つMILP上での最高のILメソッドの性能の20%以内である。
論文 参考訳（メタデータ） (2022-05-28T06:08:07Z) - Compilation-based Solvers for Multi-Agent Path Finding: a Survey,
Discussion, and Future Opportunities [7.766921168069532]
このトピックの過去の発展と現在の傾向から学んだ教訓を示し、その広範な影響について議論します。
最適MAPF解決のための2つの主要なアプローチは、(1)MAPFを直接解決する専用の検索ベース手法、(2)MAPFインスタンスを異なる確立された形式でインスタンスに還元するコンパイルベース手法である。
論文 参考訳（メタデータ） (2021-04-23T20:13:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。