  Operating Earth observing satellites requires efficient planning methods that
coordinate activities of multiple spacecraft. The satellite task planning
problem entails selecting actions that best satisfy mission objectives for
autonomous execution. Task scheduling is often performed by human operators
assisted by heuristic or rule-based planning tools. This approach does not
efficiently scale to multiple assets as heuristics frequently fail to properly
coordinate actions of multiple vehicles over long horizons. Additionally, the
problem becomes more difficult to solve for large constellations as the
complexity of the problem scales exponentially in the number of requested
observations and linearly in the number of spacecraft. It is expected that new
commercial optical and radar imaging constellations will require automated
planning methods to meet stated responsiveness and throughput objectives. This
paper introduces a new approach for solving the satellite scheduling problem by
generating an infeasibility-based graph representation of the problem and
finding a maximal independent set of vertices for the graph. The approach is
tested on a scenarios of up to 10,000 requested imaging locations for the
Skysat constellation of optical satellites as well as simulated constellations
of up to 24 satellites. Performance is compared with contemporary
graph-traversal and mixed-integer linear programming approaches. Empirical
results demonstrate improvements in both the solution time along with the
number of scheduled collections beyond baseline methods. For large problems,
the maximum independent set approach is able find a feasible schedule with 8%
more collections in 75% less time.
