First Position in International Micromouse Challenge

The team that I led won the International Micromouse Challenge at TechFest, IIT Bombay 2020-2021.

The objective was to design an autonomous bot simulated using ROS and Gazebo to reach from the corner square to the center of an unknown maze in the shortest time.

Our implementation in action —

Breaking down the problem

The problem was in two parts:

• Incrementally building a faithful representation of the maze walls and free space
• Minimizing the exploration phase to quickly find the optimal path to reach the maze center

Part 1: Maze Representation

In the first part, there were several details adding to the complexity:

• multiple reference frames attached to the world, the mobile robot, and our maze representation
• odometry and laser scan data were in continuous position coordinates
• conversion from the continuous position coordinates to discrete entries in our maze representation

After solving these, we dealt with the problem of noisy laser data. For this, we maintained a confidence matrix — if the same wall was seen above a threshold number of times, it would be added in the maze representation.

Part 2: Path Search and Planning

In order to deal with the lack of knowledge of the full maze in the exploration phase, we designed an online breadth-first search based planning algorithm that dynamically replanned whenever a new wall was seen and added to the modelled maze representation.

Approach to Minimize Time

The performance was timed in two phases: one exploratory phase and several final runs (best time considered). We began the exploration phase at a slower speed. Once it reached the target square, we incremented the speed by 0.03 m/s. This marked the end of exploration phase. Thereafter, each time it finished a final run, the speed was incremented. Evidently, it would reach high speeds within a few increments.

At some point, the speed would overpower the controls where it would slip and collide against the maze wall. Our algorithm routine gracefully shut down at that point. Since the best of final run times was taken, we were able to minimize it greatly while ascertaining that we definitely got the solution by starting at a slow velocity!

Acknowledgment

I am indebted to the course CS218M (Design & Analysis of Algorithms) that I took in Fall 2020 at IIT Bombay. I feel this course has fundamentally changed the way I think about problems.