A probabilistic roadmap (PRM) is a motion-planning method that helps a robot find a collision-free route from a starting configuration to a goal configuration. Rather than examining every possible motion, PRM samples configurations, checks whether they are safe, and connects some of them into a graph that can be searched for a path.
A robot's configuration describes its position and pose, including the values needed to specify its state for motion planning. The set of all possible configurations is called the configuration space. Some configurations place the robot in collision with obstacles; the remaining safe configurations form the free space.
All flashcards
What is configuration space?
It is the set of all possible configurations of the robot, where a configuration specifies the robot's state for motion planning.
What are the vertices and edges of a PRM?
Vertices are sampled configurations checked to be collision-free. Edges represent locally planned motions between vertices that pass collision checking.
What happens in the two PRM phases?
In construction, the planner samples safe configurations and connects nearby ones to build a roadmap. In the query phase, it connects the start and goal to the roadmap and searches for a route.
What does probabilistic completeness mean?
Under suitable conditions, if a valid path exists, the probability that PRM finds one approaches one as the number of samples increases without bound.
How can visibility affect PRM performance?
Visibility depends on the motions the local planner can connect. If points and regions can connect broadly through free space, useful routes may be found faster; limited visibility can slow convergence.
Quiz questions
What does a vertex in a probabilistic roadmap represent?Answer: A sampled configuration that has been checked and found to be collision-free.
What is the role of the local planner in PRM?Answer: It attempts motions between configurations; valid connections become graph edges.
Which activity belongs to the PRM construction phase?Answer: Sampling configurations, retaining safe ones, and attempting connections to nearby vertices.
During a query, what does Dijkstra's algorithm do in the described PRM approach?Answer: It searches the graph for a shortest path between connected start and goal configurations.
Under suitable conditions, what does probabilistic completeness imply as the number of samples grows without bound?Answer: If a valid path exists, the probability that PRM finds one approaches one.