Probabilistic roadmaps for path planning in high-dimensional configuration spaces

By Lydia E. Kavraki, P. Svestka, Jean-Claude Latombe, Mark H. Overmars. 1996

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

A Survey of Embodied AI: From Simulators to Research Tasks (2021, background): “While classic navigation approaches [82] are usually composed of hand-engineered sub-components like localization, mapping [83], path planning [84, 85] and locomotion, the visual navigation in embodied AI aims to learn these navigation systems from data.”
A Survey of Autonomous Driving: Common Practices and Emerging Technologies (2019, methodology): “RRT is faster than PRM and both are probabilistically complete [253], which means a path that satisﬁes the given conditions will be guaranteed to be found with enough runtime.”
Overcoming Exploration in Reinforcement Learning with Demonstrations (2017, background): “More recent work on task and motion planning considers both logical and physical aspects of the task [27], [28], [29], but requires domainspecific engineering.”
A Survey of Motion Planning and Control Techniques for Self-Driving Urban Vehicles (2016, background): “[104] advocate the use of random sampling within the framework of Probabilistic Roadmaps (PRM) in order to construct roadmaps in high-dimensional configuration spaces, because unlike grids, they can be naturally run in an anytime fashion.”
Search on the Replay Buffer: Bridging Planning and Reinforcement Learning (2019, background): “Planning Algorithms : Planning algorithms (Choset et al., 2005; LaValle, 2006) efﬁciently solve long-horizon tasks, including those that stymie RL algorithms (see, e.g., Kavraki et al. (1996); Lau and Kuffner (2005); Levine et al. (2011)).”
Path Planning for Autonomous Vehicles in Unknown Semi-structured Environments (2010, unknown): “An alternative approach that guarantees kinematic feasibility of the path is a forward search in continuous coordinates, e.g., using rapidly exploring random trees (Kavraki et al. 1996 LaValle 1998 Plaku et al. 2007).”
Elastic Strips: A Framework for Motion Generation in Human Environments (2002, methodology): “The introduction of probabilistically complete algorithms (Kavraki et al. 1996) has significantly increased the applicability of motion planning algorithms and remains an active area of research (Amato et al.”
Randomized Kinodynamic Planning (1999, methodology): “In the probabilistic roadmap approach (Amato and Wu 1996; Kavraki et al. 1996), a graph is constructed in the configuration space by generating random configurations and attempting to connect pairs of nearby configurations with a local planner that will connect pairs of configurations.”
Terrain traversability analysis methods for unmanned ground vehicles: A survey (2013, background): “…terrain analysis enables the application of efficient graph search algorithms for the purpose of planning, that are currently still very popular and extensively used (see Kavraki et al., 1996; Pivtoraiko and Kelly, 2005; Melchior and Simmons, 2007; Howard et al., 2008; Jaillet et al., 2010).”
Autonomous Vehicle Technologies for Small Fixed-Wing UAVs (2003, methodology): “The EKF time update equations are as follows: _ ` = p +q sin`tanµ +rcos`tanµ (1) _ µ = q cos`irsin` ( 2 ) _ ˆ = q sin`secµ +rcos`secµ (3) where p, q, and r are roll, pitch, and yaw rates as measured by on-board rate gyros.”
The Open Motion Planning Library (2012, methodology): “This paper describes the Open Motion Planning Library (OMPL, http://ompl.kavrakilab.org), an open source C++ implementation of many sampling-based algorithms (such as the Probabilistic Roadmap Method (PRM) [14], Rapidly-expanding Random Trees (RRT) [15], Kinodynamic Planning by Interior-Exterior Cel”
Reset-free Trial-and-Error Learning for Robot Damage Recovery (2016, methodology): “The traditional algorithms in this category are “Rapidly Exploring Random Trees” (RRT) [42] and “Probabilistic Roadmaps for path planning in high-dimensional configuration spaces” (PRM) [43].”
Approaches for heuristically biasing RRT growth (2003, background): “argued convincingly for the use of pseudo random sampling in favor of randomized sampling in probabilistic roadmap planners [4].”
Rapidly-exploring random trees : a new tool for path planning (1998, background): “This leads to a probabilistically complete [4] holonomic planner.”
Cable manipulation with a tactile-reactive gripper (2019, methodology): “Motion planning for DLOs has traditionally used sampling-based approaches such as a probabilistic roadmap (PRM) (Kavraki et al., 1996) or Rapidly-exploring Random Trees (RRTs) (LaValle, 1998).”
Receding horizon control of autonomous aerial vehicles (2002, methodology): “Two well-known methods that have been applied to this problem are Probabilistic Road Maps [1] (PRMs) and Rapidly-exploring Random Trees [2] (RRTs).”
Incremental Sampling-based Algorithms for Optimal Motion Planning (2010, methodology): “In practical applications, the class of sampling-based motion planning algorithms, including, for instance, Probabilistic Roadmaps (PRMs) [17], [28], and Rapidly-exploring Random ar X iv :1 00 5.”