Difference between revisions of "IU:TestPage"

From IU
Jump to navigation Jump to search
Line 1: Line 1:
   
  +
= Motion planning for autonomous vehicles =
−
= Psychology in IT sphere =
  
−
* '''Course name''': Psychology in IT sphere
 +
* '''Course name''': Motion planning for autonomous vehicles
−
* '''Code discipline''': XXX
 +
* '''Code discipline''':
−
* '''Subject area''':
+
* '''Subject area''': Robotics
   
 
== Short Description ==
  
== 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.
−
This course covers the following concepts: The structure of Psyche; The psychic mental processes: cognitive, emotional, volitional; Emotional intelligence; Personality and personality traits; Spiral Dynamics.
  
  +
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 ==
  
== Prerequisites ==
   
 
=== Prerequisite subjects ===
  
=== Prerequisite subjects ===
  +
* CSE101
−  
  +
* CSE102
  +
* CSE104 or CSE117
  +
* CSE202 and CSE204
   
 
=== Prerequisite topics ===
  
=== 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 Topics ==
Line 22: Line 28:
 
! Section !! Topics within the section
  
! Section !! Topics within the section
 
|-
  
|-
  +
| 1.0 Introduction to Optimization & Variation of Calculus & Hamiltonian theory<br>(Optimal control) & Pontryagin’s Minimum Principle ||
−
| Introduction: psychology as a science, its branches and methodology ||
 
  +
# Constrained optimization
−
# - The history of psychology
  
  +
# Least squares fitting
−
# - The notion and structure of psyche
  
  +
# Least squares fitting with regularization
−
# - The branches of psychology
  
  +
# Smoothing
−
# - The methods of psychology
  
  +
# Penalty functions
−
|-
  
  +
# Robust estimation
−
| Mental Cognitive processes: ||
 
  +
# Feasible problems
−
# - Sensation
  
  +
# Quadratic problems
−
# - Perception
  
  +
# Linear problems
−
# - Attention
  
  +
# Extremum
−
# - Memory
  
  +
# Convexity
−
# - Thinking
  
  +
# Linearization of function up to the second variation
−
# - Imagination.
  
  +
# 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 ||
−
| Mental Volitional processes ||
 
  +
# Configuration Space vs Search Space for Robot
−
# - What is willpower and how it works
  
  +
# Path Planning Problem Formulation
−
# - Body reserve of Willpower
  
  +
# Search-based Planning: Mapping
−
# - Tricks of our mind, connected with willpower and how to overcome them
  
  +
# 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)<br>& Curve Fitting & Frenet frame trajectory planning ||
−
| Mental Emotional processes ||
 
  +
# LQR Formulation
−
# - The notion and functions of emotions
  
  +
# LQR via least squares
−
# - Biological emotions
  
  +
# Hamilton Jacobi Bellman (HJB) Approach
−
# - Social emotions
  
  +
# Bellman Optimality
−
# - Emotion and stress management
  
  +
# LQR with HJB
−
|-
  
  +
# Hamiltonian formulation to find the optimal control policy
−
| Personality traits ||
 
  +
# Linear quadratic optimal tracking
−
# - The notion of personality
  
  +
# Optimal reference trajectory tracking with LQR
−
# - Personality theories
  
  +
# Ways to solve Optimal Control (OCP) Problems
−
# - Personality traits: abilities, temperament, character, orientation.
  
  +
# OCP Using Nonlinear Programming Problem (NLP)
−
|-
  
  +
# Model Predictive Control: Prediction model, Constraints
−
| Communication psychology ||
 
  +
# Reference trajectory tracking
−
# - The instrument of communication
  
  +
# Simplified Motion Model
−
# - Communication barriers
  
  +
# With Multiple Shooting and direct collocation
−
# - The main conditions of real/successful communication
  
  +
# Continuous nonlinear system linearization
−
# - Tips of successful communication
  
  +
# Discrete-time nonlinear system linearization
−
# - Networking
  
  +
# Linear Time-Varying Model Predictive Control
−
|-
  
  +
# Path tracking control
−
| System development psychology ||
 
  +
# Path tracking control with MPC: kinematic model, trajectory
−
# - Spiral dynamics as a systems evolution theory
  
  +
# generation, dynamic model, and cost, formulation
−
# - The meaning of 9 levels of spiral dynamics
  
  +
