Several artificial-intelligence search techniques have been tested as means of solving the swath segment selection problem (SSSP) ? a real-world problem that is not only of interest in its own right, but is also useful as a test bed for search techniques in general. In simplest terms, the SSSP is the problem of scheduling the observation times of an airborne or spaceborne synthetic aperture radar (SAR) system to effect the maximum coverage of a specified area (denoted the target), given a schedule of downlinks (opportunities for radio transmission of SAR scan data to a ground station), given the limit on the quantity of SAR scan data that can be stored in an onboard memory between downlink opportunities, and given the limit on the achievable downlink data rate. The SSSP is NP complete (short for “nondeterministic polynomial time complete” ? characteristic of a class of intractable problems that can be solved only by use of computers capable of making guesses and then checking the guesses in polynomial time).
For the purpose of mathematical modeling for the SSSP, a target is approximated as being planar and is subdivided in a pattern of swaths, segments, and shards (see figure). A swath is defined as area, usually rectangular, that can be scanned during a given interval of time. Segments are portions of swaths (also usually rectangular) defined by intersections of swath and target boundaries. Shards ? so named because they resemble pieces of broken glass — are polygonal areas that are derived from segments and that represent pieces of target area for which data can be gathered and downlinked. The search techniques tested as means of solving the SSSP include the following:
- Forward Dispatch: Segments are added in temporal order until the system becomes oversubscribed. When the addition of a segment results in an oversubscription, the computation is rolled back to remove that segment, then the computation resumes without that segment. In comparison with the other techniques, this technique requires the least amount of computation time but yields solutions of poor quality.
- Mixed Integer Programming: Mixed integer programming is a hybrid of integer and linear programming. It applies to a formulation of the SSSP in which the relationships among variables and constraints are expressed by matrix-vector equations and inequalities. In linear programming, the variables can have continuous values and one seeks a vector of such variables that minimizes or maximizes an objective function. An integer program includes the additional constraint that the variables must all have integer values. Integer programming gives optimal solutions, but requires the greatest amount of computation time, even when one accepts suboptimal solutions. In mixed integer programming, some variables are integers and some are continuous.
- Network Flow Relaxation With Depth-First Branch and Bound: One constructs a network flow graph ? a directed, edge-labeled graph that represents the flow of information through the problem. This graph is used in conjunction with depth-first branch-and-bound (DFBnB) algorithm. This technique provides the same information as does integer, mixed integer, or linear programming while requiring less computation time.
The results of tests performed thus far have led to the conclusion that for best performance, one should start with forward dispatch followed immediately by DFBnB.
This work was done by Russell Knight and Benjamin Smith of Caltech for NASA’s Jet Propulsion Laboratory. For further information, access the Technical Support Package (TSP) free on-line at www.techbriefs.com/tsp under the Information Sciences category.
The software used in this innovation is available for commercial licensing. Please contact Karina Edmonds of the California Institute of Technology at (626) 395-2322. Refer to NPO-40454.
This Brief includes a Technical Support Package (TSP).
Solving the Swath Segment Selection Problem
(reference NPO-40454) is currently available for download from the TSP library.
Don't have an account?
Overview
The document titled "Solving the Swath Segment Selection Problem" (NPO-40454) is a technical support package from NASA's Jet Propulsion Laboratory (JPL) that addresses the Swath Segment Selection Problem (SSSP). The SSSP involves selecting a subset of swath segments from a set of target polygons, downlinks, and memory capacities to maximize the area of targets that can be downlinked while adhering to specific constraints.
The document defines key terms, such as "shard," which refers to sub-sections of a target that can be gathered and downlinked. Shards are derived from the intersection of target polygons and swath segments, and the document assumes that targets are pre-divided into these shards for the purpose of the problem formulation.
The primary focus of the document is on the development of algorithms that can efficiently solve the SSSP. It discusses various approaches, including first solution time and quality results for different algorithms like ASTER, BnBFlow, and Integer Programming, tested on randomly generated SSSPs of varying sizes. These algorithms aim to optimize the scheduling of observations for spacecraft, particularly in the context of Earth observation missions.
The document also references several academic works and methodologies related to combinatorial optimization and scheduling, indicating a strong theoretical foundation for the proposed solutions. It highlights the importance of effective memory management and downlink capacity in maximizing the efficiency of data collection from space missions.
In addition to the technical details, the document serves as a resource for those interested in aerospace technology and its applications beyond space exploration. It emphasizes the potential for these algorithms to be adapted for various technological, scientific, or commercial uses.
Overall, the document provides a comprehensive overview of the SSSP, the challenges involved, and the innovative solutions developed by JPL researchers. It underscores the significance of optimizing spacecraft observation scheduling to enhance data collection capabilities, which is crucial for advancing our understanding of Earth and other celestial bodies. The findings and methodologies presented in this technical support package are valuable for researchers and practitioners in the field of aerospace engineering and related disciplines.
