Task planning for earth observing satellite systems
Abstract/Contents
- Abstract
- Earth observing spacecraft provide unique data collection capabilities in terms of access, coverage, and persistence not achievable with air or land-based sensor platforms. The information remote sensing constellations provide is relied upon across defense, intelligence, financial, humanitarian, agricultural, and scientific domains. Increasing access to space in the form of low-cost commercial rocket launches, combined with commercial-off-the-shelf electronics, has led to the development of large constellations of small satellites with the aim of increasing data collection throughput. However, current and planned constellation sizes are beyond what can be practically managed using human operators alone. Automated planning of on-orbit operations tasks, in particular imaging activities, is needed to effectively manage Earth observing satellite systems. This thesis provides contributions to the modeling, analysis, and solution of the task planning problem for Earth observing satellite systems. Satellite task planning entails selecting actions that best satisfy mission objectives. This planning has historically been performed by human operators using heuristic or rule-based methods. Human-in-the-loop operations does not efficiently scale with the number of 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 with the number of requested observations and linearly with the number of spacecraft. Time-ordered task scheduling is an NP-complete problem. Therefore application-specific approaches are required to solve it. This thesis presents techniques to schedule tasks for both single spacecraft, as well as multi-satellite constellations of Earth-observing spacecraft. The proposed techniques are evaluated on their ability to maximize the number of collected images over a fixed planning horizon as well as the time required to arrive at a solution. First, this thesis introduces a highly parallelizable framework for modeling the satellite task planning problem. The action space is modeled as a set of discrete opportunities that the planning agent can choose to select or ignore. Desired imaging locations can be points or areas, from which the action space computation algorithm finds the set of all possible collection opportunities. Similarly, the periods for communicating with ground stations are modeled as contact opportunities. The algorithm for computing collect and contact opportunities scales linearly in the number of requests and spacecraft, allowing for efficient action space computation for large planning problems. This thesis shows how other scheduling approaches, in particular heuristic, graph traversal, and mixed-integer linear programming (MILP) algorithms can be formulated in this opportunity-based modeling framework to take advantage of the efficient action space computation. By leveraging the discrete action-space modeling framework and applying spacecraft scheduling constraints, the underlying graph structure of the satellite task planning problem can be analyzed. The task planning problem can be viewed from a feasibility perspective as a directed acyclic graph (DAG), or viewed from an infeasibility perspective as an undirected graph. Analysis reveals that the infeasibility perspective is the more efficient representation of the problem for both single satellite and multi-satellite problems. This thesis introduces the equivalence of satellite task planning with the problem of finding a maximal independent set of vertices on an undirected graph. This formulation of the task planning problem takes advantage of the efficiency of the infeasibility interpretation of the problem. The ReduMIS algorithm, which incorporates a highly efficient local search method, is applied to the satellite task planning problem and is shown to efficiently plan activities for scenarios of up to 10,000 requested imaging locations for simulated constellations of up to 24 satellites. Performance is compared with contemporary graph traversal and MILP approaches. Empirical results demonstrate the maximum independent set approach improves on both the solution time and number of scheduled collections when compared to baseline methods. Finally, this thesis introduces a Markov Decision Process (MDP) formulation of the task planning problem when resource constraints are present. This approach enables incorporation of diverse system constraints on power and data without needing to resort to heuristics or hard-coded decision policies. Due to the high dimensionality of the decision-space, computing the optimal decision policy through Value Iteration or Policy Iteration is not feasible given current computation hardware capabilities. This work solves the problem by applying approximate, online solvers with a semi-Markov variation to reduce the number of required decisions by an order of magnitude, making the problem computational tractable. The formulation is shown to effectively balance competing constraints in single-satellite task planning.
Description
| Type of resource | text |
|---|---|
| Form | electronic resource; remote; computer; online resource |
| Extent | 1 online resource. |
| Place | California |
| Place | [Stanford, California] |
| Publisher | [Stanford University] |
| Copyright date | 2021; ©2021 |
| Publication date | 2021; 2021 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Author | Eddy, Duncan O'Daniel |
|---|---|
| Degree supervisor | Kochenderfer, Mykel J, 1980- |
| Thesis advisor | Kochenderfer, Mykel J, 1980- |
| Thesis advisor | Manchester, Zachary |
| Thesis advisor | Schwager, Mac |
| Degree committee member | Manchester, Zachary |
| Degree committee member | Schwager, Mac |
| Associated with | Stanford University, Department of Aeronautics and Astronautics |
Subjects
| Genre | Theses |
|---|---|
| Genre | Text |
Bibliographic information
| Statement of responsibility | Duncan Eddy. |
|---|---|
| Note | Submitted to the Department of Aeronautics and Astronautics. |
| Thesis | Thesis Ph.D. Stanford University 2021. |
| Location | https://purl.stanford.edu/fp397ds6833 |
Access conditions
- Copyright
- © 2021 by Duncan O'Daniel Eddy
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...