A GRASP for Next Generation Sapphire Image Acquisition Scheduling

Abstract

This paper investigates an image acquisition scheduling problem for a Canadian surveillance-of-space satellite named Sapphire that takes images of deep space Earth-orbiting objects. For a set of resident space objects (RSOs) that needs to be imaged within the time horizon of one day, the Sapphire image acquisition scheduling (SIAS) problem is to find a schedule that maximizes the “Figure of Merit” of all the scheduled RSO images. To address the problem, we propose an effective GRASP heuristic that alternates between a randomized greedy constructive procedure and a local search procedure. Experimental comparisons with the currently used greedy algorithm are presented to demonstrate the merit of the proposed algorithm in handling the SIAS problem.