A Maximum Independent Set Method for Scheduling Earth Observing Satellite Constellations

• URL: http://arxiv.org/abs/2008.08446v1
• Date: Sat, 15 Aug 2020 19:32:21 GMT
• Title: A Maximum Independent Set Method for Scheduling Earth Observing Satellite Constellations
• Authors: Duncan Eddy and Mykel J. Kochenderfer
• Abstract summary: This paper introduces a new approach for solving the satellite scheduling problem by generating an infeasibility-based graph representation of the problem. It is tested on a scenarios of up to 10,000 requested imaging locations for the Skysat constellation of optical satellites as well as simulated constellations of up to 24 satellites.
• Score: 41.013477422930755
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Operating Earth observing satellites requires efficient planning methods that coordinate activities of multiple spacecraft. The satellite task planning problem entails selecting actions that best satisfy mission objectives for autonomous execution. Task scheduling is often performed by human operators assisted by heuristic or rule-based planning tools. This approach does not efficiently scale to multiple assets as heuristics frequently fail to properly coordinate actions of multiple vehicles over long horizons. Additionally, the problem becomes more difficult to solve for large constellations as the complexity of the problem scales exponentially in the number of requested observations and linearly in the number of spacecraft. It is expected that new commercial optical and radar imaging constellations will require automated planning methods to meet stated responsiveness and throughput objectives. This paper introduces a new approach for solving the satellite scheduling problem by generating an infeasibility-based graph representation of the problem and finding a maximal independent set of vertices for the graph. The approach is tested on a scenarios of up to 10,000 requested imaging locations for the Skysat constellation of optical satellites as well as simulated constellations of up to 24 satellites. Performance is compared with contemporary graph-traversal and mixed-integer linear programming approaches. Empirical results demonstrate improvements in both the solution time along with the number of scheduled collections beyond baseline methods. For large problems, the maximum independent set approach is able find a feasible schedule with 8% more collections in 75% less time.

Related papers

• A Distance Similarity-based Genetic Optimization Algorithm for Satellite Ground Network Planning Considering Feeding Mode [53.71516191515285]
  The low transmission efficiency of the satellite data relay back mission has become a problem that is currently constraining the construction of the system. We propose a distance similarity-based genetic optimization algorithm (DSGA), which considers the state characteristics between the tasks and introduces a weighted Euclidean distance method to determine the similarity between the tasks.
  arXiv  Detail & Related papers  (2024-08-29T06:57:45Z)
• Quantum Optimization Methods for Satellite Mission Planning [0.3252295747842729]
  The ever-growing amount of satellites in orbit underscores the need to operate them efficiently. Current classical algorithms often fail to find the global optimum or take too long to execute. Here, we approach the problem from a quantum computing point of view, which offers a promising alternative.
  arXiv  Detail & Related papers  (2024-04-08T13:36:29Z)
• Toward Autonomous Cooperation in Heterogeneous Nanosatellite Constellations Using Dynamic Graph Neural Networks [0.0]
  The paper proposes a novel approach to overcome the challenges by modeling the constellations and CP as dynamic networks. The trained neural network can predict the network delay with a mean absolute error of 3.6 minutes. Simulation results show that the proposed method can successfully design a contact plan for large satellite networks, improving the delay by 29.1%, similar to a traditional approach.
  arXiv  Detail & Related papers  (2024-03-01T17:26:02Z)
• Quantum algorithms applied to satellite mission planning for Earth observation [0.0]
  This paper introduces a set of quantum algorithms to solve the satellite mission planning problem. The problem is formulated as maximizing the number of high-priority tasks completed on real datasets. A hybridized quantum-enhanced reinforcement learning agent can achieve a completion percentage of 98.5% over high-priority tasks.
  arXiv  Detail & Related papers  (2023-02-14T16:49:25Z)
• Innovations in the field of on-board scheduling technologies [64.41511459132334]
  This paper proposes an onboard scheduler, that integrates inside an onboard software framework for mission autonomy. The scheduler is based on linear integer programming and relies on the use of a branch-and-cut solver. The technology has been tested on an Earth Observation scenario, comparing its performance against the state-of-the-art scheduling technology.
  arXiv  Detail & Related papers  (2022-05-04T12:00:49Z)
• Satellite Image Time Series Analysis for Big Earth Observation Data [50.591267188664666]
  This paper describes sits, an open-source R package for satellite image time series analysis using machine learning. We show that this approach produces high accuracy for land use and land cover maps through a case study in the Cerrado biome.
  arXiv  Detail & Related papers  (2022-04-24T15:23:25Z)
• GEO satellites on-orbit repairing mission planning with mission deadline constraint using a large neighborhood search-genetic algorithm [2.106508530625051]
  This paper proposes a large neighborhood search-adaptive genetic algorithm (LNS-AGA) for many-to-many on-orbit repairing mission planning. In the many-to-many on-orbit repairing scenario, several servicing spacecrafts and target satellites are located in GEO orbits which have different inclination, RAAN and true anomaly. The mission objective is to find the optimal servicing sequence and orbit rendezvous time of every servicing spacecraft to minimize total cost of all servicing spacecrafts with all target satellites repaired.
  arXiv  Detail & Related papers  (2021-10-08T03:33:37Z)
• Model-Based Reinforcement Learning via Latent-Space Collocation [110.04005442935828]
  We argue that it is easier to solve long-horizon tasks by planning sequences of states rather than just actions. We adapt the idea of collocation, which has shown good results on long-horizon tasks in optimal control literature, to the image-based setting by utilizing learned latent state space models.
  arXiv  Detail & Related papers  (2021-06-24T17:59:18Z)
• Auction-based and Distributed Optimization Approaches for Scheduling Observations in Satellite Constellations with Exclusive Orbit Portions [0.45687771576879593]
  We investigate the use of multi-agent allocation techniques on problems related to Earth observation scenarios with multiple users and satellites. As to solve EOSCSP, we propose market-based techniques and a distributed problem solving technique based on Distributed Constraint Optimization. These contributions are experimentally evaluated on randomly generated EOSCSP instances based on real large-scale or highly conflicting observation order books.
  arXiv  Detail & Related papers  (2021-06-04T09:34:20Z)
• Bottom-up mechanism and improved contract net protocol for the dynamic task planning of heterogeneous Earth observation resources [61.75759893720484]
  Earth observation resources are becoming increasingly indispensable in disaster relief, damage assessment and related domains. Many unpredicted factors, such as the change of observation task requirements, to the occurring of bad weather and resource failures, may cause the scheduled observation scheme to become infeasible. A bottom-up distributed coordinated framework together with an improved contract net are proposed to facilitate the dynamic task replanning for heterogeneous Earth observation resources.
  arXiv  Detail & Related papers  (2020-07-13T03:51:08Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.