Path Planning for Autonomous Race Cars (Project 208)

[robertogl]

Contribute to the discussion by asking and/or answering questions, commenting, or sharing your ideas for solutions to project 208

[jkbchouinard]

Howdy! I'm a student at the University of Waterloo, and I'm super interested in working and collaborating on this project! This is going to be one of my first forays into path planning for something like an autonomous car, and I'm looking forward to learning as much as I can.

[jkbchouinard]

Thanks for linking that! It definitely provides a good overview about what exactly SCR is and how it works. I've seen a couple different uses of rapid, random exploring, but the optimization method seems to be much more efficient and effective. From what I've seen, most approaches to this question parameterize values into terms of arc length (s(t):[0,T]->[0,S]) rather than time, as the objective function and end-effect are approximately equivalent. It looks like a very central part of this optimization question is the dynamics of the lateral and longitudinal friction as the speed and direction of the bicycle model changes. Also, that sounds good. I might try to create a Markdown table of the symbols I see commonly used in this application in my repository as well as explanations on what they represent.

[veeralakshendra]

Hi! I am Veer from MathWorks.
Thanks for initiating the discussion. Great to see the sharing of knowledge and resources. Here are a few resources that I would like to share with you all:

Transformation from time to spatial dynamics: As you have mentioned, it's a minimum time problem but is converted to an equivalent space domain. One of the reasons is that the race car is parameterized mainly in terms of position. To understand the advantage of space over time, please check the section "C, Space vs Time Domain" of this article: https://arxiv.org/pdf/2003.04882.pdf

Lecture 11: Convex Optimization video: This is the lecture from Prof. Stephen Boyd based on the same set of slides shared on this thread: https://www.youtube.com/watch?v=upMWYV7S1Y0

Vehicle model: Selection of vehicle modeling strategy will define how realistic the algorithm is. Here is an article to help you decide on the selection of vehicle model: https://saemobilus.sae.org/content/2000-01-3563/. Tire forces impact vehicle dynamics. Hence, it would be great if you can include it in the model.

Please continue sharing your thoughts and technical resources.

[jkbchouinard]

Hi Veer! Thank you for the resources. I'll continue to review them in the upcoming days as I have time to do so! I'm currently engaged in trying to truly understand and be able to explain the MATLAB Script code that was linked via the first bulletin on the Readme. I feel once I understand this better, I may be able to begin understanding how to take the theoretical workings in several of the papers I've been reading and apply them realistically.

Thanks again!

[putta54]

Hello! I am a student at the Indian Institute of Technology Roorkee and I find this project really exciting! I first got to know about this project in the FB workshop where Veer mentioned this project. I am really new to the concept of optimization and path planning but I will still try to get as much as I can from this project and hopefully find a solution to it!

[jkbchouinard]

Hey there! If you find any resources or have any thoughts, feel free to share them! A couple have already been shared above, but more will always be appreciated. A big challenge I've been having is really just the understanding of solution methods. As an undergraduate engineering student still in the early years of my education, I'm not very familiar with these sorts of optimization methods, such as Projection-Based Newtonian optimization for non-linear convex problems. It's been a challenge to grasp these, as well as to approach discretizing them so that it's actually able to be implemented. If you have any thoughts or ideas, let us know!

[Akashleena]

Hi I am Akashleena Sarkar (Aleena) from India.
I am interested in path planning, have worked on RRT and some ROS related motion planning previously.
I am now interested to work on optimization of Path Planning for Autonomous Race car using RL Techniques i.e Project 208.

Open to collaboration and ideas.
Let's work together!

Cheers!
Aleena

[veeralakshendra]

Hi Akashleena,

Thanks for joining the discussion forum. I like your idea of Reinforcement Learning. Although, until now we were discussing optimization techniques, please feel free to explore RL technique solutions. Below are some of the resources to help you get started with RL in MATLAB:

• Reinforcement Learning Onramp
• Reinforcement Learning Toolbox

Also, please feel free to reach out to us if you have any questions.

Regards,
Veer

[anjishnum]

Hi Akashleena,

