Motion planning and trajectory optimization (A*, RRT, MPC, lattice planners)
The computational process of finding a geometrically feasible path from a start to a goal configuration (planning) and then refining that path into a dynamically executable, time-optimized trajectory (optimization) for autonomous systems.
This skill is the core enabling technology for safe, efficient, and intelligent autonomous operation in robotics and vehicles, directly impacting product viability, operational cost (e.g., energy consumption, cycle time), and safety certification. Mastery translates to a competitive edge in deploying reliable autonomous systems at scale.
1Careers
1Categories
9.0 Avg Demand
15%
Avg AI Risk
How to Learn Motion planning and trajectory optimization (A*, RRT, MPC, lattice planners)
1. **Graph Theory & Search Fundamentals**: Deeply understand A* (heuristics, optimality) and Dijkstra's algorithm on grid maps. 2. **Sampling-Based Planning**: Implement RRT and RRT* in 2D/3D space with obstacles, focusing on completeness and asymptotic optimality. 3. **Cost Functions & Heuristics**: Learn to design and tune cost functions that balance path length, safety margins, and computational efficiency.
1. **Kinematic/Dynamic Constraints**: Move beyond point robots. Integrate vehicle models (e.g., bicycle model) into planners like Hybrid A* or lattice planners to generate kinematically feasible paths. 2. **Trajectory Optimization**: Use convex optimization (e.g., CVXPY) to smooth raw paths. Implement basic Model Predictive Control (MPC) for trajectory tracking with dynamic obstacles. 3. **Common Pitfall Avoidance**: Avoid over-engineering the cost function prematurely; start with simple weighted sums. Never ignore the simulation-to-reality gap-always validate with high-fidelity simulators (e.g., Gazebo, CARLA).
1. **Architect System-Level Solutions**: Design planning stacks that hierarchically decompose problems (e.g., global lattice planner -> local MPC-based reactive planner). Integrate perception uncertainty (e.g., probabilistic occupancy grids) directly into the planning cost. 2. **Optimization for Performance**: Formulate motion planning as a single nonlinear program (NLP) using tools like Ceres Solver or CasADi for end-to-end optimization. Master real-time solvers (e.g., OSQP, HPIPM) for time-critical MPC. 3. **Mentorship & Review**: Develop expertise in formally verifying planner safety (e.g., using reachability analysis) and guiding teams on algorithm selection based on scene complexity, computational budget, and safety requirements.
Practice Projects
Beginner
Project
A* Pathfinding on a 2D Grid with Variable Costs
Scenario
Develop a grid-based world with obstacles and cells of varying traversal cost (e.g., rough terrain). The goal is to find the least-cost path from start to goal.
How to Execute
1. Implement a grid map class with cost values. 2. Code the A* algorithm using a priority queue, integrating cost-so-far (g) and heuristic (h). 3. Visualize the explored nodes and final path using Matplotlib. 4. Experiment by changing the cost map and heuristic (Manhattan vs. Euclidean) to observe path changes.
Intermediate
Project
Hybrid A* Planner for a Non-Holonomic Vehicle
Scenario
Extend the planning problem to a simulated car-like robot in a 2D parking lot with obstacles. The vehicle must respect minimum turning radius and avoid obstacles.
How to Execute
1. Define a state space (x, y, heading) and vehicle model (e.g., bicycle model). 2. Implement Hybrid A* search that uses the vehicle's motion primitives (forward/backward with steering actions) as edges. 3. Integrate a cost function that penalizes path length, proximity to obstacles, and reversing maneuvers. 4. Use a library like `ompl` or `nav2` for benchmarking and visualization in ROS/Gazebo.
Advanced
Project
Real-Time MPC-Based Trajectory Tracker with Obstacle Avoidance
Scenario
Given a pre-computed reference path from a planner, design an MPC controller that dynamically tracks the path while avoiding unexpected, moving obstacles in the vehicle's vicinity.
How to Execute
1. Formulate a nonlinear MPC problem with cost terms for path tracking error, control effort, and obstacle avoidance (using signed distance fields). 2. Use an optimization framework like CasADi with IPOPT or acados for real-time solving. 3. Integrate a local perception pipeline that updates obstacle states. 4. Test in a high-fidelity simulator (CARLA) under varying traffic conditions, measuring tracking accuracy and constraint violation rates.
Tools & Frameworks
Core Libraries & Solvers
OMPL (Open Motion Planning Library)CasADi (for symbolic framework for NLP)OSQP / HPIPM (QP solvers for MPC)
OMPL is the industry standard for sampling-based planners (RRT, PRM). CasADi is used to formulate and solve complex nonlinear trajectory optimization problems. OSQP and HPIPM are high-performance solvers for the quadratic programming subproblems inside MPC.
Essential for developing, testing, and benchmarking planning algorithms in safe, repeatable environments before real-world deployment. CARLA is specifically designed for urban driving scenarios with traffic.
Lattice planners provide a principled way to generate kinematically feasible motion primitives. Dynamic programming is foundational for value-based planning. Convex optimization tools are used for solving sub-problems within trajectory optimization pipelines efficiently.
Interview Questions
Answer Strategy
Structure your answer around 3 axes: **Computational Efficiency** (lattice planner's graph search is deterministic and fast, RRT* can be slower in high-D but more flexible), **Kinematic Feasibility** (lattice uses pre-computed, vehicle-admissible maneuvers, RRT* requires post-processing/smoothing), and **Adaptability to Dynamic Environments** (RRT* re-plans easily, lattice requires careful graph updates). Conclude that a hybrid approach (global lattice for coarse plan, local sampling-based replanner for dynamic crowds) is often optimal.
Answer Strategy
This tests systematic debugging of an optimization problem. 1. **Isolate the Cause**: Check if the issue is in the cost function (are obstacle penalties weighted too low relative to tracking?) or the model (is the dynamic model inaccurate, causing the controller to over-predict?). 2. **Strategic Fix**: Increase the weight on obstacle cost or introduce a hard constraint via a potential field. Consider tightening the model's turning radius. 3. **Validation**: Run a parametric sweep in simulation to find the minimal penalty that ensures zero violations. Emphasize the trade-off between aggressiveness and safety.
Careers That Require Motion planning and trajectory optimization (A*, RRT, MPC, lattice planners)