Time Sorting Filtering Algorithm for Deep Space Mission Planning

In the mission planning of deep space exploration, the uncertain and disturbance of environment affect the execution of planning result. Using dispatchable Simple Temporal Network (STN), execution time of activities can be propagated from executed activities in practical application. In traditional algorithm, dispatchable STN is obtained from filtering dominated edges in distance graph of STN, and all pairs of constraints are traversed. To ensure execution efficiency, this paper proposes an improved algorithm of Time Sorting Filtering (TSF) algorithm. According to domination relations of temporal constraints, filtering process is simplified based on time sorting of STN vertexes. After analyzing state-of-the-art Snowball algorithm, triangulation structures that should be handled are also be improved. The experiment demonstrates correctness and efficiency of this algorithm.