Micromouse Flood-fill Algorithm Mapping and Solving

The mouse uses a modified floodfill algorithm to map and solve the maze. When the mouse reaches a dead end, it does a 180 and backs up into the wall to re-calibrate its position since the turns occasionally misaligned the mouse. It uses a STM32F4 microprocessor, several IR sensors, DC motors, encoders, timers, interrupts, and a positional derivative controller.
A micromouse is a small robotic vehicle designed to navigate its way through an unknown maze. It is an autonomous, battery-operated, and self-contained robot that utilizes maze-solving algorithms to find the optimal route with the shortest run time to the center of the maze. The main challenge is to equip the electro-mechanical device with adaptive intelligence which enables the exploration of different maze configurations. In addition, the mouse must reliability navigate through the maze at accelerated speeds without crashing into the maze walls. The three main subsystems consist of the drive system, control system, and sensors. The drive system includes a mechanical chassis, a set of motors, gears, and wheels which enables the mouse to maneuver within the constraints of the maze. The control system utilizes a maze-solving algorithm based on sensor readings to calculate the fastest possible path. The final subsystem is the sensors which relays the current state of the surroundings and assists in wall detection. By combining these components, an autonomous mouse capable of navigating through a maze was designed, built, and programmed.
Github Repository:
github.com/joshuaccl/Micromouse

[@josephmk8952]

I'm a beginner and did my first micromouse last year(simple wall follower) and we often had the issue of inaccurate turns leading to the robot bumping into walls and not performing as expected, honestly when I saw the mouse backing up, which was weird at first it was a sort of eureka moment....awesome work mate. I had a few questions though, it'd be sweet you could clarify them 1)How exactly do you make the mouse go an exact amount of distance each time so accurately? Calibration? 2)In the very first prototype i made I used the wrong motors(bad torque)...Later on I used a standard small geared motor but the micromouse was extremely slow, how do we speed it up? External gears? 3)Is the arduino a good option for the micromouse's microprocessor? 4)How come your not using a motor driver, I thought they were pretty essential? Thanks for taking the time to read if you've made it till here :)

[@nathanlam7294]

Yes we initially had a simple right/left wall hugger algorithm but the competition maze was designed so that right/left wall huggers would not be able to solve the maze. Backing up to recalibrate the mouse to ensure it was in the center of the square was what we ended up doing because we realized it was a physical misalignment problem. It's been a while so I'm a little hazy on details but: 1) I believe we calibrated the encoder ticks for one square. You need an encoder to accurately move the mouse in one square increments. If you don't use an encoder you have no way of measuring the step size to move per command. Initially we based it off delays such as like sleeping for X amount of seconds but this doesn't account for acceleration. The calibrated encoder value was not 100% exact but it was good enough so that our PD controller could adjust for the slight inconsistencies. Note we had both a position controller and a speed/acceleration controller. One to ensure it doesn't hit the walls and the other to control the speed. 2) We could control the speed, faster or slower, by adjusting the voltage applied to the motor through software. This amount of voltage was determined by the PD controller. If you apply a static voltage every time you want the mouse to move, it will be off because of acceleration. 3) No don't use Arduino, you don't get far. There's tons of limitations. I recommend STM or PIC. 4) We are using a DC motor driver. I believe we had four functions that controlled left forward, left backwards, right forward, and right backward.

[@josephmk8952]

@@nathanlam7294 thank you for taking the time out to answer mate👍

[@josephmk8952]

@@nathanlam7294 I'm a complete beginner, so would you recommend going without an Arduino, cuz I have no idea how I should program an STM or to work with stuff like Gyros , accelerometer etc... Like you said ig there would be limitations, cuz most mice never use Arduino... Can working with STM, gyros etc be self taught? Can u tell me a couple of limitations of the Arduino?

[@nathanlam7294]

​@@josephmk8952 Too much to list really but the biggest reason is because there are no timers or interrupt handlers in an Arduino. Since there are no interrupt timers, there's no way to implement the PD controller and speed/acceleration. I cant think of any way to implement gyros, accelerometers, DC motors, encoders, IR sensors on an Arduino. Programming an STM is quite complicated and pretty advanced. We had two hardware guys on the team and they handled all the PCB design and schematics. Working with STM and Gyros can be self taught but its extremely difficult to learn the hardware side of it. Arduino allows you to easily get setup but I don't think it's powerful enough to be used for a Micromouse. You can take a look at the GitHub repository in the video description. In general Micromouse is a really advanced project for a beginner

[@sallyobaid7020]

who is better Arduino Nano or stm32F4 for micromouse project?

[@suricool99]

Nice video . By the way we are trying to do similar stuff. I have a doubt - how we handle the ir sensor error and Encoder based error to make bot cover 1 cell ata time and also avoid hitting the walls

[@DARSHANK-tc8xu]

can u send the parts used in your project

[@DARSHANK-tc8xu]

the components required in it plesase bro....

[@longduong7087]

Excuse me! I am newbie. Can i ask how to learn this algorithm and how to code it on microcontroller ? Do you have any tutorials or could you give me some advices ? Thanks

[@nathanlam7294]

The algorithm should be the last task in designing a micromouse. Other components such as the IR sensors for determining the position of the mouse in the maze or the encoders for motor control should be the 1st priority. Look into various types of microcontrollers such as the PIC or STM. For starters, understand IR sensors (Analog-digital converter), DC motors (Pulse width modulation), timers, interrupts, and encoders. To prevent the mouse from hitting into walls, we used a positional derivative (PD) controller. Here's the repository for the mouse. Hopefully it can point you in the right direction. github.com/joshuaccl/Micromouse Good luck!

[@pc-kn7kt]

@@nathanlam7294 thanks

[@sanketkalantre6318]

Why does it back into walls?

[@SpeedySpee]

As said in the description to re-calibrate it's position

[@nathanlam7294]

It backs into the walls because while late into the build, we did not account for friction between the wheels and the floor of the maze. In theory, the flood fill algorithm would solve the maze perfectly but when it was loaded into the mouse, the algorithm did not align with where the mouse actually was in real life. With each turn, there was slippage due to friction so over time this misalignment affected the actual pathing of the mouse. The algorithm assumed that we would have perfect 90 degree turns but in reality there was always imperfect turns.

[@JohnJohn-gy2st]

600