論文の概要: ITA-ECBS: A Bounded-Suboptimal Algorithm for the Combined Target-Assignment and Path-Finding Problem
- arxiv url: http://arxiv.org/abs/2404.05223v2
- Date: Sun, 21 Apr 2024 09:55:23 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-23 22:45:14.656655
- Title: ITA-ECBS: A Bounded-Suboptimal Algorithm for the Combined Target-Assignment and Path-Finding Problem
- Title（参考訳）: ITA-ECBS: 目標割り当てと経路フィンディングの併用問題に対する境界下最適化アルゴリズム
- Authors: Yimin Tang, Sven Koenig, Jiaoyang Li,
- Abstract要約: ITA-ECBS は ITA-CBS の最初の有界-準最適変種である。
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 target to each agent also presents a challenge. The Combined Target-Assignment and Path-Finding (TAPF) problem, a variant of MAPF, requires one to simultaneously assign targets to agents and plan collision-free paths for agents. Several algorithms, including CBM, CBS-TA, and ITA-CBS, optimally solve the TAPF problem, with ITA-CBS being the leading algorithm for minimizing flowtime. However, the only existing bounded-suboptimal algorithm ECBS-TA is derived from CBS-TA rather than ITA-CBS. So, it faces the same issues as CBS-TA, such as searching through multiple constraint trees and spending too much time on finding the next-best target assignment. We introduce ITA-ECBS, the first bounded-suboptimal variant of ITA-CBS. Transforming ITA-CBS to its bounded-suboptimal variant is challenging because different constraint tree nodes can have different assignments of targets to agents. ITA-ECBS uses focal search to achieve efficiency and determines target assignments based on a new lower bound matrix. We show that it runs faster than 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はフロータイムを最小化する主要なアルゴリズムである。
しかし、既存の有界-準最適化アルゴリズム ECBS-TA は ITA-CBS ではなく CBS-TA から派生している。
そのため、CBS-TAと同じ問題に直面している。複数の制約木を探索したり、次のベストターゲットを見つけるのに多くの時間を費やすなどだ。
ITA-ECBS は ITA-CBS の最初の有界-準最適変種である。
ITA-CBSをその有界-準最適変種に変換することは、異なる制約ツリーノードが異なるターゲットをエージェントに割り当てることができるため、困難である。
ITA-ECBSは、焦点探索を用いて効率を向上し、新しい下界行列に基づいて目標割り当てを決定する。
54,033例中87.42%でCBS-TAより高速に動作している。
関連論文リスト
- A Multiagent Path Search Algorithm for Large-Scale Coalition Structure Generation [61.08720171136229]
結合構造生成はマルチエージェントシステムにおける基本的な計算問題である。
我々はCSGの多エージェントパス探索アルゴリズムであるSALDAEを開発し、連立構造グラフ上で運用する。
論文 参考訳（メタデータ） (2025-02-14T15:21:27Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。