Back in college, I was part of the robotics club. We built robots and tested our skills at various collegiate competitions. 'Techfest', held at IIT Bombay was one such competition. At the 'International Robotics Challenge' event, the robots were tasked with solving a maze.
The maze was a walled maze with an open area in the centre, marking the endpoint. The aim of the robots was to first traverse the entire maze and store it. Then in the next run, their time to reach the end would be measured. So, the robots were expected to calculate the shortest path from the first try and reach the destination as quickly as possible. For developing the bot, we split its tasks into two major areas : Traversing the maze, and Solving the maze
Traversing the maze
For the hardware of the robot, we used Arduino Nano, a compact and cheap devkit, used for implementing rudimentary concepts of robotics.
For travelling, the robot was built with a 2-wheel chassis with a castor wheel at the front for turning. To traverse the maze, we made the robot capable of echo-location. The HC-SR04 echo sensors were used for detecting the surrounding of the robot. 3 sensors, mounted on the front and sides of the robot would help it sense its surroundings.
The concept of control systems ion robotics is based on the fact that real world scenarios play out vastly different to ideal scenarios, calculated in ideal contitions. To counteract such 'glitches', control systems are implemented. In our case, glitches in sensors and movement of motors were the factors that would cause the bot to steer off. To counteract, an algorithm was implemented to make sure the robot mantained a set distance from its surrounding walls and correct itself. The algorithm was conceptually similar to the PID controllers used in industry. With this, we made sure the bot never crashed into surrounding walls.
Solving the maze
To work with the limited memory of AtMega16 microcontroller on the Arduino Nano, to store a maze, was a challenge. Dijkstra's and A* algorithms were goodd options for a simple shortest path task, but implementing them while also handling inputs from three echo sensors was tedious for the controller. To tackle this, we implemented a greedy algorithm, that would give an efficient path as opposed to the optimal path, with the trade-off of being less resource intensive. The maze was stored in a 2 dimentional matrix in the dry run and at the same time the algorithm would delete paths that had a dead-end.
Here, we can see, the bot executes the dry run first and then the main run. In the dry run, its travels through the maze and stores the path as it goes. Then, in the main run, it ignores the path that had a dead-end and went right. This is how we, a team of 2, implemented a maze solving robot.