CS 326 A: Motion PlanningConfiguration SpaceProbabilistic Roadmap (PRM)Single-Query PRM PlanningMain Tenets of PRM PlanningNarrow-Passage IssueExpansive Configuration SpaceCS 326 A: Motion CS 326 A: Motion PlanningPlanninghttp://robotics.stanford.edu/~latombe/cs326/2002Probabilistic RoadmapsProbabilistic RoadmapsBasic TechniquesBasic TechniquesConfiguration SpaceConfiguration SpaceProblems:• Geometric complexity• Space dimensionalityApproximate the free space by random sampling Probabilistic Roadmaps[Lozano-Perez, 80]Probabilistic Roadmap Probabilistic Roadmap (PRM)(PRM)free spacemmbbmmggmilestone[Kavraki, Svetska, Latombe,Overmars, 95][Kavraki, Svetska, Latombe,Overmars, 95]local pathSingle-Query PRM PlanningSingle-Query PRM PlanningmmbbmmggMain Tenets of PRM Main Tenets of PRM PlanningPlanningChecking sampled configurations and connections between samples for collision can be done efficiently. Hierarchical collision checkingA relatively small number of milestones and local paths are sufficient to capture the connectivity of the free space. Exponential convergence in expansive free space (probabilistic completeness)Narrow-Passage IssueNarrow-Passage IssueEasyEasyDifficultExpansive Configuration Expansive Configuration SpaceSpaceLookout of F1The C-space is expansiveif all of its subsets havea large lookout[Hsu, Latombe,Motwani,
View Full Document
Unlocking...