Abstract: In view of the complex system and coupling operation constraints of deep space probes,state transition graphs are defined based on the timeline knowledge representation. With the analysis of involved constraints in task planning,the computation procedure of cost estimate for state transition is designed. In addition,the state transition graph based heuristic planning algorithm is proposed and is able to prune irrelevant search space,and accelerate the searching process. Simulation results indicate that the algorithm can reduce unnecessary planning steps and make certain improvements in planning efficiency.