Parallel, Asymptotically Optimal Algorithms for Moving Target Traveling Salesman Problems

Abstract--The Moving T arget Traveling Salesman Problem (MT -TSP) seeks an agent trajectory that intercepts several moving targets, within a particular time window for each target. Therefore, we introduce the Iterated Random Generalized (IRG) TSP framework. The key idea behind IRG is to alternate between randomly sampling a set of agent configuration-time points, corresponding to interceptions of targets, and finding a sequence of interception points by solving a generalized TSP (GTSP). This alternation enables asymptotic convergence to the optimum. We introduce two parallel algorithms within the IRG framework. The first algorithm, IRG-PGLNS, solves GTSPs using PGLNS, our parallelized extension of the state-of-the-art solver GLNS. The second algorithm, Parallel Communicating GTSPs (PCG), solves GTSPs corresponding to several sets of points simultaneously. We present numerical results for three variants of the MT -TSP: one where intercepting a target only requires coming within a particular distance, another where the agent is a variable-speed Dubins car, and a third where the agent is a redundant robot arm. We show that IRG-PGLNS and PCG both converge faster than a baseline based on prior work. The Traveling Salesman Problem (TSP) is a classic optimization problem with broad applications in various fields, including logistics, manufacturing, and robotics [1], [2]. Given a set of targets (often called "locations" or "cities") and the cost of travel between each target pair, the TSP seeks a minimum-cost order of targets for an agent to visit. However, several robotic applications require planning to visit moving targets: midair refueling [3], optimization of fishing routes [4], [5], resupplying ships at sea [6], surveillance [7]-[9], and intercepting dangerous projectiles [10]-[12]. In all subfigures, targets (stars) move along trajectories with time windows shown in bold colored lines.