Workspace importance sampling for probabilistic roadmap planning
Published 1 April 2005
Hanna Kurniawati, David Hsu
Citations76
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
Probabilistic roadmap (PRM) planners have been successful in path planning of robots with many degrees of freedom, but they behave poorly when a robot's configuration space contains narrow passages. This paper presents workspace importance sampling (WIS), a new sampling strategy for PRM planning. Our main idea is to use geometric information from a robot's workspace as "importance" values to guide sampling in the corresponding configuration space. By doing so, WIS increases the sampling density in narrow passages and decreases the sampling density in wide-open regions. We tested the new planner on rigid-body and articulated robots in 2-D and 3-D environments. Experimental results show that WIS improves the planner's performance for path planning problems with narrow passages.
Keywords
Computer ScienceEngineering
IEEE Transactions on Robotics and AutomationProbabilistic roadmaps for path planning in high-dimensional configuration spaces
6,186 Citations1996Lydia E. Kavraki, P. Švestka +2 more
Experimental results show that path planning can be done in a fraction of a second on a contemporary workstation (/spl ap/150 MIPS), after learning for relatively short periods of time (a few dozen seconds).
ACM Transactions on Mathematical SoftwareThe quickhull algorithm for convex hulls
5,343 Citations1996C. Bradford Barber, David Dobkin +1 more
This article presents a practical convex hull algorithm that combines the two-dimensional Quickhull algorithm with the general-dimension Beneath-Beyond Algorithm, and provides empirical evidence that the algorithm runs faster when the input contains nonextreme points and that it used less memory.
Choice Reviews OnlineComputer graphics: principles and practice
4,665 Citations2013
This chapter discusses the development of Hardware and Software for Computer Graphics, and the design methodology of User-Computer Dialogues, which led to the creation of the Simple Raster Graphics Package.
The International Journal of Robotics ResearchRandomized Kinodynamic Planning
3,248 Citations2001Steven M. LaValle, James Kuffner
ACM SIGGRAPH Computer GraphicsAnimating rotation with quaternion curves
1,724 Citations1985Ken Shoemake
Path planning using lazy PRM
841 Citations2000Robert Bohlin, Lydia E. Kavraki
The overall theme of the algorithm, called Lazy PRM, is to minimize the number of collision checks performed during planning and hence minimize the running time of the planner.
The power crust
707 Citations2001Nina Amenta, Sunghee Choi +1 more
A careful design of a key subroutine which labels parts of the MAT as inside or outside of the object, easy in theory but non-trivial in practice is described, which leads to a simple algorithm with theoretical guarantees comparable to those of other surface reconstruction and medial axis approximation algorithms.
Monte Carlo Methods
666 Citations2008Malvin H. Kalos
Simulations of Stochastic Systems: Radiation Transport and Monte Carlo Evaluation of Finite-Dimensional Integrals show random walks, Integral Equations, and Variance Reduction in addition to classical Monte Carlo methods.
Path planning in expansive configuration spaces
546 Citations2002David Hsu, J.-C. Latombe +1 more
The analysis of expansive configuration spaces has inspired a new randomized planning algorithm that tries to sample only the portion of the configuration space that is relevant to the current query, avoiding the cost of precomputing a roadmap for the entire configuration space.
The Gaussian sampling strategy for probabilistic roadmap planners
545 Citations2003V. Boor, M.H. Overmars +1 more
This paper presents a new, simple sampling strategy, which it is called the Gaussian sampler, that gives a much better coverage of the difficult parts of the free configuration space.
Efficient distance computation between non-convex objects
390 Citations2002Sean Quinlan
An efficient algorithm for computing the distance between nonconvex objects by using a simple search routine that uses the bounding representation to ignore most of the possible pairs of components.
The bridge test for sampling narrow passages with probabilistic roadmap planners
356 Citations2004David Hsu, Tingting Jiang +2 more
A hybrid sampling strategy in the PRM framework for finding paths through narrow passages is presented, which enables relatively small roadmaps to reliably capture the connectivity of configuration spaces with difficult narrow passages.
MAPRM: a probabilistic roadmap planner with sampling on the medial axis of the free space
337 Citations2003Steven Albert Wilmarth, Nancy M. Amato +1 more
A new method of sampling the configuration space in which randomly generated configurations are retracted onto the medial axis of the free space is proposed, and it is shown that sampling and retracting in this manner increases the number of nodes found in small volume corridors in a way that is independent of the volume of the corridor and depends only on the characteristics of the obstacles bounding it.
Planning motions with intentions
269 Citations1994Yoshihito Koga, Koichi Kondo +2 more
A new path planner is presented that automatically computes the collision-free trajectories for several cooperating arms to manipulate a movable object between two configurations and a new inverse kinematics algorithm for the human arms is presented.
International Journal of Computational Geometry & ApplicationsPATH PLANNING IN EXPANSIVE CONFIGURATION SPACES
264 Citations1999David Hsu, JEAN-CLAUDE LATOMBE +1 more
OBPRM: An Obstacle-Based PRM for 3D Workspaces
246 Citations1998
This paper presents a new class of randomized path planning methods, known as Probabilistic Roadmap Methods (prms), which use randomization to construct a graph of representative paths in C-space whose vertices correspond to collision-free con gurations of the robot.
A framework for using the workspace medial axis in PRM planners
149 Citations2000Christopher Holleman, Lydia E. Kavraki
This work examines the medial axis as a skeleton, including a method to compute an approximation to it, and forms a heuristic for finding difficult configurations using the medialaxis, and demonstrates its effectiveness in a planner for rigid objects in a 3D workspace.
Assembly maintainability study with motion planning
128 Citations2002Hsuan Chang, Tsai‐Yen Li
By applying results from and developing extensions to research in motion planning and other fields, the authors demonstrate that an automated maintainability study system is feasible and shows results from applying such a system to two classes of industrial application problems.
Journal of Computational BiologyStochastic Roadmap Simulation: An Efficient Representation and Algorithm for Analyzing Molecular Motion
121 Citations2003Mehmet Serkan Apaydın, Douglas L. Brutlag +4 more
Visibility based probabilistic roadmaps
119 Citations2003C. Nissoux, Thierry Siméon +1 more
A free-space structuring of the configuration space into visibility domains in order to produce small roadmaps is exploited and the efficiency of the approach in capturing narrow passages of collision-free configuration spaces is shown.
Journal of Computational BiologyUsing Motion Planning to Map Protein Folding Landscapes and Analyze Folding Kinetics of Known Native Structures
110 Citations2003Nancy M. Amato, Ken A. Dill +1 more
A Voronoi-based hybrid motion planner
103 Citations2002Mark Foskey, Maxim Garber +2 more
A hybrid path planning algorithm for rigid and articulated bodies translating and rotating in a 3D workspace and combines it with "bridges" computed by a randomized path planner with Voronoi-biased sampling, substantially reducing the number of random samples needed for the full query.
Stochastic roadmap simulation
53 Citations2002Mehmet Serkan Apaydın, Douglas L. Brutlag +3 more
This work introduces Stochustic Roadmap Sirrrcllation (SRS), a new approach for exploring the kinetics of molecular motion by simultaneously examining multiple pathways encoded compactly in a graph, called a roadmap, and shows that, in the limit, SRS converges to the same distribution as Monte Carlo simulation.
Using workspace information as a guide to non-uniform sampling in probabilistic roadmap planners
50 Citations2004J.P. van den Berg, M.H. Overmars
Using motion planning to map protein folding landscapes and analyze folding kinetics of known native structures
28 Citations2002Nancy M. Amato, Ken A. Dill +1 more
The ability to produce large sets of unrelated folding pathways may potentially provide crucial insight into some aspects of folding kinetics, such as proteins that exhibit both two-state and three-state kinetics that are not captured by other theoretical techniques.
Canadian Conference on Computational GeometryTetrahedralization of Simple and Non-Simple Polyhedra.
10 Citations1993Godfried T. Toussaint, Clark Verbrugge +2 more
It is shown that certain classes of rectilinear (isothetic) simple polyhedra can always be tetrahedralized in O( n2) time where n is the number of vertices in the polyhedron.