[ Home | Weather | Wiki | HN | News | xkcd ] [ Search | Settings | About ] [ Light | Dark ]

Micromouse: The Fastest Maze-Solving Competition on Earth [video]

---

[ Top | New | Ask | Show | Same poster | Same domain | Source site ]

Posted on Friday, May 26th 2023 by zdw

https://www.youtube.com/watch?v=ZMQbHMgK2rw

86 comments

---

[ Threaded | Oldest | Newest ]

@ Friday, May 26th 2023 by piyh The ducted fans design would allow for racing down curved pipes and recreating F-Zero GX on a smaller physical scale. I've read about these competitions before, but he goes into way more detail than I could get as a casual observer. Very enjoyable video.

@ Friday, May 26th 2023 by goalieca | Parent 3-D mazes!

@ Friday, May 26th 2023 by Taek | Parent 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.

@ Saturday, May 27th 2023 by fho | Parent Uh ... F-Zero style micro robotics would be awesome ... like slot cards without the slot.

@ Tuesday, May 30th 2023 by fennecfoxy | Parent RC Wipeout!

@ Thursday, June 1st 2023 by fho | Parent Just ... without the RC part. If you look at modern slot car racing, the cars are incredibly fast: https://www.youtube.com/watch?v=GtwkRd6zHwg I don't think a human operator could reasonably control the cars at that speed remotely. But, given the simplistic nature of the track, a µC equipped car might be able to.

@ Friday, May 26th 2023 by apienx Derek's (AKA Veritasium) doctoral thesis is in YouTube science communication. Cool video.

@ Friday, May 26th 2023 by Scalene2 | Parent One would think that would make him shy away from deceptive claims like the implication that a collision between two LEO satellites puts GPS at severe imminent risk.

@ Friday, May 26th 2023 by GloriousKoji | Parent 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).

@ Saturday, May 27th 2023 by tsumnia | Parent Is there a direct link to it? Since I regularly upload videos to YouTUbe, I'd love to see his thoughts.

@ Friday, May 26th 2023 by koromak Something about this looks unreasonably fun. I'd love to get into this.

@ Friday, May 26th 2023 by ChuckMcM This is the kind of thing that really makes robotics fun and exciting for folks. The blend of hardware and software. It is a lot of fun and the multiple disciplines make it more fun in groups than as a solo activity.

@ Friday, May 26th 2023 by robomartin | Parent >This is the kind of thing that really makes robotics fun and exciting Just in case you might not be familiar with this: https://www.firstinspires.org/ Check out the three options under "Programs". I was heavily involved with this as a mentor (FRC) many years ago. Our team went all the way up to nationals. The program is international in nature. The national championship had teams from absolutely everywhere.

@ Friday, May 26th 2023 by mhb | Parent There also was the Trinity Firefighting Robot competition which was great fun, but, sadly, seems to have been discontinued. https://trinityrobotcontest.org/

@ Friday, May 26th 2023 by ChuckMcM | Parent 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/

