Min7 Micromouse Robot Solves Maze In 3.921 Seconds

An anonymous reader writes with this note about the winner of an annual Micromouse Robot Competition, writing "The current champion is one Ng Bent Kiat, who works at the Ngee Ann Polytechnic focusing on embedded systems and robotics. His skill and knowledge in the field of robotics shows in his winning mouse robot called the Min7. Min7 is the first 4-wheeled robot Ng has created. It weighs just 90 grams and measures 10 x 7.5 x 2.5cm. It has a straight line speed of 3.5m/s and uses a 20MHz Hitachi 2633R processor for a brain. The Micromouse Robot Competition is a two-stage process. The robots first enter the maze and have a chance to map it out. They then get a second timed run where the object is to solve the maze as quickly as possible. Min7 managed to navigate the maze in just 3.921 seconds."

Comments

all mazes are solvable

[Anonymous Coward]

pick a wall. follow it. speed is only important if you don't like being in the maze - that whole "efficiency" nonsense from the calvinists.

Re:all mazes are solvable

[Maddog Batty]

Err. No.

Wall following only works if there is only one possible route to the centre without back tracking. With more than one route (as per these mazes), wall following will cause you to go around in circles and will never solve.

Re:all mazes are solvable

[tlhIngan]

A really basic algorithm (if you have the full maze map and not a partial one) is to do the flood-fill algorithm.

You start at the goal, and give it value 0. For all the cells you can reach from the goal, you give it 1. For the cells reachable by the 1 cell(s), you give them value 2. If a cell already has a number, you don't renumber it. Repeat until you end up at the beginning.

To traverse maze - At the beginning, search reachable cells for the lowest number. Keep going in by following the path with the smallest number - it'll get you there the quickest.

There are more advanced algorithms out there.

Re:all mazes are solvable

[TheRaven64]

Nope. Any two dimensional maze with a single exit can be solved by following a wall. You can prove this with some fairly basic topology. This only doesn't work if some of the paths cross over (i.e. with bridges / tunnels). Following a wall in a two-dimensional maze will never cause you to go around in circles - if it did then the maze would be topologically equivalent to a circle and there would be no path through it.

Re:all mazes are solvable

[TheRaven64]

Oh, or unless the walls are not all connected. As they aren't in the micromouse competition. Oh well. Ignore me.

Misleading Title

[Bottles]

Mouse solves maze in 1 minute and twenty odd seconds, then navigates through its stored map in three seconds. Watch the two linked videos.

Re:Misleading Title

[Forty Two Tenfold]

m i c e

Re:Misleading Title

[Yvan256]

T o u c h p a d s

Compared to what?

[Anonymous Coward]

"just 3.921 seconds" is spectacularly meaningless if no indication of the size of the maze is given.

Re:Compared to what?

[gl4ss]

there's a video.

I guess the point is that it's pretty speedy once it has made the map.

also, it skips some parts of the map(when mapping), so there's some intelligence there..

but it's not really SCI FI OH WOW WOW. surely makes a nice addition to the cv and piques interest from employers though..

Re:Compared to what?

[Rary]

In the video it appears to be about 10' x 10'.

Of course, the 3.921 seconds is how long it took to navigate the maze, not how long it took to solve it. The maze was solved in a couple of minutes, then once it had the solution mapped out, it ran through the maze in 3.921 seconds.

Re:Compared to what?

[Maddog Batty]

It is a standard Micromouse maze which has been around since the late 1970s (what do you mean you haven't heard of it?). 16 x 16 grid 180mm square.

Re:Compared to what?

[artor3]

It's extra meaningless since the robot was allowed to map out the maze ahead of time. You might as well say "robot is capable of moving at x m/s where x = length of path / 3.921 s."

Re:Compared to what?

[tlhIngan]

It's extra meaningless since the robot was allowed to map out the maze ahead of time. You might as well say "robot is capable of moving at x m/s where x = length of path / 3.921 s."

And extra hard because the faster you go, the greater chance of something mechanical slipping and you'll be crashing into walls.

It's a 16x16 cell grid, and traversing it quickly means having to move accurately within the grid and hoping your tires don't slip and make you lose your place.

Oh yeah, you have to turn, too, and turning at speed is just as fun because you can easily lose your spot that way.

Of course, this mouse is (looking at the web page) probably the 15th or 16th generation robot he's built.

Re:Compared to what?

[PMBjornerud]

It's extra meaningless since the robot was allowed to map out the maze ahead of time.

And the alternative? Introduce an element of blind luck to the competition?

Re:Compared to what?

[artor3]

The alternative is to test how fast the robots can map the maze, since that's the part that's actually interesting.

Re:Compared to what?

[NerveGas]

The mouse is familiar with most all of the maze... the maker of the bot describes his algorithm for when to accelerate and when to decelerate, it mostly comes down to "how far will I go before I have to turn?"

Re:I bet it couldn't solve the Billy Maze

[Anonymous Coward]

I bet it couldn't run the Billy Maze in six hundred seconds.

No, but I bet it could make the Kessel Run in less than 12 parsecs.

The early bird get the worm

[ISoldat53]

but the second mouse gets the cheese.

Proper branch testing

[Iamthecheese]

would have let him win a whole lot more often. His blog is all about how he lost due to bugs that could have been caught.

Re:Proper branch testing

[NerveGas]

That was something that surprised me, too... for example, he says that it ran with a known bug in the routine for traversing diagonal lines, but that this particular maze design (or maybe just that particular run) didn't "tickle" the bug.

In some areas, he takes a rather simplistic approach to handling problems - in a good way. For instance, he says that turning fast makes the mouse lose traction and slide, his answer to that is just to start the turn sooner if the mouse is moving fast.