Single Robot Motion PlanningSlide 2Piano Mover’s ProblemSlide 4Types of RobotsGoal of Motion PlanningSlide 7Basic ProblemTypes of Path ConstraintsIs It Easy?Outline (Mon & Wed)Path Planning for a Point RobotVisibility GraphsSimple (Naïve) AlgorithmComplexityMotion Planning FrameworkIssues With Visibility GraphsSlide 18Configuration Space: Tool to Map a Robot to a PointExample: rigid robot in 2-D workspaceConfiguration Space (C-Space)Dimension of C-spaceExample: Rigid Robot in 3-D WorkspaceExample: rigid robot in 3-D workspaceTopology of C-SpaceSlide 26Example: An Articulated RobotAn Articulated Robot Puma 560 Number of dofs = 6Obstacles in C-spaceSlide 30Disc in 2-D WorkspacePolygonal Robot Translating in 2-D WorkspaceArticulated Robot in 2-D WorkspaceSlide 34Fundamental QuestionProblem: Computing C-obstaclesMinkowski SumExerciseSlide 39Slide 40Slide 41Slide 42Minkowski Sum of Non-convex PolyhedraConfiguration Space ObstacleMinkowski Sum of Convex PolygonsComplexity of Minkowksi SumComplexity of Computing C-obstaclesWednesday’s Lecture1Single Robot Motion PlanningLiang-Jun ZhangCOMP790-058Sep 22, 20082Motion planning is the ability for an agent to compute its own motions in order to achieve certain goals. All autonomous robots and digital actors should eventually have this ability3Piano Mover’s Problem•2D or 3D rigid models45Types of Robots•Rigid robots•Articulated robotsManipulator, VideoHumanoid robots6Goal of Motion Planning•Compute motion strategies, e.g.:–geometric paths –time-parameterized trajectories–sequence of sensor-based motion commands•To achieve high-level goals, e.g.:–go from A to B without colliding with obstacles–assemble product P–build map of environment E–find object O7Plan MoveSense8Basic ProblemStatement: Compute a collision-free path for a rigid or articulated object among static obstaclesInputs:•Geometry of moving object and obstacles•Kinematics of moving object (degrees of freedom)•Initial and goal configurations (placements)Output:Continuous collision-free path connecting the initial and goal configurations9Types of Path Constraints•Local constraints –Collision-free paths•Differential constraints–A car cannot move sideways–Have bound curvature•Global constraints–Shortest or optimal pathsPath Planning Motion Planning10Is It Easy? alpha puzzle11Outline (Mon & Wed)•Path planning for a point robot•Configuration space•Approximate cell decomposition•Sampling-based motion planning12Path Planning for a Point Robotgs13Visibility GraphsIntroduced in the Shakey project at SRI in the late 60sCan produce shortest paths in a point robot in 2Dgs14Simple (Naïve) 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 BFS (any other graph search scheme)15Complexity•A point robot in 2D using visibility graphsSimple algorithm: O(n3) timeRotational sweep: O(n2 log n)Optimal algorithm: O(n2)Space: O(n2)gs16Motion Planning Framework•Motion planning: a search problem in continuous spaceDiscretization Continuous representationGraph search17gsIssues With Visibility GraphsDifficult to extend from point robots to rigid or articulated robotsA L-shaped robot18Outline (Mon & Wed)•Path planning for a point robot•Configuration space•Approximate cell decomposition•Sampling-based motion planning19Configuration Space:Tool to Map a Robot to a Point20Example: rigid robot in 2-D workspace•3-parameter specification: q = (x, y,  ) with [0, 2).–3-D configuration spacerobotworkspacereference pointxyreference direction21Configuration Space (C-Space)•The configuration of a moving object is a specification of the position of every point on the object. –Usually a configuration is expressed as a vector of position & orientation parameters: q = (q1, q2,…,qn).•Configuration space –C-space–The set of all possible configurations.–A configuration is a point in C-space.q=(q1, q2,…,qn)qq11qq22qq33qqnn22Dimension of C-space•The dimension of a configuration space is the minimum number of parameters needed to specify the configuration of the object completely.•It is also called the number of degrees of freedom (dofs) of a moving object.23Example: Rigid Robot in 3-D Workspace•What is the configuration space?24Example: rigid robot in 3-D workspace•q = (position, orientation) = (x, y, z, ???)•Number of dofs = 6•Euler anglesxxyzzxxyyzzxyzxxyyzz1  2  3  425C = S1 x S1θΦTopology of C-Space•The topology of C is usually not that of a Cartesian space Rn.022θΦθΦ26Example: Rigid Robot in 3-D Workspace•Number of dofs = 6•Topology: R3 x SO(3)27Example: An Articulated RobotNumber of dofs = 3 C-space is 3 dimensional28An articulated object is a set of rigid bodies connected at the joints.An Articulated Robot Puma 560 Number of dofs = 629Obstacles in C-spaceWorkspaceConfiguration SpacexyRobot StartGoalFree ObstacleC-obstacleA 2D Translating Robot30Obstacles in C-space•A configuration q is collision-free, or free, if a moving object placed at q does not intersect any obstacles in the workspace.•The free space F is the set of free configurations.•A configuration space obstacle (C-obstacle) is the set of configurations where the moving object collides with workspace obstacles.31Disc in 2-D Workspaceworkspace configuration space32Polygonal Robot Translating in 2-D Workspaceworkspaceconfiguration space33Articulated Robot in 2-D Workspaceworkspaceconfiguration space34•Live demo of C-space of a 2-link robot35Fundamental Questionworkspaceconfiguration spaceAre two given points connected by a path?36Problem: Computing C-obstacles•Input:–Polygonal moving object translating in 2-D workspace –Polygonal obstacles•Output: configuration space obstacles represented as polygons37Minkowski Sum},|{ BbAabaBA AB38ExerciseABA B = ?39Minkowski Sum},|{ BbAabaBA 40Minkowski Sum41Minkowski Sum},|{ BbAabaBA 42Minkowski Sum•The Minkowski sum of two sets A and B, denoted by AB, is defined as A B = { a+b | a A, bB }•Similarly, the Minkowski difference is defined as A – B = { a–b |