Fugu-MT 論文翻訳(概要): Optimal and Bounded-Suboptimal Multi-Goal Task Assignment and Path Finding

論文の概要: Optimal and Bounded-Suboptimal Multi-Goal Task Assignment and Path Finding

arxiv url: http://arxiv.org/abs/2208.01222v1
Date: Tue, 2 Aug 2022 03:17:29 GMT
ステータス: 処理完了
システム内更新日: 2022-08-03 13:37:08.983209
Title: Optimal and Bounded-Suboptimal Multi-Goal Task Assignment and Path Finding
Title（参考訳）: 最適かつ有界な多目的タスク割り当てと経路探索
Authors: Xinyi Zhong, Jiaoyang Li, Sven Koenig, Hang Ma
Abstract要約: 本稿では,多目的タスク割り当てと経路探索(MG-TAPF)問題を理論的およびアルゴリズム的観点から検討する。理論的には、MG-TAPF問題は最適解法としてNPハードであることが証明される。本稿では,多エージェントパス探索問題に対するアルゴリズムに基づくアルゴリズムを提案し,MG-TAPF問題を最適・準最適に解く。
参考スコア（独自算出の注目度）: 25.11387753357413
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We formalize and study the multi-goal task assignment and path finding (MG-TAPF) problem from theoretical and algorithmic perspectives. The MG-TAPF problem is to compute an assignment of tasks to agents, where each task consists of a sequence of goal locations, and collision-free paths for the agents that visit all goal locations of their assigned tasks in sequence. Theoretically, we prove that the MG-TAPF problem is NP-hard to solve optimally. We present algorithms that build upon algorithmic techniques for the multi-agent path finding problem and solve the MG-TAPF problem optimally and bounded-suboptimally. We experimentally compare these algorithms on a variety of different benchmark domains.
Abstract（参考訳）: マルチゴールタスク割り当てと経路探索(mg-tapf)問題を理論的およびアルゴリズム的観点から形式化・検討する。 MG-TAPF問題は、各タスクが一連のゴール位置と、割り当てられたタスクのすべてのゴール位置を順番に訪問するエージェントの衝突のない経路からなるエージェントへのタスクの割り当てを計算することである。理論的には、MG-TAPF問題は最適解法としてNPハードであることが証明される。本稿では,多エージェントパス探索問題に対するアルゴリズムに基づくアルゴリズムを提案し,MG-TAPF問題を最適・準最適に解く。これらのアルゴリズムを様々なベンチマークドメインで実験的に比較する。

関連論文リスト

