Developing Efficient Algorithms for Self-Navigating Vehicles

Overview

Objectives/Goals The purpose of this study is to develop efficient algorithms for self navigating vehicles to maneuver around roads. To simulate a self driving car, I created an optimized algorithm and programmed it on a self-driving robot to navigate through different kinds of mazes. I used two other existing algorithms for comparison. Methods/Materials The two existing algorithms are the Random Algorithm and the Right-Left Algorithm, and the optimized version of the Right-Left is the Loopable Right-Left Algorithm. I spent the most time on developing the Loopable Algorithm and then blended this looped feature with the existing Right-Left Algorithm. To prove the new algorithm was superior to the two existing ones, I used 3 mazes to test the robot. The first maze contained 2 three-way intersections. The second maze with 2 four-way intersections and 1 three-way intersection. The third maze contained 3 three-way intersections, 1 four way intersection, and a loop. I placed the robot in the three mazes and ran it through 6 times for each algorithm, compiling a total of 18 data points per maze and recording the runtimes after each run. I plotted the averages and standard deviations from the runtimes to determine the optimal algorithm. Results After 6 trials, I compared the runtimes. The Loopable Right-Left Algorithm produced the best results, solving all three mazes in shortest time by completing Mazes 1, 2 and 3 in 7, 15 and 22 seconds respectively. The runner-up was the Right-Left, which produced the identical runtimes as the Loopable Right-Left for the first two mazes, but was not able to solve Maze 3. The worst algorithm of the three was the Random Algorithm, completing the three mazes in 15, 32 and 72 seconds respectively. Conclusions/Discussion The results clearly demonstrate that the Loopable Right-Left Algorithm is superior to the other two in terms of stability, efficiency and speed. After sensing four consecutive identical turns in a certain direction, the robot knows it will be stuck in a rectangular loop. To exit out of this loop, the rules are reversed, allowing the robot to successfully exit so it doesn#t follow the same path. The Right-Left Algorithm yielded similar runtimes for the first two mazes, but did not run as well as the Loopable Right-Left due to its incapability to recognize loop patterns. Finally, the Random Algorithm performed the worst, as it chooses a random direction without evaluating it.

Competition history

• CSEF 2015 Mathematics & Software · Entry J1421

Resources

• CSEF project summary ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.

Browse more like this

• All Computational Sciences projects
• CSEF Computational Sciences projects
• Every CSEF 2015 project