@ Saturday, May 27th 2023 by robomartin | Parent Yup, quite a few of our team members went on to top universities for a range of disciplines. Some are doing PhD research at places like MIT and the other top schools known for robotics and CS. I still remember teaching some of them how to drill a hole in my garage (we sometimes met there because the school simply didn't have the resources I could contribute). Heck, I taught some of the kids now doing PhD work how to program. That was always fun and deeply rewarding.

@ Friday, May 26th 2023 by iamcasen I did this competition in college, and I was obsessed! This post brings up a lot of nostalgia for me. I partnered with my EE friends, and I built the software. I devised my implementation of the flood-fill by writing VB scripts in excel spreadsheets. I would draw out the maze in the spreadsheet by coloring the cells, then I would use VBA to navigate the maze and color in the solution. Of course, the final implementation was written in C and loaded on a microcontroller. Back in those days my options were much more limited. I can only imagine what's available these days. I actually had the itch to tinker with micromouse again not too long ago, but I became dismayed with the difficulty in setting up a physical maze for the robot. I think access to the mazes themselves is the biggest limiting factor.

@ Friday, May 26th 2023 by newaccount74 | Parent >the difficulty in setting up a physical maze for the robot Couldn't you just buy a sheet of plywood, some wood strips, and a bit of wood glue? I mean, setting up a maze will take some time, sure, but it's hardly difficult. Or am I missing something?

@ Friday, May 26th 2023 by jsharf | Parent 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.

@ Friday, May 26th 2023 by lelandbatey | Parent 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-...

@ Friday, May 26th 2023 by KennyBlanken | Parent Why would you construct an entire 9 square meter maze without testing a small portion? If only for having a physically convenient way of quickly validating hardware and software changes? Why would you paint the entire thing without testing the materials, or asking the organizers what paint they use / how to validate your own maze, or asking among fellow competitors?

@ Saturday, May 27th 2023 by blopp99 | Parent Thank you for the link! Are there other resources you can share ? I'm building a database to make a local competition

@ Friday, May 26th 2023 by Frenchgeek | Parent I wonder if something like the "while True:learn()" game would allow to iterate robots rapidly...

@ Saturday, May 27th 2023 by fho | Parent There was a short demonstration on the state-of-the art of Robocup kinematics [1]. I guess the next micromouse tournaments will equally benefit from end-to-end training of the mice. [1] https://twitter.com/haarnoja/status/1651577815836270596

@ Friday, May 26th 2023 by ChrisKnott Are you allowed to push off the walls? I feel like the fastest possible mouse would be one that just punched itself from wall to wall.

@ Friday, May 26th 2023 by kllrnohj | Parent A violent uncontrolled stop like that would be hard to get your bearings for the next burst of acceleration. Also a continuous acceleration along a curve is likely going to be faster regardless.

@ Friday, May 26th 2023 by stevehawk | Parent at least right now, those mice are dependent on gyros for navigation. wall to walk combat would no doubt interfere with that

@ Friday, May 26th 2023 by Zeetah | Parent You are not allowed to touch the walls.

@ Friday, May 26th 2023 by Taek | Parent 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?

@ Friday, May 26th 2023 by mrob | Parent 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.

@ Saturday, May 27th 2023 by boredhedgehog | Parent Citation? Scratching, marking and damaging walls is not allowed. (https://ewh.ieee.org/sb/columbus/devry/sacFiles/MicromouseRu...)

@ Friday, May 26th 2023 by sdo72 I wish the idea of shortest distance isn't always the fastest or most convenient distance. I hope Google Maps can do this. I get frustrated that it keep giving shortest distance with lots of turns. Does anyone know?

@ Friday, May 26th 2023 by aidenn0 | Parent Path finding algorithms have had options to add penalty for turns for as long as I've been alive. I remember offline navigation systems allowing you to tune this (e.g. TomTom on the palm pilot, Microsoft Streets & Trips on the PC).

@ Saturday, May 27th 2023 by drivebycomment | Parent >I hope Google Maps can do this. I get frustrated that it keep giving shortest distance with lots of turns. Google Maps has been doing this for a longest time. They take freeways and signals into account, on top of the real-time traffic. Google Maps will often show multiple route options, some shortest distance, some fastest time, and nowadays "greenest" option (based on the car you picked). If you're not happy with Google Maps' initial pick of the route, you can also try alternate routes once in the navigation.

@ Saturday, May 27th 2023 by sdo72 | Parent Have you tried running Google Maps & Waze side by side in crowded area with lots of turns?

@ Friday, May 26th 2023 by Zeetah I've competed in Micromouse for years and my mouse and I appear in snippets in this video. Happy to answer questions.

@ Friday, May 26th 2023 by Taek | Parent What are some barriers to going faster?

@ Saturday, May 27th 2023 by Zeetah | Parent 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.

@ Friday, May 26th 2023 by high_priest | Parent Are the "smooth cornering" solutions, presented at the end, complex enough to apply to a full size autonomous performance car? I am thinking about pursuing this area for my diploma, but I am not sure whether I will be able to complete prototyping stage if I can't afford a full scale vehicle for it.

@ Saturday, May 27th 2023 by Zeetah | Parent 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.

@ Sunday, May 28th 2023 by Zeetah | Parent My friend, Peter Harrison pointed me to two articles on this topic: https://micromouseonline.com/micromouse-book/robot-dynamics/... https://micromouseonline.com/wp-content/uploads/2015/06/MINO...

@ Friday, May 26th 2023 by TheHappyMan | Parent If I want to watch/read more, where should I go?

@ Saturday, May 27th 2023 by blopp99 | Parent Rt

@ Saturday, May 27th 2023 by wholinator2 | Parent The Russian state controlled news channel?

@ Saturday, May 27th 2023 by Zeetah | Parent I would first read the David Otten Circuit Cellar article, then look at the UKMars repo and https://micromouseonline.com/

@ Saturday, May 27th 2023 by prng2021 | Parent What programming language do you use? Are there SDKs for interfacing with the sensors and motors?

@ Saturday, May 27th 2023 by Zeetah | Parent 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

@ Saturday, May 27th 2023 by synapse26 | Parent I guess it varies somewhat, but how much does an average competitive mouse costs?

@ Saturday, May 27th 2023 by Zeetah | Parent 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

@ Saturday, May 27th 2023 by Orangeair | Parent Did you have an prior experience with FIRST or other robotics competitions?

@ Saturday, May 27th 2023 by Zeetah | Parent 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.

@ Saturday, May 27th 2023 by blopp99 | Parent Are there a set of rules and open source base micromouse that I can take and create a competition in my country?

@ Saturday, May 27th 2023 by Zeetah | Parent 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!

@ Saturday, May 27th 2023 by oefnak | Parent Why did you not answer any questions even though it's seven hours later now?

@ Saturday, May 27th 2023 by ilyt | Parent seventeen now

@ Saturday, May 27th 2023 by blopp99 | Parent Twenty two now

@ Saturday, May 27th 2023 by Zeetah | Parent LOVE THE ENTHUSIASM! I hope you all will make some mice. I'll watch this thread for more questions.

@ Saturday, May 27th 2023 by matt-attack | Parent Perhaps I missed it in the video, but are the mice driving fully autonomously? That is, are they using vision or other sensors to detect the walls and then are they performing path planning? It all seems blazingly fast. Or is there some pre-programmed aspect to their paths? Surely it's not dead reckoning?

@ Saturday, May 27th 2023 by juliusgeo | Parent 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.

@ Saturday, May 27th 2023 by Zeetah | Parent 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.

@ Friday, June 2nd 2023 by Shroom11 | Parent Do you have to be a college student to compete?

@ Friday, May 26th 2023 by jmspring I recall we had a variation on this for a VLSI class I took in college. It taught me to how to segment knowns and unknowns around debugging - we had parts of the program we had tested, others we had not and isolated the unknowns to figure things out.

@ Friday, May 26th 2023 by alex_dev Wish I knew about this sport earlier in life; this looks awesome.

@ Saturday, May 27th 2023 by iamgopal Awesome stuff, it was because of MM, I learned all algorithm, embedded systems, sensors and noise. Also interacted with some amazing people. First love.

@ Saturday, May 27th 2023 by lwansbrough I wonder if anyone is using electrostatic solid state fans yet. Correction: the mechanism I was thinking of is membrane based air jets, like the one being developed by AirJet. I can kind of imagine a future micromouse switching instantaneously between hovering using the air jet and suctioning as it corners by swapping intake/outflow. No wheels. Fun. I can see the appeal.

@ Saturday, May 27th 2023 by russdill | Parent Flying is not permitted

@ Saturday, May 27th 2023 by xiphias2 | Parent It would be fun to see a microbird competition

@ Saturday, May 27th 2023 by boredhedgehog | Parent Citation? Flying over walls is not permitted. (https://ewh.ieee.org/sb/columbus/devry/sacFiles/MicromouseRu...)

@ Saturday, May 27th 2023 by sacnoradhq I saw a video from my alma mater about ~14 years ago. Their entrant was really damn slow, top heavy, and did backtracking. They'd be lucky if it finished it in 5 hours. I'm curious what the runtimes are by teams at various universities these days.

@ Saturday, May 27th 2023 by unwind Meta: cool, this is the most concrete case of a video being more popular than a text source I have seen (and certainly been part of involuntarily) lately. I submitted [1] 15 hours ago, after seeing this on the ole 'Tube but wanting to avoid video and boost the competition itself rather than a particular YT channel, but that tanked. [1]: https://news.ycombinator.com/item?id=36083255

@ Saturday, May 27th 2023 by FireInsight | Parent Arguably, the video provides more information, and is more entertaining.

@ Saturday, May 27th 2023 by blopp99 | Parent Why would not consider the video as a medium? I've been looking for information like the one provided on the video for a long time, and because of my ignorance and bad querys didnt have much luck, thanks to the video and this thread I've found more and enough so I can start planning local competitions. All thanks to the effor Derek did. Btw, thanks for the wikipedia link I'll read it now :)

@ Saturday, May 27th 2023 by aramachandran7 My buddy and I solved the uMouse challenge for the final project in our college robotics course in ROS, with custom path planning and speed run and all... it was such a great feeling to see the mouse complete the maze. see code / deets here: https://github.com/aramachandran7/micro_mouse_final

@ Saturday, May 27th 2023 by blopp99 | Parent Any particular reason to use ROS?

@ Saturday, May 27th 2023 by dkbrk Derek says the search strategy is "Flood Fill", but I looked and could only find that used in reference to flooding algorithms -- like for bucket fill in paint programs. On the other hand, I thought what he describes sounds a lot like A-star. Does anyone know what algorithm is used (if, indeed, as he says, everyone's converged on using the same algorithm). Is it straight A-star, some sort of incremental A-star, or something like D-star-lite (which is apparently quite popular for path planning)?

@ Saturday, May 27th 2023 by PartiallyTyped | Parent I don't think there's any heuristic involved that would make it A-star other than having an initial guess of Manhattan distance. The bot also does not consider all active paths; it only considers the shortest possible from the current state. This makes it not A* since A* considers all open. To me, this looks like running multiple iterations of Dijkstra's. You start with Manhattan distance between nodes and finish. As you go through the maze, you update the dynamics of the current node, run dijkstra's, go to shortest path from here. This also sounds a bit like IDA*, where you are also updating the heuristic as you go, but without the iterative deepening part.

@ Saturday, May 27th 2023 by Zeetah | Parent 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.

@ Sunday, May 28th 2023 by PartiallyTyped | Parent This is so cool! I'd love to get into it! Many thanks for the thoughtful reply! Question; with A*, I assumed the issue was that you needed to backtrack to a promising node which could be very far from current position. But that is based on the assumption that A* is rooted in the start of the maze. The way you described this makes the backtracking seem like a non issue. I assume it is because you were changing the root to be the current node each time. Is this correct?

@ Monday, May 29th 2023 by drekipus | Parent The issue is that A* isn't used, so the rest of your question doesn't make sense.

@ Monday, May 29th 2023 by drekipus | Parent Breadth first search is guaranteed to get you the shortest path to a goal. That's what is called flood fill.

@ Saturday, May 27th 2023 by boredhedgehog Is that extensible camera arm long enough to cartograph the whole maze? If not, a micro-drone launcher could be the next step. Apparently that would also be legal.

@ Saturday, May 27th 2023 by ColinWright I once built a micro-mouse from scratch, intending to compete. I built a Z80 based computer with 8KB RAM and 8KB ROM, programmed directly in Z80 assembler. I build the chassis from perspex and brass, turning my own spacers to hold the various boards in the right places. I used DC motors, made my own power controllers, opto-isolators, shaft encoders, IR wall distance detectors, servo steering assembly, bearings for the front wheel, ... Everything. Then the night before the competition I blew out my one and only EEPROM by plugging it into the programmer backwards. Never got to compete. But I still have Harvey[0] somewhere. I should pull him out and make a series of videos about his construction. But it was 35 years ago and the technology has changed ... I doubt anyone would be interested, especially because he never competed. But I was proud of building the computer from scratch and having it work first time, and of being able to run down my homebuilt section of "corridor" without hitting the walls. At the time no mice had run diagonally, so I really was in the running, provided it ran. Oh well. [0] No, not named after the cocktail[1], but after the smallest species of mouse in the UK. It's the "Harvest Mouse", or "Micromys minutus". [1] https://en.wikipedia.org/wiki/Harvey_Wallbanger

@ Saturday, May 27th 2023 by cookieperson | Parent Please do document this and share it. Just because you didn't get to compete doesn't mean what you did wasn't awesome

@ Saturday, May 27th 2023 by ColinWright | Parent 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 ...

@ Saturday, May 27th 2023 by blopp99 | Parent Please do!

@ Saturday, May 27th 2023 by blopp99 | Parent I wanna see Harvey! Would like to see a blog or video about it!

Search Hacker News

---

Hacker News provided by Y Combinator and Algolia.
These pages best viewed with Netscape Navigator 1.1 or later.
Privacy policy and session data management.