2013 · 143 citations · 21 references
ComputingComputer ScienceMathematicsDynamical SystemsMotion PlanningOptimizationOptimal ControlProbabilistic RoadmapsRapidly Exploring Random TreesRobot Motion PlanningTrajectory OptimizationAlmost Sure ConvergenceAsymptotic Optimality Of Rapidly Exploring Random TreesAsymptotic PropertiesComplex Differential GeometryDubins Rapidly Exploring Random TreesMotion Planning With Rapidly Exploring Random TreesSampling-based Motion PlanningSampling-based Trajectory Planning
Sampling-based motion planning algorithms, such as the Probabilistic RoadMap (PRM) and the Rapidly-exploring Random Tree (RRT), have received a large and growing amount of attention during the past decade. Most recently, sampling-based algorithms, such as the PRM* and RRT*, that guarantee asymptotic optimality, i.e., almost-sure convergence towards optimal solutions, have been proposed. Despite the experimental success of asymptotically-optimal sampling-based algorithms, their extensions to handle complex non-holonomic dynamical systems remains largely an open problem. In this paper, with the help of results from differential geometry, we extend the RRT* algorithm to handle a large class of non-holonomic dynamical systems. We demonstrate the performance of the algorithm in computational experiments involving the Dubins' car dynamics.
21
Hypoelliptic second order differential equations
Lars Hörmander · Acta Mathematica · 1967 · 2.4K citations · Full text