Schedule optimisation algorithm for tracking sensors

Tracking sensors, e.g. radar or laser ranging systems, are used to refine orbits of catalogued objects. A special tracking request has to be submitted whenever a reduction of uncertainty is required. This is the case for objects with a close approach above a certain risk level or whenever an object state gets uncertain to a level where it might drop out of the catalogue. However, if a sensor continuously runs to support a surveillance network to maintain a catalogue, an efficient track scheduling algorithm becomes important. As multiple objects can be seen simultaneously on the sky, decisions have to be taken which objects are observed and which are reachable afterward considering a limited steering velocity.
This work proposes to formulate the track schedule optimisation as a longest path problem for a directed acyclic graph (DAG). Each track is modelled as a node of the graph and each edge connecting the nodes is assigned with a weight, e.g. information gain. The overall goal of the algorithm is to maximise the sum of these weights. It is achieved by finding the path through the graph with the largest overall weight. This weighted longest path optimisation problem can be solved in linear time for the special case of a DAG. The formulation of the problem and the solution algorithm will be presented along with an example schedule optimisation.