The Micro-Mouse

The Micro-Mouse :
We had to build a automated mobile robot which could travel to the center of a random Maze.

The Arena: It consisted of 16x16 square cells with vertical walls (as shown by the white walls). The walls had reflective coating on them to ensure sensing.

Robot Construction:
We used an 89C51 micro controller and 4 KB external RAM. It had an array of 8 IR leds and TSOPS to detect the WALLS. Two led-sensor pairs for West/South/East/North sensing (We did not front/side/back information to take care of orientation). There was a 555 astable multivibrator and a SL100 power transistor stage to drive all the LEDs at desired current and frequency(33-38 kHz). The Ext RAM and sensors were connected to the Same PORT by using a bi-dir buffer IC. There was a Regulated power supply on board for the digital circuits. The 2 uni-polar Stepper motors are controlled by a Driver Circuit(LM 293D).

Obstacle( Wall ) Detection and Error Correction: The 8 leds are driven by a astable multivibrator at 33-38kHz. This is the active operational frequency band of the TSop. When ever any of the sensors get triggered, an interrupt is generated and the micro-controller handles the interrupts as follows:
The front and back sensors are used to correct the forward-backward errors caused due to slipping of the stepper motors and due to fractional errors introduced because of the incapability of the MuC to handle fractions. We adjusted the wheel radius and the turning radius to avoid fractional distance covered per step. An interrupt is serviced only if the steps needed to complete the ongoing task (rotate/move one cell ahead) is not reached.
The left-right sensors are used to correct skew errors. If diagonally opposite sensors detect walls then the robot is rotated in such a way that the robot is aligned parallel to the side walls by continuously reading the sensors and adjusting the orientation.
Path Planning Algorithm: The robot used differential wheel movement to spin about its center. Thus within the arena, its configuration space was defined conveniently able to occupy all ROWS,COLS and tetha:
Configuration Space = {0<= ROWS <= 16 ; 0 <= COLS <= 16 ; 0 <= tetha <= 360 }.
We came up with an algorithm which resembled closely “The Flood-Fill” algorithm. This is a variant of the Dijkstra's shortest path algorithm:
The robot continuously builds the map as it encounters new obstacles. Given the constraints of the arena, from each cell the robot has two possible shortest paths to reach the center. We analyze the following situation to explain the Flood-Fill algorithm.


Summary : The fast flood fill method ensures that the robot will reach the goal in the minimum iterations. Back-tracking is taken care of by the way we number the cells while seeing a wall. But once a loop or a dead-end is visited the map and the algorithm ensures that we don’t remain in the loop or revisit the dead-end.
The Flood fill algorithm used by us has its equivalent in robot/vehicle path planning too. It is in fact a restricted version of Potential field method of reaching to a goal and to avoid obstacles on the way. Putting FF behind walls is raising its field level and numbering decreasingly from current position towards the center ensures that if we follow a cell with a lower number then we will finally avoid dead ends and reach the Minima(Goal).