Motion Planning

Finding safe, efficient paths and trajectories for robots: the planning problem and its guarantees, configuration space and Minkowski sums, breadth-first search, Dijkstra and A* with heuristics, weighted and incremental search, cost maps, state lattices and Hybrid A*, probabilistic roadmaps, RRT, RRT-Connect and RRT*, collision checking with GJK and signed distance fields, trajectory optimization with CHOMP, STOMP and TrajOpt, Dubins and Reeds-Shepp curves, arm planning with MoveIt 2, velocity obstacles and MPC, and a capstone planner design for a warehouse mobile manipulator.

ROB-350 Year 3 3 credits 12 lessons · 6 h 2 min

Offered by HSM University · Robotics

What you'll learn

Formulate motion planning problems precisely, distinguishing paths from trajectories, classifying constraints, and explaining completeness, optimality and why the general problem is hard
Construct configuration spaces for points, discs, polygons and planar arms, compute C-space obstacles with inflation and Minkowski sums, and handle wrapped angles in C-space metrics
Apply breadth-first search and Dijkstra's algorithm to planning graphs, build wavefront navigation functions, and design non-negative edge costs that encode clearance and other preferences
Implement A* with admissible and consistent heuristics, quantify the speed-optimality trade-off of weighted and anytime search, and explain Jump Point Search and incremental replanning with D* Lite
Build cost maps with inflation from occupancy grids, choose grid resolution and connectivity, smooth grid paths, and plan for car-like robots with state lattices and Hybrid A*
Construct and query probabilistic roadmaps, size edge checks and neighbor connections, analyze probabilistic completeness, and select sampling strategies for narrow passages
Implement RRT, RRT-Connect and RRT*, explain the Voronoi bias and asymptotic optimality, use informed and kinodynamic variants, and post-process sampled paths for execution
Choose collision representations, explain bounding-volume hierarchies, GJK and signed distance fields, check continuous motions, and build safety margin budgets
Formulate trajectory optimization with smoothness and obstacle costs, apply covariant gradient descent, compare CHOMP, STOMP and TrajOpt, and handle local minima and constraints
Model nonholonomic vehicles, compute minimum turning radii and Dubins paths, explain Reeds-Shepp curves, and use them as heuristics and steering functions in planners
Plan arm motions in joint and task space with inverse kinematics goals and a MoveIt 2 pipeline, and avoid moving obstacles with velocity obstacles, dynamic windows and model predictive control
Design, benchmark and justify a complete planning system for a mobile manipulator against requirements for time, success, quality, clearance and failure handling

Course content

12 lessons · 6 h 2 min total · final exam

1 The motion planning problem 31 min · quiz
2 Configuration space 29 min · quiz
3 Graph search I: breadth-first search and Dijkstra's algorithm 28 min · quiz
4 Graph search II: A* and heuristics 31 min · quiz
5 Grid and lattice planning 30 min · quiz
6 Sampling-based planning I: probabilistic roadmaps 28 min · quiz
7 Sampling-based planning II: RRT, RRT-Connect and RRT* 27 min · quiz
8 Collision checking and distance computation 31 min · quiz
9 Trajectory optimization 32 min · quiz
10 Planning for car-like and nonholonomic robots 32 min · quiz
11 Planning for manipulators and dynamic environments 35 min · quiz
12 Capstone: a planner for a warehouse mobile manipulator 28 min · quiz
E Final exam 20 questions

Requirements

Recommended background. You can start any course at any time.

Description

Part of the Science stream, typically taken in year 3.