論文の概要: Graph Neural Networks for the Offline Nanosatellite Task Scheduling Problem

• arxiv url: http://arxiv.org/abs/2303.13773v2
• Date: Wed, 20 Sep 2023 20:04:09 GMT
• ステータス: 処理完了
• システム内更新日: 2023-09-22 19:45:23.167133
• Title: Graph Neural Networks for the Offline Nanosatellite Task Scheduling Problem
• Title（参考訳）: オフラインナノサテライトタスクスケジューリング問題のためのグラフニューラルネットワーク
• Authors: Bruno Machado Pacheco, Laio Oriel Seman, Cezar Antonio Rigo, Eduardo Camponogara, Eduardo Augusto Bezerra, Leandro dos Santos Coelho
• Abstract要約: 本研究では,グラフニューラルネットワーク(GNN)を用いて,ナノサテライトタスクをより効率的にスケジュールする方法を検討する。 目標は、QoS(Quality-of-Service)を考慮して、軌道上で実行するタスクの最適なスケジュールを見つけることである。
• 参考スコア（独自算出の注目度）: 7.20853603061523
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: This study investigates how to schedule nanosatellite tasks more efficiently using Graph Neural Networks (GNNs). In the Offline Nanosatellite Task Scheduling (ONTS) problem, the goal is to find the optimal schedule for tasks to be carried out in orbit while taking into account Quality-of-Service (QoS) considerations such as priority, minimum and maximum activation events, execution time-frames, periods, and execution windows, as well as constraints on the satellite's power resources and the complexity of energy harvesting and management. The ONTS problem has been approached using conventional mathematical formulations and exact methods, but their applicability to challenging cases of the problem is limited. This study examines the use of GNNs in this context, which has been effectively applied to optimization problems such as the traveling salesman, scheduling, and facility placement problems. More specifically, we investigate whether GNNs can learn the complex structure of the ONTS problem with respect to feasibility and optimality of candidate solutions. Furthermore, we evaluate using GNN-based heuristic solutions to provide better solutions (w.r.t. the objective value) to the ONTS problem and reduce the optimization cost. Our experiments show that GNNs are not only able to learn feasibility and optimality for instances of the ONTS problem, but they can generalize to harder instances than those seen during training. Furthermore, the GNN-based heuristics improved the expected objective value of the best solution found under the time limit in 45%, and reduced the expected time to find a feasible solution in 35%, when compared to the SCIP (Solving Constraint Integer Programs) solver in its off-the-shelf configuration
• Abstract（参考訳）: 本研究では,グラフニューラルネットワーク(GNN)を用いて,ナノサテライトタスクをより効率的にスケジュールする方法を検討する。 オフライン・ナノサテライト・タスク・スケジューリング(onts)問題では、優先度、最小および最大アクティベーションイベント、実行時間枠、期間、実行ウィンドウといったqos(quality-of-service)の考慮事項や、衛星の電力資源の制約、エネルギーの収穫および管理の複雑さを考慮して、軌道上で実行するタスクの最適なスケジュールを見出すことが目的である。 ONTS問題は、従来の数学的定式化や正確な方法を用いてアプローチされてきたが、問題の挑戦事例への適用性は限られている。 本研究は,旅行セールスマン,スケジューリング,施設配置問題などの最適化問題に効果的に適用された,この文脈におけるGNNの利用について検討する。 具体的には、GNNがONTS問題の複雑な構造を、候補解の実現可能性と最適性に関して学習できるかどうかを検討する。 さらに、我々は、GNNベースのヒューリスティックソリューションを用いて、ONTS問題に対するより良いソリューション(例えば、目的値)を提供し、最適化コストを低減することを評価する。 実験の結果、GNNはONTS問題のインスタンスの実現可能性と最適性を学習できるだけでなく、トレーニング中のインスタンスよりも難しいインスタンスに一般化できることがわかった。 さらに,gnnベースのヒューリスティックスは,scip(solving constraints integer programs)ソルバのオフ・ザ・棚構成と比較して,時間制限下での最適解の期待目標値を45%改善し,実現可能な解を見つけるための所要時間を35%削減した。

関連論文リスト

• Assessing and Enhancing Graph Neural Networks for Combinatorial Optimization: Novel Approaches and Application in Maximum Independent Set Problems [0.0]
  Graph Neural Networks (GNNs)は、コンビネーション最適化(CO)問題の解決における研究者の約束を示す。 本研究では,最大独立集合(MIS)問題の解法におけるGNNの有効性について検討した。
  論文  参考訳（メタデータ） (2024-11-06T09:12:31Z)
• Optimization Proxies using Limited Labeled Data and Training Time -- A Semi-Supervised Bayesian Neural Network Approach [2.943640991628177]
  制約のある最適化問題は、在庫管理電力グリッドのような様々なエンジニアリングシステムで発生する。 本研究では,ベイジアンネットワーク(BNN)を用いて,制限されたデータと制限されたモデル時間の下での制約付き最適化問題の解法を提案する。 提案手法は,従来のBNNおよびディープニューラルネットワーク(DNN)アーキテクチャよりも優れていることを示す。
  論文  参考訳（メタデータ） (2024-10-04T02:10:20Z)
