2010 · 10 citations · 16 references
ComputingComputer ScienceRobotics EngineeringMobile RoboticsMotion PlanningRoboticsCell DecompositionMonte Carlo MethodsProbabilistic RoadmapsRigid Body KinematicsRobot Motion PlanningTrajectory GenerationExplorationFree-space PartitioningSampling In State SpaceSampling-based Motion PlanningSampling-based Trajectory Planning
We consider a problem of rigid body motion planning in a static 3D environment. In the past, methods based on random sampling like Probabilistic Roadmap and its variants proved to be able to efficiently solve many important instances of that problem. Performance of these methods degrades drastically in the presence of narrow passages. We propose a different approach to motion planning which combines elements of both cell decomposition methods and sampling based methods. We estimate signed distance to the boundary of free space at sampling points and use that information to guide farther exploration. Cell decomposition is used to generate deterministic sampling positions with non-uniform and dynamically adjusted densities. We report the results of experiments with implementation of our method.
16
Rapidly-exploring random trees : a new tool for path planning
Steven M. LaValle · 1998 · 3.6K citations