[MUSIC] In the previous module, we talked about configuration space, and we discussed the idea of a collision check function that could be used to decide whether a given point in configuration space was in free space or not. By checking whether that configuration led to a collision with the obstacles in the work space. We also talked about the idea of a simple planning scheme that worked by using the collision check function to sample the configuration space at a set of regularly spaced discreet locations on a grid. Linking adjacent points in free space with edges, and then using this graph to plan pass through the space. This approach of discreetizing the configuration space evenly on a grid, can work well when the dimension of the space is small, say two or three. But the number of samples required can grow to be frighteningly large as we increase the dimension of the space to five, six, eight, ten, or beyond. An alternative idea for dealing with these situations is to choose the points in the configuration space randomly instead of uniformly. In the hope that we will choose a set of configurations that capture the underlying structure of the free space. This set of slides illustrates the basic idea on a two dimensional configuration space. On every iteration, the system chooses a configuration in the configuration space at random, and tests whether it is in free space using the collision check function. In this figure, the new random node is the green dot. If it is in free space, it then tries to see if it can forge routes between this new configuration and the closest existing samples in the graph. Every path that it creates is recorded as a new edge in the graph that the system is building. In this figure, the solid green lines correspond to new links that are added, while the dashed green line represents a connection that failed due to collision with the obstacle. Here's the basic outline of the procedure in pseudo code. Again, our goal here is to construct a graph of configuration space points and edges that capture the underlying topology of the freespace. We can think of the edges between the random samples as roadways that form a network that hopefully spans this freespace. This helps to explain why we call this procedure the Probabilistic Road Map method, or PRM for short. Probabilistic to reflect the stochastic nature of the process and road map for the graph that the procedure constructs which we hope will serve as a road map for the freespace. Note that this procedure requires two ingredients. Firstly, a distance function that considers the configuration space coordinates of two points, x1 and x2, and returns a real number which is supposed to be reflective of the distance between those two configurations. Often, this can be done pretty simply by computing standard functions like the L1 or L2 distances as shown here. For robots that involve rotational joints, you usually need to be a bit more careful to handle wrap around correctly so that your distance function correctly captures the topology of the configuration space. For example, if theta 1 and theta 2 are two angular values in degrees between 0 and 360, you may choose to use a distance function like this that captures the fact that 0 and 360 actually correspond to the same orientation. The other element of the PRM procedure is a local planner, which decides whether there is a path between two points, x1 and x2. A common way to handle this is to construct a set of evenly spaced samples on a straight line between the two configurations. And to use the collision check function to check that all of these intermediate configurations are collision free. So in this example, the local planet would decide that there is a path between the two points in question. While in the second case, it would decide that there isn't. If the sampling between the two endpoints is fine enough, this procedure is usually sufficient. Once the PRM procedure has generated what we believe to be a sufficient sampling of the configuration space, we can try to generate paths between designated start and end configurations. We start off by attempting to connect the start and goal configurations to nearby nodes on the roadmap. If this step succeeds, one can then attempt to find a path between the start and end nodes via the road map using our usual suite of graph-based planning algorithms, like Dijkstra's method or A star. This second phase, where we are planning a path between two specific locations is referred to as the query phase. This first slide shows the original probabilistic road map constructing via random sampling. The next slide shows the road map augmented with the start and end notes, which are attached to the road map using the green edges. This final version shows the path planned through this augmented graph. Note that once the road map has been constructed, it can be used to answer various path planning problems. So the cost of constructing the road map graph can be amortized over multiple queries. This is great if you're going to be running your robot back and forth through the same environment.