I'm Anjishnu from India. I have worked on SLAM techniques and am currently looking at metaheuristic optimization approaches in path planning.

Down to collaborate and brainstorm on some ideas.

Best,
Anjishnu

[ghost]

Hey I am Sankalp from VIT Vellore, I have only recently learnt MATLAB and am expecting to use this as a great learning opportunity and brainstorm an epic way to do this project.

Open to collaboration and ideas
Let's go!

Godspeed
Sankalp ∞

[veeralakshendra]

Hi Sankalp,

Glad to have you join the discussion forum.

It is great that you are learning MATLAB.

There are various approaches to the optimized path planning problem. Please feel free to go through the background material and also the resources shared on the discussion forum.

Please let us know if you have any questions.

Regards,
Veer

[veeralakshendra]

Hello all,

I found a video lecture from the University of Pennsylvania. Here is the link: Video Lecture: Autonomous Racing: Raceline Optimization

I found this useful as it nicely explains each step. It is based on Covariance-Matrix Adaptation Evolution Strategy. For its implementation in MATLAB, you can follow this File Exchange Submission.

Please feel free to explore.

Regards,
Veer

[anjishnum]

Thank you sir.

[ghost]

Thank you for the resources sir! 

[KrishnaGit81]

Hi, I am Krishna Teja from IIT Madras. This is an interesting project and thanks for the useful resources.
I have made a video of my implementation with EV and simple control logics.

[jkbchouinard]

Hi everyone!

If you're pursing route optimization for minimum curvature, I found a good resource that I felt would be worth sharing!

The file is attached.

Cheers!
Jakeb
Optimized Trajectory Generation for Car-Like Robots on a Closed L.pdf

[veeralakshendra]

Thanks, Jakeb!

This is indeed a resourceful paper. I like their approach for velocity profile generation.

Regards,
Veer

[putta54]

Hello all,

For the optimization route, I have found this repository by TUMFTM. They have approached this problem in four different ways.

The code is in python, but the mathematics is essentially the same.

Github repository - https://github.com/TUMFTM/global_racetrajectory_optimization

You could check out the four references at the bottom of the page.

Regards,
Gautam

[jkbchouinard]

Hi all,

I'm happy to share the first iteration of my attempts at creating a minimum curvature optimizer for a given track! You can find the code here as well as example 1 video and example 2 video. I am in the midst of creating a velocity profile for these trajectories as well. Once that is complete, I will be able to better annotate and layout how it works in the repository's readme file.

As a brief overview, this uses a path searching algorithm to find ideal curvature points along given lines within the track that are predetermined using spline interpolation. It uses a much more localized (and thereby likely inefficient) approach than a global approach that some optimization methods use. In the future, I may investigate using a more global approach that relies on something like genetic/evolutionary algorithms.

Cheers!
-Jakeb

7/30 Edit: I found a glaring error in my calculation for curvature; however, it is locally fixed. That said, I'll work on uploading new optimization videos that reflect this.

8/1 Edit: The new optimization videos can be found here (Kidney Bean) and here (Oblong)

[veeralakshendra]

Hi Jakeb,

Great progress!

The current algorithm looks great. I like how the vehicle enters the apex and then takes a straight path. This will eventually improve the lap time.

As velocity is one of the control inputs that will define the car's behavior on tracks, it would be great to add a velocity profiler. Once you have implemented the same, you can also compare the lap time as the iteration progresses.

Looking forward to your submission.

-Veer

[jkbchouinard]

Hi Veer,

Thank you! I'm working on velocity now, which is more complicated than anticipated, but we'll see what happens. I'll post an update as it goes on, but hopefully, I should be able to implement this without too much scuff. I have a rough velocity generator, but it associates the velocity with distance along the path from start, which I'm not sure how to tie into the time domain.

Cheers,
Jakeb

[jkbchouinard]

Hi all,

