Course Information: ELLIIT Ph.D. Course on Motion Planning and Control, 6+3 hp

Organization

A course in advanced motion planning and control is to be held at the Division of Vehicular Systems, Linköping University during the spring semester 2021. The course is open for all Ph.D. students as well as senior undergraduate students. The course will cover both fundamental algorithms and state-of-the-art methods for motion planning and control. A significant part of the course will be dedicated to implementation of a number of selected algorithms and subsequent applications on small examples, to the purpose of gaining an understanding of the considered methods. The course relates to ongoing research within several programs, such as ELLIIT and WASP.

Meetings

In the course, there will be approximately one meeting per week, see detailed course plan below. For each meeting in the course, one participant will be assigned in advance to prepare a short lecture (approximately 45 minutes) based on the reading material that has been studied by all course participants during that week. The assigned participant is also expected to, together with the course responsible teachers, lead a joint discussion in the group on the material after the lecture. During this discussion, both the algorithms themselves and other related aspects that have appeared when implementing them are covered.

Exercises

In connection with selected course meetings, a hand-in assignment will be requested. The assignment should be submitted to the course responsible prior to each course occasion, since the exercises will be discussed during the meeting. No written reports are required for the hand-in assignments, but the implementation code and scripts with comments should be submitted. The participant should also be prepared to present and discuss the solutions in class.

Structure

