Drone Air Traffic Control: Tracking a Set of Moving Objects with Minimal Power
Chek-Manh Loi, Michael Perk, Malte Hoffmann, Sándor Fekete
AI summary
Problem
How to dynamically adjust the sensing radius of stationary tracking stations to minimize peak power consumption while continuously monitoring a set of moving objects.
Approach
The authors extend stationary disk-covering solutions over time by analytically tracking supporting point changes and object handovers between stations, combined with integer programming for optimality guarantees.
Key results
- Proves the kinetic disk covering problem remains NP-hard even with an optimal initial solution
- Develops an exact algorithm and efficient heuristics for the min-max power variant
- Solves instances with 500 moving objects and 25 stations in seconds
- Validates real-time capability and optimality across diverse benchmark scenarios
Why it matters
Enables energy-efficient, real-time tracking for emerging drone air traffic control systems and dynamic sensor networks.
Abstract
A common sensing problem is to use a set of stationary tracking locations to monitor a collection of moving devices: Given n objects that need to be tracked, each following its own trajectory, and m stationary traffic control stations, each with a sensing region of adjustable range; how should we adjust the individual sensor ranges in order to optimize energy consumption? We provide both negative theoretical and positive practical results for this important and natural challenge. On the theoretical side, we show that even if all objects move at constant speed along straight lines, no polynomial-time algorithm can guarantee optimal coverage for a given starting solution. On the practical side, we present an algorithm based on geometric insights that is able to find optimal solutions for the min max variant of the problem, which aims at minimizing peak power consumption. Runtimes for instances with 500 moving objects and 25 stations are in the order of seconds for scenarios that take minutes to play out in the real world, demonstrating real-time capability of our methods.