論文の概要: Loosely Synchronized Rule-Based Planning for Multi-Agent Path Finding with Asynchronous Actions

• arxiv url: http://arxiv.org/abs/2412.11678v2
• Date: Sat, 21 Dec 2024 08:38:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-24 15:51:33.170310
• Title: Loosely Synchronized Rule-Based Planning for Multi-Agent Path Finding with Asynchronous Actions
• Title（参考訳）: 非同期動作によるマルチエージェントパス探索のための疎同期ルールベース計画法
• Authors: Shuai Zhou, Shizhe Zhao, Zhongqiang Ren,
• Abstract要約: MAPF(Multi-Agent Path Finding)は、各開始地点から各目標地点まで、複数のエージェントの衝突のない経路を求める。 多くのMAPFアルゴリズムは数千のエージェントを処理できるが、エージェントの各アクションが時間単位を必要とするという仮定に依存している。 本稿では,新たなプランナを開発し,スケーラビリティのためのソリューション品質をトレードオフする。
• 参考スコア（独自算出の注目度）: 5.5233853454863615
• License:
• Abstract: Multi-Agent Path Finding (MAPF) seeks collision-free paths for multiple agents from their respective starting locations to their respective goal locations while minimizing path costs. Although many MAPF algorithms were developed and can handle up to thousands of agents, they usually rely on the assumption that each action of the agent takes a time unit, and the actions of all agents are synchronized in a sense that the actions of agents start at the same discrete time step, which may limit their use in practice. Only a few algorithms were developed to address asynchronous actions, and they all lie on one end of the spectrum, focusing on finding optimal solutions with limited scalability. This paper develops new planners that lie on the other end of the spectrum, trading off solution quality for scalability, by finding an unbounded sub-optimal solution for many agents. Our method leverages both search methods (LSS) in handling asynchronous actions and rule-based planning methods (PIBT) for MAPF. We analyze the properties of our method and test it against several baselines with up to 1000 agents in various maps. Given a runtime limit, our method can handle an order of magnitude more agents than the baselines with about 25% longer makespan.
• Abstract（参考訳）: MAPF(Multi-Agent Path Finding)は、経路コストを最小化しつつ、各開始地点から各目標地点まで、複数のエージェントの衝突のない経路を求める。 多くのMAPFアルゴリズムが開発され、数千のエージェントを処理できるが、エージェントの各アクションが時間単位を取るという仮定に依存し、エージェントのアクションが同じ離散時間ステップで始まるという意味で、エージェントのアクションは同期される。 非同期処理に対処するために開発されたアルゴリズムはごくわずかで、いずれもスペクトルの一端にあり、スケーラビリティに制限のある最適なソリューションを見つけることに重点を置いている。 本稿では,多くのエージェントに対して非有界なサブ最適解を求めることにより,拡張性に対するソリューション品質のトレードオフを図り,スペクトルの反対側に新たなプランナーを開発する。 本手法は,MAPFの非同期動作と規則に基づく計画手法(PIBT)にLSSを併用する。 提案手法の特性を解析し,各地図に最大1000個のエージェントを配置した複数のベースラインに対して検証する。 実行時制限が与えられた場合、我々のメソッドはベースラインよりも桁違いに多くのエージェントを処理できる。

関連論文リスト

• 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)
• DMS*: Minimizing Makespan for Multi-Agent Combinatorial Path Finding [25.756524895372454]
  Multi-Agent Combinatorial Path Finding (MCPF)は、初期から目標地点までの複数のエージェントの衝突のない経路を求める。 最近の研究は、目標における個々の到着時間の総和を最小化しながら、MPPFに対処する方法を開発している。 本稿では,MCPF の min-max 変種である MCPF-max を提案する。
  論文  参考訳（メタデータ） (2023-12-11T11:53:31Z)
• Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
  マルチエージェントパスフィンディングに適したモンテカルロ木探索(MCTS)のオリジナル版を紹介する。 具体的には,エージェントの目標達成行動を支援するために,個別の経路を用いる。 また,木探索手順の分岐係数を低減するために,専用の分解手法を用いる。
  論文  参考訳（メタデータ） (2023-07-25T12:33:53Z)
• ACE: Cooperative Multi-agent Q-learning with Bidirectional Action-Dependency [65.28061634546577]
  マルチエージェント強化学習(MARL)は非定常性問題に悩まされる。 本稿では,双方向行動依存型Q-ラーニング(ACE)を提案する。 ACEは、Google Research FootballとStarCraft Multi-Agent Challengeで最先端のアルゴリズムを上回っている。
  論文  参考訳（メタデータ） (2022-11-29T10:22:55Z)
• Multi-agent Deep Covering Skill Discovery [50.812414209206054]
  本稿では,複数エージェントの結合状態空間の予測被覆時間を最小化し,マルチエージェントオプションを構築するマルチエージェントDeep Covering Option Discoveryを提案する。 また、MARLプロセスにマルチエージェントオプションを採用するための新しいフレームワークを提案する。 提案アルゴリズムは,アテンション機構とエージェントの相互作用を効果的に把握し,マルチエージェントオプションの同定に成功した。
  論文  参考訳（メタデータ） (2022-10-07T00:40:59Z)
• MS*: A New Exact Algorithm for Multi-agent Simultaneous Multi-goal Sequencing and Path Finding [10.354181009277623]
  監視やロジスティクスといったマルチエージェントアプリケーションでは、多数のモバイルエージェントが協調し、多数の目標地点を安全に訪問することがしばしば期待されている。 本稿では、このマルチエージェント問題に対する最適解を計算するMS*と呼ばれる新しいアルゴリズムを紹介します。 計算結果から,提案アルゴリズムは標準ラップトップ上でのCPU時間1分で20エージェント,50ゴールのマルチエージェント問題を解くことができることがわかった。
  論文  参考訳（メタデータ） (2021-03-18T01:57:35Z)
• Loosely Synchronized Search for Multi-agent Path Finding with Asynchronous Actions [10.354181009277623]
  マルチエージェントパス検索(MAPF)は、各開始位置と目標位置の間の複数のエージェントの衝突のないパスのアンサンブルを決定する。 この記事では、エージェントが必ずしも同時に起動および停止しない非同期アクションによるMAPFの自然な一般化を紹介します。
  論文  参考訳（メタデータ） (2021-03-08T02:34:17Z)
• Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints [52.58352707495122]
  本稿では,不確実性およびマルチエージェント協調の下での逐次意思決定における重要な計算課題を分離するマルチロボット割当アルゴリズムを提案する。 都市におけるマルチアームコンベヤベルトピック・アンド・プレイスとマルチドローン配送ディスパッチの2つの異なる領域における広範囲なシミュレーション結果について検証を行った。
  論文  参考訳（メタデータ） (2020-05-27T01:10:41Z)

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

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