In-Depth Notes on Probabilistic Path Planning: RRT and PRM

Probabilistic Path Planning Overview

Probabilistic Path Planning techniques are essential in robotics for navigating complex environments. Among the most notable algorithms in this domain are the Rapidly-Exploring Random Tree (RRT) and the Probabilistic Roadmap (PRM). These sampling-based methods help robots find effective paths from their starting configurations to target goal configurations in various environments.

Rapidly-Exploring Random Tree (RRT)

RRT is a sampling-based algorithm that constructs a tree incrementally from an initial configuration. The process involves sampling random target configurations and expanding the tree towards these configurations. Depending on user-defined parameters, sampled targets can either be random configurations or goal configurations.

Key Features of RRT:

  • Adaptability: Adapts well in dynamic environments without requiring pre-processing.

  • Search Dynamics: Although RRT is efficient in adapting, its search process can be time-consuming because it does not retain memory of prior searches.

Probabilistic Roadmap (PRM)

PRM is designed for situations in which multiple path queries are conducted in the same environment. It consists of two main phases:

  1. Preprocessing Phase: Construct a roadmap (an undirected graph) that includes nodes representing configurations of the robot selected from the configuration space free of obstacles (C-free).

  2. Query Phase: Search for paths between a given start and goal configuration using the established roadmap.

Characteristics of PRM:

  • Core Assumptions: Assumes static obstacles, allowing the roadmap to be reused across multiple queries, such as in static environments and for robot manipulators.

  • Efficiency Gains: The precomputation allows for faster query handling, reducing planning costs over numerous queries.

Sampling Techniques in PRM

When creating a PRM, the input typically includes the geometry of both the moving object and the obstacles present in the environment. The roadmap is constructed through the following steps:

  1. Initialize empty sets for vertices (V) and edges (E).

  2. Repeatedly sample configurations uniformly at random.

  3. If a sampled configuration is free from obstacles, it is added to the vertices set.

  4. Connections to neighboring vertices are checked for feasibility, creating edges where valid paths exist.

Advantages and Disadvantages of PRM

Advantages:

  • Probabilistically complete and can handle dynamic environments effectively with relatively fast query times due to precomputation.

Drawbacks:

  • Performance can suffer in narrow passages, requiring adaptations or variants to improve success rates in challenging routes. The algorithm also does not guarantee optimality or completeness.

Comparison Between RRT and PRM

Comparative analysis of RRT and PRM reveals distinct operational efficiency:

  • Run Time: PRM generally requires less time to find paths than RRT; for instance, testing scenarios show PRM yields faster results across varied environmental complexities.

  • Path Quality: RRT might provide longer path lengths in complex spaces, while PRM can yield shorter and smoother paths upon robust preprocessing.

Overall, both RRT and PRM contextually demonstrate their utility in high-dimensional spaces, with each technique offering unique benefits regarding efficiency and adaptability to various challenge environments. Understanding their respective strengths and weaknesses allows practitioners to select the most suitable algorithm for their specific robotics applications.