論文の概要: Multi Agent Path Finding with Awareness for Spatially Extended Agents
- arxiv url: http://arxiv.org/abs/2009.09355v1
- Date: Sun, 20 Sep 2020 05:40:04 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-16 12:51:37.554914
- Title: Multi Agent Path Finding with Awareness for Spatially Extended Agents
- Title（参考訳）: 空間拡張エージェントに対する認識を伴うマルチエージェントパス探索
- Authors: Shyni Thomas and Dipti Deodhare and M.N. Murty
- Abstract要約: 経路発見問題は、共通の道路ネットワーク上のエージェントの衝突のない移動計画を特定することを含む。
本稿では,走行する道路の長さに匹敵する大きさの空間拡張剤について検討する。
eXtended Conflict Based Search (XCBS)アルゴリズムにおいて,空間拡張エージェントに対する最適マルチエージェントパス探索手法を提案した。
- 参考スコア（独自算出の注目度）: 0.5156484100374058
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Path finding problems involve identification of a plan for conflict free
movement of agents over a common road network. Most approaches to this problem
handle the agents as point objects, wherein the size of the agent is
significantly smaller than the road on which it travels. In this paper, we
consider spatially extended agents which have a size comparable to the length
of the road on which they travel. An optimal multi agent path finding approach
for spatially-extended agents was proposed in the eXtended Conflict Based
Search (XCBS) algorithm. As XCBS resolves only a pair of conflicts at a time,
it results in deeper search trees in case of cascading or multiple (more than
two agent) conflicts at a given location. This issue is addressed in eXtended
Conflict Based Search with Awareness (XCBS-A) in which an agent uses awareness
of other agents' plans to make its own plan. In this paper, we explore XCBS-A
in greater detail, we theoretically prove its completeness and empirically
demonstrate its performance with other algorithms in terms of variances in road
characteristics, agent characteristics and plan characteristics. We demonstrate
the distributive nature of the algorithm by evaluating its performance when
distributed over multiple machines. XCBS-A generates a huge search space
impacting its efficiency in terms of memory; to address this we propose an
approach for memory-efficiency and empirically demonstrate the performance of
the algorithm. The nature of XCBS-A is such that it may lead to suboptimal
solutions, hence the final contribution of this paper is an enhanced approach,
XCBS-Local Awareness (XCBS-LA) which we prove will be optimal and complete.
- Abstract（参考訳）: 経路発見問題は、共通の道路ネットワーク上のエージェントの衝突のない移動計画を特定することを含む。
この問題に対するほとんどのアプローチは、エージェントをポイントオブジェクトとして扱い、エージェントのサイズは、それが移動する道路よりもかなり小さい。
本稿では,走行する道路の長さに匹敵する大きさの空間拡張剤について検討する。
eXtended Conflict Based Search (XCBS)アルゴリズムにおいて,空間拡張エージェントに対する最適マルチエージェントパス探索手法を提案した。
XCBSは一度に1対のコンフリクトしか解決しないため、カスケーディングや複数の(複数のエージェント)コンフリクトが与えられた場所で発生した場合、より深いサーチツリーが生成される。
この問題は、エージェントが他のエージェントの計画を意識して独自の計画を立てる、eXtended Conflict Based Search with Awareness (XCBS-A)で対処される。
本稿では,XCBS-Aの完全性を理論的に検証し,道路特性,エージェント特性,計画特性の相違点から,他のアルゴリズムによる性能を実証する。
複数のマシンに分散する際の性能を評価することにより,アルゴリズムの分散特性を示す。
XCBS-Aは,メモリの効率に影響を及ぼす巨大な検索空間を生成し,メモリ効率に対するアプローチを提案し,アルゴリズムの性能を実証的に示す。
そこで本論文の最終的な貢献は,XCBS-Local Awareness (XCBS-LA) が最適かつ完全であることを証明した拡張アプローチである。
関連論文リスト
- Cooperative Reward Shaping for Multi-Agent Pathfinding [4.244426154524592]
MAPF(Multi-Agent Pathfinding)の主な目的は、全てのエージェントに対して効率的で競合のないパスを計画することである。
従来のマルチエージェントパス計画アルゴリズムは、複数のエージェントに対して効率的な分散パス計画を実現するのに苦労する。
独立Q-Learning(IQL)に基づく独自の報酬形成手法を紹介する。
論文 参考訳（メタデータ） (2024-07-15T02:44:41Z) - 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) - Pure Exploration under Mediators' Feedback [63.56002444692792]
マルチアームバンディット(Multi-armed bandits)は、各インタラクションステップにおいて、学習者が腕を選択し、報酬を観察する、シーケンシャルな意思決定フレームワークである。
本稿では,学習者が仲介者の集合にアクセスできるシナリオについて考察する。
本稿では,学習者には仲介者の方針が知られていると仮定して,最適な腕を発見するための逐次的意思決定戦略を提案する。
論文 参考訳（メタデータ） (2023-08-29T18:18:21Z) - Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
マルチエージェントパスフィンディングに適したモンテカルロ木探索(MCTS)のオリジナル版を紹介する。
具体的には,エージェントの目標達成行動を支援するために,個別の経路を用いる。
また,木探索手順の分岐係数を低減するために,専用の分解手法を用いる。
論文 参考訳（メタデータ） (2023-07-25T12:33:53Z) - Factorization of Multi-Agent Sampling-Based Motion Planning [72.42734061131569]
現代のロボティクスは、共有環境内で複数のエンボディエージェントを動作させることが多い。
標準的なサンプリングベースのアルゴリズムは、ロボットの関節空間における解の探索に使用できる。
我々は、因子化の概念をサンプリングベースアルゴリズムに統合し、既存の手法への最小限の変更しか必要としない。
本稿では, PRM* のサンプル複雑性の観点から解析的ゲインを導出し, RRG の実証結果を示す。
論文 参考訳（メタデータ） (2023-04-01T15:50:18Z) - Multi-agent Deep Covering Skill Discovery [50.812414209206054]
本稿では,複数エージェントの結合状態空間の予測被覆時間を最小化し,マルチエージェントオプションを構築するマルチエージェントDeep Covering Option Discoveryを提案する。
また、MARLプロセスにマルチエージェントオプションを採用するための新しいフレームワークを提案する。
提案アルゴリズムは,アテンション機構とエージェントの相互作用を効果的に把握し,マルチエージェントオプションの同定に成功した。
論文 参考訳（メタデータ） (2022-10-07T00:40:59Z) - Subdimensional Expansion Using Attention-Based Learning For Multi-Agent
Path Finding [9.2127262112464]
MAPF(Multi-Agent Path Finding)は、各開始点から目標地点までの複数のエージェントに対する競合のないパスを見つける。
我々は、この学習に基づくシングルエージェントプランナーをM*に統合することにより、LM*と呼ばれる新しいマルチエージェントプランナーを開発する。
以上の結果から,M* と比較した場合,LM* はコンフリクトが少なく,高速に動作し,高い成功率を享受できることがわかった。
論文 参考訳（メタデータ） (2021-09-29T20:01:04Z) - 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) - Heterogeneous Explore-Exploit Strategies on Multi-Star Networks [0.0]
エージェントがマルチスターネットワーク上で通信する分散帯域幅問題について検討する。
モデル不規則ネットワークグラフとしてマルチスターを用いた異種探索探索戦略を提案する。
論文 参考訳（メタデータ） (2020-09-02T20:56:49Z) - Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal
Constraints [52.58352707495122]
本稿では,不確実性およびマルチエージェント協調の下での逐次意思決定における重要な計算課題を分離するマルチロボット割当アルゴリズムを提案する。
都市におけるマルチアームコンベヤベルトピック・アンド・プレイスとマルチドローン配送ディスパッチの2つの異なる領域における広範囲なシミュレーション結果について検証を行った。
論文 参考訳（メタデータ） (2020-05-27T01:10:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。