論文の概要: MS*: A New Exact Algorithm for Multi-agent Simultaneous Multi-goal
Sequencing and Path Finding
- arxiv url: http://arxiv.org/abs/2103.09979v1
- Date: Thu, 18 Mar 2021 01:57:35 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-19 13:56:03.996020
- Title: MS*: A New Exact Algorithm for Multi-agent Simultaneous Multi-goal
Sequencing and Path Finding
- Title（参考訳）: MS*:マルチエージェント同時マルチゴールシークエンシングとパス探索のための新しいエクササイズアルゴリズム
- Authors: Zhongqiang Ren, Sivakumar Rathinam and Howie Choset
- Abstract要約: 監視やロジスティクスといったマルチエージェントアプリケーションでは、多数のモバイルエージェントが協調し、多数の目標地点を安全に訪問することがしばしば期待されている。
本稿では、このマルチエージェント問題に対する最適解を計算するMS*と呼ばれる新しいアルゴリズムを紹介します。
計算結果から,提案アルゴリズムは標準ラップトップ上でのCPU時間1分で20エージェント,50ゴールのマルチエージェント問題を解くことができることがわかった。
- 参考スコア（独自算出の注目度）: 10.354181009277623
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In multi-agent applications such as surveillance and logistics, fleets of
mobile agents are often expected to coordinate and safely visit a large number
of goal locations as efficiently as possible. The multi-agent planning problem
in these applications involves allocating and sequencing goals for each agent
while simultaneously producing conflict-free paths for the agents. In this
article, we introduce a new algorithm called MS* which computes an optimal
solution for this multi-agent problem by fusing and advancing state of the art
solvers for multi-agent path finding (MAPF) and multiple travelling salesman
problem (mTSP). MS* leverages our prior subdimensional expansion approach for
MAPF and embeds the mTSP solvers to optimally allocate and sequence goals for
agents. Numerical results show that our new algorithm can solve the multi-agent
problem with 20 agents and 50 goals in a minute of CPU time on a standard
laptop.
- Abstract（参考訳）: 監視やロジスティクスといったマルチエージェントアプリケーションでは、多数のモバイルエージェントが協調し、可能な限り多くの目標地点を安全に訪問することが期待されている。
これらのアプリケーションにおけるマルチエージェント計画問題は、エージェントのコンフリクトフリーパスを同時に生成しながら、各エージェントに目標を割り当て、シーケンシングすることである。
本稿では,マルチエージェントパス探索 (mapf) とマルチトラベルセールスマン問題 (mtsp) の解法を融合・発展させることにより,マルチエージェント問題の最適解を求めるms*と呼ばれる新しいアルゴリズムを提案する。
MS*はMAPFに対する我々の以前の部分次元展開アプローチを活用し、mTSPソルバを埋め込んでエージェントの目標を最適に割り当て、シーケンスする。
計算結果から,提案アルゴリズムは標準ラップトップ上でのCPU時間1分で20エージェント,50ゴールのマルチエージェント問題を解くことができることがわかった。
関連論文リスト
- Loosely Synchronized Rule-Based Planning for Multi-Agent Path Finding with Asynchronous Actions [5.5233853454863615]
MAPF(Multi-Agent Path Finding)は、各開始地点から各目標地点まで、複数のエージェントの衝突のない経路を求める。
多くのMAPFアルゴリズムは数千のエージェントを処理できるが、エージェントの各アクションが時間単位を必要とするという仮定に依存している。
本稿では,新たなプランナを開発し,スケーラビリティのためのソリューション品質をトレードオフする。
論文 参考訳（メタデータ） (2024-12-16T11:36:24Z) - Scalable Mechanism Design for Multi-Agent Path Finding [87.40027406028425]
MAPF (Multi-Agent Path Finding) は、複数のエージェントが同時に移動し、与えられた目標地点に向かって共有領域を通って衝突しない経路を決定する。
最適解を見つけることは、しばしば計算不可能であり、近似的な準最適アルゴリズムを用いることが不可欠である。
本稿では、MAPFのスケーラブルな機構設計の問題を紹介し、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) - DMS*: Minimizing Makespan for Multi-Agent Combinatorial Path Finding [25.756524895372454]
Multi-Agent Combinatorial Path Finding (MCPF)は、初期から目標地点までの複数のエージェントの衝突のない経路を求める。
最近の研究は、目標における個々の到着時間の総和を最小化しながら、MPPFに対処する方法を開発している。
本稿では,MCPF の min-max 変種である MCPF-max を提案する。
論文 参考訳（メタデータ） (2023-12-11T11:53:31Z) - A Dynamic LLM-Powered Agent Network for Task-Oriented Agent Collaboration [55.35849138235116]
本稿では,様々なタスクやドメインに対する動的コミュニケーション構造において,候補からエージェントのチームを自動的に選択する手法を提案する。
具体的には, LLMを利用したエージェント協調のための動的LLMパワーエージェントネットワーク(textDyLAN$)というフレームワークを構築した。
我々は、コード生成、意思決定、一般的な推論、算術的推論タスクにおいて、適度な計算コストで、DyLANが強力なベースラインを上回ることを実証する。
論文 参考訳（メタデータ） (2023-10-03T16:05:48Z) - 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) - Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
マルチエージェントパスフィンディングに適したモンテカルロ木探索(MCTS)のオリジナル版を紹介する。
具体的には,エージェントの目標達成行動を支援するために,個別の経路を用いる。
また,木探索手順の分岐係数を低減するために,専用の分解手法を用いる。
論文 参考訳（メタデータ） (2023-07-25T12:33:53Z) - Multi-agent Deep Covering Skill Discovery [50.812414209206054]
本稿では,複数エージェントの結合状態空間の予測被覆時間を最小化し,マルチエージェントオプションを構築するマルチエージェントDeep Covering Option Discoveryを提案する。
また、MARLプロセスにマルチエージェントオプションを採用するための新しいフレームワークを提案する。
提案アルゴリズムは,アテンション機構とエージェントの相互作用を効果的に把握し,マルチエージェントオプションの同定に成功した。
論文 参考訳（メタデータ） (2022-10-07T00:40:59Z) - 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) - Decentralised Approach for Multi Agent Path Finding [6.599344783327053]
MAPF (Multi Agent Path Finding) は、空間的に拡張されたエージェントに対する競合のない経路の同定を必要とする。
これらは、Convoy Movement ProblemやTraning Schedulingといった現実世界の問題に適用できる。
提案手法であるDecentralized Multi Agent Path Finding (DeMAPF) は、MAPFを経路計画と割り当ての問題の系列として扱う。
論文 参考訳（メタデータ） (2021-06-03T18:07:26Z) - Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal
Constraints [52.58352707495122]
本稿では,不確実性およびマルチエージェント協調の下での逐次意思決定における重要な計算課題を分離するマルチロボット割当アルゴリズムを提案する。
都市におけるマルチアームコンベヤベルトピック・アンド・プレイスとマルチドローン配送ディスパッチの2つの異なる領域における広範囲なシミュレーション結果について検証を行った。
論文 参考訳（メタデータ） (2020-05-27T01:10:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。