Autonomous Robots: Nonholonomic Motion Planning Algorithms

Learn the how to calculate smooth vehicle trajectories, and combine this with sampling based motion planning!

What you'll learn

Learn the Dubins Curve algorithm for smooth trajectory generation between two waypoints on a map.

Calculate a path using the Rapidly Exploring Random Trees (RRT) and RRT* algorithms combined with Dubins curves.

Learn the basics of incremental path planning for real time applications.

Determine a path using Incremental RRT with Dubins curves, and analyze your results quantitatively.

Requirements

No programming experience needed. I will teach you everything from scratch.

It is recommended that students have Python 3.9.x, Numpy 1.23.x and Matplotlib 3.x ready for the assignments.

Description

Important Note:This course is a Part 2 to my free course Introduction to Sampling Based Motion Planning Algorithms.However, you do not need to finish the free course first, since I cover all of the free course material (plus a whole lot more!) within this course. With that said, if you already have completed Introduction to Sampling Based Motion Planning Algorithms, then you will have an advantage.HighlightsLearn affine transformations and vector rotation matrices.Derivation of the Dubins Path to generate smooth trajectories given two points on a map.Combine Dubins Path with motion planning RRT and RRT* algorithms.4 interactive assignments.Description Motion planning is a field of engineering dealing with calculating a path from a start to a goal location whilst avoiding obstacles, for example using Google or Apple Maps. The vast majority of vehicles in today's world i.e (cars, boats, planes) are non holonomic, meaning they have limited degrees of freedom of movement with respect to the available space. For instance, think of shifting a car between adjacent parking spots. The car cannot 'slide' sideways into the second parking spot. It has to reverse and turn in to the spot, or go around in a circular path. Given two arbitrary positions and headings on a map, the task is to find a smooth trajectory which satisfies the speed constraints of the vehicle. This is accomplished by using the Dubins Path. In this course, you will learn how to derive the Dubins Path from first principles and also implement and test the method via an assignment. Next, you will learn how to combine this theory with sampling based motion planning algorithms. The next two assignments will involve finding a path using RRT and RRT* with Dubins Path. Lastly, the final assignment will involve incremental RRT with Dubins Path for a realistic roadmap scenario, where the vehicle has limited information.RequirementsPython, Numpy and MatplotlibBasic understanding of scalars and vectorsYou could alternatively complete the course using another programming language, however in this case you will have to transcribe the assignments on your own, in that specific language.

Overview

Section 1: Introduction

Lecture 1 Introduction, Course Overview, Getting in Touch, Motion Planning Basics

Lecture 2 Overview: Setting up Python and the Course Assignments

Lecture 3 Assignment 0: Overview

Lecture 4 Assignment 0: Solution

Section 2: Overview of Sampling Algorithms

Lecture 5 Overview: RRT Algorithm

Lecture 6 Overview: RRT* Algorithm

Lecture 7 Nonholonomic Vehicles

Section 3: Calculating Smooth Trajectories

Lecture 8 Dubins Curve: Part 1

Lecture 9 Dubins Curve: Part 2

Lecture 10 Assignment 1: Intro

Lecture 11 Assignment 1: Solution

Section 4: Rapidly Exploring Random Trees with Dubins Path

Lecture 12 RRT With Dubins: Overview

Lecture 13 Assignment 2 Part 1: Intro

Lecture 14 Assignment 2 Part 1: Solution

Lecture 15 Assignment 2 Part 2: Intro

Lecture 16 Assignment 2 Part 2: Solution

Section 5: Rapidly Exploring Random Trees Star with Dubins Path

Lecture 17 RRT Star With Dubins: Overview

Lecture 18 Assignment 3: Intro

Lecture 19 Assignment 3: Solution

Section 6: Incremental Path Planning for Autonomous Driving

Lecture 20 RRT with Dubins for Driving

Lecture 21 Assignment 4: Intro

Lecture 22 Assignment 4: Solution

Section 7: Conclusion

Lecture 23 Outro: Thank You!

Anyone with an interest in autonomy, robotics, algorithms and path planning.