Improving RRT* Algorithm for dynamic obstacle avoidance in F1Tenth Autonomous head-to-head racing

The optimization of RRT algorithm to suit our purpose needed to be such that the code would run at a faster rate than the incoming LaserScan data from the Hokuyu 2D LIDAR data, which was at a rate of one LaserScan every 25ms.?

?The RRT* algorithm provides a much cleaner path as against the RRT algorithm. The path is not just closer to the ideal path, but is also not very random, as compared to RRT. In RRT, the path is chosen based on the existing nodes which join the robot to the target. But there is no optimization done to reduce the distance traveled.

We decided to implement a spline based RRT* algorithm for local path planning around the obstacle. As most races happen at high speed, emphasis needs to be given on improving the performance of RRT* and making it run faster, rather than making it accurate and planning long paths. We implemented the following improvements which significantly improved our performance-

1)?Goal point – Because we were planning in the local frame, we used a pure pursuit algorithm and implemented a local goal point which appeared at a set distance ahead of the ego racecar on the pure pursuit spline. Changing the look ahead and the location of this goal point was essential because the closer the local goal point was, to the ego racecar, lower the number of nodes needed to return a path. At the same time if the local goal point was too closer, it would increase the curvature of the planned path, which would make maneuvering the ego racecar difficult especially at higher speeds. A lot of tuning and testing was necessary to reach the optimal length and look ahead. In addition to this, we also implemented a multi-look ahead system. This has been separately discussed in the detailed project report.

2)?Occupancy grid – We used the occupancy grid in ROS to sample random points and hence the nodes that make up the tree. Because the path planning needs to be in the local frame of the car, and the goal point is closer, we made the occupancy grid sparse. Thus, we reduced the overall size of the occupancy grid and made the cells bigger. This reduced the cell density of occupancy grid. The occupancy grid was declared in a way so that only the region ahead of the car was covered.

3)?Sampling – Sampling the random points on occupancy grid was done using polar coordinates. Converting from local X, Y coordinates to polar R, theta allowed them to be compared with the LaserScan data from the ROS topic. This allowed to limit sampling in the forward direction in a set angle and prevented sampling outside the walls in a race environment.

4)?Number of nodes- Reducing the number of nodes meant that RRT* performed faster and consumed lesser computational resources. A perfect balance had to be maintained while tuning this parameter. If the number of nodes was reduced too much, then that affected the performance of the path planned and the paths planned in consecutive updates would switch sides around the opponent/ obstacle. This in turn is an especially bad scenario for obstacle avoidance as the wheel receives opposing odometry messages to turn and hence prevents the car from avoiding the obstacle successfully.