論文の概要: ITA-ECBS: A Bounded-Suboptimal Algorithm for Combined Target-Assignment and Path-Finding Problem

• arxiv url: http://arxiv.org/abs/2404.05223v1
• Date: Mon, 8 Apr 2024 06:36:42 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-09 15:23:43.571675
• Title: ITA-ECBS: A Bounded-Suboptimal Algorithm for Combined Target-Assignment and Path-Finding Problem
• Title（参考訳）: ITA-ECBS: 目標割り当てと経路フィンディングを併用した境界下最適化アルゴリズム
• Authors: Yimin Tang, Sven Koenig, Jiaoyang Li,
• Abstract要約: ITA-ECBS を ITA-CBS の最初の有界-準最適変種として紹介する。 ITA-ECBSは,54,033例中87.42%でベースライン法であるCBS-TAよりも優れていた。
• 参考スコア（独自算出の注目度）: 20.090818762687565
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Multi-Agent Path Finding (MAPF), i.e., finding collision-free paths for multiple robots, plays a critical role in many applications. Sometimes, assigning a specific target to each agent also presents a challenge. The Combined Target-Assignment and Path-Finding (TAPF) problem, a variant of MAPF, requires simultaneously assigning targets to agents and planning collision-free paths. Several algorithms, including CBM, CBS-TA, and ITA-CBS, can optimally solve the TAPF problem, with ITA-CBS being the leading method of flowtime. However, the only existing suboptimal method ECBS-TA, is derived from CBS-TA rather than ITA-CBS, and adapting the optimal ITA-CBS method to its bounded-suboptimal variant is a challenge due to the variability of target assignment solutions in different search nodes. We introduce ITA-ECBS as the first bounded-suboptimal variant of ITA-CBS. ITA-ECBS employs focal search to enhance efficiency and determines target assignments based on a new lower bound matrix. We show that ITA-ECBS outperforms the baseline method ECBS-TA in 87.42% of 54,033 test cases.
• Abstract（参考訳）: マルチエージェントパス探索(MAPF, Multi-Agent Path Finding)とは、複数のロボットの衝突のない経路を見つけることであり、多くのアプリケーションにおいて重要な役割を果たす。 特定のターゲットを各エージェントに割り当てる場合もあります。 MAPFの変種であるTAPF(Combined Target-Assignment and Path-Finding)問題では、エージェントに同時にターゲットを割り当て、衝突のない経路を計画する必要がある。 CBM、CBS-TA、ITA-CBSを含むいくつかのアルゴリズムは、TAPF問題を最適に解くことができ、ITA-CBSがフロータイムの主要な方法である。 しかし, ITA-CBS ではなく CBS-TA から派生した唯一のサブ最適化手法である ECBS-TA は, 最適な ITA-CBS 法を有界-準最適変種に適応させることは, 異なる探索ノードにおけるターゲット割り当て解のばらつきのため, 課題である。 ITA-ECBS を ITA-CBS の最初の有界-準最適変種として紹介する。 ITA-ECBSは、効率を高めるために焦点探索を使用し、新しい下界行列に基づいて目標割り当てを決定する。 ITA-ECBSは,54,033例中87.42%でベースライン法であるCBS-TAよりも優れていた。

関連論文リスト

• 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)
• Solving Multi-Agent Target Assignment and Path Finding with a Single Constraint Tree [9.518757918128799]
  TAPF(Target-Assignment and Path-Finding problem)とTAPF(Target-Assignment and Path-Finding problem)は、エージェントに同時にターゲットを割り当てることを必要とする。 競合ベースのターゲティング・アサインメント(CBS-TA)は、TAPFに対処するための主要なアプローチである。 我々は,理論上,ITA-CBSは最適解を見つけることが保証され,実際は計算効率が高いことを示す。
  論文  参考訳（メタデータ） (2023-07-02T20:52:16Z)
• Patch-aware Batch Normalization for Improving Cross-domain Robustness [55.06956781674986]
  クロスドメインタスクは、トレーニングセットとテストセットが異なるディストリビューションに従うと、モデルのパフォーマンスが低下する課題を示す。 パッチ対応バッチ正規化(PBN)と呼ばれる新しい手法を提案する。 画像の局所的なパッチの違いを利用して、提案したPBNはモデルパラメータの堅牢性を効果的に向上させることができる。
  論文  参考訳（メタデータ） (2023-04-06T03:25:42Z)
• Analysis Of The Anytime MAPF Solvers Based On The Combination Of Conflict-Based Search (CBS) and Focal Search (FS) [2.320417845168326]
  競合ベースの探索 (CBS) は多エージェントパスフィンディング問題を最適に解くために広く用いられているアルゴリズムである。 CBSのバウンテッド・サブ最適の異なる変種を走らせるためのトレードオフ最適性を設計した。 CBSの双方のレベルのFocal Searchは、幅広いセットアップにおいて有益であることを示す。
  論文  参考訳（メタデータ） (2022-09-20T11:05:14Z)
• $\beta$-DARTS: Beta-Decay Regularization for Differentiable Architecture Search [85.84110365657455]
  本研究では,DARTSに基づくNAS探索過程を正規化するために,ベータデカイと呼ばれるシンプルだが効率的な正規化手法を提案する。 NAS-Bench-201の実験結果から,提案手法は探索過程の安定化に有効であり,探索されたネットワークを異なるデータセット間で転送しやすくする。
  論文  参考訳（メタデータ） (2022-03-03T11:47:14Z)
• Improving Continuous-time Conflict Based Search [19.36475688888736]
  Conflict-Based Search (CBS) はマルチエージェントパス探索 (MAPF) 問題を最適に解くための強力なフレームワークである。 Continuous-time CBS(CCBS)は、CBSの最近提案されたバージョンで、時間を差別することなく最適なソリューションを保証します。 コンフリクト(PC)、ディジョイン分割(DS)、ハイレベルエージェントをCCBSの連続時間設定に優先順位付けすることで、CBSの改善を成功させる方法を紹介します。
  論文  参考訳（メタデータ） (2021-01-24T14:34:25Z)
• EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding [40.0986954496361]
  明示的推定CBS(英: Explicit Estimation CBS、英: Explicit Estimation CBS)は、オンライン学習を用いて、各ハイレベルノードのソリューションのコストの不可避な推定値を得る、制限付き最適化型CBSである。 EECBSは、さまざまなMAPFインスタンス上で、最先端の有界MAPFアルゴリズムであるECBS、BCP-7、eMDD-SATよりもはるかに高速に動作する。
  論文  参考訳（メタデータ） (2020-10-03T14:19:00Z)
• Multi Agent Path Finding with Awareness for Spatially Extended Agents [0.5156484100374058]
  経路発見問題は、共通の道路ネットワーク上のエージェントの衝突のない移動計画を特定することを含む。 本稿では,走行する道路の長さに匹敵する大きさの空間拡張剤について検討する。 eXtended Conflict Based Search (XCBS)アルゴリズムにおいて,空間拡張エージェントに対する最適マルチエージェントパス探索手法を提案した。
  論文  参考訳（メタデータ） (2020-09-20T05:40:04Z)
• Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints [52.58352707495122]
  本稿では,不確実性およびマルチエージェント協調の下での逐次意思決定における重要な計算課題を分離するマルチロボット割当アルゴリズムを提案する。 都市におけるマルチアームコンベヤベルトピック・アンド・プレイスとマルチドローン配送ディスパッチの2つの異なる領域における広範囲なシミュレーション結果について検証を行った。
  論文  参考訳（メタデータ） (2020-05-27T01:10:41Z)

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

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