An important variant of the classic Traveling Salesman Problem (TSP) is the Dynamic TSP, in which a system with dynamic constraints is tasked with visiting a set of n target locations (in any order) in the shortest amount of time. Such tasks arise naturally in many robotic motion planning problems, particularly in exploration, surveillance and reconnaissance, and classical TSP algorithms on graphs are typically inapplicable in this setting. An important question about such problems is: if the target points are random, what is the length of the tour (either in expectation or as a concentration bound) as n grows? This problem is the Dynamic Stochastic TSP (DSTSP), and has been studied both for specific important vehicle models and for general dynamic systems; however, in general only the order of growth is known. In this work, we explore the connection between the distribution from which the targets are drawn and the dynamics of the system, yielding a more precise lower bound on tour length as well as a matching upper bound for the case of symmetric (or driftless) systems. We then extend the symmetric dynamics results to the case when the points are selected by a (non-random) adversary whose goal is to maximize the length, thus showing worst-case bounds on the tour length.

翻译：典型旅游推销员问题(TSP)的一个重要变体是动态TSP(动态TSP),在TSP中,一个具有动态限制的系统的任务是在最短的时间内访问一组目标地点(按任何顺序),这些任务自然出现在许多机器人运动规划问题中,特别是在勘探、监视和侦察方面,图表上的传统的TSP算法通常不适用于这一环境。关于这些问题的一个重要问题是:如果目标点是随机的,那么旅行的长度(预期的或集中的)随着对称(或无漂移)系统的增长而增加?这个问题是动态托盘TSP(DSTSP),并且已经为特定的重要车辆模型和一般动态系统进行了研究;然而,一般来说,只有增长的顺序是已知的。在这项工作中,我们探索了目标的分布与系统动态之间的联系,从而更精确地缩短了旅行的长度,同时为对称(或无漂移)系统设定的高度界限。我们随后将对称的动态结果扩大到由最短的导游选择的点显示最短的距离时的情况。