Slashdot Mirror

← Back to Stories (view on slashdot.org)

Min7 Micromouse Robot Solves Maze In 3.921 Seconds

Posted by timothy on from the spurious-precision-is-always-fun dept.

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

58 comments

  1. I bet it couldn't solve the Billy Maze by tepples · · Score: 1, Funny

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

    1. Re:I bet it couldn't solve the Billy Maze by Anonymous Coward · · Score: 2, Funny

      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.

    2. Re:I bet it couldn't solve the Billy Maze by Anonymous Coward · · Score: 0

      I bet it couldn't run around Billy Mays in six hundred seconds.

    3. Re:I bet it couldn't solve the Billy Maze by Yvan256 · · Score: 1

      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?

    4. Re:I bet it couldn't solve the Billy Maze by travisco_nabisco · · Score: 1

      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.

    5. Re:I bet it couldn't solve the Billy Maze by CaptainOblivion · · Score: 1

      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.

    6. Re:I bet it couldn't solve the Billy Maze by Anonymous Coward · · Score: 0

      A parsec is 3.26 light year. So according to your theory, Hans would take over 40 years to complete the Kessel Run.

  2. all mazes are solvable by Anonymous Coward · · Score: 2, Informative

    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.

    1. Re:all mazes are solvable by Maddog+Batty · · Score: 5, Informative

      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.

      --
      wot no sig
    2. Re:all mazes are solvable by Anonymous Coward · · Score: 1

      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.

    3. Re:all mazes are solvable by jtownatpunk.net · · Score: 1

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

    4. Re:all mazes are solvable by Anonymous Coward · · Score: 0

      That only works if all the walls in the maze are connected. Take a look at the videos given in the article and you'll see that this maze was impossible to solve by following a wall.

    5. Re:all mazes are solvable by Anonymous Coward · · Score: 1

      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 :)

    6. Re:all mazes are solvable by tlhIngan · · Score: 2

      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.

    7. Re:all mazes are solvable by Ralph+Spoilsport · · Score: 1

      pick the other wall.

      --
      Shoes for Industry. Shoes for the Dead.
    8. Re:all mazes are solvable by TheRaven64 · · Score: 2

      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.

      --
      I am TheRaven on Soylent News
    9. Re:all mazes are solvable by TheRaven64 · · Score: 2

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

      --
      I am TheRaven on Soylent News
    10. Re:all mazes are solvable by troon · · Score: 1

      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.

      --
      Ydco co ,df C erb-y go. a Ekrpat t.fxrapev
  3. Misleading Title by Bottles · · Score: 5, Informative

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

    1. Re:Misleading Title by marcosdumay · · Score: 1

      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.

      --
      Rethinking email
    2. Re:Misleading Title by Forty+Two+Tenfold · · Score: 5, Informative

      m i c e

      --
      Upward mobility is a slippery slope - the higher you climb the more you show your ass.
    3. Re:Misleading Title by Yvan256 · · Score: 2, Funny

      T o u c h p a d s

    4. Re:Misleading Title by Anonymous Coward · · Score: 0

      M I C E S ... duh

    5. Re:Misleading Title by TheRaven64 · · Score: 1

      meece.

      --
      I am TheRaven on Soylent News
    6. Re:Misleading Title by Tubal-Cain · · Score: 1

      mousen

    7. Re:Misleading Title by Anonymous Coward · · Score: 0

      Feces

  4. Compared to what? by Anonymous Coward · · Score: 3, Insightful

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

    1. Re:Compared to what? by gl4ss · · Score: 4, Informative

      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..

      --
      world was created 5 seconds before this post as it is.
    2. Re:Compared to what? by Rary · · Score: 2

      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.

      --

      "You cannot simultaneously prevent and prepare for war." -- Albert Einstein

    3. Re:Compared to what? by Maddog+Batty · · Score: 3

      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.

      --
      wot no sig
    4. Re:Compared to what? by artor3 · · Score: 2

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

    5. Re:Compared to what? by Anonymous Coward · · Score: 0

      180mm square.

      Wow. It looks way bigger than that in the video. How do they even fit the mousebot into it?

    6. Re:Compared to what? by Anonymous Coward · · Score: 0

      That's what I was thinking.

      That's like saying I can get a solve a Rubik's Cube in under 10 seconds, if I was allowed to memorize the 10 turns or whatever put it into it's current position.

    7. Re:Compared to what? by tlhIngan · · Score: 3, Insightful

      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.

    8. Re:Compared to what? by Anonymous Coward · · Score: 1

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

    9. Re:Compared to what? by PMBjornerud · · Score: 3, Insightful

      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?

      --
      I lost my sig.
    10. Re:Compared to what? by artor3 · · Score: 3, Interesting

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

    11. Re:Compared to what? by perryizgr8 · · Score: 1

      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!

      --
      Wealth is the gift that keeps on giving.
    12. Re:Compared to what? by NerveGas · · Score: 2

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

      --
      Oh, you're not stuck, you're just unable to let go of the onion rings.
  5. Cool, but... by Anonymous Coward · · Score: 1

    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.

  6. Re:Ng by Anonymous Coward · · Score: 0

    Who names their child after the sounds the mother made while she was in labor?

    Someone giving birth to twins?

  7. In an other story by Anonymous Coward · · Score: 0

    The "dirty harry mouse" solved and navigated the maze in 2 seconds, what do you mean microbazookas are not accepted in the reglementation ?
    (sometimes friday afternoon falls a thursday even in secular countries.)

    1. Re:In an other story by TheRaven64 · · Score: 1

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

      --
      I am TheRaven on Soylent News
    2. Re:In an other story by Anonymous Coward · · Score: 0

      The Rules state "The mouse must negotiate the maze; it must not jump over, climb, scratch, damage or destroy the walls of the maze." However this doesn't stop the mouse jumping straight up and taking a picture :p Since 1/30 of the search time is also added as a handicap.

  8. The early bird get the worm by ISoldat53 · · Score: 3, Funny

    but the second mouse gets the cheese.

  9. Proper branch testing by Iamthecheese · · Score: 2

    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.

    --
    If video games influenced behavior the Pac Man generation would be eating pills and running away from their problems.
    1. Re:Proper branch testing by NerveGas · · Score: 2

      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.

      --
      Oh, you're not stuck, you're just unable to let go of the onion rings.
    2. Re:Proper branch testing by Anonymous Coward · · Score: 1

      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...

  10. Ngee Ann Polytechnic by Anonymous Coward · · Score: 0

    Show of hand who knew Ngee Ann Polytechnic was in Singapore? (or even heard of it?)
    Apologies to google.com for wasting their server bandwidth to find this out.

    Matthew Humphries of geek.com is also the author of a DIY amateur bomb disposal manual with similarly clear and unambiguous exposition.

  11. Misleading by Dunbal · · Score: 1

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

    --
    Seven puppies were harmed during the making of this post.
    1. Re:Misleading by oji-sama · · Score: 1

      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.

      --
      It is what it is.
  12. Re:Ng by Anonymous Coward · · Score: 0

    Your mom uttered "Anonymous Coward" when you were born?

  13. Coolest thing ive never heard of by wesleyjconnor · · Score: 1

    I know what im doing over the summer!

    --
    http://www.awfullybigmoustache.com
  14. that timing irrelevant by georgesdev · · Score: 1

    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.