Traveing Salesperson Problems for a double integrator
<|reference_start|>Traveing Salesperson Problems for a double integrator: In this paper we propose some novel path planning strategies for a double integrator with bounded velocity and bounded control inputs. First, we study the following version of the Traveling Salesperson Problem (TSP): given a set of points in $\real^d$, find the fastest tour over the point set for a double integrator. We first give asymptotic bounds on the time taken to complete such a tour in the worst-case. Then, we study a stochastic version of the TSP for double integrator where the points are randomly sampled from a uniform distribution in a compact environment in $\real^2$ and $\real^3$. We propose novel algorithms that perform within a constant factor of the optimal strategy with high probability. Lastly, we study a dynamic TSP: given a stochastic process that generates targets, is there a policy which guarantees that the number of unvisited targets does not diverge over time? If such stable policies exist, what is the minimum wait for a target? We propose novel stabilizing receding-horizon algorithms whose performances are within a constant factor from the optimum with high probability, in $\real^2$ as well as $\real^3$. We also argue that these algorithms give identical performances for a particular nonholonomic vehicle, Dubins vehicle.<|reference_end|>
@article{savla2006traveing,
    title={Traveing Salesperson Problems for a double integrator},
    author={Ketan Savla, Francesco Bullo and Emilio Frazzoli},
    journal={arXiv preprint arXiv:cs/0609097},
    year={2006},
    archivePrefix={arXiv},
    eprint={cs/0609097},
    primaryClass={cs.RO}
}