Motion Planning for Autonomous Vehicles

How to run the docker image

Refer to 💻

Course Structure 👾

• Introduction 📚

• Introduction to Optimization 📚

  • Constrained optimization 📜code
  • Least squares fitting 📜code
  • Least squares fitting with regularization📜code
  • Smoothing📜code
  • Penalty functions📜code
  • Robust estimation📜code
  • Feasible problems📜code
  • Quadratic problems📜code
  • Linear problems📜code 📜code

• Variation of Calculus 📚

  • Extremum 📜code 📜code
  • Convexity
  • Linearization of function up to the second variation
  • Incremental of a function
  • Incremental of a functional
  • Fixed value problem
  • Free terminal point problem
  • Fix point problem ( t f is fixed and x(t f ) is free)
  • Fix point problem ( t f is free and x(t f ) is fixed)
  • Free endpoint problem: if t f and x(t f ) are uncorrelated
  • Free endpoint problem: if t f and x(t f ) are depended on each other

• Hamiltonian (Optimal control theory)📚

  • Constrained Minimization of functions
  • Elimination method (direct method)
  • The Lagrange multiplier method: examples general formulation
  • Constrained Minimization of functional: Point constraints, differential equation constraints
  • Hamiltonian
  • The necessary condition for optimal control
  • Boundary conditions for optimal control: with the fixed final time and the final state specified or free
  • Boundary conditions for optimal control: with the free final time and the final state specified, free, lies on the moving point x f = θ (t f ) , or lies on a moving surface m(x(t)) )

• Pontryagin’s Minimum Principle 📚

  • Optimal control problem
  • Pontryagin’s Minimum Principle
  • Optimal boundary value problem
  • Minimizing the square of the jerk
  • Minimizing the square of acceleration 📜min_acc_obvp(line 41)

• Linear Quadratic Regulator 📚

  • LQR Formulation
  • LQR via least squares
  • Hamilton Jacobi Bellman (HJB) Approach
  • Bellman Optimality
  • LQR with HJB 📜DARE
  • Hamiltonian formulation to find the optimal control policy
  • Linear quadratic optimal tracking
  • Optimal reference trajectory tracking with LQR

• Model Predictive Control (MPC)📚

  • Ways to solve Optimal Control (OCP) Problems
  • OCP Using Nonlinear Programming Problem (NLP)
  • Model Predictive Control: Prediction model, Constraints
  • Reference trajectory tracking
  • Simplified Motion Model
  • With Multiple Shooting 📜code and direct collocation 📜code
  • Continuous nonlinear system linearization
  • Discrete-time nonlinear system linearization
  • Linear Time-Varying Model Predictive Control
  • Path tracking control
  • Path tracking control with MPC: kinematic model, trajectory generation, dynamic model, and cost, formulation

• Path planning 📚

  • Configuration Space vs Search Space for Robot
  • Path Planning Problem Formulation
  • Search-based Planning: Mapping
  • Search-based Planning: Graph
  • Graph Searching
  • Depth First Search
  • Breath First Search 📜code
  • Cost Consideration
  • Dijkstra’s Algorithm 📜code
  • Greedy Best First Search 📜code
  • A*: Combination of Greedy Best First Search and Dijkstra’s Algorithm 📜code
  • A*: Design Consideration
  • Graph-based search problem classification
  • KinoDynamic A*:Heuristics, Generating motion primitives, finding neighbors 📜code
  • Hybrid A*: Motion model, finding neighbors, cost to go h, and cost so far g 📜code
  • Sampling-based path planning
  • Probabilistic Road Map (PRM)
  • Rapidly-exploring Random Tree (RRT) 📜code
  • Rapidly-exploring Random Tree* (RRT*) 📜code
  • Pros and Cons of RRT and RRT*

• Curve Fitting 📚

  • n degree polynomial fitting
  • Euler–Lagrange equation
  • Minimum jerk trajectory (MJT) generation
  • Quintic polynomial
  • Lagrange polynomials
  • Lagrange first-order, second-order, and nth-order interpolation
  • Spline interpolation: Linear, Quadratic, and Cubic Spline 📜Spine
  • Other types of curve fitting: Gradient descent, Double arc trajectory interpolation
  • Nonlinear curve fitting
  • Bezier curve fitting
  • B-spline curve fitting
  • Minimum-snap curve fitting

• Frenet frame trajectory planning 📚

  • Frenet frame
  • Curve parameterization of the reference trajectory
  • Estimate the position of a given Spline
  • The road-aligned coordinate system with a nonlinear dynamic bicycle model
  • Frenet frame trajectory tracking using a nonlinear bicycle model
  • Transformations from Frenet coordinates to global coordinates
  • Polynomial motion planning
  • Frenet frame trajectory generation algorithm
  • Calculate global trajectories

