CS 326 A: Motion PlanningConfiguration Space: Tool to Map a Robot to a PointProblemSlide 4Types of Path ConstraintsHomotopy of Free PathsMotion-Planning FrameworkPath-Planning ApproachesRoadmap MethodsSimple AlgorithmComplexityRotational SweepSlide 13Slide 14Slide 15Slide 16Reduced Visibility GraphGeneralized (Reduced) Visibility GraphThree-Dimensional SpaceSlide 20Slide 21Slide 22Cell-Decomposition MethodsTrapezoidal decompositionSlide 25Slide 26Slide 27Slide 28Slide 29Slide 30Octree DecompositionSketch of AlgorithmSlide 33Potential Field MethodsAttractive and Repulsive fieldsLocal-Minimum IssueSketch of Algorithm (with best-first search)Simple Navigation FunctionSlide 39Slide 40Completeness of PlannerSlide 42Preprocessing / Query ProcessingIssues for Future ClassesCS 326 A: Motion CS 326 A: Motion PlanningPlanningrobotics.stanford.edu/~latombe/cs326/2004/index.htmPath Planning Path Planning for a Point Robotfor a Point RobotConfiguration Space:Configuration Space:Tool to Map a Robot to a PointTool to Map a Robot to a PointProblemProblemfree spacesgfree pathProblemProblemsemi-free pathTypes of Path ConstraintsTypes of Path ConstraintsLocal constraints: lie in free space Differential constraints: have bounded curvatureGlobal constraints: have minimal lengthHomotopy of Free PathsHomotopy of Free PathsMotion-Planning Motion-Planning FrameworkFrameworkContinuous representationDiscretizationGraph searching(blind, best-first, A*)Path-Planning ApproachesPath-Planning Approaches1. RoadmapRepresent the connectivity of the free space by a network of 1-D curves2. Cell decompositionDecompose the free space into simple cells and represent the connectivity of the free space by the adjacency graph of these cells3. Potential fieldDefine a function over the free space that has a global minimum at the goal configuration and follow its steepest descentRoadmap MethodsRoadmap MethodsVisibility graphIntroduced in the Shakey project at SRI in the late 60s. Can produce shortest paths in 2-D configuration spacesgsSimple AlgorithmSimple Algorithm1. Install all obstacles vertices in VG, plus the start and goal positions2. For every pair of nodes u, v in VG3. If segment(u,v) is an obstacle edge then4. insert (u,v) into VG5. else6. for every obstacle edge e7. if segment(u,v) intersects e8. then goto 29. insert (u,v) into VG10. Search VG using A*ComplexityComplexitySimple algorithm: O(n3) timeRotational sweep: O(n2 log n)Optimal algorithm: O(n2)Space: O(n2)Rotational SweepRotational SweepRotational SweepRotational SweepRotational SweepRotational SweepRotational SweepRotational SweepRotational SweepRotational SweepReduced Visibility GraphReduced Visibility Graphtangent segments Eliminate concave obstacle verticescan’t be shortest pathGeneralized (Reduced) Generalized (Reduced) Visibility GraphVisibility Graphtangency pointThree-Dimensional SpaceComputing the shortest collision-free path in a polyhedral space is NP-hardShortest path passes through none of the verticeslocally shortest path homotopic to globally shortest pathRoadmap MethodsRoadmap MethodsVoronoi diagram Introduced by Computational Geometry researchers. Generate paths that maximizes clearance. O(n log n) timeO(n) spaceRoadmap MethodsRoadmap MethodsVisibility graphVoronoi diagram SilhouetteFirst complete general method that applies to spaces of any dimension and is singly exponential in # of dimensions [Canny, 87]Probabilistic roadmapsPath-Planning ApproachesPath-Planning Approaches1. RoadmapRepresent the connectivity of the free space by a network of 1-D curves2. Cell decompositionDecompose the free space into simple cells and represent the connectivity of the free space by the adjacency graph of these cells3. Potential fieldDefine a function over the free space that has a global minimum at the goal configuration and follow its steepest descentCell-Decomposition Cell-Decomposition MethodsMethodsTwo classes of methods:Exact cell decompositionThe free space F is represented by a collection of non-overlapping cells whose union is exactly FExample: trapezoidal decompositionTrapezoidal decompositionTrapezoidal decompositionTrapezoidal decompositionTrapezoidal decompositionTrapezoidal decompositionTrapezoidal decompositionTrapezoidal decompositionTrapezoidal decompositionTrapezoidal decompositionTrapezoidal decompositioncritical events  criticality-based decomposition…Trapezoidal decompositionTrapezoidal decompositionPlanar sweep  O(n log n) time, O(n) spaceCell-Decomposition Cell-Decomposition MethodsMethodsTwo classes of methods:Exact cell decompositionApproximate cell decompositionF is represented by a collection of non-overlapping cells whose union is contained in FExamples: quadtree, octree, 2n-treeOctree DecompositionOctree DecompositionSketch of AlgorithmSketch of Algorithm1. Compute cell decomposition down to some resolution2. Identify start and goal cells3. Search for sequence of empty/mixed cells between start and goal cells4. If no sequence, then exit with no path5. If sequence of empty cells, then exit with solution6. If resolution threshold achieved, then exit with failure7. Decompose further the mixed cells8. Return to 2Path-Planning ApproachesPath-Planning Approaches1. RoadmapRepresent the connectivity of the free space by a network of 1-D curves2. Cell decompositionDecompose the free space into simple cells and represent the connectivity of the free space by the adjacency graph of these cells3. Potential fieldDefine a function over the free space that has a global minimum at the goal configuration and follow its steepest descentPotential Field MethodsPotential Field MethodsGoalRobot)(GoalpGoalxxkF 00200,111ififxFObstacleGoalRobotApproach initially proposed for real-time collision avoidance [Khatib, 86]. Hundreds of papers published on it.Attractive and Repulsive Attractive and Repulsive fieldsfieldsLocal-Minimum IssueLocal-Minimum Issue Perform best-first search (possibility of combining with approximate cell decomposition) Alternate descents and random walks Use local-minimum-free potential (navigation function)Sketch of Algorithm Sketch of Algorithm (with best-first search)(with best-first search)1. Place regular grid G over space2. Search G using best-first search algorithm with potential as heuristic functionSimple