提出并行算法解决动态目标旅行商问题，高效逼近最优解。
Parallel, Asymptotically Optimal Algorithms for Moving Target Traveling Salesman Problems
- 交替随机采样与求解广义旅行商，渐进收敛到最优。
- 在三种动态场景下，算法收敛速度优于已有基准方法。
- 适合需要实时规划的机器人、自动驾驶等复杂系统应用。
移动目标旅行商问题（MT-TSP）旨在寻找一条轨迹，在每个目标的特定时间窗口内完成拦截。当目标轨迹为非线性或对代理有运动约束时，现有算法无法保证收敛至最优解。为此，本文提出迭代随机广义旅行商（IRG）框架：通过交替随机采样代理与目标的时空交汇点，并求解广义旅行商问题（GTSP）来优化路径，实现渐近最优。在此框架下，提出两种并行算法：IRG-PGLNS使用我们改进的并行化状态前沿求解器PGLNS求解GTSP；PCG则并行求解多组点集的GTSP。在三种变体上验证：仅需接近目标、变量速杜宾斯车辆、机械臂场景。结果表明IRG-PGLNS与PCG比基线算法收敛更快。进一步通过物理机器人实验验证了该框架的有效性。
原文摘要 · Abstract (English)
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-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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。