[HN Gopher] Micromouse: The Fastest Maze-Solving Competition on ...
___________________________________________________________________
Micromouse: The Fastest Maze-Solving Competition on Earth [video]
Author : zdw
Score : 307 points
Date : 2023-05-26 17:39 UTC (1 days ago)
(HTM) web link (www.youtube.com)
(TXT) w3m dump (www.youtube.com)
| piyh wrote:
| 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.
| fho wrote:
| Uh ... F-Zero style micro robotics would be awesome ... like
| slot cards without the slot.
| goalieca wrote:
| 3-D mazes!
| Taek wrote:
| 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.
| aramachandran7 wrote:
| 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
| blopp99 wrote:
| Any particular reason to use ROS?
| sdo72 wrote:
| 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?
| aidenn0 wrote:
| 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).
| drivebycomment wrote:
| > 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.
| sdo72 wrote:
| Have you tried running Google Maps & Waze side by side in
| crowded area with lots of turns?
| apienx wrote:
| Derek's (AKA Veritasium) doctoral thesis is in YouTube science
| communication.
|
| Cool video.
| tsumnia wrote:
| Is there a direct link to it? Since I regularly upload videos
| to YouTUbe, I'd love to see his thoughts.
| Scalene2 wrote:
| 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.
| GloriousKoji wrote:
| 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).
| Zeetah wrote:
| I've competed in Micromouse for years and my mouse and I appear
| in snippets in this video.
|
| Happy to answer questions.
| oefnak wrote:
| Why did you not answer any questions even though it's seven
| hours later now?
| ilyt wrote:
| seventeen now
| blopp99 wrote:
| Twenty two now
| Zeetah wrote:
| LOVE THE ENTHUSIASM! I hope you all will make some mice.
|
| I'll watch this thread for more questions.
| high_priest wrote:
| 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.
| Zeetah wrote:
| 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.
| prng2021 wrote:
| What programming language do you use? Are there SDKs for
| interfacing with the sensors and motors?
| Zeetah wrote:
| 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
| Taek wrote:
| What are some barriers to going faster?
| Zeetah wrote:
| 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.
| TheHappyMan wrote:
| If I want to watch/read more, where should I go?
| blopp99 wrote:
| Rt
| wholinator2 wrote:
| The Russian state controlled news channel?
| synapse26 wrote:
| I guess it varies somewhat, but how much does an average
| competitive mouse costs?
| Zeetah wrote:
| 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
| blopp99 wrote:
| Are there a set of rules and open source base micromouse that I
| can take and create a competition in my country?
| Zeetah wrote:
| 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!
| Orangeair wrote:
| Did you have an prior experience with FIRST or other robotics
| competitions?
| Zeetah wrote:
| 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.
| matt-attack wrote:
| 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?
| juliusgeo wrote:
| 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.
| lwansbrough wrote:
| 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.
| russdill wrote:
| Flying is not permitted
| [deleted]
| xiphias2 wrote:
| It would be fun to see a microbird competition
| chinaman425 wrote:
| [dead]
| boredhedgehog wrote:
| Citation? Flying _over walls_ is not permitted.
|
| (https://ewh.ieee.org/sb/columbus/devry/sacFiles/MicromouseRu
| ...)
| dkbrk wrote:
| 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)?
| PartiallyTyped wrote:
| 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.
| sacnoradhq wrote:
| 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.
| jmspring wrote:
| 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.
| ColinWright wrote:
| 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
| blopp99 wrote:
| I wanna see Harvey! Would like to see a blog or video about it!
| cookieperson wrote:
| Please do document this and share it. Just because you didn't
| get to compete doesn't mean what you did wasn't awesome
| ColinWright wrote:
| 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 ...
| blopp99 wrote:
| Please do!
| koromak wrote:
| Something about this looks unreasonably fun. I'd love to get into
| this.
| boredhedgehog wrote:
| 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.
| iamcasen wrote:
| 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.
| newaccount74 wrote:
| > 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?
| Frenchgeek wrote:
| I wonder if something like the "while True:learn()" game
| would allow to iterate robots rapidly...
| fho wrote:
| 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
| jsharf wrote:
| 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.
| lelandbatey wrote:
| 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-...
| blopp99 wrote:
| Thank you for the link! Are there other resources you can
| share ? I'm building a database to make a local competition
| KennyBlanken wrote:
| 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?
| ChuckMcM wrote:
| 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.
| robomartin wrote:
| > 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.
| ChuckMcM wrote:
| 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/
| robomartin wrote:
| 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.
| mhb wrote:
| There also was the Trinity Firefighting Robot competition
| which was great fun, but, sadly, seems to have been
| discontinued.
|
| https://trinityrobotcontest.org/
| ChrisKnott wrote:
| 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.
| stevehawk wrote:
| at least right now, those mice are dependent on gyros for
| navigation. wall to walk combat would no doubt interfere with
| that
| Zeetah wrote:
| You are not allowed to touch the walls.
| mrob wrote:
| 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.
| Taek wrote:
| 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?
| boredhedgehog wrote:
| Citation? Scratching, marking and damaging walls is not
| allowed.
|
| (https://ewh.ieee.org/sb/columbus/devry/sacFiles/MicromouseRu
| ...)
| kllrnohj wrote:
| 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.
| unwind wrote:
| 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
| blopp99 wrote:
| 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 :)
| FireInsight wrote:
| Arguably, the video provides more information, and is more
| entertaining.
| alex_dev wrote:
| Wish I knew about this sport earlier in life; this looks awesome.
| [deleted]
| iamgopal wrote:
| Awesome stuff, it was because of MM, I learned all algorithm,
| embedded systems, sensors and noise. Also interacted with some
| amazing people. First love.
___________________________________________________________________
(page generated 2023-05-27 23:02 UTC)