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問題を最適・準最適に解く。これらのアルゴリズムを様々なベンチマークドメインで実験的に比較する。

関連論文リスト

MGCBS: An Optimal and Efficient Algorithm for Solving Multi-Goal Multi-Agent Path Finding Problem [5.580214316179672]
MG-MAPF問題は、各エージェントが少なくとも1回は衝突することなく、予め割り当てられた複数のゴールポイントを訪問する必要がある。そこで本研究では,単一エージェントパスフィンディング(Single-Adnt pathfinding)とセーフ区間探索(Single-Adnt pathfinding)の分離に基づくMulti-Goal Conflict-Based Search (MGCBS)を提案する。提案手法は, 常に最適な結果を得ることができ, 評価において最先端の手法よりも最大7倍高速に実行することができる。
論文参考訳（メタデータ） (2024-04-30T12:49:54Z)
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 [6.223269541026908]
マルチエージェントパス探索(mapf)問題を最適に解くことは、メイクスパンと全到着時間の最小化の両方においてnpハードであることが知られている。あらゆる種類の問題でうまく機能する最適なMAPFアルゴリズムは存在せず、どのアルゴリズムを使用するかの標準ガイドラインも存在しない。私たちは、MAPF問題インスタンスを取り、アルゴリズムのポートフォリオから使用する最速のアルゴリズムを選択しようとする深い畳み込みネットワークMAPFASTを開発しました。
論文参考訳（メタデータ） (2021-02-24T18:41:37Z)
A Benchmark for Multi-UAV Task Assignment of an Extended Team Orienteering Problem [0.47302336845610055]
異なるアルゴリズムを評価するために,マルチUAVタスク割り当てのベンチマークを示す。拡張されたチームオリエンテーリング問題は、ある種のマルチUAVタスク割り当て問題のためにモデル化される。
論文参考訳（メタデータ） (2020-09-01T11:35: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)
Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
論文参考訳（メタデータ） (2020-01-29T09:40:58Z)
Pareto Multi-Task Learning [53.90732663046125]
マルチタスク学習は複数の相関タスクを同時に解くための強力な方法である。異なるタスクが互いに衝突する可能性があるため、すべてのタスクを最適化するひとつのソリューションを見つけることは、しばしば不可能である。近年,マルチタスク学習を多目的最適化として活用することにより,タスク間のトレードオフが良好である1つのパレート最適解を求める方法が提案されている。
論文参考訳（メタデータ） (2019-12-30T08:58:40Z)

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