Tracking a Set of Moving Objects with Minimal Peak Power

Keeping track of a collection of moving objects is a fundamental problem with a long history in Computational Geometry. In air traffic control, stationary centers monitor planes with powerful tracking devices to coordinate overall motion. With the growing ubiquity of drones, air traffic control needs further development [4, 16], such as the use of less powerful tracking stations: How should we adjust sensing radii over time to minimize power consumption?

We illustrate exact and heuristic methods for the $\min \max$ variant of the Kinetic Disk Cover problem (KDC): Given a set of $m$ stationary sensors at positions $𝒴\subset {ℝ}^2$, as well as a set $𝒫$ of $n$ moving objects, each moving along a linear trajectory $p_i(t)$ over the time interval $t\in [0,1]$. How should we adjust the sensor range $r_i(t)$ to each center $y_i\in 𝒴$ at each time $t$, such that all objects are always within range of some sensor, and the maximum sum of areas ${\max }_{t\in [0,1]}{\sum }_{i=1}^m\pi r_i{(t)}^2$ of all disks is minimized?

We solve the kinetic problem with a primal–dual, iterative strategy. By combining exact stationary solutions with good heuristics for obtaining overall kinetic solutions, we generate a sequence of tighter and tighter upper and lower bounds and therefore provably near-optimal or even optimal solutions.

Our approach starts from a feasible, stationary solution at time $t=0$. We can extend any solution to the DC problem at time $t$ to a solution for the KDC problem over time by maintaining the same assignment of objects to stations and altering the supporting point of each station as needed to ensure coverage. This produces a feasible solution for all $t\in [0,1]$, yielding an upper bound for the optimal objective value. The upper bound can be further improved by considering the times at which it is advantageous to switch objects between covering stations, so-called handover points. In the full version of our paper [14], we establish the following; this can be generalized to three or more stations.

On the other hand, we can consider the time $t^{\prime }$ at which the peak total area is attained; an optimal solution for the static DC problem at $t^{\prime }$, which can be computed with the help of an Integer Programming (IP) solver, provides a lower bound for the kinetic problem.

In this formulation, $C$ is the set of all possible disks that can be formed by a station and an object, $r_i$ is the radius of the disk $d_i$, and $x_i$ indicates whether $d_i$ is selected. A solution for the stationary problem can again be extended to an overall solution for the kinetic problem. Combining it with the previous kinetic solution by extracting the lower envelope of both solutions yields an improved feasible solution, and thus a better upper bound, see Figure 2.

We carried out extensive experiments for solving a wide range of benchmark instances; see our full paper [14, 15] for a detailed description.

We considered the following benchmark sets.

fix_n

Fix number of objects to $n=500$. For $m\in \{5,10,\mathrm{\dots },50\}$ we generate $10$ instances.

fix_m

Fix number of sensors to $m=25$. For $n\in \{50,100,\mathrm{\dots },500\}$ we generate $10$ instances.

pub

Instances from well-known publicly available benchmarks used in [8], such as point sets from the CG:SHOP challenges [6, 5] and [18, 19, 7]. We scaled point sets to a fixed size and sampled $m=25$ centers and point pairs (for trajectories) at random.

We start by introducing and motivating the KDC problem before describing the primal-dual approach, illustrating the computation of upper and lower bounds as well as the overall iterative method. We proceed by showing some of the involved technical components and evaluations, concluding with a benchmark instance with $87$ objects and $25$ stations derived from a point set of the well-known TSPLIB benchmark library, as shown in Figure 5.

Overall video production was based on an integrated tool chain: Visual elements were produced with the free, open-source software Manim [20] for creating mathematical animations, which also supports conversion from scripted text to synchronized voiceover and animation. Voiceover was generated with the help of Microsoft Azure Speech [17].