CS 326A: Motion PlanningSlide 2Piano Mover’s ProblemSlide 4Slide 5Slide 6Slide 7Slide 8ARL RobotSlide 10Slide 11Goal of Motion PlanningFundamental QuestionSlide 14Basic ProblemSlide 16Tool: Configuration SpaceSlide 18Extensions of Basic ProblemSome ApplicationsSlide 21Slide 22Climbing RobotDexterous ManipulationModular Reconfigurable RobotsSlide 26Manipulation of Deformable ObjectsDigital CharactersSlide 29Animation of CrowdsSlide 31Design for Manufacturing and ServicingDesign for Manufacturing and ServicingSlide 34Assembly Sequence PlanningSlide 36Cable Harness/ Pipe designSlide 38Navigation Through Virtual EnvironmentsVirtual Angiography / Bronchoscopy / ColonoscopyRadiosurgical PlanningBuilding Code VerificationEgress SimulationSelf-ParkingTransportation of A380 Fuselage through Small VillagesStudy of Motion of Bio-MoleculesGoals of CS326AGeneral FrameworkPractical Algorithms (1/2)Practical Algorithms (2/2)Prerequisites for CS326ACS326A is not a course in …Work to DoProgramming ProjectWebsite and ScheduleCS 326A: Motion PlanningJean-Claude LatombeCA: Aditya MandayamMotion 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 abilityPiano Mover’s ProblemPlan MoveSenseARL RobotGoalPlan MoveSenseLearnMotion libraryGoal 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 QuestionAre two given points connected by a path?Valid regionForbidden regionFundamental QuestionAre two given points connected by a path?Valid regionForbidden regionE.g.:▪Collision with obstacle▪Lack of visibility of an object▪Lack of stabilityBasic 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 sequence of collision-free robot configurations connecting the initial and goal configurationsIs It Easy?Tool: Configuration SpaceProblems:• Geometric complexity• Space dimensionalityContinuous spaceDiscretization SearchC-spaceSampling-based Criticality-basedExtensions of Basic Problem•Moving obstacles•Multiple robots•Movable objects•Assembly planning•Goal is to acquire information by sensing–Model building–Object finding/tracking–Inspection•Nonholonomic constraints•Dynamic constraints•Stability constraints•Optimal planning•Uncertainty in model, control and sensing•Exploiting task mechanics (sensorless motions, under-actualted systems)•Physical models and deformable objects•Integration of planning and control•Integration with higher-level planningSome ApplicationsHumanoid RobotsHRP-2, AIST, JapanLunar Vehicle (ATHLETE, NASA/JPL)Climbing Robothttp://www.youtube.com/watch?v=biSx-aKN690Dexterous ManipulationModular Reconfigurable RobotsManipulation of Deformable ObjectsTopologicallydefined goalDigital CharactersA Bug’s Life (Pixar/Disney)Toy Story (Pixar/Disney)Tomb Raider 3 (Eidos Interactive) Final Fantasy VIII (SquareOne)The Legend of Zelda (Nintendo)Antz (Dreamworks)Digital CharactersAnimation of CrowdsDesign for Manufacturing and ServicingDesign for Manufacturing and ServicingDesign for Manufacturing and ServicingAssembly Sequence PlanningCable Harness/ Pipe designMap BuildingWhere to move next?Navigation Through Virtual EnvironmentsVirtual Angiography / Bronchoscopy / ColonoscopyRadiosurgical PlanningCyberKnife (Accuray)Building Code Verification9-inch turning radius24-inch turning radiusEgress SimulationPrimary escape routeSecondary escape routePotential congesting areasSelf-ParkingTransportation of A380 Fuselage through Small VillagesKineoStudy of Motion of Bio-MoleculesInhibitor binding to HIV proteaseGoals of CS326APresent a coherent framework for motion planning problemsEmphasis of “practical” algorithms with some guarantees of performance over “theoretical” or purely “heuristic” algorithmsGeneral FrameworkContinuous representation(configuration space and related spaces + constraints)Discretization(probabilistic sampling, criticality-based decomposition)Graph searching(blind, best-first, A*)Practical Algorithms (1/2)A complete motion planner always returns a solution plan when one exists and indicates that no such plan exists otherwise.Most motion planning problems are hard, meaning that complete planners take exponential time in # of degrees of freedom, objects, etc.Practical Algorithms (2/2)Theoretical algorithms strive for completeness and minimal worst-case complexity. Difficult to implement and not robust.Heuristic algorithms strive for efficiency in commonly encountered situations. Usually no performance guarantee. Weaker completeness Simplifying assumptions Exponential algorithms that work in practicePrerequisites for CS326AAbility and willingness to complete a significant programming project with graphic interface.Basic knowledge and taste for geometry and algorithms.Interest in devoting reasonable time each week in reading papers.CS326A is not a course in …Differential Geometry and TopologyKinematics and DynamicsGeometric Modeling… but it makes use of knowledge from all these areasWork to DoA. Attend every classB. Prepare/give two presentations with ppt slides (20 minutes each)C. For each class read the two papers listed as “required reading” in advanceD. Complete the programming projectE. Complete two homework assignmentsProgramming Project•Navigate in virtual environment•Simulate legged robot•Inspection of structures•Search and escapeWebsite and