Heterogeneous Pursuit of Multiple Translating Targets

We consider the problem of minimum time inter- cept of multiple mobile targets that are translating in a fixed direction, i.e., moving with identical constant speeds in the same direction. Every target has to be intercepted by a heterogeneous pursuer assembly – a mobile vehicle that carries another pursuer whose speed is higher than that of the vehicle. Aside from this novel problem formulation, our main contributions are as follows. First, we formally establish that the optimal heterogeneous intercept problem is equivalent to solving an appropriately defined Euclidean Traveling Salesperson Problem with Neighborhoods (ETSPN). We show that each neighborhood is an ellipse with a specified center and lengths of the major and minor axis. Second, we provide novel upper bounds on the optimal length as a function of the problem parameters, i.e., the number of targets, the speed ratio between the target and the assembly, the speed between the pursuer and the assembly, the geometry of the region containing the targets and the time required for the pursuer to intercept a target. Finally, we offer insight into the approach through a numerical visualization and a discussion on improving the upper bounds.