• Enhancing GNNs Performance on Combinatorial Optimization by Recurrent Feature Update [0.09986418756990156]
  本稿では,組合せ最適化(CO)問題を効率よく解くために,GNNのパワーを活用して,QRF-GNNと呼ぶ新しいアルゴリズムを提案する。 QUBO緩和による損失関数の最小化による教師なし学習に依存している。 実験の結果、QRF-GNNは既存の学習ベースアプローチを大幅に上回り、最先端の手法に匹敵することがわかった。
  論文  参考訳（メタデータ） (2024-07-23T13:34:35Z)
• DNN Partitioning, Task Offloading, and Resource Allocation in Dynamic Vehicular Networks: A Lyapunov-Guided Diffusion-Based Reinforcement Learning Approach [49.56404236394601]
  本稿では,Vehicular Edge Computingにおける共同DNNパーティショニング,タスクオフロード,リソース割り当ての問題を定式化する。 我々の目標は、時間とともにシステムの安定性を保証しながら、DNNベースのタスク完了時間を最小化することである。 拡散モデルの革新的利用を取り入れたマルチエージェント拡散に基づく深層強化学習(MAD2RL)アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-06-11T06:31:03Z)
• BalMCTS: Balancing Objective Function and Search Nodes in MCTS for Constraint Optimization Problems [7.196057722218442]
  制約問題最適化(COP)は、通常ブランチ・アンド・バウンド(B&B)法によって解決される問題において、複雑な課題を提起する。 COPを解くための深度優先探索アルゴリズムに基づく新しいニューラルネットワークアルゴリズムを提案する。 提案手法は,最初の5つの実現可能な解のうち17.63%未満のギャップを有する実現可能な解を同定する。
  論文  参考訳（メタデータ） (2023-12-26T03:09:08Z)
• Learning to Solve Combinatorial Graph Partitioning Problems via Efficient Exploration [72.15369769265398]
  実験により、ECORDは最大カット問題に対するRLアルゴリズムのための新しいSOTAを実現する。 最も近い競合と比較して、ECORDは最適性ギャップを最大73%削減する。
  論文  参考訳（メタデータ） (2022-05-27T17:13:10Z)
• Robust Graph Neural Networks via Probabilistic Lipschitz Constraints [7.359962178534361]
  グラフニューラルネットワーク(GNN)は、最近、さまざまなネットワークベースのタスクでうまく機能することが実証されている。 GNNは入力のシフトや摂動の影響を受けやすく、ノード属性とグラフ構造の両方を含むことができる。
  論文  参考訳（メタデータ） (2021-12-14T17:33:32Z)
• A Biased Graph Neural Network Sampler with Near-Optimal Regret [57.70126763759996]
  グラフニューラルネットワーク(GNN)は、グラフおよびリレーショナルデータにディープネットワークアーキテクチャを適用する手段として登場した。 本論文では,既存の作業に基づいて,GNN近傍サンプリングをマルチアームバンディット問題として扱う。 そこで本研究では,分散を低減し,不安定かつ非限定的な支払いを回避すべく設計されたバイアスをある程度導入した報酬関数を提案する。
  論文  参考訳（メタデータ） (2021-03-01T15:55:58Z)
• Learning to Execute Programs with Instruction Pointer Attention Graph Neural Networks [55.98291376393561]
  グラフニューラルネットワーク(GNN)は、ソフトウェアエンジニアリングタスクを学習するための強力なツールとして登場した。 リカレントニューラルネットワーク(RNN)は、長いシーケンシャルな推論の連鎖に適しているが、プログラム構造を自然に組み込んでいるわけではない。 本稿では,新しいGNNアーキテクチャ,IPA-GNN(Instruction Pointer Attention Graph Neural Networks)を導入する。
  論文  参考訳（メタデータ） (2020-10-23T19:12:30Z)
• Graph Neural Networks for Motion Planning [108.51253840181677]
  低次元問題に対する高密度固定グラフ上のGNNと高次元問題に対するサンプリングベースGNNの2つの手法を提案する。 RRT(Rapidly-Exploring Random Trees)におけるクリティカルノードの特定やサンプリング分布の学習といった計画上の問題にGNNが取り組む能力について検討する。 臨界サンプリング、振り子、6つのDoFロボットアームによる実験では、GNNは従来の分析手法の改善だけでなく、完全に接続されたニューラルネットワークや畳み込みニューラルネットワークを用いた学習アプローチも示している。
  論文  参考訳（メタデータ） (2020-06-11T08:19:06Z)
• Optimizing Wireless Systems Using Unsupervised and Reinforced-Unsupervised Deep Learning [96.01176486957226]
  無線ネットワークにおけるリソース割り当てとトランシーバーは、通常最適化問題の解決によって設計される。 本稿では,変数最適化と関数最適化の両問題を解くための教師なし・教師なし学習フレームワークを紹介する。
  論文  参考訳（メタデータ） (2020-01-03T11:01:52Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。