論文の概要: Adaptive Anytime Multi-Agent Path Finding Using Bandit-Based Large
Neighborhood Search
- arxiv url: http://arxiv.org/abs/2312.16767v2
- Date: Mon, 1 Jan 2024 13:43:52 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-02 19:55:41.292228
- Title: Adaptive Anytime Multi-Agent Path Finding Using Bandit-Based Large
Neighborhood Search
- Title(参考訳): Bandit-based Large Neborhood Search を用いた適応型任意のマルチエージェント経路探索
- Authors: Thomy Phan, Taoan Huang, Bistra Dilkina, Sven Koenig
- Abstract要約: MAPFはLarge Neborhood Search(LNS)に基づいている
探索を併用したBandit-based Adaptive LArge Neighborhood Search(BALANCE)を提案する。
大規模シナリオでは、最先端のMAPFと比較して、少なくとも50%のコスト改善が実証的に実証されている。
- 参考スコア(独自算出の注目度): 30.364955687049292
- 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 large-scale multi-agent systems. State-of-the-art anytime
MAPF is based on Large Neighborhood Search (LNS), where a fast initial solution
is iteratively optimized by destroying and repairing a fixed number of parts,
i.e., the neighborhood, of the solution, using randomized destroy heuristics
and prioritized planning. Despite their recent success in various MAPF
instances, current LNS-based approaches lack exploration and flexibility due to
greedy optimization with a fixed neighborhood size which can lead to low
quality solutions in general. So far, these limitations have been addressed
with extensive prior effort in tuning or offline machine learning beyond actual
planning. In this paper, we focus on online learning in LNS and propose
Bandit-based Adaptive LArge Neighborhood search Combined with Exploration
(BALANCE). BALANCE uses a bi-level multi-armed bandit scheme to adapt the
selection of destroy heuristics and neighborhood sizes on the fly during
search. We evaluate BALANCE on multiple maps from the MAPF benchmark set and
empirically demonstrate cost improvements of at least 50% compared to
state-of-the-art anytime MAPF in large-scale scenarios. We find that Thompson
Sampling performs particularly well compared to alternative multi-armed bandit
algorithms.
- Abstract(参考訳): anytime multi-agent path finding (mapf) は大規模マルチエージェントシステムにおけるスケーラブルパス最適化への有望なアプローチである。
MAPFはLarge Neighborhood Search (LNS)に基づいており、高速な初期解は、ランダム化された破壊ヒューリスティック(英語版)と優先順位付けされた計画を用いて、一定数の部品を破壊・修復することで反復的に最適化される。
近年のMAPFインスタンスの成功にもかかわらず、現在のLSSベースのアプローチでは探索と柔軟性が欠如している。
これまでのところ、これらの制限は、実際の計画を超えて、チューニングやオフラインの機械学習に先立って取り組まれてきた。
本稿では,LNSにおけるオンライン学習に着目し,BALANCE(Adaptive LArge Neighborhood Search with Exploration)を提案する。
BALANCEは、二段式マルチアームバンディットスキームを使用して、探索中のフライ時の破壊ヒューリスティックと近傍サイズの選択に適応する。
我々はMAPFベンチマークセットから複数の地図上でのBALANCEを評価し、大規模シナリオにおける最先端のMAPFと比較して、少なくとも50%のコスト改善を実証的に実証した。
我々は、トンプソンサンプリングが、代替のマルチアームバンディットアルゴリズムと比較して特に優れていることを発見した。
関連論文リスト
- Multimodal Learned Sparse Retrieval with Probabilistic Expansion Control [66.78146440275093]
学習検索(LSR)は、クエリとドキュメントを疎語彙ベクトルにエンコードするニューラルネットワークのファミリーである。
テキスト画像検索に焦点をあて,マルチモーダル領域へのLSRの適用について検討する。
LexLIPやSTAIRのような現在のアプローチでは、大規模なデータセットで複雑なマルチステップのトレーニングが必要です。
提案手法は, 密度ベクトルを凍結密度モデルからスパース語彙ベクトルへ効率的に変換する。
論文 参考訳(メタデータ) (2024-02-27T14:21:56Z) - Scalable Mechanism Design for Multi-Agent Path Finding [90.68703851865585]
MAPF (Multi-Agent Path Finding) は、複数のエージェントが特定の目標地点に向かって共有領域を同時に移動するための経路を決定する。
最適解を見つけることは、しばしば計算不可能であり、近似アルゴリズムを用いることが不可欠である。
本稿では,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) - 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) - LaCAM: Search-Based Algorithm for Quick Multi-Agent Pathfinding [5.025654873456756]
MAPF(LaCAM)の遅延制約付加探索という,マルチエージェントパスフィンディング(MAPF)のための新しい完全アルゴリズムを提案する。
LaCAMは2段階の検索を使って、何百ものエージェントでも素早くソリューションを見つける。
実験の結果,LaCAMは様々なシナリオにおいて最先端のMAPFアルゴリズムに匹敵する,あるいは優れることがわかった。
論文 参考訳(メタデータ) (2022-11-24T06:27:18Z) - Multi-Goal Multi-Agent Pickup and Delivery [25.11387753357413]
我々は、エージェントが常に新しいタスクに取り組み、それらを実行するために衝突のない経路を計画する必要がある、マルチエージェントピックアップ・アンド・デリバリ(MAPD)問題を考える。
我々は、任意のアルゴリズムLNS(Large Neighborhood Search)を用いて各エージェントにタスク列を割り当てるアルゴリズムの2つの変種を提案し、MAPF(Multi-Agent Path Finding)アルゴリズム(PBS)を用いて経路を計画する。
LNS-PBS は MAPD インスタンスの現実的なサブクラスである MAPD インスタンスに対して完全であり、既存の完全 MAPD アルゴリズム CENTRAL よりも経験的に有効である。
LN
論文 参考訳(メタデータ) (2022-08-02T03:20:59Z) - Reinforcement Learning for Branch-and-Bound Optimisation using
Retrospective Trajectories [72.15369769265398]
機械学習は分岐のための有望なパラダイムとして登場した。
分岐のための単純かつ効果的なRLアプローチであるレトロ分岐を提案する。
我々は現在最先端のRL分岐アルゴリズムを3~5倍に上回り、500の制約と1000の変数を持つMILP上での最高のILメソッドの性能の20%以内である。
論文 参考訳(メタデータ) (2022-05-28T06:08:07Z) - Learning Space Partitions for Path Planning [54.475949279050596]
PlaLaMは2次元ナビゲーションタスクにおける既存の経路計画手法よりも優れており、特に難解な局所最適化の存在下では優れている。
これらは高マルチモーダルな実世界のタスクに移行し、コンパイラフェーズでは最大245%、分子設計では最大0.4の強いベースラインを0-1スケールで上回ります。
論文 参考訳(メタデータ) (2021-06-19T18:06:11Z) - The Surprising Effectiveness of MAPPO in Cooperative, Multi-Agent Games [67.47961797770249]
マルチエージェントPPO(MAPPO)は、集中型値関数を採用するマルチエージェントPPOバリアントである。
MAPPOは,3つの一般的なマルチエージェントテストベッドにおいて,最先端技術に匹敵する性能を実現していることを示す。
論文 参考訳(メタデータ) (2021-03-02T18:59:56Z) - MAPFAST: A Deep Algorithm Selector for Multi Agent Path Finding using
Shortest Path Embeddings [6.223269541026908]
マルチエージェントパス探索(mapf)問題を最適に解くことは、メイクスパンと全到着時間の最小化の両方においてnpハードであることが知られている。
あらゆる種類の問題でうまく機能する最適なMAPFアルゴリズムは存在せず、どのアルゴリズムを使用するかの標準ガイドラインも存在しない。
私たちは、MAPF問題インスタンスを取り、アルゴリズムのポートフォリオから使用する最速のアルゴリズムを選択しようとする深い畳み込みネットワークMAPFASTを開発しました。
論文 参考訳(メタデータ) (2021-02-24T18:41:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。