Last update: May 6, 2010RoboticsCMSC 421: Chapter 25CMSC 421: Chapter 25 1What is a robot?A machine to perform tasks♦ Some level of autonomy and flexibility, in some type of environment♦ Sensory-motor functions- Locomotion on wheels, legs, or wings- Manipulation with mechanical arms, grippers, and hands♦ Communication and information-processing capabilities- Localization with odomoters, sonars, lasers, inertial sensors, GPS, etc.- Scene analysis and environment modeling with a stereovision systemon a pan-and-tilt platformReasonably mature technology when robots restricted to either♦ well-known, well-engineered environments (e.g., manufacturing)♦ performing single simple tasks (e.g., vacuum cleaning, lawn mowing)For more diverse tasks and open-ended environments, robotics remains avery active research fieldCMSC 421: Chapter 25 2Examples of Mobile RobotsCMSC 421: Chapter 25 3Examples of ManipulatorsCMSC 421: Chapter 25 4Examples of SensorsRange finders: sonar (land, underwater), laser range finder, radar (aircraft),tactile sensors, GPSImaging sensors: cameras (visual, infrared)Proprioceptive sensors:shaft decoders (joints, wheels),inertial sensors, force sensors, torque sensorsCMSC 421: Chapter 25 5Hand-coding of robot controllersManual development of a robot controller for a specific taskTo do hand-coding reliably and inexpensively, need♦ well-structured, stable environment♦ restrictions on the scope and diversity of the robot’s tasks♦ only a limited human-robot interactionDeveloping the reactive controller♦ Devices to memorize motion of a pantomime♦ Graphical programming interfacesCMSC 421: Chapter 25 6Automated robot controllersIntegrate planning, acting, sensing, learningNead to deal with♦ heterogeneous partial models of the environment and of the robot♦ information acquired through sensors and communication channels♦ noisy and partial knowledge of the stateSpecialized algorithms for different types of tasks:♦ Path and motion planning♦ Perception♦ Navigation♦ Motor controlCMSC 421: Chapter 25 7Path PlanningPath planning: find geometric path from starting position to goal position♦ Input: geometric model of the environment (obstacles, free space)♦ Solution path must avoid collision with obstacles• must also satisfy the robot’s kinematic (movement) constraintsconf-3conf-1conf-2startgoalCMSC 421: Chapter 25 8Motion PlanningMotion planning: find a trajectory that’sfeasible in both space and time♦ Need a feasible path(relies on path planning)♦ Also need a control policy thatsatisfies the robot’s speedand acceleration constraintsTechnology for path planning and motion planning is relatively mature♦ Deployed in areas such as CAD and computer animation♦ Computational geometry and probabilistic algorithmsCMSC 421: Chapter 25 9Configuration parametersConfiguration parameters: the numbers that specify the robot’s current stateθ(x, y)Three parameters: x, y, θ Seven parameters10 parameters: 6 for arm,4 for platform & trailer52 parameters:2 for the head7 for each arm6 for each leg12 for each handCMSC 421: Chapter 25 10Configuration parametersq = the configuration of the robot = an n-tuple of realsCS = the robot’s configuration space = {all possible values for q}The configuration parameters aren’t independentE.g., can’t change θ without changing x and yCSfree = free configuration space (configs that don’t collide with obstacles)CSfree can be quite complicatedCMSC 421: Chapter 25 11Motion PlanningIn ordinary geometric space, the robot occupies a regionIn configuration space, it occupies a pointIdea: do path planning in configuration spaceFind a path in CSfree from an initial config qito a final config qgconf-3conf-1conf-2conf-3conf-2conf-1wwelbshouCMSC 421: Chapter 25 12Dealing with the configuration spacen-dimensional space, where n = number of configuration parametersEach parameter is a real number ⇒ ∞npossible statesFor state-space search, convert to a finite state space.Cell decomposition:♦ Divide up space into simple cells, such thateach of them can be traversed “easily” (e.g., convex)♦ Find a path through the pure freespace cells(the ones that don’t contain any part of an obstacle)Skeletonization: identify a finite number points/lines that form a graphWant a graph such that any two points can easily be connectedby following a path on the graphCMSC 421: Chapter 25 13Cell decomposition exampleconf-3conf-2conf-1wwelbshoustartgoalHow many cells, how large?♦ Large number of small cells ⇒ large computation time♦ Small number of large cells ⇒ no path through pure freespaceSolution: recursively decompose mixed (free+obstacle) cells into smaller cells♦ quadtreesCMSC 421: Chapter 25 14Skeletonization: Voronoi diagramVoronoi diagram: locus of points equidistant from obstaclesProblem: doesn’t scale well to higher dimensionsCMSC 421: Chapter 25 15Skeletonization: Probabilistic RoadmapProbabilistic roadmap R:1. generate random points in CS,and keep the ones in CSfree2. create graph by joining eachadjacent pair p1, p2by a lineL(p1, p2)To keep things simple, we’ll usestraight linesMore generally, the lines mightbe curved, in order to satisfy therobot’s kinematic constraintsR is adequate if it contains enough points to ensure that every start/goalpair is connected through the graphCMSC 421: Chapter 25 16Path planning with roadmapsGiven an adequate roadmap for CSfree and two configurations qiand qginCSfree, a feasible path from qito qgcan be found as follows:♦ Find configuration q0iin R such that L(qi, q0i) is in CSfree♦ Find configuration q0gin R such that L(qg, q0g) is in CSfree♦ In R, find a path from q0ito q0g♦ The planned path is the finite sequence of line segments between themDo postprocessing to optimize and smooth the pathThis reduces path planning to a simple graph-search problem,plus collision checking and kinematic steeringCMSC 421: Chapter 25 17When is a roadmap adequate?The property we want: whenever there’s apath in CSfree from qito qg, the roadmapcontains a path from q0ito q0gThe coverage of a configuration q isD(q) = {q0∈ CSfree | L(q, q0) ⊆ CSfree}i.e., every point that can be reached by astraight line from qThe coverage of a set of configurations Q = {q1, q2, . . . , qn} isD(Q) = D(q1) ∪ D(q2) ∪ . . . ∪ D(qn)R is adequate if R is connected and D(vertices(R)) = CSfreeCMSC 421: Chapter 25 18Generating an adequate roadmap♦ Easier to use probabilistic techniques