論文の概要: Loosely Synchronized Search for Multi-agent Path Finding with Asynchronous Actions

• arxiv url: http://arxiv.org/abs/2103.04516v1
• Date: Mon, 8 Mar 2021 02:34:17 GMT
• ステータス: 処理完了
• システム内更新日: 2021-03-09 15:23:42.698047
• Title: Loosely Synchronized Search for Multi-agent Path Finding with Asynchronous Actions
• Title（参考訳）: 非同期動作によるマルチエージェントパスの疎同期探索
• Authors: Zhongqiang Ren, Sivakumar Rathinam and Howie Choset
• Abstract要約: マルチエージェントパス検索(MAPF)は、各開始位置と目標位置の間の複数のエージェントの衝突のないパスのアンサンブルを決定する。 この記事では、エージェントが必ずしも同時に起動および停止しない非同期アクションによるMAPFの自然な一般化を紹介します。
• 参考スコア（独自算出の注目度）: 10.354181009277623
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Multi-agent path finding (MAPF) determines an ensemble of collision-free paths for multiple agents between their respective start and goal locations. Among the available MAPF planners for workspaces modeled as a graph, A*-based approaches have been widely investigated and have demonstrated their efficiency in numerous scenarios. However, almost all of these A*-based approaches assume that each agent executes an action concurrently in that all agents start and stop together. This article presents a natural generalization of MAPF with asynchronous actions where agents do not necessarily start and stop concurrently. The main contribution of the work is a proposed approach called Loosely Synchronized Search (LSS) that extends A*-based MAPF planners to handle asynchronous actions. We show LSS is complete and finds an optimal solution if one exists. We also combine LSS with other existing MAPF methods that aims to trade-off optimality for computational efficiency. Extensive numerical results are presented to corroborate the performance of the proposed approaches. Finally, we also verify the applicability of our method in the Robotarium, a remotely accessible swarm robotics research platform.
• Abstract（参考訳）: マルチエージェントパス検索(MAPF)は、各開始位置と目標位置の間の複数のエージェントの衝突のないパスのアンサンブルを決定する。 グラフとしてモデル化されたワークスペースのためのMAPFプランナのうち、A*ベースのアプローチは広く研究され、多くのシナリオでその効率を実証している。 しかしながら、これらのA*ベースのアプローチのほとんど全てが、各エージェントが同時にアクションを実行し、すべてのエージェントが一緒に開始して停止することを前提としている。 この記事では、エージェントが必ずしも同時に起動および停止しない非同期アクションによるMAPFの自然な一般化を紹介します。 この作業の主な貢献は、非同期アクションを処理するためにA*ベースのMAPFプランナーを拡張するLoosely Synchronized Search(LSS)と呼ばれる提案されたアプローチである。 LSS が完全であることを示し、もし存在するなら最適解を求める。 また,LSSと既存のMAPF手法を組み合わせることで,計算効率の最適性をトレードオフする。 提案手法の性能を裏付ける大規模な数値計算結果が提示される。 最後に、遠隔でアクセス可能な群ロボット研究プラットフォームであるRobotariumの手法の適用性についても検証する。

関連論文リスト

• Cooperative Reward Shaping for Multi-Agent Pathfinding [4.244426154524592]
  MAPF(Multi-Agent Pathfinding)の主な目的は、全てのエージェントに対して効率的で競合のないパスを計画することである。 従来のマルチエージェントパス計画アルゴリズムは、複数のエージェントに対して効率的な分散パス計画を実現するのに苦労する。 独立Q-Learning(IQL)に基づく独自の報酬形成手法を紹介する。
  論文  参考訳（メタデータ） (2024-07-15T02:44:41Z)
• MGCBS: An Optimal and Efficient Algorithm for Solving Multi-Goal Multi-Agent Path Finding Problem [5.580214316179672]
  MG-MAPF問題は、各エージェントが少なくとも1回は衝突することなく、予め割り当てられた複数のゴールポイントを訪問する必要がある。 そこで本研究では,単一エージェントパスフィンディング(Single-Adnt pathfinding)とセーフ区間探索(Single-Adnt pathfinding)の分離に基づくMulti-Goal Conflict-Based Search (MGCBS)を提案する。 提案手法は, 常に最適な結果を得ることができ, 評価において最先端の手法よりも最大7倍高速に実行することができる。
  論文  参考訳（メタデータ） (2024-04-30T12:49:54Z)
• 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)
• 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)
• 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)
• Multi-agent Policy Optimization with Approximatively Synchronous Advantage Estimation [55.96893934962757]
  マルチエージェントシステムでは、異なるエージェントの警察を共同で評価する必要がある。 現在の方法では、バリュー関数やアドバンテージ関数は非同期に評価される対実関節アクションを使用する。 本研究では,近似的に同期する利点推定を提案する。
  論文  参考訳（メタデータ） (2020-12-07T07:29:19Z)
• Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints [52.58352707495122]
  本稿では,不確実性およびマルチエージェント協調の下での逐次意思決定における重要な計算課題を分離するマルチロボット割当アルゴリズムを提案する。 都市におけるマルチアームコンベヤベルトピック・アンド・プレイスとマルチドローン配送ディスパッチの2つの異なる領域における広範囲なシミュレーション結果について検証を行った。
  論文  参考訳（メタデータ） (2020-05-27T01:10:41Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。