Sample Based Motion Planning Methods
Simple Planning scheme:
• Sample the configuration space as a set of regularly-spaced discrete locations on a grid. This is called grid-based sampling.
Copyright By PowCoder代写 加微信 powcoder
• Use the CollisionCheck (x) function to determine whether the point is in free space.
• Link the adjacent locations in the free space with edges and use this graph to plan path through the space.
Recap: Collision Checking
CollisionCheck (x) = 0
Recap: Collision Checking
CollisionCheck (x) = 1
Sampled Points in freespace
We used the CollisionCheck (x) function to determine whether the point is in free space.
Graph Made from Sampled Points
• Link the adjacent locations in the free space with edges and use this graph to plan path through the space.
Path through graph
Issues with uniformly-sampled Planning scheme:
• This approach of discretizing the configuration space evenly on a grid can work well when the dimension of the space is small, say 2 or 3.
• Issue arises when the number of dimension is higher, say 5 or 6 or higher, as the number of samples increases significantly.
• Computationally expensive
• An idea to address to this issue to choose the samples in the configuration space randomly instead of uniformly. The hope is that we choose as set of configurations/locations that capture the underlying structure of the free space.
• This random sampling strategy leads us to explore probabilistic approaches such as probabilistic roadmap.
Random Graph Construction
Recap: Path-Planning Approaches
1. Roadmap
Represent the connectivity of the free space by
a network of 1-D curves
2. Cell decomposition
Decompose the free space into simple cells and represent the connectivity of the free space by the adjacency graph of these cells
3. Potential field
Define a function over the free space that has a global minimum at the goal configuration and follow its steepest descent
Roadmap Methods
§Visibility graph §Voronoi diagram
§ Silhouette
First complete general method that applies to spaces of any dimension and is singly exponential in # of dimensions [Canny, 87]
§Probabilistic roadmaps
Probabilistic Road Map (PRM) Pseudocode
• Repeatntimes
o Generate a random point in configuration space, x o If x is in freespace
• Find the k closest points in the roadmap to x according to the Dist function
• Try to connect the new random sample to each of the k neighbors using the LocalPlanner procedure. Each successful connection forms a new edge in the graph.
Random Graph Construction
Random Graph Construction
Random Graph Construction
Solid green lines: new edges added to the graph
Dashed green line: failed due to collision with obstacles
Random Graph Construction
Probabilistic Road Map (PRM)
The PRM procedure relies on two important component: (1) Distance function
(2)Local Planner
(1) The Dist function
• The PRM procedure relies upon a distance function, Dist, that can be used to gauge the distance between two points in configuration space. This function takes as input the coordinates of the two points and returns a real number:
• Common choices for distance functions include:
– T he L1 distance (Manhattan distance): – The L2 distance (Euclidean distance):
Handling angular displacements
• There are often cases where some of the coordinates of the configuration space correspond to angular rotations. In these situations care must be taken to ensure that the Dist function correctly reflects distances in the
presence of wraparound.
• For example if and denote two angles between 0 and 360 degrees the expression below can be used to capture the angular displacement between them.
(2) Local Planner
The local planner element of a PRM procedure decides whether there is a path between two points/configurations X1 and X2.
A common approach is to construct a set of evenly sampled points on a straight line between the two configuration X1 and X2. Then, we can use the collision function to check all these intermediary configurations are collision free.
If the sampling between two end points is fine enough, this procedure is usually sufficient.
Example: Checking for collision along a path
Local planner says there is a path between two configurations.
Example: Checking for collision along a path
Local planner says there is not a path between two configurations.
Probabilistic Road Map (PRM)
Once the PRM procedure has generated what we believe to be a sufficient sampling of the configuration space, we can try to generate path between designated START and END configurations.
STEP 1: We start of by attempting to connect the START and END configurations to the nearby nodes on the roadmap.
STEP 2 (query phase): If this step succeeds, we can then attempt to find a path from the START node to the END node via the roadmap, using graph-based methods such as Dijkstra’s and A*.
Initial Road Map
• This slide shows the original Probabilistic roadmap constructed via random sampling.
Road Map with Start and End added
• This slide shows the roadmap augmented with the start and end nodes which are attached to the roadmap using the green edges.
Final Route
• This slide shows the path planned through the augmented graph
• Note that once the roadmap has been constructed it can be used to answer various path planning problems so the cost of constructing the roadmap graph can be amortized over multiple queries.
• Thisisgreatifyouaregoingtoberunningthe robot back and forth through the same environment.
Characteristics of Sample-Based Planners
Characteristics of Random Sampling Based approaches
• Firstoff,whilethesemethodsworkverywellin practice they are not strictly speaking complete.
• Remember: a complete path planning algorithm would find a path if one existed and report failure if it didn’t.
• MorespecifictoPRMprocedure,itispossible to have a situation where the algorithm would fail to find a path even when one exists, if the sampling procedure fails to generate an appropriate set of samples.
Twisty Passageway – Failure Case (sparse samples)
Twisty Passageway – Success via denser samples
We may need a post-processing step to smooth out the (jerky) path.
Characteristics of Random Sampling Based approaches
• What we can say is that if there is a route and the planner keeps adding random samples it will, eventually find a solution.
• However it may take a long time to generate a sufficient number of samples.
• We capture this behaviour by saying this sampling based algorithms are probabilistically complete to capture this notion that if there is a solution, there is a probability (hopefully a large probability) that we can find it. However, is the procedure doesn’t find a path, it is hard to know whethere there is in fact no path, or whether we would be able to find it we kept trying long enough.
• In practice, the number of samples to generate for the roadmap is an important parameter.
Characteristics of Random Sampling Based approaches
• To deal with twisty passage problems, a number of approaches have been proposed to bias the sampling procedure so to increase the chances of finding routes in these cases.
• For example, on idea is to try to sample more points closer to the boundaries of the configuration space
obstacles in the hope of construction the path that skirts the surfaces.
• Note: there is no single sampling strategy that guarantees to work well in all cases.
• In practice, most path planning problems are not pathological and a uniform sampling is a good place to start.
Trajectory for 6 degree of freedom arm
Conclusion
• In conclusion by relaxing the notion of completeness a bit and embracing the power of randomization these probablistic road map algorithms provide effective methods for planning routes that can be applied to a wide range of robotic systems including systems with many degrees of freedom.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com