Relaxed planning graph based hybrid heuristic planning method for multi-spacecraft cooperative mission

Multi-spacecraft cooperation is crucial for addressing increasingly complex space missions, such as astronomical observation, planetary exploration, and gravitational wave detection. Although mission planning technologies provide effective support for spacecraft to autonomously complete missions, existing planning methods still face challenges in quickly generating autonomous sequences when confronted with complex constraints in multi-spacecraft cooperation missions. To efficiently solve this problem, a relaxed planning graph based hybrid heuristic planning method is proposed. First, a general mathematical formulation for the multi-spacecraft mission planning problem is constructed, and it is reformulated as a path search problem within state space under multiple constraints. Next, a fast forward extension algorithm for relaxed planning graph is proposed to efficiently evaluate the reachability of spacecraft to mission goals, while greedily selecting effective spacecraft to narrow the search space of the planning problem. Finally, a hybrid heuristic greedy best-first search algorithm is proposed to efficiently solve the planning problem, employing a heuristic evaluator switching strategy to avoid the algorithm getting stuck in a plateau. The effectiveness and efficiency of the proposed method are validated through a series of simulations, including scenarios with multiple rovers and satellites. The results show that the proposed method significantly reduces the computational time compared to the advanced planning approaches. The proposed method offers a promising solution for complex, large-scale space missions involving multi-spacecraft.