• Timed Elastic Band 📚

  • Elastic band and time elastic band
  • Way points and obstacles: polynomial approximation of constraints
  • Estimate the position of a given Spline
  • Velocity and acceleration generation
  • Non-holonomic kinematics

• Gradient-based online trajectory generation 📚

  • Piecewise polynomial trajectory generation
  • Formulation of the objective function
  • The cost of the smoothness
  • The cost of the clearance
  • The cost of the dynamic feasibility

References

[1]. Werling, M., Ziegler, J., Kammel, S., & Thrun, S. (2010, May). Optimal trajectory generation for dynamic street scenarios in a frenet frame. In 2010 IEEE International Conference on Robotics and Automation (pp. 987-993). IEEE.

[2]. Mueller, M. W., Hehn, M., & D'Andrea, R. (2015). A computationally efficient motion primitive for quadrocopter trajectory generation. IEEE transactions on robotics, 31(6), 1294-1310.

[3]. Takahashi, A., Hongo, T., Ninomiya, Y., & Sugimoto, G. (1989, September). Local path planning and motion control for agv in positioning. In Proceedings. IEEE/RSJ International Workshop on Intelligent Robots and Systems'.(IROS'89)'The Autonomous Mobile Robots and Its Applications (pp. 392-397). IEEE.

[4]. Frolkovič, P. (1990). Numerical recipes: The art of scientific computing.

[5]. Lima, P. F., Mårtensson, J., & Wahlberg, B. (2017, December). Stability conditions for linear time-varying model predictive control in autonomous driving. In 2017 IEEE 56th Annual Conference on Decision and Control (CDC) (pp. 2775-2782). IEEE.

[6]. Lima, P. F., Oliveira, R., Mårtensson, J., & Wahlberg, B. (2017, October). Minimizing long vehicles overhang exceeding the drivable surface via convex path optimization. In 2017 IEEE 20th International Conference on Intelligent Transportation Systems (ITSC) (pp. 1-8). IEEE.

[7]. Kulathunga, G., Devitt, D., Fedorenko, R., & Klimchik, A. (2021). Path planning followed by kinodynamic smoothing for multirotor aerial vehicles (mavs). Russian Journal of Nonlinear Dynamics, 17(4), 491-505.

[8]. Kulathunga, G., Devitt, D., & Klimchik, A. (2022). Trajectory tracking for quadrotors: An optimization‐based planning followed by controlling approach. Journal of Field Robotics, 39(7), 1001-1011.

[9]. Kulathunga, G., Hamed, H., Devitt, D., & Klimchik, A. (2022). Optimization-Based Trajectory Tracking Approach for Multi-Rotor Aerial Vehicles in Unknown Environments. IEEE Robotics and Automation Letters, 7(2), 4598-4605.

[10]. Robust and Efficient Quadrotor Trajectory Generation for Fast Autonomous Flight, Boyu Zhou, Fei Gao, Luqi Wang, Chuhao Liu and Shaojie Shen, IEEE Robotics and Automation Letters (RA-L), 2019.

[11]. https://web.casadi.org/

[12]. https://www.cvxpy.org/

[13]. https://osqp.org/

[14]. Kulathunga, G., & Klimchik, A. (2022). Optimization-based Motion Planning for Multirotor Aerial Vehicles: a Review. arXiv preprint arXiv:2208.14647.

[15]. Mellinger D, Kumar V. Minimum snap trajectory generation and control for quadrotors[C]//Robotics and Automation (ICRA), 2011 IEEE International Conference on. IEEE, 2011: 2520-2525.

[16]. Polynomial Trajectory Planning for Aggressive Quadrotor Flight in Dense Indoor Environments, Charles Richter, Adam Bry, and Nicholas Roy

[17]. Rösmann, C., Feiten, W., Wösch, T., Hoffmann, F., Bertram, T. (2012, May). Trajectory modification considering dynamic constraints of autonomous robots. In ROBOTIK 2012; 7th German Conference on Robotics (pp. 1-6). VDE.

[18]. Rösmann, C., Hoffmann, F., & Bertram, T. (2017). Integrated online trajectory planning and optimization in distinctive topologies. Robotics and Autonomous Systems, 88, 142-153.

[19]. Gao, F., Lin, Y., Shen, S. (2017, September). Gradient-based online safe trajectory generation for quadrotor flight in complex environments. In 2017 IEEE/RSJ international conference on intelligent robots and systems (IROS) (pp. 3681-3688). IEEE.