論文の概要: Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results

• arxiv url: http://arxiv.org/abs/2307.13453v1
• Date: Tue, 25 Jul 2023 12:33:53 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-26 17:16:32.322763
• Title: Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results
• Title（参考訳）: マルチエージェントパスフィニングのためのモンテカルロ木探索:予備結果
• Authors: Yelisey Pitanov, Alexey Skrynnik, Anton Andreychuk, Konstantin Yakovlev, Aleksandr Panov
• Abstract要約: マルチエージェントパスフィンディングに適したモンテカルロ木探索(MCTS)のオリジナル版を紹介する。 具体的には,エージェントの目標達成行動を支援するために,個別の経路を用いる。 また,木探索手順の分岐係数を低減するために,専用の分解手法を用いる。
• 参考スコア（独自算出の注目度）: 60.4817465598352
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this work we study a well-known and challenging problem of Multi-agent Pathfinding, when a set of agents is confined to a graph, each agent is assigned a unique start and goal vertices and the task is to find a set of collision-free paths (one for each agent) such that each agent reaches its respective goal. We investigate how to utilize Monte-Carlo Tree Search (MCTS) to solve the problem. Although MCTS was shown to demonstrate superior performance in a wide range of problems like playing antagonistic games (e.g. Go, Chess etc.), discovering faster matrix multiplication algorithms etc., its application to the problem at hand was not well studied before. To this end we introduce an original variant of MCTS, tailored to multi-agent pathfinding. The crux of our approach is how the reward, that guides MCTS, is computed. Specifically, we use individual paths to assist the agents with the the goal-reaching behavior, while leaving them freedom to get off the track if it is needed to avoid collisions. We also use a dedicated decomposition technique to reduce the branching factor of the tree search procedure. Empirically we show that the suggested method outperforms the baseline planning algorithm that invokes heuristic search, e.g. A*, at each re-planning step.
• Abstract（参考訳）: 本研究では,エージェントの集合がグラフに限定された場合,各エージェントにユニークな開始点と目標頂点が割り当てられ,各エージェントがそれぞれの目標に達するような衝突のない経路(エージェント毎に1つ)を見つけることが課題である,多エージェントパスフィンディングのよく知られた課題について検討する。 モンテカルロ木探索 (MCTS) を用いてこの問題の解法を検討する。 MCTSは、対戦型ゲーム(例えば、Go、Chessなど)や高速な行列乗算アルゴリズムなどの幅広い問題において優れた性能を示すことが示されているが、その問題に対するその適用は、これまではあまり研究されなかった。 この目的のために,マルチエージェントパスフィンディングに適したMCTSのオリジナル版を導入する。 私たちのアプローチの要点は、mctsを導く報酬がどのように計算されるかです。 具体的には,各経路を用いてエージェントが目標達成行動を行うのを支援すると同時に,衝突を避けるためにトラックを離れる自由を残している。 また,木探索手順の分岐係数を低減するために,専用の分解手法を用いる。 提案手法は,A*などのヒューリスティック探索を行うベースライン計画アルゴリズムよりも,各再計画段階において優れていることを示す。

関連論文リスト

• LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
  本研究では,動的ノード選択とノードレベルの探索予算を備えた新しいガイド付き木探索アルゴリズムを提案する。 GSM8KおよびTabMWPデータセットを用いて行った実験により,本手法はベースライン法に比べて計算コストが大幅に低いことを示した。
  論文  参考訳（メタデータ） (2024-06-29T05:14:04Z)
• 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)
• 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)
• Improved Anonymous Multi-Agent Path Finding Algorithm [3.694001372535405]
  エージェントの集合をグラフに限定する匿名多エージェントパスフィンディング(AMAPF)問題を考える。 我々は,検索空間を探索するアイデアを,個別の検索状態ではなく,一括して考えることによって活用する,特定の検索アルゴリズムを提案する。 その結果、AMAPFソルバは最先端の競合に比べて優れた性能を示し、30秒未満で利用可能なすべてのMAPFインスタンスを解決できる。
  論文  参考訳（メタデータ） (2023-12-17T00:49:30Z)
• 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)
• Multi-Goal Multi-Agent Path Finding via Decoupled and Integrated Goal Vertex Ordering [15.99072005190786]
  本稿では,MAPF問題を一般化したマルチゴールマルチエージェントパス探索法(MAPF$MG$)を提案する。 我々は,MAPF$MG$に対処するために,異なるパラダイムを用いた2つの新しいアルゴリズムを提案する。Hamiltonian-CBS (HCBS) と呼ばれる検索ベース検索アルゴリズムと,SMTパラダイムを用いたコンパイルベースアルゴリズムであるSMT-Hamiltonian-CBS (SMT-HCBS) を提案する。
  論文  参考訳（メタデータ） (2020-09-10T22:27:18Z)
• Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints [52.58352707495122]
  本稿では,不確実性およびマルチエージェント協調の下での逐次意思決定における重要な計算課題を分離するマルチロボット割当アルゴリズムを提案する。 都市におけるマルチアームコンベヤベルトピック・アンド・プレイスとマルチドローン配送ディスパッチの2つの異なる領域における広範囲なシミュレーション結果について検証を行った。
  論文  参考訳（メタデータ） (2020-05-27T01:10:41Z)

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

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