Distributed Greedy Algorithm for Satellite Assignment Problem with Submodular Utility Function∗

Recent advances in spacecraft technology allow a large number of smaller and cheaper satellites to fulfill useful Earth monitoring roles. An emerging challenge is to coordinate those satellites to monitor the Earth's surface and atmosphere. In this paper, we study the satellite assignment problem for a large constellation of Earth observing satellites, where a set of satellites assign themselves to observe a set of locations. The objective is to maximize a global utility function that is associated with the assignment profile. Due to the communication constraints of the space system, we develop a distributed assignment algorithm where each satellite makes its choice based on local information and local communication. We show that the efficiency ratio of the distributed solution to the optimal one is lower bounded by 1/2. Moreover, this bound is proven to be tight in the sense that there exist scenarios where the bound 1/2 is approached as close as possible.