An update on my previous post, I have managed to create and implement a velocity profile generator based on point mass kinematics found in a resource I shared previously. Some example videos of this execution can be found here for the oblong track I shared previously and here for the kidney bean track I shared previously. This relies on looking at the curvature of the track at specific instances based on the arc-length position of the mass and the mass's maximum lateral and longitudinal forces. This is then converted to a time domain through a state updater based on "zero" (1e-6) initial velocity and time steps of 0.001s. The curvature path also has a 20% buffer, which ensures that the mass will, at no point, exit the inner or outer bounds of the path. I'll be refreshing my repository here in a minute if anyone has an interest in looking through it!

Note: The oblong track looks different from the previous video due to differences in plotting. The velocity video uses axis equal, but the curvature optimizer doesn't (yet). I'm hoping to fix this soon.

If you have any questions or suggestions, please feel free to ask!

Cheers,
Jakeb

[veeralakshendra]

Hi Jakeb,

Appreciate your effort in incorporating velocity profiler in the code during the weekend. 💯

I tested your code on various racing tracks (track width = 6 m, Norm factor gain = 5) and the optimized paths obtained are impressive and as expected. 👍

Regarding the video shared for the oblong track, I can see that the vehicle cuts corners at approximately 25 m/s to 30 m/s which I think is on a higher side. Can you provide some explanation on this? We can also discuss this by email.

Also, do you have any plans of implementing the dynamic model velocity profile as presented in the thesis (Section 4.2) you have referred to?

Great job! 👍
Regards,
Veer

[jkbchouinard]

Hi Veer,

Thank you! Your feedback is much appreciated.

The FSG Track looks great! I'm happy to see the algorithm working properly on a track that isn't of my own design haha. Documentation is currently underway, and hopefully, it will be complete soon.

Cheers,
Jakeb

[veeralakshendra]

Sure, Jakeb! Take your time. :)

Regards,
Veer

[jkbchouinard]

Hi Veer,

Sounds good. I've updated it rather substantially so far, but there's likely more to come. The README has been updated to feature GIFs and PNGs of the process and outcomes. Each *.m file has also received a fairly intensive documentation, excluding those moved to the archived scripts section as well as the track scripts. The Live Script has also been modified to better use the properties of the live script for documentation purposes. The repository has been updated with the latest code.

Let me know if you have any thoughts on the documentation or otherwise!

Cheers,
Jakeb

[veeralakshendra]

Hi Jakeb,

Just went through the documented version. It looks perfect 👍 . Below are a few suggestions:

• Users might like to change the input parameters of the function, "velocityProfilerV2." It would be better to define these using variables.
  
• I think adding a "distance vs velocity" profile as an additional output might be interesting.
• In the later part of the script you have nicely described video 1, video 2, and video 3. As the boolean controls of these videos are in the initial part, it might be good to add one line comment on each of these controls. Also, it would be worth if you can mention this note: Using these boolean controls to output video/GIF might increase the script run time.
• Just a minor suggestion. Now as you have only one velocity profiler, you can remove "2" from the function. :)

Overall the documentation looks perfect.

Regards,
Veer

[jkbchouinard]

Hi Veer,

I've added in several of your suggestions — thank you for those! I'll be pushing the updated code to my repository here in a few minutes; it includes an additional PNG output showcasing distance vs velocity and distance vs critical velocity plots (see below) as well as variable fields to modify values going into functions. Let me know if you have any other suggestions!

Cheers,
Jakeb

8/8 Midday Update: Additional changes have been made to the code to make it more scalable and efficiently executed. This was due to significant time consumption simulating Silverstone track data brought in from the DSD via OSM, partly due to the significantly higher track length than previously tested tracks. Interestingly, there are some issues importing track data via OSM, such as where roads meet. Thresholds for the optimizer were adjusted, and methods for the datasets to revert to best fit were introduced. Maximum velocity was also implemented to prevent the vehicle from reaching 2.5e6 m/s on a straightaway lol. Code will be updated soon with Silverstone circuit testing data. Additional tracks may be introduced as well; however, the process to bring them into DSD and convert them to code takes a long time and has a tendency to latch on certain operations.

[putta54]

Hello all,

