論文の概要: Anytime Multi-Agent Path Finding with an Adaptive Delay-Based Heuristic
- arxiv url: http://arxiv.org/abs/2408.02960v1
- Date: Tue, 6 Aug 2024 05:15:35 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-07 14:59:44.446745
- Title: Anytime Multi-Agent Path Finding with an Adaptive Delay-Based Heuristic
- Title（参考訳）: 適応的遅延に基づくヒューリスティックによる任意のマルチエージェントパス検出
- Authors: Thomy Phan, Benran Zhang, Shao-Hung Chan, Sven Koenig,
- Abstract要約: MAPF-LNSの単一破壊ヒューリスティックな変種として,Adaptive Delay-based Destroy-and-Repair with Enhanced Success-based Self-Learning (ADDRESS)を提案する。
我々は,1000エージェントまでの大規模シナリオにおいて,MAPF-LNSと比較して,少なくとも50%のコスト改善を実証した。
- 参考スコア（独自算出の注目度）: 16.4408116214332
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Anytime multi-agent path finding (MAPF) is a promising approach to scalable path optimization in multi-agent systems. MAPF-LNS, based on Large Neighborhood Search (LNS), is the current state-of-the-art approach where a fast initial solution is iteratively optimized by destroying and repairing selected paths of the solution. Current MAPF-LNS variants commonly use an adaptive selection mechanism to choose among multiple destroy heuristics. However, to determine promising destroy heuristics, MAPF-LNS requires a considerable amount of exploration time. As common destroy heuristics are non-adaptive, any performance bottleneck caused by these heuristics cannot be overcome via adaptive heuristic selection alone, thus limiting the overall effectiveness of MAPF-LNS in terms of solution cost. In this paper, we propose Adaptive Delay-based Destroy-and-Repair Enhanced with Success-based Self-Learning (ADDRESS) as a single-destroy-heuristic variant of MAPF-LNS. ADDRESS applies restricted Thompson Sampling to the top-K set of the most delayed agents to select a seed agent for adaptive LNS neighborhood generation. We evaluate ADDRESS in multiple maps from the MAPF benchmark set and demonstrate cost improvements by at least 50% in large-scale scenarios with up to a thousand agents, compared with the original MAPF-LNS and other state-of-the-art methods.
- Abstract（参考訳）: Anytime Multi-Adnt Path Finding (MAPF) はマルチエージェントシステムにおけるスケーラブルパス最適化への有望なアプローチである。
MAPF-LNSはLarge Neborhood Search (LNS)に基づいており、高速初期解を反復的に最適化し、選択した経路を破壊・修復する手法である。
現在のMAPF-LNS変種は、適応的な選択機構を用いて複数の破壊ヒューリスティックを選択する。
しかし、有望な破壊ヒューリスティックスを決定するためには、MAPF-LNSは相当な時間を要する。
一般的な破壊ヒューリスティックは適応的ではないため、これらのヒューリスティックによって引き起こされるパフォーマンスボトルネックは、適応ヒューリスティック選択だけでは克服できないため、ソリューションコストの観点からMAPF-LNSの全体的な有効性を制限することができる。
本稿では,MAPF-LNSの単一デストロジヒューリスティック変種として,adaptive Delay-based Destroy-and-Repair Enhanced with Success-based Self-Learning (ADDRESS)を提案する。
ADDRESSは制限されたトンプソンサンプリングを最も遅延したエージェントのトップK集合に適用し、適応的なLSN近傍生成のためのシードエージェントを選択する。
我々は、MAPFベンチマークセットから複数の地図でADDRESSを評価し、1000エージェントまでの大規模シナリオにおいて、従来のMAPF-LNSや他の最先端手法と比較して、少なくとも50%のコスト改善を実証した。
関連論文リスト
- Provably Mitigating Overoptimization in RLHF: Your SFT Loss is Implicitly an Adversarial Regularizer [52.09480867526656]
人間の嗜好を学習する際の分布変化と不確実性の一形態として,不一致の原因を同定する。
過度な最適化を緩和するために、まず、逆選択された報酬モデルに最適なポリシーを選択する理論アルゴリズムを提案する。
報奨モデルとそれに対応する最適ポリシーの等価性を用いて、優先最適化損失と教師付き学習損失を組み合わせた単純な目的を特徴とする。
論文 参考訳（メタデータ） (2024-05-26T05:38:50Z) - Scalable Mechanism Design for Multi-Agent Path Finding [87.40027406028425]
MAPF (Multi-Agent Path Finding) は、複数のエージェントが同時に移動し、与えられた目標地点に向かって共有領域を通って衝突しない経路を決定する。
最適解を見つけることは、しばしば計算不可能であり、近似的な準最適アルゴリズムを用いることが不可欠である。
本稿では、MAPFのスケーラブルな機構設計の問題を紹介し、MAPFアルゴリズムを近似した3つの戦略防御機構を提案する。
論文 参考訳（メタデータ） (2024-01-30T14:26:04Z) - Adaptive Anytime Multi-Agent Path Finding Using Bandit-Based Large
Neighborhood Search [30.364955687049292]
MAPFはLarge Neborhood Search(LNS)に基づいている
探索を併用したBandit-based Adaptive LArge Neighborhood Search(BALANCE)を提案する。
大規模シナリオでは、最先端のMAPFと比較して、少なくとも50%のコスト改善が実証的に実証されている。
論文 参考訳（メタデータ） (2023-12-28T01:24:42Z) - Decentralized Monte Carlo Tree Search for Partially Observable
Multi-agent Pathfinding [49.730902939565986]
マルチエージェントパスフィンディング問題は、グラフに閉じ込められたエージェントのグループに対するコンフリクトフリーパスのセットを見つけることである。
本研究では、エージェントが他のエージェントをローカルにのみ観察できる分散MAPF設定に焦点を当てた。
MAPFタスクのための分散マルチエージェントモンテカルロ木探索法を提案する。
論文 参考訳（メタデータ） (2023-12-26T06:57:22Z) - Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding [29.76466191644455]
MAPF(Multi-Agent Path Finding)は、ロボット工学における基本的な問題であり、エージェントのチームに対して衝突のない経路の計算を求める。
本稿では,MAPFにエージェントを誘導する手法を提案する。
各エージェントが1つの宛先を持つワンショットMAPFと、エージェントが常に新しい宛先を割り当てる終身MAPFの2つの大規模設定でこのアイデアを評価する。
論文 参考訳（メタデータ） (2023-08-22T07:17:39Z) - Engineering LaCAM$^\ast$: Towards Real-Time, Large-Scale, and
Near-Optimal Multi-Agent Pathfinding [12.02023514105999]
本稿では,最近提案されたLaCAM*アルゴリズムの改良を通じて,リアルタイム,大規模,準最適マルチエージェントパスフィンディング(MAPF)の課題に対処する。
LaCAM*はスケーラブルな検索ベースのアルゴリズムであり、累積遷移コストに対する最適解の最終的な発見を保証する。
論文 参考訳（メタデータ） (2023-08-08T14:36:58Z) - Multi-Agent Reinforcement Learning via Adaptive Kalman Temporal
Difference and Successor Representation [32.80370188601152]
本稿では,マルチエージェント適応カルマン時間差分(MAK-TD)フレームワークとその継承表現に基づく変種(MAK-SR)を提案する。
提案するMAK-TD/SRフレームワークは,高次元マルチエージェント環境に関連付けられたアクション空間の連続的な性質を考察する。
論文 参考訳（メタデータ） (2021-12-30T18:21:53Z) - Automatic Mapping of the Best-Suited DNN Pruning Schemes for Real-Time
Mobile Acceleration [71.80326738527734]
本稿では,汎用的,きめ細かな構造化プルーニング手法とコンパイラの最適化を提案する。
提案手法は,より微細な構造化プルーニング手法とともに,最先端のDNN最適化フレームワークよりも優れていることを示す。
論文 参考訳（メタデータ） (2021-11-22T23:53:14Z) - Plan Better Amid Conservatism: Offline Multi-Agent Reinforcement
Learning with Actor Rectification [74.10976684469435]
オフライン強化学習(RL)アルゴリズムは、直接マルチエージェント設定に転送することができる。
本稿では,この重要な課題に対処するために,Actor Rectification (OMAR) を用いたオフラインマルチエージェント RL を提案する。
OMARはマルチエージェント連続制御ベンチマークにおける最先端性能と強いベースラインを著しく上回る。
論文 参考訳（メタデータ） (2021-11-22T13:27:42Z) - RoMA: Robust Model Adaptation for Offline Model-based Optimization [115.02677045518692]
入力出力クエリの静的データセットからブラックボックス目的関数を最大化する入力を探索する問題を考える。
この問題を解決するための一般的なアプローチは、真の客観的関数を近似するプロキシモデルを維持することである。
ここでの大きな課題は、検索中に逆最適化された入力を避ける方法である。
論文 参考訳（メタデータ） (2021-10-27T05:37:12Z) - Loosely Synchronized Search for Multi-agent Path Finding with
Asynchronous Actions [10.354181009277623]
マルチエージェントパス検索(MAPF)は、各開始位置と目標位置の間の複数のエージェントの衝突のないパスのアンサンブルを決定する。
この記事では、エージェントが必ずしも同時に起動および停止しない非同期アクションによるMAPFの自然な一般化を紹介します。
論文 参考訳（メタデータ） (2021-03-08T02:34:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。