A Multiagent Path Search Algorithm for Large-Scale Coalition Structure Generation [61.08720171136229]
結合構造生成はマルチエージェントシステムにおける基本的な計算問題である。我々はCSGの多エージェントパス探索アルゴリズムであるSALDAEを開発し、連立構造グラフ上で運用する。
論文参考訳（メタデータ） (2025-02-14T15:21:27Z)
Multi Agent Reinforcement Learning for Sequential Satellite Assignment Problems [5.896440476510869]
割り当て問題は、エージェントのグループをタスクのグループに割り当てる古典的な最適化問題である。衛星、電力網、移動ロボットスケジューリングといった現代の多くの応用において、割り当て問題は時間とともに展開される。この問題にマルチエージェント強化学習を適用し、既知のRL時間グリージーソルバからのブートストラップによる代入値の学習を行う。我々は,本アルゴリズムが理論的に正当化され,他のアルゴリズムが経験した落とし穴を回避することを実証した。
論文参考訳（メタデータ） (2024-12-20T05:10:34Z)
Theoretical Analysis of Quality Diversity Algorithms for a Classical Path Planning Problem [12.1622929638257]
本稿では,古典的計画問題に対する品質多様性(QD)アルゴリズムの挙動について検討する。この結果から,Map-Elites QDアルゴリズムは各ノードの最短経路を並列に計算できることがわかった。
論文参考訳（メタデータ） (2024-12-16T04:58:32Z)
Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
マルチエージェントパスフィンディングに適したモンテカルロ木探索(MCTS)のオリジナル版を紹介する。具体的には,エージェントの目標達成行動を支援するために,個別の経路を用いる。また,木探索手順の分岐係数を低減するために,専用の分解手法を用いる。
論文参考訳（メタデータ） (2023-07-25T12:33:53Z)
MS*: A New Exact Algorithm for Multi-agent Simultaneous Multi-goal Sequencing and Path Finding [10.354181009277623]
監視やロジスティクスといったマルチエージェントアプリケーションでは、多数のモバイルエージェントが協調し、多数の目標地点を安全に訪問することがしばしば期待されている。本稿では、このマルチエージェント問題に対する最適解を計算するMS*と呼ばれる新しいアルゴリズムを紹介します。計算結果から,提案アルゴリズムは標準ラップトップ上でのCPU時間1分で20エージェント,50ゴールのマルチエージェント問題を解くことができることがわかった。
論文参考訳（メタデータ） (2021-03-18T01:57:35Z)
A Two-stage Framework and Reinforcement Learning-based Optimization Algorithms for Complex Scheduling Problems [54.61091936472494]
本稿では、強化学習(RL)と従来の運用研究(OR)アルゴリズムを組み合わせた2段階のフレームワークを開発する。スケジューリング問題は,有限マルコフ決定過程 (MDP) と混合整数計画過程 (mixed-integer programming process) の2段階で解決される。その結果,本アルゴリズムは,アジャイルな地球観測衛星スケジューリング問題に対して,安定かつ効率的に十分なスケジューリング計画を得ることができた。
論文参考訳（メタデータ） (2021-03-10T03:16:12Z)
MAPFAST: A Deep Algorithm Selector for Multi Agent Path Finding using Shortest Path Embeddings [5.506178421979142]
MAPF(Multi-Agent Path Finding)問題を最適に解くことは、make-spanと総到着時間最小化の両方においてNP-Hardであることが知られている。最適なMAPFアルゴリズムは、あらゆる種類の問題でうまく機能し、そのアルゴリズムをいつ使用するかに関する標準ガイドラインは存在しない。我々は、MAPF問題インスタンスを取り込み、アルゴリズムポートフォリオから最も高速なアルゴリズムを選択しようとする、深層畳み込みネットワークMAPFASTを開発した。
論文参考訳（メタデータ） (2021-02-24T18:41:37Z)
Follow the bisector: a simple method for multi-objective optimization [65.83318707752385]
複数の異なる損失を最小化しなければならない最適化問題を考える。提案手法は、各イテレーションにおける降下方向を計算し、目的関数の相対的減少を等しく保証する。
論文参考訳（メタデータ） (2020-07-14T09:50:33Z)
Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints [52.58352707495122]
本稿では,不確実性およびマルチエージェント協調の下での逐次意思決定における重要な計算課題を分離するマルチロボット割当アルゴリズムを提案する。都市におけるマルチアームコンベヤベルトピック・アンド・プレイスとマルチドローン配送ディスパッチの2つの異なる領域における広範囲なシミュレーション結果について検証を行った。
論文参考訳（メタデータ） (2020-05-27T01:10:41Z)
sKPNSGA-II: Knee point based MOEA with self-adaptive angle for Mission Planning Problems [2.191505742658975]
いくつかの問題には、多くの非支配的な解をもたらす多くの目的がある。本稿では,最も重要な解を得るために設計された新しいアルゴリズムを提案する。このアルゴリズムは無人航空機(UAV)ミッション計画問題における実世界の応用に応用されている。
論文参考訳（メタデータ） (2020-02-20T17:07:08Z)
Pareto Multi-Task Learning [53.90732663046125]
マルチタスク学習は複数の相関タスクを同時に解くための強力な方法である。異なるタスクが互いに衝突する可能性があるため、すべてのタスクを最適化するひとつのソリューションを見つけることは、しばしば不可能である。近年,マルチタスク学習を多目的最適化として活用することにより,タスク間のトレードオフが良好である1つのパレート最適解を求める方法が提案されている。
論文参考訳（メタデータ） (2019-12-30T08:58:40Z)

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