CS 326 A: Motion PlanningGoal of Motion PlanningFundamental QuestionBasic ProblemExamples with Rigid ObjectIs It Easy?Example with Articulated ObjectSlide 8Tool: Configuration SpaceSome Extensions of Basic ProblemAerospace Robotics Lab RobotSlide 12Autonomous HelicopterSlide 14Dynamic Unpredictable EnvironmentSlide 16Assembly PlanningSlide 18Map BuildingTarget TrackingSlide 22Planning for Nonholonomic RobotsSlide 24Planning with Uncertainty in Sensing and ControlSlide 26Motion Planning for Deformable ObjectsExamples of ApplicationsRobot ProgrammingRobot PlacementHumanoid RobotModular Reconfigurable RobotsVideoSlide 34Design for Manufacturing/ServicingAssembly Planning and Design of Manufacturing SystemsSlide 37Military Scouting and Planet ExplorationSlide 39Digital ActorsMotion Planning for Digital ActorsSlide 42Radiosurgical PlanningSlide 44Study of the Motion of Bio-MoleculesSlide 46Slide 47Building Code VerificationGoals of CS326AFrameworkSlide 51Practical Algorithms (1/2)Practical Algorithms (2/2)Prerequisites for CS326ACS326A is not a course in …Work to DoWebsite / Class ScheduleProgramming ProjectCS 326 A: Motion CS 326 A: Motion PlanningPlanninghttp://robotics.stanford.edu/~latombe/cs326/2002Instructor: Jean-Claude LatombeTeaching Assistant: Itay LotanComputer Science DepartmentStanford UniversityGoal of Motion PlanningGoal 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 to A without colliding with obstacles–assemble product P–build map of environment E–find object OFundamental QuestionFundamental QuestionAre two given points connected by a path?Basic ProblemBasic ProblemStatement: Compute a collision-free path for a rigid or articulated object (the robot) among static obstaclesInputs:–Geometry of robot and obstacles–Kinematics of robot (degrees of freedom)–Initial and goal robot configurations (placements)Output:–Continuous sequence of collision-free robot configurations connecting the initial and goal configurationsExamples with Rigid ObjectExamples with Rigid Object Ladder problemPiano-mover problem Is It Easy?Is It Easy?Example with Articulated Example with Articulated ObjectObjectExample with Articulated Example with Articulated ObjectObjectTool: Configuration SpaceTool: Configuration SpaceProblems:• Geometric complexity• Space dimensionalitySome Extensions of Basic Some Extensions of Basic ProblemProblem•Moving obstacles•Multiple robots•Movable objects•Assembly planning•Goal is to acquire information by sensing–Model building–Object finding/tracking•Nonholonomic constraints•Dynamic constraints•Optimal planning•Uncertainty in control and sensing•Exploiting task mechanics (sensorless motions)•Physical models and deformable objects•Integration of planning and controlAerospace Robotics Lab Aerospace Robotics Lab RobotRobotair bearinggas tankair thrustersobstaclesrobotTotal duration : 40 secTwo concurrent planning goals:• Reach the goal• Reach a safe regionAutonomous HelicopterAutonomous Helicopter[Feron, 2000] (AA Dept., MIT)Some Extensions of Basic Some Extensions of Basic ProblemProblem•Moving obstacles•Multiple robots•Movable objects•Assembly planning•Goal is to acquire information by sensing–Model building–Object finding/tracking•Nonholonomic constraints•Dynamic constraints•Optimal planning•Uncertainty in control and sensing•Exploiting task mechanics (sensorless motions)•Physical models and deformable objects•Integration of planning and controlDynamic Unpredictable EnvironmentSome Extensions of Basic Some Extensions of Basic ProblemProblem•Moving obstacles•Multiple robots•Movable objects•Assembly planning•Goal is to acquire information by sensing–Model building–Object finding/tracking•Nonholonomic constraints•Dynamic constraints•Optimal planning•Uncertainty in control and sensing•Exploiting task mechanics (sensorless motions)•Physical models and deformable objects•Integration of planning and controlAssembly PlanningAssembly PlanningSome Extensions of Basic Some Extensions of Basic ProblemProblem•Moving obstacles•Multiple robots•Movable objects•Assembly planning•Goal is to acquire information by sensing–Model building–Object finding/tracking•Nonholonomic constraints•Dynamic constraints•Optimal planning•Uncertainty in control and sensing•Exploiting task mechanics (sensorless motions)•Physical models and deformable objects•Integration of planning and controlMap BuildingMap BuildingWhere to move next?Target TrackingTarget TrackingSome Extensions of Basic Some Extensions of Basic ProblemProblem•Moving obstacles•Multiple robots•Movable objects•Assembly planning•Goal is to acquire information by sensing–Model building–Object finding/tracking•Nonholonomic constraints•Dynamic constraints•Optimal planning•Uncertainty in control and sensing•Exploiting task mechanics (sensorless motions)•Physical models and deformable objects•Integration of planning and controlPlanning for Nonholonomic Planning for Nonholonomic RobotsRobotsSome Extensions of Basic Some Extensions of Basic ProblemProblem•Moving obstacles•Multiple robots•Movable objects•Assembly planning•Goal is to acquire information by sensing–Model building–Object finding/tracking•Nonholonomic constraints•Dynamic constraints•Optimal planning•Uncertainty in control and sensing•Exploiting task mechanics (sensorless motions)•Physical models and deformable objects•Integration of planning and controlPlanning with Uncertainty in Planning with Uncertainty in Sensing and ControlSensing and ControlIGWW11WW22Some Extensions of Basic Some Extensions of Basic ProblemProblem•Moving obstacles•Multiple robots•Movable objects•Assembly planning•Goal is to acquire information by sensing–Model building–Object finding/tracking•Nonholonomic constraints•Dynamic constraints•Optimal planning•Uncertainty in control and sensing•Exploiting task mechanics (sensorless motions)•Physical models and deformable objects•Integration of planning and controlMotion Planning for Motion Planning for Deformable ObjectsDeformable Objects[Kavraki, 1999]Examples of ApplicationsExamples of Applications•Manufacturing:–Robot programming–Robot placement–Design of part feeders•Design for manufacturing