This is the official repository for the Micromouse project at IvLabs, VNIT Nagpur
The objectives of the summer internship were to create a compact( 8 x 8 cm) robot that can autonomously solve and obtain the fastest path for any given maze.
In the initial weeks, we worked on implementing the maze solving algorithms in python. We implemented and explored a set of algorithms, namely
1.Wall Following:
The bot just follows the walls till it reaches the
goal. Not very efficient as it is a brute force approach and can run into loops
when there are dead ends and for this algorithm to work, the goal has to be in one of the corners .
=100x200
2.BFS: Breadth First Search systematically examines all available nodes at a given level before delving deeper into the tree or graph structure or in this case, the maze.
3.DFS: Depth First Search, on the other hand, delves as deeply as possible into a branch of nodes before backtracking to explore other branches.
4.Flood Fill
Code for each of the above mentioned algorithms can be found in Algorithmic Implementations Folder.
After this, we built a maze using corrugated sheets ,The dimensions used were 16 x 16 cell.The maze consists of plus shaped holders that can be used to hold two or more sheets according to requirements. Subsequently initiated work on hardware components, which involved tasks such as testing sensors and assembling the necessary equipment.
The detailed hardware breakdown is mentioned below.
We went with using sensor data for precise turning, and we were able to solve the maze. Testing included 5 different mazes.
Image of the final bot:
Here is a both high level and low level diagram for understanding of the hardware implementation
The circuit overall is controlled by the Arduino nano.
The code for movement and speed control as well for maintaining a particular distance from the wall is uploaded in the Arduino nano. It analyzes the data sent by the motor encoders and calculates the distance covered accordingly.
It also reads the data from all the three ultrasonic sensors and gives output to the motor so that the bot maintains a particular distance from the wall.
The motor driver receives the input from the Arduino nano and accordingly supplies the signal to the motor so that the motor can perform the required movement.
The circuit drives its power from a 7.4V LiPo batttery.
The connections of the circuit are as shown in the circuit digram above.
Since the initial simulations were in python, we had to create data structures for the maze map and directions. We implemented flood fill as the final algorithm as it was the fastest comparitively and gave good results.
How it works: The flood fill is an optimistic search algorithm that can help in solving mazes, it simulates water flooding a maze and reaching the goal and thus the name.
It initially assumes that there are no walls and generates a first maze map using bfs/dfs. A maze map considers the goal as 0 and each preceding cell has value one more than the earlier cell.
Example : current_cell.value() = previous_cell.value()+1 ;
Flood fill video:
The mouse then runs once to generate a maze map according to intial run. It then backtracks using a different path and then decides the shortest path based on these two runs.
Link to extensive breakdown of code: https://hackmd.io/@l_WDq7lkQq29Pz-KD1JPNA/HkYDExRTh
Download the arudino ide and run the files.
For simulation:
pip install pyamaze
Then you are good to go