.png){kind=icon}
.png){kind=icon}
Return
Parallel, Asymptotically Optimal Algorithms for Moving Target Traveling Salesman Problems
.png){kind=icon}
PRE
AI
A
G
B
Z
S
H
DOI：10.1109/tro.2026.3706565.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The moving target traveling salesman problem (MT-TSP) seeks a trajectory that intercepts several moving targets, within a particular time window for each target. When generic nonlinear target trajectories or kinematic constraints on the agent are present, no prior algorithm guarantees convergence to an optimal MT-TSP solution. Therefore, we introduce the iterated random generalized (IRG) TSP framework. The 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 asymptotically converges to the optimum. We introduce two parallel algorithms within the IRG framework. The first algorithm, IRG-parallel generalized large neighborhood search (PGLNS), solves GTSPs using PGLNS, our parallelized extension of state-of-the-art solver GLNS. The second algorithm, parallel communicating GTSPs (PCG), solves GTSPs for several sets of points simultaneously. We present numerical results for three MT-TSP variants: 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 robot arm. We show that IRG-PGLNS and PCG converge faster than a baseline based on prior work. We further validate our framework with physical robot experiments.
Keywords:
Combinatorial search
Dubins car
motion planning
parallelization
traveling salesman problem (TSP)
Journal
IF:
10.5
Papers:
3.3K
Citations:
2.8W
Organization
Cited Papers