Finding a Way Through Obstacles
Path planning is a core challenge in robotics: find a collision-free path from start to goal in an environment with obstacles. While simple in a 2D maze, the problem becomes extraordinarily hard for robot arms with 6+ degrees of freedom, where the 'space' is high-dimensional and obstacles create complex forbidden regions. Sampling-based algorithms like RRT and PRM solve this efficiently by exploring the space randomly rather than exhaustively.
Rapidly-Exploring Random Trees (RRT)
RRT grows a tree rooted at the start configuration. Each iteration samples a random point in space, finds the nearest node in the tree, and extends toward the sample by a fixed step size. If the extension is collision-free, the new node is added. The tree has a natural bias toward unexplored regions because random samples in large empty areas are more likely to be nearest to frontier nodes. This Voronoi bias is the key insight that makes RRT effective.
Probabilistic Roadmaps (PRM)
PRM takes a different approach: first build a roadmap of the free space, then query it. The construction phase samples many random collision-free configurations and connects nearby pairs with collision-free straight-line paths. The result is a graph that approximates the connectivity of free space. Any start-goal query is answered by connecting both to the nearest roadmap nodes and running a graph search algorithm like Dijkstra's or A*.
From 2D to Configuration Space
This simulation shows path planning in 2D for visual clarity, but the same algorithms work in any dimension. For a 6-DOF robot arm, each axis represents a joint angle, and obstacles in physical space map to complex forbidden regions in this 6D configuration space. RRT and PRM handle this gracefully because they only need collision checking (not explicit obstacle representation) and scale well with dimensionality.