To develop a maze solving micromouse with hardware integration using simulation
People Involved :
Mentors:
Members:
- Algorithm: To try out and find the best algorithm for our micromouse and simulate it in mms
- Hardware: To find the most suitable and optimal hardware for our micromouse according to the requirements and rules.
- Optimizations: If time allows, to optimize the movement of our mouse.
It involves visiting all the connected nodes of the maze one by one and explores the whole node till it reaches a dead end.
DFS.mp4
It is an algorithm for finding the shortest paths between nodes in a weighted graph, which may represent, for example, road networks.
Dijkstra.s.mp4
It is a graph traversal and pathfinding algorithm. A* achieves better performance by using heuristics to guide its search.
A-star.mp4
This algorithm calculates the manhattan distances of each cell from the center and makes the mouse move towards the smallest distance from the cell choices it has. Our mouse doesn't know about the maze wall placements at the starting, so this algorithm dynamically adapts and calculates new distances as soon as the mouse finds a new/undiscovered wall.
Floodfill.mp4
We finalised this algorithm for our micromouse as it dynamically adapts to the maze and ensures the shortest path when run for a couple of times.
Next we added return trips to the algorithm as the rules state that the mouse has to return to the start on it's own. This return trip is again utilised by our mouse to find a better path.
FloodfillReturnTrip.mp4
Once we were done with selection of an algorithm, our next step was to look out for the best hardware that we could put in our micromouse.
The microcontroller is the brain of our mouse. It carries out all the computation, hence we needed a powerful yet compact microcontroller. We compared various microcontrollers on a certain criteria.
We finalised STM32F103C8T6 for our micromouse.
Sensors are the eyes of our mouse. They help the mouse detect where the walls are and move in the center of the maze, without colliding into the wall. After much thought, we went with IR sensors and ultrasonic sensors. IR sensor:
Ultrsonic sensor:
We needed a high rpm, accurate, and compact motor. A comparison was done keeping in mind these factors.
We chose N20 metal gear motors since they are powerful and compact.
We needed a motor driver which is accurate and has a voltage range which can drive our motors.
After a detailed comparison, we locked our choice on TB6612FNG Dual H-Bridge motor driver.
An inertial measurement unit sensor was needed for the bot to know where in the maze it exactly is. Finalised IMU was MPU6050 which is a 6-axis IMU sensor.
The power source was required to provide power to all the components sufficiently. We first noted down how much power each component took. We checked the voltage requirement
and the current requirement
After comparing different power sources, we chose two 3.7V lithium ion cell.
Due to constraints in time and lack of resources, we were unable to optimize much of it performance, but we optimized floodfill to follow more straighter paths.
Floodfill_optimised.mp4
- https://github.com/mackorone/mms
- https://projects.ieeebruins.com/micromouse/
- https://youtu.be/ktn3C7aXVR0?feature=shared
- https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-greedy-algo-7/
- https://en.wikipedia.org/wiki/Dijkstra's_algorithm
- https://www.geeksforgeeks.org/flood-fill-algorithm/
- https://en.wikipedia.org/wiki/Depth-first_search
- https://www.geeksforgeeks.org/depth-first-search-or-dfs-for-a-graph/
- https://github.com/mackorone/breadth-first-search
- https://en.wikipedia.org/wiki/Breadth-first_search
- https://en.wikipedia.org/wiki/A*_search_algorithm
- https://www.geeksforgeeks.org/a-search-algorithm/
- https://youtu.be/EPDAweXxKJ4?si=ESgo3BmEeuBTNCYC