We present methods for offline generation of sparse roadmap spanners that result in graphs 79 smaller than existing approaches while returning solutions of equivalent path quality. Our method uses a hybrid approach to sampling that combines traditional graph discretization with random sampling. We present techniques that optimize the graph for the L1-norm metric function commonly used in joint-based robotic planning, purposefully choosing a @math -stretch factor based on the geometry of the space, and removing redundant edges that do not contribute to the graph quality. A high-quality pre-processed sparse roadmap is then available for re-use across many different planning scenarios using standard repair and re-plan methods. Pre-computing the roadmap offline results in more deterministic solutions, reduces the memory requirements by affording complex rejection criteria, and increases the speed of planning in high-dimensional spaces allowing more complex problems to be solved such as multi-modal task planning. Our method is validated through simulated benchmarks against the SPARS2 algorithm. The source code is freely available online as an open source extension to OMPL.
One of the most popular methods for solving the robotic motion planning problem has been the sampling-based probabilistic roadmap (PRM) @cite_8 . While in theory PRMs are pre-processed and reusable across all environments, in practice they are typically only re-usable for a given environment, though in some implementations more general re-use is actually achieved such as in Dynamic Roadmaps @cite_4 . Even for versions of PRMs that can re-use their roadmap in changing environments, there are open questions on how to generate efficient and high quality graphs. Traditional PRMs are probabilistically complete but do not provide any guarantees on the quality of the path returned. PRM* @cite_5 has been proven to be asymptotically optimal as samples are infinitely added to the roadmap.
@cite_5 @cite_4 @cite_8
2122724557 1986004895 2142644931 2000194319
Probabilistic roadmap (PRM) planners have been successful in path planning of robots with many degrees of freedom, but sampling narrow passages in a robot's configuration space remains a challenge for PRM planners. This paper presents a hybrid sampling strategy in the PRM framework for finding paths through narrow passages. A key ingredient of the new strategy is the bridge test, which reduces sample density in many unimportant parts of a configuration space, resulting in increased sample density in narrow passages. The bridge test can be implemented efficiently in high-dimensional configuration spaces using only simple tests of local geometry. The strengths of the bridge test and uniform sampling complement each other naturally. The two sampling strategies are combined to construct the hybrid sampling strategy for our planner. We implemented the planner and tested it on rigid and articulated robots in 2-D and 3-D environments. Experiments show that the hybrid sampling strategy enables relatively small roadmaps to reliably capture the connectivity of configuration spaces with difficult narrow passages. Sampling-based algorithms have proven practical in solving motion planning challenges in relatively high-dimensional instances in geometrically complex workspaces. Early work focused on quickly returning feasible solutions. Only recently was it shown under which conditions these algorithms asymptotically return optimal or near-optimal solutions. These methods yield desired properties only in an asymptotic fashion, i.e., the properties are attained after infinite computation time. This work studies the finite-time properties of sampling-based planners in terms of path quality. The focus is on roadmap-based methods, due to their simplicity. This work illustrates that existing sampling-based planners which construct roadmaps in an asymptotically (near-)optimal manner exhibit a “probably near-optimal” property in finite time. This means that it is possible to compute a confidence value, i.e. a probability, regarding the existence of upper bounds for the length of the path returned by the roadmap as a function of the number of configuration space samples. This property can result in useful tools for determining existence of solutions and a probabilistic stopping criterion for PRM-like methods. These properties are validated through experimental trials. This paper presents a randomized motion planner for kinodynamic asteroid avoidance problems, in which a robot must avoid collision with moving obstacles under kinematic, dynamic constraints and reach a specified goal state. Inspired by probabilistic-roadmap (PRM) techniques, the planner samples the state x time space of a robot by picking control inputs at random in order to compute a roadmap that captures the connectivity of the space. However, the planner does not precompute a roadmap as most PRM planners do. Instead, for each planning query, it generates, on the fly, a small roadmap that connects the given initial and goal state. In contrast to PRM planners, the roadmap computed by our algorithm is a directed graph oriented along the time axis of the space. To verify the planner's effectiveness in practice, we tested it both in simulated environments containing many moving obstacles and on a real robot under strict dynamic constraints. The efficiency of the planner makes it possible for a robot to respond to a changing environment without knowing the motion of moving obstacles well in advance. 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.