論文の概要: Solving Multi-Agent Target Assignment and Path Finding with a Single Constraint Tree

• arxiv url: http://arxiv.org/abs/2307.00663v1
• Date: Sun, 2 Jul 2023 20:52:16 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-05 14:58:53.863039
• Title: Solving Multi-Agent Target Assignment and Path Finding with a Single Constraint Tree
• Title（参考訳）: 単一制約木を用いたマルチエージェントターゲット割り当てと経路探索の解法
• Authors: Yimin Tang, Zhongqiang Ren, Jiaoyang Li, Katia Sycara
• Abstract要約: TAPF(Target-Assignment and Path-Finding problem)とTAPF(Target-Assignment and Path-Finding problem)は、エージェントに同時にターゲットを割り当てることを必要とする。 競合ベースのターゲティング・アサインメント(CBS-TA)は、TAPFに対処するための主要なアプローチである。 我々は,理論上,ITA-CBSは最適解を見つけることが保証され,実際は計算効率が高いことを示す。
• 参考スコア（独自算出の注目度）: 9.523063628118317
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Combined Target-Assignment and Path-Finding problem (TAPF) requires simultaneously assigning targets to agents and planning collision-free paths for agents from their start locations to their assigned targets. As a leading approach to address TAPF, Conflict-Based Search with Target Assignment (CBS-TA) leverages both K-best target assignments to create multiple search trees and Conflict-Based Search (CBS) to resolve collisions in each search tree. While being able to find an optimal solution, CBS-TA suffers from scalability due to the duplicated collision resolution in multiple trees and the expensive computation of K-best assignments. We therefore develop Incremental Target Assignment CBS (ITA-CBS) to bypass these two computational bottlenecks. ITA-CBS generates only a single search tree and avoids computing K-best assignments by incrementally computing new 1-best assignments during the search. We show that, in theory, ITA-CBS is guaranteed to find an optimal solution and, in practice, is computationally efficient.
• Abstract（参考訳）: 目標割り当て問題と経路探索問題(tapf: target-assignment and path-finding problem)は、エージェントに対して同時にターゲットを割り当てることと、エージェントの開始位置から割り当てられたターゲットへの衝突のない経路を計画することである。 TAPFに対処するための主要なアプローチとして、CBS-TA(Conflict-Based Search with Target Assignment)は、K-bestターゲットの割り当てを利用して複数の検索ツリーを作成し、CBS(Conflict-Based Search)は各検索ツリーの衝突を解決する。 最適解を見つけることができる一方で、cbs-taは複数の木で重複する衝突解決とk-best代入の高価な計算のためにスケーラビリティに苦しむ。 そこで我々は,この2つの計算ボトルネックを回避するために,Incremental Target Assignment CBS (ITA-CBS) を開発した。 ITA-CBSは、単一の検索ツリーのみを生成し、検索中に新しい1-bestの割り当てをインクリメンタルに計算することで、K-bestの割り当ての計算を避ける。 我々は,理論上,ITA-CBSは最適解を見つけることが保証され,実際は計算効率が高いことを示す。

関連論文リスト

• Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
  本稿では,バッチ取得のための新しいグリーディ型サブセット選択アルゴリズムを提案する。 赤蛍光タンパク質に関する実験により,提案手法は1.69倍少ないクエリでベースライン性能を達成できることが判明した。
  論文  参考訳（メタデータ） (2024-06-21T05:57:08Z)
• ITA-ECBS: A Bounded-Suboptimal Algorithm for the Combined Target-Assignment and Path-Finding Problem [20.090818762687565]
  ITA-ECBS は ITA-CBS の最初の有界-準最適変種である。 54,033例中87.42%でCBS-TAより高速に動作している。
  論文  参考訳（メタデータ） (2024-04-08T06:36:42Z)
• Optimal Task Assignment and Path Planning using Conflict-Based Search with Precedence and Temporal Constraints [5.265273282482319]
  本稿では,TAPF-PTC問題におけるタスク割り当てと経路探索について検討する。 我々は、競合ベースの検索(CBS)を拡張して、優先度と時間的制約に従うタスク割り当てと衝突のない経路を同時に生成する。 実験により,我々のアルゴリズムであるCBS-TA-PTCは,優先度と時間的制約を効果的に解決できることを示した。
  論文  参考訳（メタデータ） (2024-02-13T20:07:58Z)
• Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
  マルチエージェントパスフィンディングに適したモンテカルロ木探索(MCTS)のオリジナル版を紹介する。 具体的には,エージェントの目標達成行動を支援するために,個別の経路を用いる。 また,木探索手順の分岐係数を低減するために,専用の分解手法を用いる。
  論文  参考訳（メタデータ） (2023-07-25T12:33:53Z)
• TreeDQN: Learning to minimize Branch-and-Bound tree [78.52895577861327]
  Branch-and-Boundは、Mixed Linear Programsという形で最適化タスクを解決するための便利なアプローチである。 解法の効率は、分割する変数を選択するのに使用される分岐に依存する。 分岐を効率的に学習できる強化学習法を提案する。
  論文  参考訳（メタデータ） (2023-06-09T14:01:26Z)
• Optimal Multi-Agent Path Finding for Precedence Constrained Planning Tasks [0.7742297876120561]
  我々は,PC-MAPF (Precedence Constrained Multi-Agent Path Finding) 問題の拡張について検討する。 そこで我々は,PC-CBS (Precedence Constrained Conflict Based Search) という新しいアルゴリズムを提案する。 本アルゴリズムは, 各種倉庫集合体, マルチエージェントピックアップ, 配送タスクに対して性能をベンチマークし, 最近提案された効率的なベースラインのサブ最適性を評価する。
  論文  参考訳（メタデータ） (2022-02-08T07:26:45Z)
• Combined Depth Space based Architecture Search For Person Re-identification [70.86236888223569]
  個人再識別(ReID)のための軽量で適切なネットワークの設計を目指しています。 本研究では,CDNetと呼ばれる効率的なネットワークアーキテクチャの探索に基づく,複合深さ空間(Componed Depth Space, CDS)と呼ばれる新しい検索空間を提案する。 そこで我々はTop-k Sample Search戦略という低コストの検索戦略を提案し、検索空間をフル活用し、局所的な最適結果のトラップを避ける。
  論文  参考訳（メタデータ） (2021-04-09T02:40:01Z)
• Decoupled and Memory-Reinforced Networks: Towards Effective Feature Learning for One-Step Person Search [65.51181219410763]
  歩行者検出と識別サブタスクを1つのネットワークで処理するワンステップ方式を開発しました。 現在のワンステップアプローチには2つの大きな課題があります。 本稿では,これらの問題を解決するために,分離メモリ強化ネットワーク(DMRNet)を提案する。
  論文  参考訳（メタデータ） (2021-02-22T06:19:45Z)
• Multi-objective Conflict-based Search for Multi-agent Path Finding [10.354181009277623]
  マルチオブジェクトパスプランナーは通常、パスの長さなどの単一の目的を最適化しながら、パスのアンサンブルを計算します。 本稿では、マルチオブジェクトコンフリクトベース検索(MO-CBS)という、いわゆる次元の呪いをバイパスする手法を紹介します。
  論文  参考訳（メタデータ） (2021-01-11T10:42:38Z)
• Learning Optimal Tree Models Under Beam Search [27.92120639502327]
  既存のツリーモデルは、トレーニングテストの相違に悩まされている。 我々はビームサーチとキャリブレーションの下でベイズ最適性の概念を開発する。 本稿では,ビームサーチによる最適木モデル学習のための新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-27T17:20:04Z)
• Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints [52.58352707495122]
  本稿では,不確実性およびマルチエージェント協調の下での逐次意思決定における重要な計算課題を分離するマルチロボット割当アルゴリズムを提案する。 都市におけるマルチアームコンベヤベルトピック・アンド・プレイスとマルチドローン配送ディスパッチの2つの異なる領域における広範囲なシミュレーション結果について検証を行った。
  論文  参考訳（メタデータ） (2020-05-27T01:10:41Z)

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

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