# n degree polynomial fitting
−
# - Crises of the levels
  
  +
# Euler–Lagrange equation
−
# - The usage of Spiral dynamics theory in personal life and business
  
  +
# 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) ==
  
== Intended Learning Outcomes (ILOs) ==
   
 
=== What is the main purpose of this course? ===
  
=== What is the main purpose of this course? ===
  +
What is the main goal of this course formulated in one sentence?
−
This is an introductory course in general psychology. During the course, students will learn the fundamental terms, conceptual apparatus and principles of psychological science, its different directions, branches and also the history of its development.
  
  +
The main purpose of this course is for you to design a motion planner for a specified scenario.
   
 
=== ILOs defined at three levels ===
  
=== ILOs defined at three levels ===
Line 74: Line 148:
 
==== Level 1: What concepts should a student know/remember/explain? ====
  
==== Level 1: What concepts should a student know/remember/explain? ====
 
By the end of the course, the students should be able to ...
  
By the end of the course, the students should be able to ...
  +
* Understand the basis of motion planning
−
* • key psychological terms and concepts
  
  +
* Design a motion planner for a given vehicle considering specified scenarios
−
* • psychological science stage of development and its perspectives
  
−
* • the structure of the psyche and the principles of its functioning
 +
* Explain what are the main principles of optimal motion planner
  +
* Describe various classifications of path planning
−
* • important techniques and best practices for self-regulation of emotional and mental state
  
  +
* State the characteristics of a different curve fitting
−
* • the spiral dynamics conception and its stages
  
−
* • the main principles of communication
 +
* 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? ====
  
==== 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 ...
  
By the end of the course, the students should be able to ...
  +
* Formulate and assess a given motion planning problem
−
* • How to observe the functioning of their mental cognitive processes
  
  +
* Perform different representations of the problem
−
* • How to define their emotions, emotional conditions and the reasons of them
  
  +
* Design effective motion planner
−
* • How they can use such mental process as willpower for achieving their goals
  
−
* • What personality traits they and their environment have got.
 +
* Model, design, and conduct experiments on a simulated environment
  +
* Compare with different planning algorithm in terms of accuracy, performance, and complexity
−
* • The level of any community system development
  
−
* • How and in which situations they can use the main principles of communication
  
   
 
==== Level 3: What complex comprehensive skills should a student be able to apply in real-life scenarios? ====
  
==== 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 ...
  
By the end of the course, the students should be able to ...
  +
* Understand the given motion planning problem and formulate an appropriate planner
−
* • Use technics for managing and improving their cognitive processes
  
  +
* Elicit and document requirements
−
* • Use technics for managing and improving their willpower
  
  +
* Split the problem formulation into several sub-problems and analyses
−
* • Use the technics of emotional and stress management
  
  +
* Generate different types of trajectory for specified scenarios
−
* • Consider their and their environment personal traits in making decisions.
  
  +
* Understand when to use soft and hard constraints-based motion planning problem formulation
−
* • Plan their actions with the systems concerning its level of development.
  
−
* • Use corresponding principles of communication in different interactions
 
 
== Grading ==
  
== Grading ==
   
Line 106: Line 181:
 
! Grade !! Range !! Description of performance
  
! Grade !! Range !! Description of performance
 
|-
  
|-
−
| A. Excellent || 90-100 || -
 +
| A. Excellent || 90.0-100.0 || -
 
|-
  
|-
−
| B. Good || 75-89 || -
 +
| B. Good || 75.0-89.0 || -
 
|-
  
|-
−
| C. Satisfactory || 60-74 || -
 +
| C. Satisfactory || 50.0-74.0 || -
 
|-
  
|-
−
| D. Poor || 0-59 || -
 +
| D. Fail || 0.0-50.0 || -
 
|}
  
|}
   
Line 121: Line 196:
 
! Activity Type !! Percentage of the overall course grade
  
! Activity Type !! Percentage of the overall course grade
 
|-
  
|-
−
| Attendance || 80
 +
| Assignment || 50
 
|-
  
|-
−
| Essay || 10
 +
| Quizzes || 20
 
|-
  
|-
−
| Exam || 10
 +
| In-class activity || 10
  +
|-
  +
| Mini-project || 20
 
|}
  
