2006 · 57 citations · 16 references
ComputingComputer ScienceIndustrial EngineeringAlgorithmsPath PlanningTransportationRoute PlanningShortest Path AlgorithmsStochastic Shortest Path ProblemsTrajectory GenerationTransportation ModelsTransportation ProblemsCurvatureCurvature Bounded AboveDubins Path PlanningStochastic Process AnalysisTour PlanningTraveling Salesman ProblemTraveling Salesperson ProblemTraveling Salesperson Problem Approximation
In this paper we propose some novel planning and routing strategies for Dubins’ vehicle, i.e., for a nonholonomic vehicle moving along paths with bounded curvature, without reversing direction. First, we study a stochastic version of the Traveling Salesperson Problem (TSP): given n targets randomly sampled from a uniform distribution in a rectangle, what is the shortest Dubins'tour through the targets and what is its length? We show that the expected length of such a tour is Ω(n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m=2/3</sup> )and we propose a novel algorithm that generates a tour of length O(n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m=2/3</sup> log(n) <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m=1/3</sup> ) with high probability. Second, we study a dynamic version of the TSP (known as "Dynamic Traveling Repairperson Problem" in the Operations Research literature): given a stochastic process that generates targets, is there a policy that allows a Dubins vehicle to stabilize the system, in the sense that the number of unvisited targets does not diverge over time? If such policies exist, what is the minimum expected waiting period between the time a target is generated and the time it is visited? We propose a novel receding-horizon algorithm whose performance is almost within a constant factor from the optimum.
16
P-Complete Approximation Problems
Sartaj Sahni, Teofilo F. Gonzalez · Journal of the ACM · 1976 · 1.7K citations · Full text