Samuel Fedeler, University of Colorado at Boulder; Marcus Holzinger, University of Colorado Boulder; William Whitacre, Draper Laborartory
Keywords: Sensor Tasking, SSA
Abstract:
In this work, we propose and analyze the application of tree search methodologies to resolve the challenging problem of multi-sensor tasking over a receding horizon. Determination of policies for a set of sensors tasked to maintain custody of space objects in various orbit regimes is increasingly relevant to Space Domain Awareness. As a result of accelerating growth in satellite populations, it is imperative that limited observational assets are utilized efficiently.The problem at hand quickly becomes combinatoric as the object catalog considered expands, and multiple competing objectives are often desired to leverage uncued detection of objects in addition to catalog maintenance. As such, the sensor tasking problem is largely broken into tractable subproblems, in which the objective is to capture a single aspect of the overarching goal. A variety of methodologies have previously been proposed for object discovery and catalog maintenance, typically with special focus on the geostationary regime.
We consider the subproblem of catalog maintenance, posing the multi-sensor tasking problem as a Partially Observable Markov Decision Process (POMDP) with the goal of determining time histories of optimal pointing for a given set of sensor locations and specifications. Monte Carlo Tree Search (MCTS) approaches are considered given the broad action space and continuous observation and state spaces inherent to the sensor tasking problem. In previous work, a tree search methodology was developed treating belief in states as a set of Gaussian random variables. While many MCTS methods represent belief as a set of particles, this methodology allows for high dimensional states to be represented in the tree search format while avoiding the curse of dimensionality inherent to particle-based techniques.
Several contributions are submitted in this proposed work. Primarily, an induction-based proof is applied to demonstrate convergence and guarantees of the tree search methodology as a function of tree search iterations; this proof differs from that of Auger et al. (2013) in its application to the POMDP framework. Instead of a randomized, generative state transition model, the POMDP framework must use measurements and likelihood sampling in the traversal from decision nodes to observation nodes. As a further modification, consistent with seminal MCTS works by Kocsis and Szevepari and Chang et al., a logarithmic function is used for exploration of the action space. To accompany this derivation, regret analyses are performed to numerically evaluate algorithmic behavior over a variety of use cases. In these cases, we compare average realized reward as a function of search tree iterations to an oracle defined by the search tree result with a large number of simulations. Parallelization implementations are discussed as a means to ensure sufficient search tree simulation for online usage of MCTS over a receding horizon. Finally, the tree search algorithm is applied to a large-scale, multi-observer use case studying a population of 1000 objects in both geostationary and low-Earth orbits over a several day observation campaign.
The methodologies discussed are most impactful in that tree search techniques can be applied in an embarrassingly parallel manner, allowing for broad exploration of possible tasking decisions. There is also high potential for the use of tree search methods in situations where dynamic environments and measurement models must be considered. Given appropriate modeling, the MCTS methods discussed are easily augmented to incorporate false alarm and detection probabilities, weather and lighting conditions, and sensor uncertainties. As such, MCTS techniques offer addition and extension to information theoretic methodologies, allowing for broader understanding of the tasking problem.
Date of Conference: September 15-18, 2020
Track: SSA/SDA