Traveing Salesperson Problems for a double integrator
| dc.creator | Savla, Ketan | |
| dc.creator | Bullo, Francesco | |
| dc.creator | Frazzoli, Emilio | |
| dc.date | 2006-09-17 | |
| dc.date.accessioned | 2026-07-07T07:23:54Z | |
| dc.date.available | 2026-07-07T07:23:54Z | |
| dc.description | 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. | |
| dc.identifier | https://arxiv.org/abs/cs/0609097 | |
| dc.identifier | http://arxiv.org/abs/cs/0609097 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/116153 | |
| dc.subject | Robotics | |
| dc.title | Traveing Salesperson Problems for a double integrator | |
| dc.type | text |