論文の概要: MGCBS: An Optimal and Efficient Algorithm for Solving Multi-Goal Multi-Agent Path Finding Problem

• arxiv url: http://arxiv.org/abs/2404.19518v1
• Date: Tue, 30 Apr 2024 12:49:54 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-01 14:15:27.625952
• Title: MGCBS: An Optimal and Efficient Algorithm for Solving Multi-Goal Multi-Agent Path Finding Problem
• Title（参考訳）: MGCBS:多目的多元経路探索問題の最適かつ効率的な解法
• Authors: Mingkai Tang, Yuanhang Li, Hongji Liu, Yingbing Chen, Ming Liu, Lujia Wang,
• Abstract要約: MG-MAPF問題は、各エージェントが少なくとも1回は衝突することなく、予め割り当てられた複数のゴールポイントを訪問する必要がある。 そこで本研究では,単一エージェントパスフィンディング(Single-Adnt pathfinding)とセーフ区間探索(Single-Adnt pathfinding)の分離に基づくMulti-Goal Conflict-Based Search (MGCBS)を提案する。 提案手法は, 常に最適な結果を得ることができ, 評価において最先端の手法よりも最大7倍高速に実行することができる。
• 参考スコア（独自算出の注目度）: 5.580214316179672
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: With the expansion of the scale of robotics applications, the multi-goal multi-agent pathfinding (MG-MAPF) problem began to gain widespread attention. This problem requires each agent to visit pre-assigned multiple goal points at least once without conflict. Some previous methods have been proposed to solve the MG-MAPF problem based on Decoupling the goal Vertex visiting order search and the Single-agent pathfinding (DVS). However, this paper demonstrates that the methods based on DVS cannot always obtain the optimal solution. To obtain the optimal result, we propose the Multi-Goal Conflict-Based Search (MGCBS), which is based on Decoupling the goal Safe interval visiting order search and the Single-agent pathfinding (DSS). Additionally, we present the Time-Interval-Space Forest (TIS Forest) to enhance the efficiency of MGCBS by maintaining the shortest paths from any start point at any start time step to each safe interval at the goal points. The experiment demonstrates that our method can consistently obtain optimal results and execute up to 7 times faster than the state-of-the-art method in our evaluation.
• Abstract（参考訳）: ロボット工学応用の規模が拡大するにつれ、MG-MAPF(multi-goal multi-agent pathfinding)問題に注目が集まるようになった。 この問題は各エージェントが、少なくとも1回は衝突することなく、事前に割り当てられた複数のゴールポイントを訪問する必要がある。 目的のVertex訪問順序探索とシングルエージェントパスフィンディング(DVS)に基づくMG-MAPF問題の解法が提案されている。 しかし,本稿はDVSに基づく手法が常に最適解を得ることができないことを示す。 最適結果を得るため,目的の安全区間訪問順序探索と単一エージェントパスフィンディング(DSS)を分離したMulti-Goal Conflict-Based Search (MGCBS)を提案する。 さらに,TISフォレスト(Time-Interval-Space Forest, TISフォレスト)を,任意の開始時点から目標地点の各安全区間までの最短経路を維持することにより,MGCBSの効率を向上させる。 実験により,本手法は最適結果が常に得られ,評価において最先端の手法よりも最大7倍高速に実行可能であることが示された。

関連論文リスト

• Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
  本稿では,バッチ取得のための新しいグリーディ型サブセット選択アルゴリズムを提案する。 赤蛍光タンパク質に関する実験により,提案手法は1.69倍少ないクエリでベースライン性能を達成できることが判明した。
  論文  参考訳（メタデータ） (2024-06-21T05:57:08Z)
• UCB-driven Utility Function Search for Multi-objective Reinforcement Learning [75.11267478778295]
  マルチオブジェクト強化学習(MORL)エージェントでは、意思決定行動の最適化を行う。 重みベクトル w でパラメータ化される線型効用関数の場合に焦点を当てる。 学習過程の異なる段階で最も有望な重みベクトルを効率的に探索する上信頼境界に基づく手法を提案する。
  論文  参考訳（メタデータ） (2024-05-01T09:34:42Z)
• 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)
• Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
  マルチエージェントパスフィンディングに適したモンテカルロ木探索(MCTS)のオリジナル版を紹介する。 具体的には,エージェントの目標達成行動を支援するために,個別の経路を用いる。 また,木探索手順の分岐係数を低減するために,専用の分解手法を用いる。
  論文  参考訳（メタデータ） (2023-07-25T12:33:53Z)
• Multi-objective Conflict-based Search Using Safe-interval Path Planning [10.354181009277623]
  低レベル探索のための新しい多目的セーフインターバルパス計画法 (MO-SIPP) アルゴリズムを利用するMO-CBS(Multi-objective conflict-based search)を提案する。 我々は, 平均低レベル探索時間において, 等級が大幅に改善されていることを示すために, 広範囲な数値計算結果を示す。 また,建設現場計画における提案アルゴリズムの適用可能性を示すケーススタディも提示する。
  論文  参考訳（メタデータ） (2021-08-02T09:42:08Z)
• Loosely Synchronized Search for Multi-agent Path Finding with Asynchronous Actions [10.354181009277623]
  マルチエージェントパス検索(MAPF)は、各開始位置と目標位置の間の複数のエージェントの衝突のないパスのアンサンブルを決定する。 この記事では、エージェントが必ずしも同時に起動および停止しない非同期アクションによるMAPFの自然な一般化を紹介します。
  論文  参考訳（メタデータ） (2021-03-08T02:34:17Z)
• Multi-objective Conflict-based Search for Multi-agent Path Finding [10.354181009277623]
  マルチオブジェクトパスプランナーは通常、パスの長さなどの単一の目的を最適化しながら、パスのアンサンブルを計算します。 本稿では、マルチオブジェクトコンフリクトベース検索(MO-CBS)という、いわゆる次元の呪いをバイパスする手法を紹介します。
  論文  参考訳（メタデータ） (2021-01-11T10:42:38Z)
• 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)

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

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