|}
   
 
=== Recommendations for students on how to succeed in the course ===
  
=== Recommendations for students on how to succeed in the course ===
  +
Participation is important. Showing up is the key to success in this course.<br>You will work individually, however, getting help from others is acceptable<br>Review lecture materials before classes to do well in quizzes.<br>Reading the recommended literature is optional and will give you a deeper understanding of the material.
−  
   
 
== Resources, literature and reference materials ==
  
== Resources, literature and reference materials ==
   
 
=== Open access resources ===
  
=== Open access resources ===
  +
* The Open Motion Planning Library
−
* Jo Godefroid “Les Chemins de la psychologie”, 1988 Paris
  
  +
* 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.
−
* Edited by L.M. Popov and S.V. Petrushin “Methods and techniques of practical psychology”, 2007 St. Petersburg
  
  +
* 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.
−
* R.S. Nemov “General psychology” in 3 volumes, 2011 Moscow
  
−
* Kelly McGonigal “The Willpower Instinct”, 2011 The USA
  
   
 
=== Closed access resources ===
  
=== 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 ===
  
=== 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 =
  
= Teaching Methodology: Methods, techniques, & activities =
   
 
== Activities and Teaching Methods ==
  
== Activities and Teaching Methods ==
  +
{| class="wikitable"
−  
  +
|+ Activities within each section
−
'''NO DATA'''
  
  +
|-
−
 
  +
! 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 ==
  
== Formative Assessment and Course Activities ==
   
Line 155: Line 258:
   
 
==== Section 1 ====
  
==== Section 1 ====
  +
{| class="wikitable"
−  
  +
|+
  +
|-
  +
! Activity Type !! Content !! Is Graded?
  +
|-
  +
| Quiz || 1. Solving constrained optimization?<br>2. Solving Least squares fitting with regularization?<br>3. Solving smoothing of a trajectory?<br>4. Solving problems with penalty functions?<br>5. How to estimate robust control? || 10
  +
|-
  +
| Individual Assignments || A1: Fix point problem ( t f is fixed and x(t f ) is free)<br>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 <br><br>Submit a report and source code:<br>- Experimenting on different scenarios <br>- Check problem formulation and implementation accuracy <br><br>A2: Fix point problem ( t f is fixed and x(t f ) is free)<br>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 <br><br>Submit a report and source code:<br>- Experimenting on different scenarios <br>- Importance of placing constraints on state and control spaces <br><br>A2: Optimal boundary value problem<br>Define a motion planner that minimizes the square of acceleration for ground vehicle <br>Submit a report and source code:<br>- Experimenting on different scenarios <br>- Check problem formulation and implementation accuracy <br>- Effects of minimizing jerk over acceleration || 20
  +
|}
 
==== Section 2 ====
  
==== Section 2 ====
  +
{| class="wikitable"
−  
  +
|+
  +
|-
  +
! Activity Type !! Content !! Is Graded?
  +
|-
  +
| Quiz || 1. Difference between configuration space vs search space for robots?<br>2. How to estimate heuristics for KinoDynamic A*?<br>3. How to find the motion model, neighbours, cost to go h, and<br>cost so far g for Hybrid A*?<br>4. Different between Depth First Search, breath first search, and best first search algorithms?<br>5. How to classify graph-based search problem? || 5
  +
|-
  +
| Individual Assignments || A1: kinematically feasible path planning <br>Implementation of the Hybrid A* for car-like ground vehicle and simulate planning in various environments <br>Submit a report and source code:<br>- Experimenting on different scenarios <br>- Check problem formulation and implementation accuracy <br><br>A2: Dynamically feasible path planning <br>Implementation of the KinoDynamic A* for car-like ground vehicle and simulate planning in various environments <br><br>Submit a report and source code:<br>- Experimenting on different scenarios <br>- Check problem formulation and implementation accuracy <br><br>A2: Sampling-based path planning <br>Develop a sampling-based path planner, RRT*, and compare with KinoDynamic A* and Hybrid A*<br>Submit a report and source code:<br>- Experimenting on different scenarios <br>- Check problem formulation and implementation accuracy <br>- Check the performance in term of reaching the goal and execution time || 15
  +
|}
 
==== Section 3 ====
  
==== Section 3 ====
  +
{| class="wikitable"
−  
  +
|+
−
==== Section 4 ====
  
  +
|-
−  
  +
! Activity Type !! Content !! Is Graded?
−
==== Section 5 ====
  
  +
|-
−  
  +
| Quiz || 1. List down ways to solve optimal control (OCP) problems.<br>2. How to formulate OCP using nonlinear programming problem (NLP)?<br>3. Difference between multiple shooting and direct collocation?<br>4. Explain the hamilton Jacobi bellman (HJB) approach?<br>5. How to formulate optimal reference trajectory tracking using (Linear Quadratic Regulator) LQR? || 5
−
==== Section 6 ====
  
  +
|-
−  
  +
| Individual Assignments || A1: Path tracking control with Model predictive control (MPC)<br>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<br>Submit a report and source code:<br>- Experimenting on different scenarios <br>- Check problem formulation and implementation accuracy <br><br>A2: Hamilton Jacobi Bellman (HJB) Approach<br>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 <br><br>Submit a report and source code:<br>- Experimenting on different scenarios <br>- Checking the accuracy of the trajectory tracker <br>A2: Lagrange polynomials and Spline interpolation<br>Apply a path planner to generate a set of intermediate waypoints and then apply Lagrange polynomials and Spline interpolation and generate trajectory <br>Submit a report and source code:<br>- Compare the properties of these <br>- Check problem formulation and implementation accuracy <br>- Compare results with nonlinear curve fitting algorithms: B-spline and Bezier || 15
−
==== Section 7 ====
  
  +
|}
−  
 
=== Final assessment ===
  
=== Final assessment ===
 
'''Section 1'''
  
'''Section 1'''
  +
# Can be a final exam, project defence, or some other equivalent of the final exam.
−
# What is psychology studying?
  
  +
# For the final assessment, students present the project work they have accomplished during the course. Below are the grading criteria for each section.
−
# What are the methods of psychology?
  
  +
# Section 1/2/3 Mini-Project
−
# Describe the structure of Psyche.
  
  +
# 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
  +
# Understanding how to formulate a given motion planning problem
  +
# Checking implementation accuracy
  +
# Reporting on finding and difficulting while formulating and implementing the proposed approach
 
'''Section 2'''
  
'''Section 2'''
  +
−
# 1. Give the definition to every mental cognitive process and its properties.
  
−
# 2. How do you use the knowledge of every mental cognitive process and practices connected with them in your personal life and communication?
  
 
'''Section 3'''
  
'''Section 3'''
  +
−
# 1. Tell about the part of our brain answers for Willpower?
  
−
# 2. What should we do with our body in order to improve our Willpower?
  
−
# 3. What are our mind tricks, connected with willpower and how to overcome them?
  
−
# 4. Describe the possible algorithm of coping with self-blaming.
  
−
'''Section 4'''
  
−
# 1. How do you understand emotional intelligence?
  
−
# 2. Describe the base emotions and tell how we can manage them.
  
−
# 3. Describe the social emotions and tell how we can work with them.
  
−
'''Section 5'''
  
−
# 1. Describe the Freud Conception of the Human Psyche and Personality.
  
−
# 2. Give the definition of Personality and its traits
  
−
# 3. Describe how our personality and its traits form and develop.
  
−
'''Section 6'''
  
−
# 1. Tell about the main instrument and conditions of communication.
  
−
# 2. What rules should we follow for successful communication?
  
−
# 3. What is the definition and main principles of networking?
  
−
'''Section 7'''
  
−
# 1. What does the Spiral dynamics theory describe?
  
−
# 2. Describe all the levels with crises of Spiral dynamics theory.
  
   
 
=== The retake exam ===
  
=== The retake exam ===
 
'''Section 1'''
  
'''Section 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 2'''
   
 
'''Section 3'''
  
'''Section 3'''
−  
−
'''Section 4'''
  
−  
−
'''Section 5'''
  
−  
−
'''Section 6'''
  
−  
−
'''Section 7'''
  

Revision as of 15:23, 9 February 2023

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
  1. Constrained optimization
  2. Least squares fitting
  3. Least squares fitting with regularization
  4. Smoothing
  5. Penalty functions
  6. Robust estimation
  7. Feasible problems
  8. Quadratic problems
  9. Linear problems
  10. Extremum
  11. Convexity
  12. Linearization of function up to the second variation
  13. Incremental of a function
  14. Incremental of a functional
  15. Fixed value problem
  16. Free terminal point problem
  17. Fix point problem ( t f is fixed and x(tf) is free)
  18. Fix point problem ( t f is free and x(tf) is fixed)
  19. Free endpoint problem: if tf and x(tf) are uncorrelated
  20. Free endpoint problem: if tf and x(tf) are depended on each other
  21. Constrained Minimization of functions
  22. Ï Elimination method (direct method)
  23. Ï The Lagrange multiplier method: examples, general
  24. formulation
  25. Constrained Minimization of functional: Point constraints,
  26. differential equation constraints
  27. Hamiltonian
  28. The necessary condition for optimal control
  29. Boundary conditions for optimal control: with the fixed final
  30. time and the final state specified or free
  31. Boundary conditions for optimal control: with the free final
  32. time and the final state specified, free, lies on the moving
  33. point x f = θ (t f ) , or lies on a moving surface m(x(t)) )
  34. Optimal control problem
  35. Pontryagin’s Minimum Principle
  36. Optimal boundary value problem
  37. Minimizing the square of the jerk
  38. Minimizing the square of acceleration
