Solving the Swath Segment Selection Problem
- Wednesday, 15 November 2006
Several techniques for solving the problem have been tested and compared.
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.
Please Login at the top of the page to download.