<p>The multi-satellite Earth observation mission planning problem represents a complex combinatorial optimization challenge characterized by high-dimensional variables, large-scale problem instances, and complex constraints. Existing solution methods struggle to concurrently satisfy the high requirements of real-time, high-performance computing and solution quality for satellite autonomous mission planning. This study employs matroid theory to construct a directed acyclic graph that significantly reduces problem scale while guaranteeing solution quality lower bounds. We rigorously analyze and demonstrate the performance characteristics of potential game approach and greedy algorithm for multi-satellite planning, highlighting their respective strengths in solution quality and computational efficiency. By integrating their computational and quality advantages, we propose a three-phase matroid-based approach for autonomous multi-satellite planning with proven performance guarantees. Simulations of multiple scale scenarios validate the performance of the approach’s effectiveness, particularly demonstrating the three-phase approach’s capability to simultaneously meet the high-performance computing requirements.</p>