1CS 188: Artificial IntelligenceFall 2007Lecture 6: Robot Motion Planning9/13/2007Dan Klein – UC BerkeleyMany slides over the course adapted from either Stuart Russell or Andrew MooreAnnouncements Project 1 due (yesterday)! Project 2 (Pacman with ghosts) up in a few days Reminder: you are allowed to work with a partner! If you need a partner, come up to the front after class Mini-HomeworksToday Robot motion planning Local searchRobot motion planning!Robotics Tasks Motion planning (today) How to move from A to B Known obstacles Offline planning Localization (later) Where exactly am I? Known map Ongoing localization (why?) Mapping (much later) What’s the world like? Exploration / discovery SLAM: simultaneous localization and mappingMobile Robots High-level objectives: move around obstacles, etc Low-level: fine motor control to achieve motion Why is motion planning hard?Start ConfigurationImmovable ObstaclesGoal Configuration2Manipulator Robots High-level goals: reconfigure environment Low-level: move from configuration A to B (point-to-point motion) Why is this already hard? Also: compliant motionSensors and Effectors Sensors vs. Percepts Agent programs receive percepts Agent bodies have sensors Includes proprioceptivesensors Real world: sensors break, give noisy answers, miscalibrate, etc. Effectors vs. Actuators Agent programs have actuators (control lines) Agent bodies have effectors (gears and motors) Real-world: wheels slip, motors fail, etc.Degrees of Freedom2 DOFs3 DOFsQuestion: How many DOFs for a polyhedron free-flying in 3D space? The degrees of freedom are the numbers required to specify a robot’s configuration – the “dimensionality” Positional DOFs: (x, y, z) of free-flying robot direction robot is facing Effector DOFs Arm angle Wing position Static state: robot shape and position Dynamic state: derivatives of static DOFs (why have these?)Example How many DOFs? What are the natural coordinates for specifying the robot’s configuration? These are the configuration space coordinates What are the natural coordinates for specifying the effector tip’s position? These are the work spacecoordinatesExample How many DOFs? How does this compare to your arm? How many are required for arbitrary positioning of end-effector?Holonomicity Holonomic robots control all their DOFs (e.g. manipulator arms) Easier to control Harder to build Non-holonomic robots do not directly control all DOFs (e.g. a car)3Coordinate Systems Workspace: The world’s (x, y) system Obstacles specified here Configuration space The robot’s state Planning happens here Obstacles can be projected to hereKinematics Kinematics The mapping from configurations to workspace coordinates Generally involves some trigonometry Usually pretty easy Inverse Kinematics The inverse: effectorpositions to configurations Usually non-unique (why?)Forward kinematicsConfiguration Space Configuration space Just a coordinate system Not all points are reachable / legal Legal configurations: No collisions No self-intersectionObstacles in C-Space What / where are the obstacles? Remaining space is free spaceMore Obstacles Topology You very quickly get into tricky issues of topology: Point robot in 3D: R3 Directional robot with fixed position in 3D: SO(3) Two rotational-jointed robot in 2D: S1xS1 For the present purposes, we’ll just ignore these issues In practice, you have to deal with it properly4Example: 2D PolygonsWorkspace Configuration SpaceExample: RotationExample: A Less Simple Arm[DEMO]Summary Degrees of freedom Legal robot configurations form configuration space Even simple obstacles have complex images in c-spaceMotion as Search Motion planning as path-finding problem Problem: configuration space is continuous Problem: under-constrained motion Problem: configuration space can be complexWhy are there two paths from 1 to 2?Decomposition Methods Break c-space into discrete regions Solve as a discrete problem5Exact Decomposition? With polygon obstacles: decompose exactly Problems? Doesn’t scale at all Doesn’t work with complex, curved obstaclesApproximate Decomposition Break c-space into a grid Search (A*, etc) What can go wrong? If no path found, can subdivide and repeat Problems? Still scales poorly Incomplete* Wiggly pathsSGHierarchical Decomposition But: Not optimal Not complete Still hopeless above a small number of dimensions Actually used in some real systemsSkeletonization Methods Decomposition methods turn configuration space into a grid Skeletonization methods turn it into a set of points, with preset linear paths between themVisibility Graphs Shortest paths: No obstacles: straight line Otherwise: will go from vertex to vertex Fairly obvious, but somewhat awkward to prove Visibility methods: All free vertex-to-vertex lines (visibility graph) Search using, e.g. A* Can be done in O(n3) easily, O(n2log(n)) less easily Problems? Bang, screech! Not robust to control errors Wrong kind of optimality?qstartqgoalqstartVoronoi Decomposition Voronoi regions: points colored by closest obstacle Voronoi diagram: borders between regions Can be calculated efficiently for points (and polygons) in 2D In higher dimensions, some approximation methodsRGBY6Voronoi Decomposition Algorithm: Compute the Voronoi diagram of the configuration space Compute shortest path (line) from start to closest point on Voronoi diagram Compute shortest path (line) from goal to closest point on Voronoi diagram. Compute shortest path from start to goal along Voronoidiagram Problems: Hard over 2D, hard with complex obstacles Can do weird things:Probabilistic Roadmaps Idea: just pick random points as nodes in a visibility graph This gives probabilistic roadmaps Very successful in practice Lets you add points where you need them If insufficient points, incomplete, or weird pathsRoadmap Example Potential Field Methods So far: implicit preference for short paths Rational agent should balance distance with risk! Idea: introduce cost for being close to an obstacle Can do this with discrete methods (how?) Usually most
View Full Document
Unlocking...