CoChat

QUEST – A new quadratic decision model for the multi-satellite scheduling problem

Berger, J., Lo, N., Barkaoui, M. · 2020 · Computers & Operations Research
Cited by 37

The DOI matches its Crossref record; 11 of the 11 references it cites were found in a registry or an index.

Abstract

Abstract Demand for earth observation satellite imagery is pervasive and increasing rapidly across multiple domains, highlighting the key problem to optimally schedule satellite image acquisition/collection, subject to ground and on-board constraints. Despite the variety of reported approaches to solving the NP-hard multi-satellite scheduling problem (m-SatSP), serious limitations still prevail, largely overlooking problem structure exploitation and/or domain knowledge. Assuming a few constraints, problem modelling—or scope—is often confined to a simple trailing satellite constellation composition perspective and tends to conveniently oversimplify footprint coverage intricacies. As a result, adequate problem task decomposition properly reflecting complex kinematic behaviour for an ad hoc satellite constellation remains elusive. Known approaches also fail to provide valuable solution optimality gap estimations to objectively qualify best computed solution and/or to control run-time execution in solving hard problem instances. In this paper, a novel approach to solving the single objective static m-SatSP is proposed. It is based on network flow optimization using mathematical programming. Unlike previous methods, QUEST (QUadratically constrainEd program Solver Technology) relies on a sound alternative approximate objective function and, the exploitation of exact problem-solving techniques. Derived from domain knowledge and problem structure considerations, QUEST generalizes problem modelling to successfully handle virtual constellation, avoiding unsuitable utilization of traditional area coverage decomposition scheme. The proposed decision model concurrently captures coverage approximation, imaging success uncertainty and quality for a variety of tasks. It also includes new and optional constraints while embracing an acceptable upper bound on collection value. A QUEST variant alternatively relying on “delayed reward” to bridge promising search regions on move selection, further shows optimality gap reduction and provides additional speedup. Computational results prove QUEST to be cost-effective and to outperform some recent baseline methods derived from best-known m-SatSP procedures. It comparatively demonstrates measurable collection and run-time gains, and provides a tight upper bound on the optimal solution of hard problems.

Overview

The claims and statistics of this paper haven’t been checked yet.

Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1016/j.cor.2019.104822

Cites

11 of 11 references verified0 citation errors · 0 not checkable

Statistics

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.

A few free checks a day · papers already verified open instantly · results are public

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

Cited by

See all 37

Metadata

Authors
Berger, J., Lo, N., & Barkaoui, M.
Venue
Computers & Operations Research
Publisher
Elsevier BV
Published
2020-03
Volume
115
Pages
104822
ISSN
0305-0548 (ISSN-L)
OpenAlex
W2981002223
Cited by
37
References
11
FWCI
2.56
Type
journal article
Language
en
Open access
closed

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review

Data sources

Bibliographic data: Semantic Scholar, OpenAlex, Crossref.

Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).

Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.