2️⃣Sampling-based Path Planning

Rapidly-exploring Random Tree (RRT)

Completeness

Probabilistic Completeness:

• Definition: An algorithm is probabilistically complete if, given infinite time, the probability that it will find a path, if one exists, approaches one.

• RRT: RRT is probabilistically complete. This means that if a feasible path exists, the RRT algorithm will eventually find it, given enough time and iterations. This is due to the nature of the algorithm, which randomly samples the search space and incrementally builds a tree that explores new regions. Over time, this random sampling ensures that all areas of the space are explored, increasing the likelihood of finding a valid path.

Optimality

RRT: The basic RRT algorithm is not optimal. While it is effective at finding feasible paths, it does not guarantee that the path found is the shortest or least-cost path. This is because the RRT algorithm prioritizes rapid exploration over optimization, often resulting in suboptimal paths.

RRT*

• Description: RRT* (RRT-Star) is an extension of RRT that aims to find optimal paths. It introduces a rewiring step that iteratively improves the path by considering the cost to reach each node and potentially rerouting the tree to reduce overall path cost.

• Optimality: RRT* is asymptotically optimal, meaning that as the number of samples approaches infinity, the path found by RRT* converges to the optimal path.

RRT-Smart*

• Completeness: RRT is probabilistically complete, meaning it will find a path if one exists, given enough time.

• Optimality: The basic RRT algorithm is not optimal, but extensions like RRT* and RRT*-Smart provide asymptotic optimality, ensuring that the path quality improves over time and eventually converges to the optimal path.