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".
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.
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.
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.
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 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.
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.
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?
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.
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.
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!
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.
> 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?
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.
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?
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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).
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.
Awesome stuff, it was because of MM, I learned all algorithm, embedded systems, sensors and noise. Also interacted with some amazing people. First love.
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.
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.
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)?
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.
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.
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.
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?
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.
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.
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 :)
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.
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.
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?
> 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.
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).
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