First of all, I want to say that Jakeb has done an excellent job. The videos he created were outstanding, and the documentation he is currently building also looks pretty neat. Keep it up!

I also wanted to share that I have completed developing a trajectory generator and velocity profiler. I will briefly explain each section of the entire process.

Concept

My main idea was similar to Jakeb's: first, create a minimum curvature trajectory and then develop a velocity profile based around it. This method is generally used by almost every paper written on this topic, at least as a starting point. I also calculated the velocity profile of the shortest path around the given track to show how bad the lap times are for it compared to the min curvature one. I also validated most of my results with data and literature I found online.

Trajectory Generation

For this section, I followed a global approach for both the shortest path and min curvature trajectory. The methodology I stuck to is outlined in this paper, Race Driver Model.

I converted this entire subject into a quadratic programming (QP) problem and solved it with the help of the 'quadprog' function in MATLAB. I also derived the equations for H and B matrices myself in terms of the coordinates of the track edges. Then I substituted these matrices in the QP solver along with the constraints that restrict the trajectory within the boundaries. I also added another condition that requires the starting point to be the same as the end one. The reasoning behind this was to create a loop rather than a broken track at the end.

As soon as the solver is executed, it automatically outputs the results, making the solving time almost negligible. It usually takes around 11-12 iterations to find the result. Unfortunately, quadprog doesn't have the functionality to output the result of every iteration, making me incapable of rendering the really cool animated GIFs Jakeb had presented.

Some of the drawbacks and improvements to my method have been mentioned in this paper Minimum curvature trajectory planning and control for an autonomous race car. One critical simplifying assumption I made was neglecting the 2x'y' term in my curvature definition. This leads to a slightly suboptimal solution but significantly reduces the effort for calculating the H and B matrices. One improvement would be to use an iterative QP routine that replaces the reference line with the solution of the previous QP iteration.

Images

Shortest Path - Silverstone --- Minimum curvature - Silverstone

For comparison - Raceline uploaded by TUMFTM for Silverstone track

Velocity Profile Generation

To generate a velocity profile, I referred to this paper, Optimized Trajectory Generation for Car-Like Robots on a Closed-Loop Track that Jakeb shared. Along with that, I also followed Optimal velocity profile generation for given acceleration limits: theoretical analysis, which actually inspired the previous report and mentioned it as a reference.

The main idea was to identify the max curvature points for the optimized trajectory, assign a certain critical velocity to each one, and generate velocity profiles around these points. Since it is assumed that the vehicle follows the course perfectly, the only driver input would be the throttle and brake commands. It is mentioned in the previous papers that to achieve minimum time, control inputs for acc and dec must be 1 and -1, respectively.

These intermediate velocity profiles are generated according to specific rules defined in the literature. The final profile is the minimum of all these in-between profiles. One modification that I made to these rules was to check if the critical velocity at the max curvature point was greater than the acc profile from the previous step; if it was, I continued the previous profile rather than starting a new one. The exact process was followed for the deceleration profiles.

Finally, lap times were calculated from the velocity and length vectors in order to validate my results with actual data.

Lap Time Silverstone, UK (F1) [calculated] - 96.6s -- Current Lap record - 90s
Lap Time Spa, Belgium (F1) [calculated] - 109s -- Current lap record - 106s

As it was previously discussed, the literature mentioned in this section has some errors in the critical velocity and velocity iteration formulae. I have corrected them in my implementation. I have also included aerodynamics effects for traction and braking by inserting a -v^2 term within the equations. Since the velocities are really high in F1, aerodynamics drag cannot be neglected.

Images

Velocity Profile for min curvature trajectory of Silverstone track

Notes

Most of the track data I tested was from this Github repository, Race Track Database that Krishna mentioned in his LinkedIn post. The data is available in a neat format with the x and y coordinates in the first two columns and the left and right track widths on the other two. Currently, the only animations that I have are for a marker moving along the trajectory. I am working on adding a velocity component to that.

I will upload the code for this project on my Github repository with the appropriate comments and documentation to increase clarity.

Any feedback or suggestions are welcome!

Regards,
Gautam

