PRM & PRM*
RRT generates an entirely new graph each time a new location was given. An alternative approach that addresses this deficiency is the Probabilistic Roadmap (PRM) algorithm. Probabilistic Road map (PRM) builds a single roadmap that aims to cover a good portion of the Cfree area. However it also cannot generate the shortest path at the same time. A shortest path planning algorithm like Dijkstra’s algorithm, A* or D* is then used to navigate across the roadmap.
When applied to 3D space, PRM first defines the configuration space 𝑋 and an obstacle free space 𝑋free. The method samples a random state in 𝑋free. Then it tries to connect to nearest 𝑘 neighbors (𝐾-PRM) or connect to states within a 𝛿-ball region (𝑆-PRM)
Types of PRM
𝐾-PRM: Here each step choose nearest 𝑘 neighbors to be the states which are under consideration. Although 𝐾-PRM has the advantage of adopting enough samples to ensure smoothness by adjusting parameter 𝑘, the result will be biased if a fixed direction tends to be much denser.
𝑆-PRM: The expected states are to be chosen within a predefined radius. 𝑆-PRM can keep out the shortcoming of 𝐾-PRM, but an unreasonable radius ‘𝑟’ may result in an excessive computational burden.
𝐾-𝑆-PRM: A combination of above two, where for a given radius ‘𝑟’ the upper bound of the vertices to be chosen is 𝑘. 𝐾-𝑆-PRM is adaptable as it can guarantee all direction connection and also limit the computational burden to a certain degree.
Methodology
After a new node is generated, the PRM algorithm clusters nodes into connected components. To perform clustering, all nodes within a fixed radius of the randomly generated node are collected. These neighboring nodes are ordered by increasing distance (or the desired metric). Looping through the ordered neighboring nodes, check if the randomly generated node is not in the same cluster as the examined node. The new node is added to the cluster if the condition is satisfied. A node can, and should, belong to multiple clusters.
PRM Pseudo Code
G(V,E) = Null //Initialize a graph as empty
limit = n //number of nodes to make graph out of
Rad = r //radius of neighborhoods
For itr in 0…limit:
Xnew = RandomPosition()
Xnearest = Near(G(V,E),Xnew,Rad) //find all nodes within a Rad
Xnearest = sort(Xnearest) //sort by increasing distance
For node in Xnearest:
if not ConnectedComp(Xnew,node) and not Obstacle(Xnew,node):
G(V,E) += {Xnew,node} //add edge and node to graph
Xnew.comp += node.comp//add Xnew to connected component
Return G(V,E)
Tunable Parameters:
Radius: Radius size defines the extent till which the neighbors are chosen. A larger radius will involve parsing through more neighbors whereas a smaller radius will cover lesser number of neighbors.
No. of Nodes: Another parameter the user determines is the number of nodes. The PRM algorithm ends once the number of desired nodes is generated. Having to generate too many nodes can prolong the time it takes to develop the roadmap. Having too few nodes can result in a fractured graph. Clusters, especially in high density obstacle regions, can become disconnected from the remainder of the road map.
PRM*
Similarly to RRT*, PRM* makes two modifications to the default PRM algorithm. This optimized algorithm does not use a fixed radius. Instead, the radius used to find neighbors varies by the number of nodes that have already been placed.
The radius, labeled Rprm* is determined by the number of nodes, n , the number of dimensions, d , and a constant based on characteristics of the space being used, 𝛾prm*.
Log(n)/n term
Considering how this function behaves, we expect the size of the radius to be fairly large (ideally covering the whole space) when there are few nodes and shrink as more nodes are added. This modification in radius makes sure that the paths generated are straighter.
The second modification made to PRM removes the whole cluster system. When new nodes are added, their relation to neighboring nodes is not limited by other nodes they have already been added to. Instead, any node that falls within the radius value becomes connected.
The benefit of such a graph is that generated paths will be incredibly smooth. Part of the jaggedness in default PRM is due to clustering.
PRM* Pseudo Code
G(V,E) = Null //Initialize a graph as empty
limit = n //number of nodes to make graph out of
For itr in 0…limit:
Xnew = RandomPosition()
Rad = yprm*(log(itr)/(itr))^(1/d)
Xnearest = Near(G(V,E),Xnew,Rad) //find all nodes within a Rad
For node in Xnearest:
if not Obstacle(Xnew,node):
G(V,E) += {Xnew,node}connected component
Return G(V,E)
