Skip to content

Latest commit

 

History

History
212 lines (181 loc) · 12.5 KB

README.md

File metadata and controls

212 lines (181 loc) · 12.5 KB
Raw

Motion Planning for Autonomous Vehicles

How to run the docker image

Refer to 💻

Course Structure 👾

  • Introduction 📚

  • Introduction to Optimization 📚

  • 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.