RobotGraph

This robot is capable of finding the end of a non-cyclic line maze, calculating the shortest path from the start point to the end point, and then driving that shortest path.

Components

1. Arduino Uno
   

2. H-Bridge
   

3. Motors
   

4. LiPo Battery
   

5. TCRT5000 Sensors
   

6. LCD Screen
   

Algorithm

To solve the maze, the robot may use two algorithms:

Left Hand Rule

For this implementation, the robot always uses the left-hand rule, which means:

1. Always prefer a left turn over going straight ahead or taking a right turn.
2. Always prefer going straight over going right.

If the maze has no loops, this will always lead to the end of the maze.

Right Hand Rule

The right-hand rule is just the opposite:

1. Always prefer a right turn over going straight ahead or taking a left turn.
2. Always prefer going straight over going left.

If the maze has no loops, this will also lead to the end of the maze.

The 8 Possibilities

Given a maze, there are only 8 possible situations that the robot can encounter:

Main Algorithm

To solve the maze, the robot needs to traverse the maze twice.

First Run

• The robot will save the path in a string.
  For example: PATH = "FLLFDFRLS"
  • If the robot goes forward: PATH += "F"
  • If the robot goes left: PATH += "L"
  • If the robot goes right: PATH += "R"
  • If the robot finds a dead end: PATH += "D"
  • If the robot finishes: PATH += "S"

Second Run

• The robot calculates the shortest way after applying a graph algorithm to PATH.

Conclusion

This robot maze solver showcases the combination of hardware and algorithmic design to autonomously navigate through complex environments. With the left-hand and right-hand rules implemented, the robot demonstrates fundamental principles of maze solving and pathfinding.

Feel free to explore the repository for code, schematics, and further documentation!