Optimal Pursuit of Moving Targets using Dynamic Voronoi Diagrams

Abstract

We consider Voronoi-like partitions for a team of moving targets distributed in the plane, such that each set in this partition is uniquely associated with a particular moving target in the following sense: a pursuer residing inside a given set of the partition can intercept this moving target faster than any other pursuer outside this set. It is assumed that each moving target employs its own "evading" strategy in response to the pursuer actions. In contrast to standard formulations of problems of this kind in the literature, the evading strategy does necessarily restrict the evader to be slower than its pursuer. In the special case when all moving targets employ a uniform evading strategy, the previous problem reduces to the characterization of the Zermelo-Voronoi diagram.