2.0 Graph-based Path planning & Sampling-based path planning
  1. Configuration Space vs Search Space for Robot
  2. Path Planning Problem Formulation
  3. Search-based Planning: Mapping
  4. Search-based Planning: Graph
  5. Graph Searching
  6. Depth First Search
  7. Breath First Search
  8. Cost Consideration
  9. Dijkstra’s Algorithm
  10. Greedy Best First Search
  11. A*: Combination of Greedy Best First Search and Dijkstra’s
  12. Algorithm
  13. A*: Design Consideration
  14. Graph-based search problem classification
  15. KinoDynamic A*:Heuristics, Generating motion primitives,
  16. finding neighbours
  17. Hybrid A*: Motion model, finding neighbours, the cost to go h, and cost so far g
  18. Probabilistic Road Map (PRM)
  19. Rapidly-exploring Random Tree (RRT)
  20. Rapidly-exploring Random Tree* (RRT*)
  21. Pros and Cons of RRT and RRT*
3.0 Linear Quadratic Regulator (LQR) & Model Predictive Control (MPC)
& Curve Fitting & Frenet frame trajectory planning
  1. LQR Formulation
  2. LQR via least squares
  3. Hamilton Jacobi Bellman (HJB) Approach
  4. Bellman Optimality
  5. LQR with HJB
  6. Hamiltonian formulation to find the optimal control policy
  7. Linear quadratic optimal tracking
  8. Optimal reference trajectory tracking with LQR
  9. Ways to solve Optimal Control (OCP) Problems
  10. OCP Using Nonlinear Programming Problem (NLP)
  11. Model Predictive Control: Prediction model, Constraints
  12. Reference trajectory tracking
  13. Simplified Motion Model
  14. With Multiple Shooting and direct collocation
  15. Continuous nonlinear system linearization
  16. Discrete-time nonlinear system linearization
  17. Linear Time-Varying Model Predictive Control
  18. Path tracking control
  19. Path tracking control with MPC: kinematic model, trajectory
  20. generation, dynamic model, and cost, formulation
  21. n degree polynomial fitting
  22. Euler–Lagrange equation
  23. Minimum jerk trajectory (MJT) generation
  24. Quintic polynomial
  25. Lagrange polynomials
  26. Lagrange first-order, second-order, and nth-order
  27. interpolation
  28. Spline interpolation: Linear, Quadratic, and Cubic Spline
  29. Other types of curve fitting: Gradient descent, Double arc
  30. trajectory interpolation
  31. Nonlinear curve fitting
  32. Bezier curve fitting
  33. B-spline curve fitting
  34. Frenet frame
  35. Curve parameterization of the reference trajectory
  36. Estimate the position of a given Spline
  37. The road-aligned coordinate system with a nonlinear
  38. dynamic bicycle model
  39. Frenet frame trajectory tracking using a nonlinear bicycle
  40. model
  41. Transformations from Frenet coordinates to global
  42. coordinates
  43. Polynomial motion planning
  44. Frenet frame trajectory generation algorithm
  45. 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

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

Retrieved from "https://eduwiki.innopolis.university/index.php?title=IU:TestPage&oldid=8087"