The course will be divided into two parts. The first part will focus on motion planning and an introduction to motion control; this part will give 6 hp. The second part will focus on more advanced aspects of combined motion planning and control, and will also comprise a specialization part where the participant performs a slightly larger theoretical or experimental evaluation of a selected method, preferably related to the research field of the participant. The assignment could, e.g., be based on the Open Motion Planning Library (OMPL, http://ompl.kavrakilab.org/), the PythonRobotics Toolbox (https://pythonrobotics.readthedocs.io/en/latest/index.html), or the Robot Operating System (ROS, http://www.ros.org/). The second part of the course will give 3 hp.

Guest Lectures

Guest lectures will be given by invited speakers later in the course. They will give focused lectures on specific topics related to their own research. The speakers and exact times will be announced in the course plan below.

Literature

The planning part is based on the book:

• LaValle, S. M., Planning Algorithms, Cambridge University Press, Cambridge, UK, 2006, which is available for free download at the homepage of the author:
  • http://lavalle.pl/planning/
• Selected chapters from B. Siciliano & O. Khatib (Eds.) Springer Handbook of Robotics, 2nd Edition, 2016, will also be used as literature, which is available here:
  • https://doi.org/10.1007/978-3-319-32552-1
• The control part will be based on selected book chapters.
• The books will be complemented by several articles and papers (announced during each meeting for the following week).

Examination

In order to receive course credits, the participant is required to:

• Attend the weekly meetings and actively take part in the discussions.
• Submit the hand-in assignments prior to each meeting where it is requested (primarily implementation code or scripts with comments and conclusions from the results, no extensive written reports required).
• Prepare one lecture during the course.
• Complete a final project, give an oral presentation at the project seminar, and submit a written report.
• The course is nominally 6+3 hp (where the first part primarily comprises the planning part).

Examiner for the course is Björn Olofsson.

Course Plan

The course meetings and associated reading and implementation assignments are specified in the list below.

Introduction Meeting

Date: Tuesday January 12, 2021, at 15:15-16:15 in Zoom (link distributed to registered participants via e-mail).
Topics: About the course, introduction of participants, course administration, and planning of next meeting.
Responsible: Björn Olofsson
Slides: [Link]

Introduction to Motion Planning and Control & Discrete Graph Search

Date: Tuesday January 19, 2021, at 15:15-17:00 in Zoom.
Topics: Introduction to motion planning and control, overview of methods and their applicability, and graph-search algorithms (such as Dijkstra, A*, ARA*).
Responsible: Björn Olofsson
Assignments: [Link]
Links to material:

• LaValle, S. M., Planning Algorithms, Cambridge University Press, Cambridge, UK, 2006.
• B. Paden et al., "A survey of motion planning and control techniques for self-driving urban vehicles". IEEE Transactions on Intelligent Vehicles 1.1, 33-55, 2016.
• M. Likhachev et al., "ARA*: Anytime A* with provable bounds on sub-optimality", Advances in Neural Information Processing Systems, 16, 767-774, 2003.
• Hand-in Exercise 1 in TSFS12 [Link].
• Lecture 2 in TSFS12 on Discrete Motion Planning [Link].
• Links to recorded videos for Lecture 2 in TSFS12 [Link].

Motion-Planning Fundamentals

Date: Tuesday January 26, 2021, at 15:15-17:00 in Zoom.
Topics: Geometric representations, configuration and state spaces, and optimal paths for some wheeled vehicles.
Responsible: Faseeh Ahmad
Assignments: [Link]
Links to material:

• LaValle, S. M., Planning Algorithms, Cambridge University Press, Cambridge, UK, 2006.
• Dubins, L. E., "On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents", American Journal of Mathematics, 79(3), 497-516, 1957.

Rapidly-Exploring Random Trees (RRTs) and Variants

Date: Tuesday February 2, 2021, at 15:15-17:00 in Zoom.
Topics: RRT, RRT*, CL-RRT, sampling-based planning with differential motion constraints.
Responsible: Anja Hellander
Assignments: [Link]
Links to material:

• LaValle, S. M., Planning Algorithms, Cambridge University Press, Cambridge, UK, 2006.
• LaValle, S. M. & Kuffner Jr, J. J. (2001). "Randomized kinodynamic planning", The International Journal of Robotics Research, 20(5), 378-400, 2001.
• Karaman, S. & E. Frazzoli, "Sampling-based algorithms for optimal motion planning", The International Journal of Robotics Research, 30(7), 846-894, 2011.
• S. Karaman & E. Frazzoli, "Optimal kinodynamic motion planning using incremental sampling-based methods", In: 49th IEEE Conference on Decision and Control (CDC), Atlanta, GA, 7681-7687, 2010.
• Kuwata, Y., Teo, J., Fiore, G., Karaman, S., Frazzoli, E., & How, J. P., "Real-Time Motion Planning With Applications to Autonomous Urban Driving", IEEE Transactions on Control Systems Technology, 17(5), 1105-1118, 2009.
• Arslan, O., Berntorp, K., & Tsiotras, P., "Sampling-based algorithms for optimal motion planning using closed-loop prediction", In: IEEE International Conference on Robotics and Automation (ICRA), 4991-4996, 2017.
• Hand-in Exercise 2 in TSFS12 [Link].
• Lecture 4 in TSFS12 on Motion Planning with Differential Constraints [Link].
• Links to recorded videos for Lecture 4 in TSFS12 [Link].

Motion Primitives and Lattice Planning

Date: Tuesday February 9, 2021, at 15:15-17:00 in Zoom.
Topics: Motion primitives, discretization of state space, state lattices, and lattice planning using graph search.
Responsible: Jian Zhou
Assignments: [Link]
Links to material:

• LaValle, S. M., Planning Algorithms, Cambridge University Press, Cambridge, UK, 2006.
• Pivtoraiko, M., Knepper, R. A., & Kelly, A., "Differentially constrained mobile robot motion planning in state lattices", Journal of Field Robotics, 26(3), 308-333, 2009.
• Likhachev, M., & Ferguson, D., "Planning long dynamically feasible maneuvers for autonomous vehicles", The International Journal of Robotics Research, 28(8), 933-945, 2009.
• Ljungqvist, O., "Motion planning and feedback control techniques with applications to long tractor-trailer vehicles", Ph.D. Thesis No. 2070, Division of Automatic Control, Linköping University, 2020.
• Hand-in Exercise 2 in TSFS12 [Link].
• Lecture 4 in TSFS12 on Motion Planning with Differential Constraints [Link].
• Links to recorded videos for Lecture 4 in TSFS12 [Link].

Feedback-Based Planning and Artificial Potential Fields

Date: Tuesday February 16, 2021, at 15:15-17:00 in Zoom.
Topics: Planning using feedback methods, navigation functions, and artificial potential fields.
Responsible: Theodor Westny
Assignments: [Link]
Links to material:

• LaValle, S. M., Planning Algorithms, Cambridge University Press, Cambridge, UK, 2006.
• Khatib, O, "Real-time obstacle avoidance for manipulators and mobile robots", In: Proceedings IEEE International Conference on Robotics and Automation, Vol. 2, pp. 500-505, 1985.
• Rimon, E., & Koditschek, D. E., "Exact robot navigation using artificial potential functions", IEEE Transactions on Robotics and Automation, 8(5), 501-518, 1992.

Trajectory Optimization for Planning and Control

Date: Tuesday March 9, 2021, at 15:15-17:00 in Zoom.
Topics: Trajectory optimization, numerical optimal control, and optimization-based planning methods.
Responsible: Julian Salt
Assignments: [Link]
Links to material:

• LaValle, S. M., Planning Algorithms, Cambridge University Press, Cambridge, UK, 2006.
• Limebeer, D. J., & Rao, A. V., "Faster, higher, and greener: Vehicular optimal control", IEEE Control Systems Magazine, 35(2), 36-56, 2015.
• Chapter 8 in Rawlings, J. B., D. Q. Mayne, & M. Diehl, Model Predictive Control: Theory, Computation, and Design, Nob Hill Publishing, 2017.
• Bergman, K., Ljungqvist, O., & Axehill, D., "Improved path planning by tightly combining lattice-based path planning and optimal control", IEEE Transactions on Intelligent Vehicles, 2020.
• Andersson, J. A., Gillis, J., Horn, G., Rawlings, J. B., & Diehl, M., "CasADi: A software framework for nonlinear optimization and optimal control", Mathematical Programming Computation, 11(1), 1-36, 2019.
• Berntorp, K., Olofsson, B., Lundahl, K., & Nielsen, L., "Models and methodology for optimal trajectory generation in safety-critical road-vehicle manoeuvres". Vehicle System Dynamics, 52(10), 1304-1332, 2014.
• Bergman, K., "On Motion Planning Using Numerical Optimal Control", Licentiate Thesis No. 1843, Division of Automatic Control, Linköping University, 2019.
• Fors, V., "Autonomous Vehicle Maneuvering at the Limit of Friction", Ph.D. Thesis No. 2102, Division of Vehicular Systems, Linköping University, 2020.
• Magnusson, F., "Numerical and Symbolic Methods for Dynamic Optimization", Ph.D. Thesis No. TFRT-1115, Department of Automatic Control, Lund University, 2016.
• Lecture 5 in TSFS12 on Motion Planning with Differential Constraints [Link].
• Links to recorded videos for Lecture 5 in TSFS12 [Link].

Motion Prediction for Planning and Control

Date: Tuesday March 16, 2021, at 15:15-17:00 in Zoom.
Topics: Vehicle-motion prediction and vehicle-intent prediction.
Responsible: Carl Hynén
Assignments: [Link]
Links to material:

• Lefèvre, S., Vasquez, D., & Laugier, C., "A survey on motion prediction and risk assessment for intelligent vehicles", ROBOMECH journal, 1(1), 1-14, 2014.
• Mozaffari, S., Al-Jarrah, O. Y., Dianati, M., Jennings, P., & Mouzakitis, A., "Deep learning-based vehicle behavior prediction for autonomous driving applications: A review", IEEE Transactions on Intelligent Transportation Systems, 2020.
• Hand-in Exercise 5 in TSFS12 [Link].
• Lecture 11 in TSFS12 on Motion Planning with Differential Constraints [Link].
• Links to recorded videos for Lecture 11 in TSFS12 [Link].

Path and Trajectory-Following Control

Date: Tuesday March 23, 2021, at 15:15-17:00 in Zoom.
Topics: Path and trajectory following for wheeled vehicles.
Responsible: Birgitta Wingqvist
Assignments: [Link]
Links to material:

• C. Samson, Morin, P., & Lenain, R., "Modeling and Control of Wheeled Mobile Robots", Chapter 49 in Springer Handbook of Robotics (Eds. Siciliano, B. & Khatib, O.), 2nd Edition, Springer, 2016.
• Coulter, R.C., "Implementation of the pure pursuit path tracking algorithm", Robotics Institute, Carnegie Mellon University, Pittsburgh PA, Report number CMU-RI-TR-92-01, 1992.
• Werling, M., Gröll, L., & Bretthauer, G., "Invariant trajectory tracking with a full-size autonomous road vehicle". IEEE Transactions on Robotics, 26(4), 758-765, 2010.
• Hand-in Exercise 3 in TSFS12 [Link].
• Lecture 6 in TSFS12 on Motion Planning with Differential Constraints [Link].
• Links to recorded videos for Lecture 6 in TSFS12 [Link].

Motion Planning and Control Using Invariant Sets

Date: Tuesday April 6, 2021, at 15:15-17:00 in Zoom.
Topics: Invariant sets for motion planning and control, and design for robustness to disturbances.
Guest lecturer: Karl Berntorp, Mitsubishi Electric Research Labs, Boston, MA
Assignments: [Link]
Links to material:

• Berntorp, K., Bai, R., Erliksson, K. F., Danielson, C., Weiss, A., & Di Cairano, S., "Positive invariant sets for safe integrated vehicle motion planning and control", IEEE Transactions on Intelligent Vehicles, 5(1), 112-126, 2019.
• Danielson, C., Berntorp, K., Di Cairano, S., & Weiss, A., "Motion-planning for unicycles using the invariant-set motion-planner", In: American Control Conference (ACC), pp. 1235-1240, 2020.
• Danielson, C., Berntorp, K., Weiss, A., & Di Cairano, S., "Robust Motion Planning for Uncertain Systems With Disturbances Using the Invariant-Set Motion Planner", IEEE Transactions on Automatic Control, 65(10), 4456-4463, 2020.

Model Predictive Control for Planning and Control

Date: Tuesday April 13, 2021, at 15:15-17:00 in Zoom.
Topics:Receding-horizon control and model predictive control for path following, trajectory following, and integrated planning and control for autonomous vehicles.
Responsible: Jonas Nordlöf
Assignments: [Link]
Links to material:

• Falcone, P., Borrelli, F., Asgari, J., Tseng, H. E., & Hrovat, D., "Predictive active steering control for autonomous vehicle systems", IEEE Transactions on Control Systems Technology, 15(3), 566-580, 2008.
• Nilsson, J., Falcone, P., Ali, M., & Sjöberg, J., "Receding horizon maneuver generation for automated highway driving", Control Engineering Practice, 41, 124-133, 2015.
• Rosolia, U., & Borrelli, F., "Learning how to autonomously race a car: A predictive control approach", IEEE Transactions on Control Systems Technology, 28(6), 2713-2719, 2019.
• Svensson, L., Bujarbaruah, M., Kapania, N. R., & Törngren, M., "Adaptive Trajectory Planning and optimization at Limits of Handling", In: IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 3942-3948, 2019.
• Berntorp, K., Quirynen, R., Uno, T., & Di Cairano, S., "Trajectory tracking for autonomous vehicles on varying road surfaces by friction-adaptive nonlinear model predictive control". Vehicle System Dynamics, 58(5), 705-725, 2020.
• Fors, V., Anistratov, P., Olofsson, B., & Nielsen, L., "Predictive Force-Centric Emergency Collision Avoidance", ASME Journal of Dynamic Systems, Measurement, and Control, 143(8), 081005, 2021.
• Hand-in Exercise 3 in TSFS12 [Link].
• Lecture 7 in TSFS12 on Motion Planning with Differential Constraints [Link].
• Links to recorded videos for Lecture 7 in TSFS12 [Link].

Motion Planning Using Numerical Optimal Control

Date: Tuesday April 20, 2021, at 15:15-17:00 in Zoom.
Topics: Planning using numerical optimal control, receding-horizon planning, and planning for surface vehicles.
Guest lecturer: Kristoffer Bergman, Division of Automatic Control, Linköping University
Assignments: [Link]
Links to material:

• Bergman, K., Ljungqvist, O., & Axehill, D., "Improved path planning by tightly combining lattice-based path planning and optimal control", IEEE Transactions on Intelligent Vehicles, 6(1), 57-66, 2021.
• Bergman, K., Ljungqvist, O., Glad, T., & Axehill, D., "An Optimization-Based Receding Horizon Trajectory Planning Algorithm", In: 21st IFAC World Congress, 2020.
• Bergman, K., Ljungqvist, O., Linder, J., & Axehill, D., "A COLREGs Compliant Motion Planner for Autonomous Maneuvering of Marine Vessels in Complex Environments", arXiv preprint arXiv:2012.12145, 2021.
• Bergman, K., "Exploiting Direct Optimal Control for Motion Planning in Unstructured Environments", Ph.D. Thesis No. 2133, Division of Automatic Control, Linköping University, 2021.

Project Seminar

Date: Friday May 28, 2021, at 13:15-15:45 in Zoom.
Topics: Presentations of projects by participants.
Responsible: Björn Olofsson
Project organization: [Link]
Agenda: [Link]

Course Responsible

Responsible for the course is Björn Olofsson (bjorn.olofsson@liu.se) and Erik Frisk (erik.frisk@liu.se) at the Division of Vehicular Systems, Department of Electrical Engineering, Linköping University.

Informationsansvarig: Björn Olofsson
Senast uppdaterad: 2021-05-24