IU:TestPage

Motion planning for autonomous vehicles

• Course name: Motion planning for autonomous vehicles
• Code discipline:
• Subject area: Robotics

Short Description

Robots are evolving from factory manufacturing to increasingly complicated apparatuses capable of accomplishing demanding tasks in our everyday life. One of the manifestations to accomplish such demanding tasks is motion planning and controlling. This course will introduce you to some of the main concepts of optimal control, including basic concepts of calculus of variation, Linear Quadratic regulator, Linear Quadratic Gaussian, Model predictive control, and transforming an optimal control problem into constrained or unconstrained optimization formulation. The second part of the course focuses on planning tasks in autonomous navigations, including path planning and trajectory planning in hierarchical and cascade, e.g., global planning and local planning. The path planning section includes A*, Hybrid A*, Kinodynamic A*, RRT, and RRT*. The trajectory planning section contains several techniques for trajectory generation and trajectory planning based on different constraints. By the end of this course, you will be able to design a motion planner for a specified scenario. To succeed in this course, you should have programming experience in Python 3. x, C++, ROS, and familiarity with basic concepts of Linear Algebra and Calculus.

Prerequisites

Prerequisite subjects

• CSE101
• CSE102
• CSE104 or CSE117
• CSE202 and CSE204

Prerequisite topics

• Programming experience in Python 3. x, and C++
• ROS (Robot Operating System)
• Familiarity with basic concepts of Linear Algebra and Calculus

Course Topics

Course Sections and Topics

Section	Topics within the section
1.0 Introduction to Optimization & Variation of Calculus & Hamiltonian theory (Optimal control) & Pontryagin’s Minimum Principle	Constrained optimization Least squares fitting Least squares fitting with regularization Smoothing Penalty functions Robust estimation Feasible problems Quadratic problems Linear problems Extremum 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(tf) is free) Fix point problem ( t f is free and x(tf) is fixed) Free endpoint problem: if tf and x(tf) are uncorrelated Free endpoint problem: if tf and x(tf) are depended on each other 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)) ) Optimal control problem Pontryagin’s Minimum Principle Optimal boundary value problem Minimizing the square of the jerk Minimizing the square of acceleration
2.0 Graph-based Path planning & Sampling-based 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 Cost Consideration Dijkstra’s Algorithm Greedy Best First Search A*: Combination of Greedy Best First Search and Dijkstra’s Algorithm A*: Design Consideration Graph-based search problem classification KinoDynamic A*:Heuristics, Generating motion primitives, finding neighbours Hybrid A*: Motion model, finding neighbours, the cost to go h, and cost so far g Probabilistic Road Map (PRM) Rapidly-exploring Random Tree (RRT) Rapidly-exploring Random Tree* (RRT*) Pros and Cons of RRT and RRT*
3.0 Linear Quadratic Regulator (LQR) & Model Predictive Control (MPC) & Curve Fitting & Frenet frame trajectory planning	LQR Formulation LQR via least squares Hamilton Jacobi Bellman (HJB) Approach Bellman Optimality LQR with HJB Hamiltonian formulation to find the optimal control policy Linear quadratic optimal tracking Optimal reference trajectory tracking with LQR 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 and direct collocation 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 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 Other types of curve fitting: Gradient descent, Double arc trajectory interpolation Nonlinear curve fitting Bezier curve fitting B-spline curve fitting 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

Intended Learning Outcomes (ILOs)

What is the main purpose of this course?

What is the main goal of this course formulated in one sentence? The main purpose of this course is for you to design a motion planner for a specified scenario.

ILOs defined at three levels

Level 1: What concepts should a student know/remember/explain?

By the end of the course, the students should be able to ...

• Understand the basis of motion planning
• Design a motion planner for a given vehicle considering specified scenarios
• Explain what are the main principles of optimal motion planner
• Describe various classifications of path planning
• State the characteristics of a different curve fitting
• Elaborate on the main principles model predictive control paradigm
• List the key commonalities and differences between linear and nonlinear motion planning formulation
• Explain what is Frenet frame trajectory generation
• Describe the important aspects and elements of a plan-based control paradigm

Level 2: What basic practical skills should a student be able to perform?

By the end of the course, the students should be able to ...

• Formulate and assess a given motion planning problem
• Perform different representations of the problem
• Design effective motion planner
• Model, design, and conduct experiments on a simulated environment
• Compare with different planning algorithm in terms of accuracy, performance, and complexity

Level 3: What complex comprehensive skills should a student be able to apply in real-life scenarios?

By the end of the course, the students should be able to ...

• Understand the given motion planning problem and formulate an appropriate planner
• Elicit and document requirements
• Split the problem formulation into several sub-problems and analyses
• Generate different types of trajectory for specified scenarios
• Understand when to use soft and hard constraints-based motion planning problem formulation

Grading

Course grading range

Grade	Range	Description of performance
A. Excellent	90.0-100.0	-
B. Good	75.0-89.0	-
C. Satisfactory	50.0-74.0	-
D. Fail	0.0-50.0	-

Course activities and grading breakdown

Activity Type	Percentage of the overall course grade
Assignment	50
Quizzes	20
In-class activity	10
Mini-project	20

Recommendations for students on how to succeed in the course

Participation is important. Showing up is the key to success in this course.
You will work individually, however, getting help from others is acceptable
Review lecture materials before classes to do well in quizzes.
Reading the recommended literature is optional and will give you a deeper understanding of the material.

