1Robot Motion Planning… or: Movie DaysMovies/demos provided by James Kuffner and Howie Choset + Examples from J.C. Latombe’s book (references on the last page)Example from Howie ChosetExample from James KuffnerExample from Howie ChosetRobot Motion Planning• Application of earlier search approaches (A*, stochastic search, etc.)• Search in geometric structures• Spatial reasoning• Challenges:– Continuous state space– Large dimensional spaceBiologyProcess Engineering/DesignAnimation/Virtual actorsRobotics is only (a small) one of many applications of spatial reasoning(Kineo)2Degrees of FreedomExamplesAllowed to move only in x and y: 2DOFAllowed to move in xand y and to rotate: 3DOF (x,y,θ)Control versus SpaceHow many control DOF’s do you need for x,y,θ to all be controlled?- synchro-drive- diff-drive- AckermanExamplesFixed (attached at the base)Free FlyingFixed (the dashed line is constrained to be horizontal)Fixed• Configuration space = set of values of qcorresponding to legal configurations of the robot• Defines the set of possible parameters (the search space) and the set of allowed pathsConfiguration Space (C-Space) Free Space: Point Robot• free= {Set of parameters q for which A(q) does not intersect obstacles}• For a point robot in the 2-D plane: R2minus the obstacle regions3Free Space: Symmetric Robot• We still have = R2because orientation does not matter• Reduce the problem to a point robot by expanding the obstacles by the radius of the robotFree Space: Non-Symmetric Robot• The configuration space is now three-dimensional (x,y,θ)• We need to apply a different obstacle expansion for each value of θ• We still reduce the problem to a point robot by expanding the obstaclesθxyMore Complex C-SpacesMotion Planning Problem4Any Formal Guarantees? Generic Piano Movers ProblemApproaches• Basic approaches:–Roadmaps• Visibility graphs• Voronoi diagrams–Cell decomposition–Potential fields• Extensions–Sampling Techniques–On-line algorithmsIn all cases: Reduce the intractable problem in continuous C-space to a tractable problem in a discrete space Use all of the techniques we know (A*, stochastic search, etc.)RoadmapsVisibility GraphsVisibility GraphsIn the absence of obstacles, the best path is the straight line between qstartand qgoalVisibility Graphs5Visibility Graphs• Assuming polygonal obstacles: It looks like the shortest path is a sequence of straight lines joining the vertices of the obstacles.• Is this always true?Visibility GraphsVisibility Graphs• Visibility graph G = set of unblocked lines between vertices of the obstacles + qstartand qgoal• A node P is linked to a node P’ if P’ is visible from P• Solution = Shortest path in the visibility graphConstruction: Sweep Algorithm• Sweep a line originating at each vertex• Record those lines that end at visible verticesComplexity• N = total number of vertices of the obstacle polygons• Naïve: O(N3)• Sweep: O(N2log N)• Optimal: O(N2)6Visibility Graphs: Weaknesses• Shortest path but:– Tries to stay as close as possible to obstacles– Any execution error will lead to a collision– Complicated in >> 2 dimensions• We may not care about strict optimality so long as we find a safe path. Staying away from obstacles is more important than finding the shortest path• Need to define other types of “roadmaps”Voronoi Diagrams• Given a set of data points in the plane:– Color the entire plane such that the color of any point in the plane is the same as the color of its nearest neighborVoronoi Diagrams• Voronoi diagram = The set of line segments separating the regions corresponding to different colors• Line segment = points equidistant from 2 data points• Vertices = points equidistant from > 2 data pointsVoronoi Diagrams• Voronoi diagram = The set of line segments separating the regions corresponding to different colors• Line segment = points equidistant from 2 data points• Vertices = points equidistant from > 2 data pointsVoronoi Diagrams• Complexity (in the plane):• O(N log N) time• O(N) space(See for example http://www.cs.cornell.edu/Info/People/chew/Delaunay.html for an interactive demo)7Voronoi Diagrams: Beyond Points• Edges are combinations of straight line segments and segments of quadratic curves• Straight edges: Points equidistant from 2 lines• Curved edges: Points equidistant from one corner and one lineVoronoi Diagrams (Polygons)• Key property: The points on the edges of the Voronoi diagram are the furthest from the obstacles• Idea: Construct a path between qstartand qgoalby following edges on the Voronoi diagram• (Use the Voronoi diagram as a roadmap graph instead of the visibility graph)Voronoi Diagrams: Planning• Find the point q*startof the Voronoi diagram closest to qstart• Find the point q*goalof the Voronoi diagram closest to qgoal• Compute shortest path from q*startto q*goalon the Voronoi diagram8ExampleVoronoi: Weaknesses• Difficult to compute in higher dimensions or nonpolygonal worlds• Approximate algorithms exist• Use of Voronoi is not necessarily the best heuristic (“stay away from obstacles”) Can lead to paths that are much too conservative, or lead to “ranging sensor deprivation”• Can be unstable Small changes in obstacle configuration can lead to large changes in the diagram• Localization is hard (e.g. museums) if you stay away from known surfacesApproaches• Basic approaches:–Roadmaps• Visibility graphs• Voronoi diagrams–Cell decomposition–Potential fields• Extensions–Sampling Techniques–On-line algorithmsDecompose the space into cells so that any path inside a cell is obstacle freeApproximate Cell Decomposition• Define a discrete grid in C-Space• Mark any cell of the grid that intersects obsas blocked• Find path through remaining cells by using (for example) A* (e.g., use Euclidean distance as heuristic)• Cannot be complete as described so far. Why?9Approximate Cell Decomposition• Cannot find a path in this case even though one exists• Solution:• Distinguish between – Cells that are entirely contained in obs (FULL) and– Cells that partially intersect obs(MIXED)• Try to find a path using the current set of cells• If no path found:– Subdivide the MIXED cells and try again with the new set of cellsStartGoalStartGoalApproximate Cell Decomposition: Limitations• Good:– Limited assumptions on obstacle
View Full Document
Unlocking...