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

I bet it couldn't solve the Billy Maze

[tepples]

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

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.

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

[Yvan256]

Luke Skywalker (Chris): Is it a fast ship?
Han Solo (Peter): Are you kiddin'? It's the ship that made the Kessel Run in less than 12 parsecs.
Luke Skywalker (Chris): Um, isn't a parsec a unit of distance, not time?

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

[travisco_nabisco]

Does that mean that the Kessel Run is a measure of time?

If so then running it in less than 12 parsecs may not be impressive as it would be setting the upper bound on the distance covered in a given amount of time.

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

[CaptainOblivion]

Have they explained in Star Wars canon how hyperspace works? If it's fifth dimension space folding, maybe the Falcon was able to fold space such that the Kessel Run was reduced to 12 parsecs, which were then traveled at near light speed, whereas when other ships do it they are not as efficient at folding space and thus have to travel a further distance at the same cap speed?

Or maybe I should stop throwing ideas off the top of my head.

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

[Anonymous Coward]

The micromouse mazes are designed not to be solvable by wall-hugging bots. You can foul them up fairly easily--just put a loop in the maze.

Re:all mazes are solvable

[jtownatpunk.net]

That's okay. The world needs ditch diggers, too.

Re:all mazes are solvable

[Anonymous Coward]

When you detect you're in a loop (back in the origin), you switch the wall you follow from left to right and vice versa.

You know where you're going (direction) and how far you've gone (odometer). With these you can calculate your position.

It's impressively fast, this thing. I want to build one for myself :)

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

[Ralph Spoilsport]

pick the other wall.

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.

Re:all mazes are solvable

[troon]

Imagine a giant *outline* letter Q (that is, the line in Q is the path) where the outer bit of the tail is the start and the inner bit is the finish. As you enter, following either left or right walls will take you back to the start.

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

[marcosdumay]

That is actualy how you count the time real mouses need to solve a maze. Worse yet, for real mouses you may grant several learning tries before you measure its time. Of course, that is for seeing how they memorize things, and the entire idea isn't quite valid for computers.

Re:Misleading Title

[Forty Two Tenfold]

m i c e

Re:Misleading Title

[Yvan256]

T o u c h p a d s

Re:Misleading Title

[TheRaven64]

meece.

Re:Misleading Title

[Tubal-Cain]

mousen

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?

[Anonymous Coward]

Not Meaningless. It means we're going to need a faster cat.

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?

[perryizgr8]

also, it moves diagonally thru a significant part of the maze, and it moves really fast. also, while solving the maze, it goes real fast once it thinks that its in a familiar part of the maze. very clever programming!

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?"

Cool, but...

[Anonymous Coward]

It is amazing, but I can't help but think that it was helped immensely by the maze design, the solution was only 8 turns and 3 straights that are over half the length of the maze each (one is almost the entire length.) It seems like the maze was designed for breaking records.

But, as I said, it's still amazing to see the robot zip through that fast.

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.

Re:Proper branch testing

[Anonymous Coward]

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.

Drifting: Not just for cars...

Misleading

[Dunbal]

Robot Solves Maze In 3.921 Seconds

The robots first enter the maze and have a chance to map it out.

How about "robot follows predetermined path in 3.921 seconds", since the "solving" part is obviously done between the mapping segment and the actual "race".

Re:Misleading

[oji-sama]

How about "robot follows predetermined path in 3.921 seconds", since the "solving" part is obviously done between the mapping segment and the actual "race".

You didn't watch the mapping video, did you? Seemed to me that the robot finished mapping and took the shortest route home. Obviously.

Re:In an other story

[TheRaven64]

The walls actually look pretty low. I bet you could make a mouse that could hop over them pretty easily...

Coolest thing ive never heard of

[wesleyjconnor]

I know what im doing over the summer!

that timing irrelevant

[georgesdev]

the 3.9 second timing mentioned is the speed to MOVE trough the maze once the robot has found the solution. it just means that robot has fast mechanic.
the interesting measure would be how much time it took the robot to SOLVE the maze.