{"id":8762,"date":"2022-10-03T17:06:06","date_gmt":"2022-10-03T21:06:06","guid":{"rendered":"https:\/\/blogs.mathworks.com\/student-lounge\/?p=8762"},"modified":"2022-10-20T05:01:04","modified_gmt":"2022-10-20T09:01:04","slug":"path-planning-for-formula-student-driverless-cars-using-delaunay-triangulation","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/student-lounge\/2022\/10\/03\/path-planning-for-formula-student-driverless-cars-using-delaunay-triangulation\/","title":{"rendered":"Path Planning for Formula Student Driverless Cars Using Delaunay Triangulation"},"content":{"rendered":"
\r\n
In this blog, Veer Alakshendra<\/a> will show how you can develop a basic path planning algorithm for Formula Student Driverless competitions.<\/div>\r\n
Before we get started, we just want to mention that you can run this code in your browser or can download the complete live script using the buttons at the bottom right corner.<\/div>\r\n
\r\n
Table of Contents<\/span><\/div>\r\n
Introduction\r\n<\/a>What is Delaunay Triangulation?\r\n<\/a>Methodology\r\n<\/a> Step 1: Create 2-D Delaunay triangulation\r\n<\/a> Step 2: Remove exterior triangles\r\n<\/a> Step 3: Find midpoints of internal edges\r\n<\/a> Step 4: Interpolate midpoints\r\n<\/a>What next?<\/a><\/div>\r\n<\/div>\r\n

Introduction<\/h3>\r\n
Various Formula Student competitions have introduced the driverless category, where the goal for the teams is to design and build an autonomous vehicle that can compete in different disciplines. In this script, we have demonstrated the steps to plan a path through a racing track using Delaunay triangulation. The application is analogous to the first lap path planning of the Formula Student Driverless competition to plan the path through the coordinates of the detected cones.<\/div>\r\n
Please note that the Delaunay triangulation is just one of the methods for planning a path for Formula Student Driverless competitions. You can also try to develop a sampling-based planner like RRT, RRT*, etc, or any other custom algorithm that best fulfills your requirements. To develop such planners using MATLAB, please check out the functions listed on the motion planning<\/a> webpage.<\/div>\r\n
<\/div>\r\n
\"\"<\/div>\r\n
Figure 1<\/div>\r\n
<\/div>\r\n

What is Delaunay Triangulation?<\/h3>\r\n
First, let us briefly try to understand Delaunay triangulations. The fundamental property is the Delaunay criterion. The criterion says that for a set of points in 2-D, a Delaunay triangulation of these points ensures the circumcircle associated with each triangle contains no other point in its interior. In the figure below, the circumcircle associated with T2<\/span> is empty. It does not contain a point in its interior. Hence, this triangulation is a Delaunay triangulation.<\/div>\r\n
In the algorithm below, we have used this property to create a path using the detected cones as vertices.<\/div>\r\n
\"\"<\/div>\r\n
Figure 2<\/div>\r\n
Reference:<\/span> Working with Delaunay Triangulations<\/a><\/div>\r\n

<\/h4>\r\n

Methodology<\/h3>\r\n
Figure 3 shows the methodology we have implemented to plan the path through the cones. To understand the algorithm, let us go through the code.<\/div>\r\n
\"\"<\/div>\r\n
Figure 3<\/div>\r\n

Step 1: Create 2-D Delaunay triangulation<\/h4>\r\n