To address the challenge of mission re-planning when a deep space probe with multiple nodes landing on small celestial bodies, planning constraint model and re-planning algorithm are studied in this paper. Based on the multiple nodes collaborative working mechanism and complex time constraint forms, the graph representation of system and time constraints are defined, and a layered constraint graph is constructed to describe the deep space probe system. The proposed algorithm combines the idea of binary and dynamic programming, including layered delay satisfaction verification mechanism and layered constraint search algorithm. A delay satisfaction verification mechanism for burst constraints is established by hierarchical storage of constraints with different granularity. For the scenarios where the overall delay cannot meet all constraints, a multi granularity constraint search algorithm is proposed based on the hierarchical matching of constraints. Simulation experiments have shown that the proposed algorithm can quickly generate a re-planning result with minimal time constraint loss cost to meet the real-time autonomous decision-making requirements for deep space explorations.