A Double Auction Mechanism for Task Scheduling of An EOS Constellation

This brief investigates the task scheduling problem for an earth observation satellite (EOS) constellation. The EOS constellation needs to collaboratively complete a set of observation tasks, but each EOS should satisfy the observation order specification described by a task graph due to its motion constraints. The goal is to maximize the total number of observation tasks by the constellation, for which repeated observations are counted only for once. Firstly, the task scheduling problem is formulated as an exact potential game and the goal of the task scheduling problem is converted to find a Nash equilibrium (NE). Secondly, a double auction strategy is proposed to solve for an NE iteratively and a sieving scheme is presented for the buyer to build its candidate set. It is proved that our algorithm converges to an NE in finite steps.

Automated summary

This study investigates the task scheduling problem for an earth observation satellite (EOS) constellation. The EOS constellation collaboratively completes a set of observation tasks, with each EOS following a specified observation order described by a task graph. The goal is to maximize the total number of observation tasks by the constellation, considering repeated observations only once. The task scheduling problem is formulated as an exact potential game to find a Nash equilibrium (NE), and a double auction strategy along with a sieving scheme is proposed to iteratively solve for an NE, with proven convergence in finite steps.