[putta54]

Hi Veer,

Thanks for the positive feedback.

I actually had a meeting with my team members yesterday in which I introduced this model. They were really excited about its current capabilities. We had a lengthy discussion on different ways in which we could incorporate this model in our design process, as well as the potential improvements that can be made to it in the future.

Coming to your questions,

• This was one of the points that we talked about. Slightly modifying the force equations to include Cd and Cl coefficients to simulate aero performance would help us justify adding an aero package to our vehicle.
• Yes, it is a point mass model since load transfer or any information regarding the vehicle's heading is not accounted for.
• Definitely! It will better estimate the real scenario and help us understand the effect of different parameters like wheelbase, tire friction, and weight distribution on the overall Laptime. This paper, Optimal Velocity Profile Generation for Given Acceleration Limits; The Half-Car Model Case and the one mentioned in the velocity profile section expands upon this topic and can be used as references.
• We have access to multiple commercial software like IPG CarMaker and Vi-grade, through which we are planning to validate the test results.
• I have already done that. I was going to share the result in the original post, but I decided to reserve it for later. The main reason for the shortest path to be slower is a high degree of curvature, which caps the maximum velocity for turns resulting in a lower Lap Time. The benefit of the shorter path is largely outweighed by the higher turn velocity offered by the Minimum Curvature Path. Actually, the best path is somewhere between the shortest and min curvature trajectory. This topic is explored in the race driver model paper in the trajectory generation section and also in this paper, Searching for the Optimal Racing Line Using Genetic Algorithms.

Images
Shortest Path vs Min Curvature - Velocity Profile - Silverstone track - Lap Time of min curvature trajectory is around 14s lower than the shortest path.

I have added the code on my Github page. Please check it out and let me know if you are facing any issues.

Regards,
Gautam

[putta54]

Hi Jakeb,

Thank you for the kind words.

I will definitely try to implement your suggestion in my program. I have looked at your repo to understand your approach to creating the animations. Your code for the same seems pretty neat, and I will try to develop something similar to that.

As previously mentioned, I have uploaded the code on my Github page. Feel free to go through it and run it yourself!

Regards,
Gautam

[veeralakshendra]

Hi Gautam,

Thanks for all the answers to my questions 👍 . Glad that you have plans to validate it.

Also, thanks for sharing a few more relevant technical articles. It will help the registered students to explore different solutions to the problem.

Thanks for sharing the comparison plot. It is interesting to see the min curvature path algorithm passing over a few low-velocity regions present in the shortest path algorithm.

We are currently going through your code and approach. This week is slightly busy due to some upcoming events. Is it fine if I share my feedback by next week?

Regards,
Veer

[putta54]

Hi Veer,

I'm glad that you are satisfied with my response.

Yes, that would be fine. Until then, I will try to expand and refine my documentation and code and hopefully put up some interesting animations with it too.

Regards,
Gautam

[veeralakshendra]

Hi Gautam,

I went through your code for the min curvature and shortest path. The results obtained are perfect. 💯 .

To make the code easy for the users, I have a few comments:

• Add the Silverstone track CSV file to the folder.
• Currently, the folder doesn't have a script to call the functions. Please add a script to call the function. Check out an example below:
  
• Also, make sure to provide a reference to the GitHub repo from where you obtained the race track CSV file.
• Here is a short video to get started with Live Script: How to Use Live Scripts in MATLAB
• From the images that you shared earlier, the velocity profile seems close to that obtained in racing car competitions. However, I was unable to run the velocity profiler function as the "curvature" function is missing. Please add the same.
• Also, please make sure that the function name and file name are the same.

Above are just minor comments. We just need to make the submission user-friendly.

Once we get on a call, we will try to create a closed-loop path tracking vehicle model to track the reference velocity and racing line.

Overall, great job for testing the algorithm on F1 race circuits. 👍

Regards,
Veer

[veeralakshendra]

Hi all,

We are glad to share that we have received our first submission from Jakeb. You can find the submission here.

We have accepted the solution. Congratulation Jakeb! 🥇

