Micromouse: The fastest maze-solving competition [video]

That's very kind, and you've made me start to think about it seriously.

I'd have to find him first, of course. And find some space to lay out the pieces to photograph.

Hmm ...

This eventually evolves into a controls problem i.e. reading the sensors and then driving the motors and keeping the mouse in control.

With the use of a fan, the limit is now how much down force can you generate and then can you drive the wheels to take advantage of that. And then how much time do you have to maximize this loop.

I think autonomous performance cars are using different but related techniques. I am not close enough to what the autonomous performance cars are doing to say where things are in terms of the state of the art but I think there is opportunity.

For Micromouse, there are several methods people use. One is to create a trapezoidal angular velocity profile while holding the forward speed constant. The trapezoidal profile parameters are determined through iterative simulation.

Another approach - the one I use - uses cubic spirals which is described in: Smooth Local Path Planning for Autonomous Vehicles by Yutaka Kanayama and Bruce I. Hartman. What is amazing about this technique is that it is closed form, is like four or five multiply and adds and executes in trivial time on (even) an 8-bit processor. For my latest entry, I have a more sophisticated scheme where I try to maximize the load on the tires and the lateral and longitudinal loads are asymmetric.

In this article: http://www.dtweed.com/circuitcellar/xottenda.htm#183 - David Otten describes a scheme where he controls the rotational velocity such that the load on the tires is maximised.

I think you can get very far with simulations and then trying it on a RC car and then on a real car.

A few years back, there was some amazing work that was done at Stanford where they developed tire models and a controller that could handle sliding modes.

I encourage you to explore because if nothing else, you will learn.

Rt

I would first read the David Otten Circuit Cellar article, then look at the UKMars repo and https://micromouseonline.com/

I use C. I write all the code from bare metal i.e. no OS and I write my own routines to initialize and use the hardware.

I could use the routines that the MCU manufacturer provides but when I've tried, I've found that I spend a large amount of time understanding the API and what they are doing and writing the drivers myself is faster.

Take a look at this code base: https://github.com/ukmars/ukmarsbot

Depends on where you draw the line.

I think one can be made for under $50 USD.

MCU: $5 PCB: $5 Sensors: $8 Motor driver: $3 Battery: $5 Misc. electrical components: $5 Motors: $4 3D printed parts: $15

I did not.

Funny story - I was in college and the IEEE chapter was having a meeting with free pizza. I went to the meeting but went into the wrong room and in that room they were having the Robotics club meeting. I was intrigued enough to sit through it and wanted to do this. One of the the presenters said that no one had yet made a working mouse at our college. I was determined that I would be on the team that was the first. And we were!

FIRST is a fine competition.

Absolutely.

Please take a look at the repos at:

https://github.com/ukmars

https://github.com/ukmars/ukmarsbot <- this mouse was shown in the Veritasium video. It is exceptionally low cost and easy to assemble, source parts for and there is enough code in the repo to make good progress.

I hope you do this!

seventeen now

There was a very brief mention in the video, but this link goes into more detail: https://micromouseonline.com/micromouse-book/rules/. The score of each run factors in 1/30th of the time spent to search. There is a separate period where the mouse can search, and then it goes through the maze at high speed using the route it planned prior. Obviously if you spend a massive amount of time searching, that will impact your score but it seems to prioritize the later, faster runs in terms of scoring.

The mouse is fully autonomous. At the start, the mouse only knows that the coordinates of the goal and that the goal is some combination of to the right and front of the start square.

Currently mice use reflective infrared sensors. The reflected infrared light is used to estimate the distance. Based on this reading, one can determine the position of the mouse and the presence/absence of the wall. This information is used to create a maze map and to navigate.

The Circuit Cellar article mentioned in this thread is an awesome comprehensive introduction to micromouse.

They need to be dimensioned and finished quite accurately. Most plywood has a slight bend to it. At the speeds and accelerations needed to be competitive, any imperfection would mean your car will fly off the track or hit a wall.

Yes you can build your own, but it's tougher to get right than you might think. Those tiny robots are incredibly sensitive to the conditions of the maze, and you can get things wrong quite easily. You could build the whole thing to all the millimeter tolerances, then learn that oh no, your white paint actually has some undisclosed additives that absorb IR light instead of reflecting it, meaning you have to complete re-paint and re-sand all the walls in your 9-square-meter maze. Oops.

You can do it, but it's still quite tough; in many ways tougher and less fun than building the mouse.

Link to some helpful notes on building your own Micromouse maze: https://micromouseonline.com/micromouse-book/mazes-and-maze-...

I wonder if something like the "while True:learn()" game would allow to iterate robots rapidly...

There also was the Trinity Firefighting Robot competition which was great fun, but, sadly, seems to have been discontinued.

https://trinityrobotcontest.org/

Did I mention I was the President of the Homebrew Robotics Club[1] for 10 years? :-) That said, FIRST is excellent and I mentored the Fremont HS team one year.

One of my favorite thing about robotics is when people go from something in software to something that is actually built. Sensors are "noisy" in the real world, and HBRC has a great series of challenges that are designed to get people to actually build robots (and for that they need to span the easily grasped to the more complex). A number of kids that came to the club when I was running the meetings went on to top engineering schools, always gratifying to see them take off like that.

[1] https://www.hbrobotics.org/

[2] https://www.hbrobotics.org/index.php/challenges/

Fun to think how the rules could change if you made the maze 3D. Now jumping is allowed. Flying as well? Touching walls? Cameras can't necessarily see the whole maze anymore either.

RC Wipeout!

It would be fun to see a microbird competition

Citation? Flying over walls is not permitted.

(https://ewh.ieee.org/sb/columbus/devry/sacFiles/MicromouseRu...)

His thesis was something along the lines of you let people guess the incorrect answer first and then show how it's wrong the lesson will stick better. This was very apparent and great with his earlier works (eg. teaching gravity and letting people guess heavier objects fall faster) but got obnoxious when youtube revised their algorithm and he went full click bait and controversy (eg. modelling electricity as water is wrong).

Have there been thoughts to adjust the rules or make a parallel format that increases the amount if opportunity that competitors have to get creative?

No mention of this in the UK rule set at least:

https://ukmars.org/contests/contest-rules/micromouse-classic...

And even if you're not pushing off from the walls, additional wheels on the sides of the mouse could help get more traction by running along the walls.

Citation? Scratching, marking and damaging walls is not allowed.

(https://ewh.ieee.org/sb/columbus/devry/sacFiles/MicromouseRu...)

Many of us have tried A* but because the maze is so "small" (16x16 or 32x32), the "just solve it every time" using Dijkstra's or a flood fill or similar algorithm wins out.

In particular, in A*, the "to be explored" queue has to be kept sorted. This sorting dominates the compute time.

For example, using the "flood fill" method on an 8-bit processor, depending on the state of the maze, it took less than 3milliseconds (hand optimized assembly) to solve a maze. On a Cortex M4, with decently thought through maze representation, but not optimized beyond that, it takes under 1.5milliseconds. This is in the "don't need to bother" category.

This is a great article to start from: https://dl.acm.org/doi/10.5555/26011.26020

PDF version of this can be found online.

What we have done is extended it to be time based rather than distance based i.e. we take into account the motion parameters - acceleration, maximum speed on the straight and through different turns, distance and use that together to generate a cost table and then use the cost table to generate the fastest path.

Have you tried running Google Maps & Waze side by side in crowded area with lots of turns?