Abstract: Facing the increasingly complex deep-space exploration missions and the dynamic space environment, deep-space probes need efficient planning methods for the fast generation of plans. The distribution and concurrency of subsystems make a probe suitable to be modeled as a multi-agent system. Existing multi-agent planners, however, cannot be used directly in mission planning of deep space probes that involve handling numeric constraints such as time resources. To solve the above problem, a multi-agent mission plan-space planning method based on distributed refinement search was proposed. A dynamic agent interaction graph (DAIG) was designed to coordinate interactions between agents during planning. Temporal constraints and resource constraints were modeled as constraint satisfaction problems and were handled by graph theory methods. Experiments show that the method proposed in this paper can save computing time of mission planning problems for a probe with multiple subsystems.