Lorenzo Federici, The University of Arizona; Andrea D’Ambrosio, The University of Arizona; Roberto Furfaro, The University of Arizona; Vishnu Reddy, The University of Arizona
Keywords: Telescope tasking, A* search, Space Domain Awareness, Optical observations
Abstract:
Sensor or telescope tasking for Space Domain Awareness (SDA) is the process of scheduling observations of artificial objects in space from one telescope in order to achieve the scientific objectives of the observations, while taking into account factors such as the objects’ motion in the sky, the telescope’s location and characteristics, and the available observation time. A typical scenario is to select the celestial objects and schedule the different observations to either maximize the number of objects tracked in a given time window or a cumulative score. Indeed, a given score or priority index can be associated with each object to express the importance of observing it. For example, in case of suspected conjunctions between space objects, there would be the need to collect as many observations as possible in a very short time window, so that to take the necessary counteractions to avoid the conjunction.
One of the main challenges in optimal telescope tasking is the complexity of the problem. This is, in general, an NP-hard combinatorial problem, as both the set of objects of interest, selected within a larger list, and the optimal order of the observations must be determined. In this case, the use of exact integer linear programming solution algorithms, such as branch and bound methods, is usually impractical because of the prohibitive computational times required. Moreover, the problem is even further complicated by the presence of different factors and constraints that need to be considered when selecting the objects to track, including the capabilities of the telescope and the observing conditions (weather conditions, Sun altitude, and so on). Several approaches to sensor tasking have been proposed in the literature. The most common approach is to use either greedy-solution mechanisms or heuristic algorithms that rely on pre-determined rules and decision trees to quickly find a (usually sub-optimal) solution. Dynamic programming methods and Monte Carlo-based tree search algorithms have been also investigated to approximately solve long-term sensor planning problems, although they still require a substantial computational effort to evaluate the possible observations. Recently, machine learning techniques, such as deep reinforcement learning, which can learn from past problem instances and adapt to new data, have been proposed, showing good accuracy and robustness against changes in the objects’ orbital regimes, observation window length, observers location, and sensor properties.
In this paper, the sensor tasking problem is formulated as a variant of the Orienteering Problem (OP), an NP-hard combinatorial problem that combines the score-maximization objective of the Knapsack Problem (KP) with the path-length minimization elements of the Traveling Salesman Problem (TSP). This problem takes its name from an outdoor sport, orienteering, where the objective is to visit, in a limited amount of time, a subset of the checkpoints located on a map, starting from the home base, so that to maximize the total score associated with them. In the telescope tasking scenario, each checkpoint corresponds to a different observation opportunity for a given object, and the time-to-go from one checkpoint to the next one corresponds to the time needed to track the object and physically move the telescope to the new pointing direction, given the maximum slew rate of the sensor.
The sensor tasking problem is tackled in this paper with the A* search algorithm. A* search is a widely used algorithm for finding the optimal path in a graph, and it can be applied to the optimal telescope tasking to efficiently search through the vast number of possible observation schedules. The A* algorithm is a combination of two approaches: Dijkstra’s algorithm for finding the shortest path in a graph, and a heuristic function that estimates the distance between a node and the goal. The algorithm uses a priority queue to keep track of nodes that have been visited and those that need to be explored. Each node is assigned a cost based on its distance from the start node and the estimated distance to the goal. The algorithm selects the node with the lowest cost and explores its neighbors, updating the costs of neighboring nodes as necessary. The search continues until the goal node is reached or until no more nodes can be explored. The efficiency of A* search mainly depends on the accuracy of the heuristic function. The more accurate the heuristic, the fewer nodes are expanded, but, generally, the more complex the heuristic is to be computed. Hence, a trade-off between the accuracy of the heuristics and its simplicity is usually required. Several admissible heuristics for A* are proposed and compared in this study in terms of time complexity. Being A* an exact solution algorithm, it can struggle to find an optimal solution in a reasonable computational time based on the problem’s complexity. To reduce the size of the graph, pruning techniques will be used to eliminate, from the priority queue, schedules that are unlikely to yield a high scientific output (Beam search). These techniques can be based on the current state of the telescope and the properties of the celestial objects being observed. For example, if the telescope is currently pointing in a particular direction, schedules that involve observing objects in the opposite direction can be safely discarded. This pruning allows for a considerable speed up the search, at the cost of losing guarantees on the global optimality of the solution.
Simulations will be carried out using real data, generated through the SDA infrastructure and telescopes of the Space4 Center at The University of Arizona, to evaluate the effectiveness of the proposed A*-search-based algorithm for telescope tasking.
Specifically, different scenarios will be considered to test the algorithm’s robustness to changing conditions, such as the variation of the orbital regime of the celestial objects (LEO, GEO, and X-GEO), the total number of objects, and the characteristics of the telescope. In the simplest cases, the output of the simulations will be also compared with the exact solution provided by a standard A* search algorithm to assess the performance and time efficiency of the proposed approach.
Date of Conference: September 19-22, 2023
Track: Space Domain Awareness