Resources, literature and reference materials

Open access resources

• The Open Motion Planning Library
• 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.
• 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.

Closed access resources

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

Software and tools used within the course

• Provide at least 3 open/freemium access tools
• Gazebo https://gazebosim.org/home
• ROS, https://www.ros.org/
• CasADi https://web.casadi.org/

Teaching Methodology: Methods, techniques, & activities

Activities and Teaching Methods

Activities within each section

Learning Activities	Section 1	Section 2	Section 3
Lectures	1	1	1
Interactive Lectures	1	1	1
Lab exercises	1	1	1
Development of individual parts of software product code	1	1	1
Individual Projects	1	1	1
Quizzes (written or computer-based)	1	1	1
Discussions	1	1	1
Presentations by students	1	1	1
Written reports	1	1	1
Experiments	0	0	1

Formative Assessment and Course Activities

Ongoing performance assessment

Section 1

Activity Type	Content	Is Graded?
Quiz	1. Solving constrained optimization? 2. Solving Least squares fitting with regularization? 3. Solving smoothing of a trajectory? 4. Solving problems with penalty functions? 5. How to estimate robust control?	10
Individual Assignments	A1: Fix point problem ( t f is fixed and x(t f ) is free) Define a motion planner where the start and final states are fixed, Given an objective function, the objective is to derive optimal control based on Hamiltonian and simulate on Gazebo-based environment Submit a report and source code: - Experimenting on different scenarios - Check problem formulation and implementation accuracy A2: Fix point problem ( t f is fixed and x(t f ) is free) Define a motion planner where the start and final states are fixed, however placing a set of state and control constraints. Given an objective function, the objective is to derive optimal control based on Pontryagin’s Minimum Principle and simulate on Gazebo-based environment Submit a report and source code: - Experimenting on different scenarios - Importance of placing constraints on state and control spaces A2: Optimal boundary value problem Define a motion planner that minimizes the square of acceleration for ground vehicle Submit a report and source code: - Experimenting on different scenarios - Check problem formulation and implementation accuracy - Effects of minimizing jerk over acceleration	20

Section 2

Activity Type	Content	Is Graded?
Quiz	1. Difference between configuration space vs search space for robots? 2. How to estimate heuristics for KinoDynamic A*? 3. How to find the motion model, neighbours, cost to go h, and cost so far g for Hybrid A*? 4. Different between Depth First Search, breath first search, and best first search algorithms? 5. How to classify graph-based search problem?	5
Individual Assignments	A1: kinematically feasible path planning Implementation of the Hybrid A* for car-like ground vehicle and simulate planning in various environments Submit a report and source code: - Experimenting on different scenarios - Check problem formulation and implementation accuracy A2: Dynamically feasible path planning Implementation of the KinoDynamic A* for car-like ground vehicle and simulate planning in various environments Submit a report and source code: - Experimenting on different scenarios - Check problem formulation and implementation accuracy A2: Sampling-based path planning Develop a sampling-based path planner, RRT*, and compare with KinoDynamic A* and Hybrid A* Submit a report and source code: - Experimenting on different scenarios - Check problem formulation and implementation accuracy - Check the performance in term of reaching the goal and execution time	15

Section 3

Activity Type	Content	Is Graded?
Quiz	1. List down ways to solve optimal control (OCP) problems. 2. How to formulate OCP using nonlinear programming problem (NLP)? 3. Difference between multiple shooting and direct collocation? 4. Explain the hamilton Jacobi bellman (HJB) approach? 5. How to formulate optimal reference trajectory tracking using (Linear Quadratic Regulator) LQR?	5
Individual Assignments	A1: Path tracking control with Model predictive control (MPC) Develop a motion planner that sends a set of control commands to the robot to follow a path. Need to design path tracking controller considering: kinematic model, trajectory generation, dynamic model, and cost, formulation Submit a report and source code: - Experimenting on different scenarios - Check problem formulation and implementation accuracy A2: Hamilton Jacobi Bellman (HJB) Approach Define jerk minimization problem and apply Linear Quadratic Regulator for tracking the trajectory. Initially, the analytical solution should be developed and develop in a Gazabo-based simulated environment Submit a report and source code: - Experimenting on different scenarios - Checking the accuracy of the trajectory tracker A2: Lagrange polynomials and Spline interpolation Apply a path planner to generate a set of intermediate waypoints and then apply Lagrange polynomials and Spline interpolation and generate trajectory Submit a report and source code: - Compare the properties of these - Check problem formulation and implementation accuracy - Compare results with nonlinear curve fitting algorithms: B-spline and Bezier	15

Final assessment

Section 1

1. Can be a final exam, project defence, or some other equivalent of the final exam.
2. For the final assessment, students present the project work they have accomplished during the course. Below are the grading criteria for each section.
3. Section 1/2/3 Mini-Project
4. Need to select a topic from the provided project list, and propose the approach to solve the problem. Afterwards, need to develop and test the proposed approach in a simulated setup
5. Understanding how to formulate a given motion planning problem
6. Checking implementation accuracy
7. Reporting on finding and difficulting while formulating and implementing the proposed approach

Section 2

Section 3

The retake exam

Section 1

1. For the retake, students have to implement a given motion planning problem. First, need to formulate it with logical reasons for justifying it. Second, need to develop the proposed idea in a simulated setup. Answer a set of theoretical questions that comes from section 1, section 2, and section 3.

Section 2

Section 3