Jakeb has shared the certificate on his LinkedIn account. You can check the post here.

We are looking forward to your submissions. Please let us know if you have any questions.

Regards,
Veer

[veeralakshendra]

Hi all,

I hope you are doing well.

Here is our second submission from Arthur RodriguezStatus from the University of Southampton. With his implementation, Arthur was able to reduce the lap time by 17%.

You can check out the repository here: https://github.com/Arttrm/MW_EiI_208_Trajectory_Planning_and_Tracking

Congratulations Arthur! 🥇

Regards,
Veer

[jkbchouinard]

Congrats, Arthur!

[Arttrm]

Thanks !
Sorry for not being very active on this forum.
I just discovered it at the end of my MSc project...

[Akashleena]

Hello Sir, Is the competition still open? I was trying simulink for path planning and optimization of aerial robots. I would like to share my progress and discuss with other peers to progress faster. Kind Regards Akashleena

…

On Sun, Aug 15, 2021, 10:09 veeralakshendra ***@***.***> wrote: Hi all, We are glad to share that we have received our first submission from Jakeb. You can find the submission here <https://github.com/borealis31/MW208_AUTON_RACECARS/tree/f5b26b8289c44989aab2fba4683b0a9c0830a4d5> . We accepted the solution. Congratulation Jakeb! 🥇 Jakeb has shared the certificate on his LinkedIn account. You can check the post here <https://www.linkedin.com/posts/activity-6831203106261413888-H5PO>. We are looking forward to your submissions. Please let us know if you have any questions. Regards, Veer — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#39 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AJBWXW62QXUEFC7SEDBZYBDT45AIPANCNFSM45BCBSXQ> .

[robertogl]

Hello Akashleena,

The project is still active. So, please, feel free to share your progress and ask questions here.

This is not a competition, or not yet :). However, if you use Simulink for your solution you can participate in the Simulink Student Challenge 2021 and get the chance to win up to $1,000. This is valid for all the students working on an innovative project using Simulink, but you get extra points if you pick one of the projects from this repository.

Good luck!
Roberto

[veeralakshendra]

Hi all,

Here is a detailed video from Jakeb where he explains his solution to the problem: MathWorks Excellence in Innovation Project 208: Raceline Optimization Using Discrete Mathematics

Regards,
Veer

[rakshitjangid22]

Hey everyone!
I am Rakshit Jangid, a student of Indian Institute of Technology, Indore. I, along with my teammate Pulkit Gupta, started working on this project about a month ago. We have made significant progress in the project but we are stuck at a point for last few days, generating a Velocity Profile for the optimized trajectory. We are using a dynamic Single Track model for this project. We referred https://digitalcommons.du.edu/cgi/viewcontent.cgi?article=2370&context=etd this paper but the implementation seems quite difficult. Any help would be highly appreciated.
Thanks,
Rakshit Jangid

[AakashPrabhurajK]

Hello, This is Aakash and I am a student pursuing my masters at KTH. I would like to work on the Path-Planning-for-Autonomous-Race-Car. I would like to get started with the project and would like to get some help on the same.

[veeralakshendra]

Hi Aakash,
We can surely meet and discuss more. I have sent an email with some resources.
-Veer

[AakashPrabhurajK]

Hi Veer,
Thank you for mail and reply. I look into it and start my work on it.

[Shubhg1498]

Hello everyone,

I am Shubham from Technical University of Kaiserslautern. I have started working on the ath-Planning-for-Autonomous-Race-Car project. I have already learned a lot from the discussion here and it is beneficial indeed. I look forward to collaborating and learning from you all.

Thank you!

Regards,
Shubham Ghogare

[magantijahnavi]

Could anyone please tell the abstract of the project and the datasets that can be used

[veeralakshendra]

Thanks for your interest. To keep it simple, refer to a racetrack and develop an algorithm for optimizing the raceline. Then build a simple vehicle dynamics model and generate a velocity profile. For the dataset, I am assuming you mean to say racetrack. So, you can refer to this GitHub repo to download the F1 racetracks: Race Track Database