論文の概要: Extending the Multiple Traveling Salesman Problem for Scheduling a Fleet
of Drones Performing Monitoring Missions
- arxiv url: http://arxiv.org/abs/2006.01473v1
- Date: Tue, 2 Jun 2020 09:17:18 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-26 00:28:26.605024
- Title: Extending the Multiple Traveling Salesman Problem for Scheduling a Fleet
of Drones Performing Monitoring Missions
- Title（参考訳）: 監視任務を遂行するドローン群をスケジューリングするマルチトラベリングセールスマン問題の拡張
- Authors: Emmanouil Rigas, Panayiotis Kolios, Georgios Ellinas
- Abstract要約: 事前に定義された地点でノードを複数回訪問する必要があるグラフ上で、一連のドローンの走行経路をスケジュールする方法を示す。
提案した定式化は,交通ネットワークにおける交通流のモニタリングや遠隔地からの探索・救助活動の監視など,いくつかの領域に適用することができる。
詳細な評価では、グリーディアルゴリズムは最適の92.06%でほぼ最適性能を示し、数百台のドローンや位置で設定できる可能性がある。
- 参考スコア（独自算出の注目度）: 4.477547027158141
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper we schedule the travel path of a set of drones across a graph
where the nodes need to be visited multiple times at pre-defined points in
time. This is an extension of the well-known multiple traveling salesman
problem. The proposed formulation can be applied in several domains such as the
monitoring of traffic flows in a transportation network, or the monitoring of
remote locations to assist search and rescue missions. Aiming to find the
optimal schedule, the problem is formulated as an Integer Linear Program (ILP).
Given that the problem is highly combinatorial, the optimal solution scales
only for small sized problems. Thus, a greedy algorithm is also proposed that
uses a one-step look ahead heuristic search mechanism. In a detailed
evaluation, it is observed that the greedy algorithm has near-optimal
performance as it is on average at 92.06% of the optimal, while it can
potentially scale up to settings with hundreds of drones and locations.
- Abstract（参考訳）: 本稿では,事前に定義された地点でノードを複数回訪問する必要があるような,一組のドローンの走行経路をグラフ上でスケジュールする。
これはよく知られた旅行セールスマン問題の延長である。
提案した定式化は,交通ネットワークにおける交通流のモニタリングや遠隔地からの探索・救助活動の監視など,いくつかの領域に適用することができる。
最適なスケジュールを見つけるために、問題は整数線形プログラム(ILP)として定式化される。
問題は非常に組合せ的であるため、最適解は小さな問題に対してのみスケールする。
したがって,一段階のヒューリスティック探索機構を用いた欲求アルゴリズムも提案されている。
詳細な評価では、グリーディアルゴリズムは平均で92.06%の最適性能を持つため、ほぼ最適に近い性能を持つが、数百のドローンやロケーションを持つ設定までスケールアップできる可能性がある。
関連論文リスト
- Optimization of Multi-Agent Flying Sidekick Traveling Salesman Problem over Road Networks [10.18252143035175]
道路ネットワーク上でのマルチエージェント飛行サイドキック走行セールスマン問題(MA-FSTSP)について紹介する。
このNPハード問題に対して,混合整数線形計画モデルと効率的な3相アルゴリズムを提案する。
当社のアプローチは5分間の時間制限内で300以上の顧客にスケールし、大規模な実世界のロジスティクスアプリケーションの可能性を示している。
論文 参考訳（メタデータ） (2024-08-20T20:44:18Z) - A Real-Time Rescheduling Algorithm for Multi-robot Plan Execution [9.839983977902671]
Switchable-Edge Search (SES) は最適通過順序を見つけるために設計されたA*スタイルのアルゴリズムである。
本研究では,SESの最適性を証明し,シミュレーションによる効率評価を行う。
論文 参考訳（メタデータ） (2024-03-26T23:10:41Z) - A self-adaptive genetic algorithm for the flying sidekick travelling
salesman problem [0.0]
本稿では,自己適応型遺伝的アルゴリズムを用いてFSTSP(Flying Sidekick Travelling Salesman Problem)の解法を提案する。
FSTSPでは、ドローンを戦略的に展開し、顧客の位置情報を入手し難い場所に提供しながら、すべての場所を訪問するための総時間を最小化する。
論文 参考訳（メタデータ） (2023-10-23T08:51:02Z) - Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
マルチエージェントパスフィンディングに適したモンテカルロ木探索(MCTS)のオリジナル版を紹介する。
具体的には,エージェントの目標達成行動を支援するために,個別の経路を用いる。
また,木探索手順の分岐係数を低減するために,専用の分解手法を用いる。
論文 参考訳（メタデータ） (2023-07-25T12:33:53Z) - A Search and Detection Autonomous Drone System: from Design to
Implementation [7.760962597460447]
ターゲットを見つけるのに要する時間の観点からの探索効率は、山火事の検出に不可欠である。
経路計画と目標検出という2つのアルゴリズムが提案されている。
その結果,提案アルゴリズムはミッションの平均時間を大幅に短縮することがわかった。
論文 参考訳（メタデータ） (2022-11-29T01:44:29Z) - GoRela: Go Relative for Viewpoint-Invariant Motion Forecasting [121.42898228997538]
精度や一般化を犠牲にすることなく、全てのエージェントとマップに対して効率的な共有符号化を提案する。
不均一空間グラフにおけるエージェントとマップ要素間の幾何学的関係を表現するために、ペアワイズ相対的な位置符号化を利用する。
我々のデコーダは視点非依存であり、レーングラフ上でエージェント目標を予測し、多様かつコンテキスト対応のマルチモーダル予測を可能にする。
論文 参考訳（メタデータ） (2022-11-04T16:10:50Z) - A Metaheuristic Algorithm for Large Maximum Weight Independent Set
Problems [58.348679046591265]
ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。
このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。
我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-03-28T21:34:16Z) - Time-Optimal Planning for Quadrotor Waypoint Flight [50.016821506107455]
立方体の作動限界における時間-最適軌道の計画は未解決の問題である。
四重項のアクチュエータポテンシャルをフル活用する解を提案する。
我々は、世界最大規模のモーションキャプチャーシステムにおいて、実世界の飛行における我々の方法を検証する。
論文 参考訳（メタデータ） (2021-08-10T09:26:43Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - A Maximum Independent Set Method for Scheduling Earth Observing
Satellite Constellations [41.013477422930755]
本稿では,衛星スケジューリング問題の解法として,実現不可能なグラフ表現を生成する手法を提案する。
光衛星のスカイサット星座と、最大24個の衛星のシミュレートされた星座の、要求された最大10,000の撮像位置のシナリオでテストされている。
論文 参考訳（メタデータ） (2020-08-15T19:32:21Z) - Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal
Constraints [52.58352707495122]
本稿では,不確実性およびマルチエージェント協調の下での逐次意思決定における重要な計算課題を分離するマルチロボット割当アルゴリズムを提案する。
都市におけるマルチアームコンベヤベルトピック・アンド・プレイスとマルチドローン配送ディスパッチの2つの異なる領域における広範囲なシミュレーション結果について検証を行った。
論文 参考訳（メタデータ） (2020-05-27T01:10:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。