Optimal Maze Storage & Safe Speed Runs in Micromouse Robotics

[00:00:06]so you probably thought by now that we had done everything we needed to ever do about solving the maze and working out an appropriate path and stuff like that and earlier this year i was messing around with some code and scribbled down some notes and suddenly realized that actually no there is yet still a better way so that's really what today is about it's about improving the the way that you store and use the maze information um to drive your mouse and uh i thought i'd look for a nice quote and unbelievably gk chesterton had something to say about it now i have not seen them at contests but i'm you know living hope so let's just review the problem i understand that you should all know about the problem but um for the sake of anybody coming later and watching a recording um let's just cover some details so we won't look at the maze itself but consider that every maze must have a start and a goal the goal may be an individual cell or it may be a block of cells but for the sake of this um work today we'll consider the goal to be a single cell and you need a path from a given location to a target and i distinguish between them because of course the current mouse location might be the start of the path that you need and the target may be the start cell or it may be a goal cell or it may be some other arbitrary cell in the maze that you want to visit and what you want your code to do is to find an optimum path to go from start to goal eventually or from location to target on a kind of minute to minute basis second to second of course if your performance is up and the most important thing about this path is that it must be safe to run at speed we've talked quite a lot about how to find a path and how to get to the goal and all that kind of thing but we haven't really given much thought i think to how to guarantee that that path that you want to run is safe and doesn't go through unvisited cells or unseen walls or anything like that and that's actually slightly more tricky than it may at first appear and of course time is limited um you really want all this done quite quickly ideally you would like to be able to solve the maze and generate the path in the time it takes for the mouse to get from you know well certainly from one cell to the next but maybe in the time it takes for the mouse to move 10 or 20 uh millimeters i spoke once to a contestant in in japan about how he generated his final pass and he used a variant of dijkstra's algorithm on a half size maze 32 by 32 and i asked him how long it took for his algorithm to run and he said 17 seconds which was a little upsetting his rationale was that by the time it was running it by the time the mouse ran its way back it had worked out how to get to the goal again um and he acknowledged that it could be improved so when we store details about the maze and i understand that there are other ways to do this but the most common way is to use a little bit map and although we duplicate walls doing it this way it makes the code an awful lot simpler right you can you can pack it down to one bit per wall and no duplications and that's all very clever but even the arduino has enough resources not to need to do that and your code is faster and simpler to understand if you don't so we would typically have one byte per cell and we'd mark out one bit per wall direction my convention is to number them like this so that the north wall is bit zero and so forth and then we can in any given cell we can describe the walls um as a simple single byte value binary 1110 or e is what you'd see in the start cell right so you've got a west a south and an east wall and nothing to the north and the corresponding cell above which in my method is cell one would have a wall to the west only so it would have a value of one zero zero zero or eight in hex but my aim really is to keep this as simple as possible there's just no point in making life more complicated than you need to usually so when you start off you need to set all of the walls as being absent add known walls for the perimeter and known walls for the start cell because not everybody does that they just zap all walls in some cases but since you know there should be walls around the perimeter it seems sensible to me to mark them in to save you running off the edge of the world in your software so i always mark them in for me the start cell is zero and the and i use a single goal cell for the algorithm which for a classic maze would be seven seven or eight eight um and by seven seven i mean seven cells across and eight cells up so it's an x y coordinate and we set the robot target to the goal so far so good how does the mouse explore well it has to move from cell cell to cell every time it encounters a new cell those the walls must be added to the map and something which is often um overlooked for me at least walls never get removed they're only added you see a gap you don't say oh there used to be a wall but now there isn't right it's simpler to just always add them in and then that obviously leads to the um frequent claim that you hear a contest of oh no it's putting a wall that shouldn't be there and then bangs into it and that's that nonetheless that's the rule at every step of the explore planning is optimistic that is to say any decision you make about getting to the goal and passing through cells that you don't know anything about your assumption is always that you can do that and then as you get into those unknown cells you discover that's not right and so off you drop in some other direction but optimistic path planning is how you do the exploration there's there really isn't anything else you can do now the problem is that when you get to the goal you've gone by some roundabout route which depends on what you discovered as you were doing it and your route that you have taken is very unlikely to be optimal it may not even be very good and more importantly it's unsafe right so if you just drive to the goal have a look at what you know about the maze and then make a map and make a route that route almost certainly goes through cells which are dangerous that is to say you don't know what's going on in them so this is where it gets slightly harder to see and my apologies if you're sat out in sunshine with a tiny laptop but you know what can i do um this maze is how we start and if you can see the characters on there uh if there's a problem tell me and i'll wiggle the mouse around and try and point stuff out but the m is the mouse position bottom left or old david squinting in the sunlight now the x's represent the path going through unexplored cells and the g is the goal all right so off we set and after making a few moves the mouse has discovered some walls it's recalculated a new path to the goal and this path is still optimistic you can see that from the start to the current mouse mouth mouse position there's some little um kind of arrows which indicate the direction that you would take in each cell but still the x's say this is my best guess of how to get to the goal but i know that those cells are not safe so one single step of exploration onwards which will move the mouse north into the the cell just above and you discover two walls and all of a sudden everything's gone crazy the optimal route or or rather the route that you think should exist between start and goal still goes through a whole pile of unexplored cells but now your mouse is in some kind of hinterland where um it doesn't really know what's around it except for the cells that it's seen so what what move is it likely to make next well if you wish at this point you could go back and find the first of those unexplored cells and set out again but that's a waste of time so what people do as a rule is they just carry on right they they plot a path from where they are and the mouse will move to the west um and then carry on and what i've arranged for in this simulation is to always show the current best route from start to goal not the route that the mouse is going to take now but the best route from start to goal so after an awful lot of messing about and discovering walls and turning back and all of the other stuff that they do finally after 127 steps in this particular maze the mouse has found the goal uh this maze by the way um if you care is the japan 2007 expert finals maze it's just my my standard practicing with algorithms maze now clearly at this point the mouse is able to find a way to the goal right it's there so there must be a path right but if you just take your standard algorithm uh it's a simple one in this case it's just a you know a kind of stepwise one cost increases one percent if you take your standard algorithm and try and work out what should be the best route you can see that even now that path goes through an awful lot of unexplored cells so let's say that you crashed at this point and you had to pick the mouse up put it back at the beginning and set it off again you couldn't do a speed run because your best guess at the path the correct path goes through a whole pile of unexplored cells you've got no idea what's there the only thing you can do at this point is to explore some more um and then the question is how do you know when you've actually got an optimal route one which you can safely run at speed without having to check the walls every single time if you don't crash what you will do is you will generally speaking simply change the mouse's target to the start cell and explore some more and in this particular maze with this particular algorithm it takes us a total of 207 steps to get back to the start right so we've explored out we've explored back we've discovered different cells on the way back and you can see that the mouse has wandered around at the top of the screen there found a whole pile of walls but still it does not have a path which is safe to run at speed now there are other strategies you can you can use at this point some people choose to do a run now with an algorithm that only uses explored cells uh you know after all there must be a route and it probably is better than the one you first used so you could choose to get a speed run in now so that you can get some points before you eventually crash or whatever your problem might be alternatively you can carry on exploring back and forth from start to goal until you think you actually do have an optimal route it takes in this maze for this algorithm a further 160 steps to go out and back and you still have a non-optimal route to keep going back and forth until you get an optimal route takes 317 steps in total which is an awful lot of wandering about right and this is where you know in the days where you got penalized for your searching method you'd have just no point doing a speed run now you might just as well pack up and go home it's taking you so long to find an ideal route that you can't possibly you you could you know teleport yourself and still not get a decent score but there is now finally a route the mouse in this hour in this demonstration the mouse has stopped at the cell in which it finally worked out that it had an optimal ring so now is the how does it know how can you tell that this is an optimal route i haven't marked on any of those cells which are not explored but if you have a look in the kind of uh lower leftish area you can see there's a whole bunch of places where the mouse clearly hasn't been because it hasn't put in any walls right so how does it know that there's not some faster way through there how do you how can you tell that you have finished and got an optimal route well there are several techniques one is to have an extra bit in your bitmap and just every time you've marked a cell you every time you visit a cell you set that bit then you can tell your path generation algorithm only go to cells where that bit is set and this will make you a safe path so you can choose to either flood all of the cells and then make the path generator only use visited cells or you may choose to use a different variation on the flood where the flood only allows you to to actually mark visited cells either way these are these are special cases right you've already got an algorithm that does this and now you have to do something different you have to add an extra rule that says only go into visited cells either for the path or for the flood uh it's simple uh it's reasonably straightforward but it you know it complicates the algorithm slightly and you have to be a little bit careful uh about what's going on an alternative is to add an extra flag for each wall so we've still got the four bits for the walls and then we have another four bits which say i have definitely seen that wall or space as the case may be right so you've not taken up any more storage you have made life more complicated in terms of software but now better than individually visited cells you can now say i want to know if my path goes through this particular wall whether or not it's really there or whether it's really a gap this is the method that decimus has been using for a while it works very well but it is a bit of a pain the code looks unpleasant it's all full of you know tests for how do you know if a wall is there or really there or really not there or just not seen yet and it works well but the code's just kind of scruffy so now having reviewed all that onto the easy eye anybody before i do that has anybody got any questions or issues with stuff so far no okay so a different way of looking at it is to consider that that you record two mazes an open maze and a closed maze the open maze begins with no walls in it at all except of course for the boundary whenever you find a wall you add it to the open maze so the open maze gradually gets more and more walls as the explore goes on note that the open maze always always has a path to the goal if there is one it's optimistic the closed maze starts off with all of the walls filled in except you know the one just to the north of the start cell every single wall is present and as you discover gaps you add the gaps to the closed maze now at the start obviously there is no way to get from start to goal through the closed maze everything's got walls in the way when you finally get to the goal you can use the closed maze to plot your path because once the goal has been found that closed maze is always safe to run and this is a really really important point right the open maze is optimistic and always unsafe until you've found an optimal route but the closed maze is always always safe to run through so let's have a look at how that works we've got our own maze on the left and our closed maze on the right and this is the initialization this is the same maze as before it's the japan maze and you can see the open maze has no walls to close my house all walls except for the start cell so we'll go and explore to that first place that i stopped before and now you can see that the open maze has got some extra walls added and a closed maze has got some extra gaps added carry on until we find the goal and now you can see the use of the closed maze whilst the open maze has this optimistic path that goes through unexplored cells the closed maze you could if you picked your mouse up and brought it back to the beginning you could do a speed run now it may not be terribly fast speed run but you could do one as long as you use the closed maze and at any time you can run through the closed maze there are plenty of practical contest mazes where by the time you got to the goal you may very well have found a nearly optimal route anywhere and you might just as well try and run it and under the old rules with the search time ben penalty sometimes that was a good strategy it was a good strategy for a lot of apec mazes go to the goal come back and immediately run with what you've got but you do need to have a safe path so we do a bit more exploring um uh oh i should say at the bottom left there you can see the open cost if you can read that 54 that's the number of cells taken to traverse the maze with an optimistic unsafe path when we finally got our optimal path again you can see that the open cost has gone up and that the path in the open maze and the path in the closed maze should be the same and although i haven't put it in in this uh demonstration the cost in the open maze and the cost in the closed maze that is the number of cells is the same in both cases that is how you know you've finished when the cost in the open maze is the same as the cost in the closed maze you have an optimal path so you have to flood it twice right but because the flooding is simpler and was never hard in the first place that's not a terribly big deal it's much easier than going through and checking all the walls all the rest of it you've got to flood it to do that anyway so you might just as well do it twice with a simple case when the cost is the same the exploration's done right so to recap you explore using the open maze that always gives you an optimistic path to the goal but those paths are unsafe at any point after you have found the goal you can use the closed maze to do a speedrun they are always safe also closed paths will improve over time as you do more exploration and so at any given time during your searching of the maze the path through the closed maze is optimal and improve optimal at you know up to that minute and improves as you carry on and when they're the same the whole thing is done does anybody actually already do this no no okay so um how are we going to implement that on the face of it it's a problem now because you you've got to have it store two mazes right on open maze and close maze and that's what i did for ages um until my little epiphany if you store two mazes then you have to pass a pointer to the maze right you can have a single piece of code which will operate on any maze but you have to tell the code which major you're going to operate on which is just a pointer right but it's still a pain um and you don't really want the extra um messing around the de-referencing of pointers and all that sort of stuff you can do without so what can we do instead well we had these four spare bits right we only needed four bits to store the walls in a cell we can use the other four bits to store the other maze so the lower four bits are the open maze and the upper four bits are the closed maze so a completely unexplored cell will have the value of the starting value f 0 1 1 1 1 0 0 0 0 if i've not lost count so it'll have all walls in the closed maze nothing in the open maze nice and straightforward if at any point i want to have a look at the walls in a maze i can choose the closed maze or the open maze by simply shifting the contents down four bits or not shifting them and if that number is a constant i always do the shift right in the code i always do the shift and if that constant happens to have the current value of 4 i'm looking at the closed maze if it happens to have the value of 0 i'm looking at the open maze right so my code is always the same and there's just some global constant somewhere which says whether i'm currently looking at the open maze or the closed maze and this is now true for all of the maze flooding and all of the path generation i select the maze simply by changing a constant value from zero to four and nothing else changes in the code and since a bit shift is usually a fairly efficient operation it doesn't make them much in the way of performance difference either so if i had given my directions numbers north of zero east is one south is two and west is three and so forth if i wish i can have a look at an individual wall with a bit mask i can say one shifted left south right there's a one shifted left two bits and if i just do that i'm looking at the south wall of the open maze if i do it if i shift it left south plus four then i'm looking at the closed maze and again if if that four is a constant so it's one shifted left south plus maze type let's say and maze type happens to have the value zero then it's the open maze if maze type happens to have the value four then it's the closed base so again the code is the same just as one number changes in my code if i want to test for an exit um i can write a function to do this um this is pseudo code don't copy this into anything it won't work so i can i can have a function called has exit and i give it the cell that i'm interested in the direction i'm looking on what maze type i'm using and then away we go right so i just i create my bit mask and it with the current contents of the map and if that's a zero i've got an exit it honestly it just it could not be simpler i suspect i hope i think now what are we going to do to flood the maze using this technique well we'll start off with some kind of function called flood maze because that sounds reasonable and we're going to give it a target cell and a maze type which again zero for the open maze four for the closed maze first thing to do is to initialize the whole of the costs array um that's just another 256 bytes for a classic maze to some maximum value 255 is convenient or whatever the maximum integer unsigned integer is that you can store in there we set the cost of the target to be zero when we add that target cell not the value but the actual you know the address of the cell we shoved that in a queue then we processed the queue right there's one cell in it so we take this cell out from the queue and that's where we are looking at now we work out what the cost is for the neighboring cells and if we're just using a simple manhattan flood the cost will be one more than whatever was in that cell and then we just run around all four directions and for each of those directions we say if there's an exit in that direction and we've already seen this is a trivially simple function if there's an exit in that direction what are we going to do we find out this so there's just a neighbor calculation so you know the cell to the north or the east or the west that function will be dependent on how you store the maze derricks stores in a different order to the way i store mine for example so you work out what the neighbor address is and then we say if the neighboring cell looks more expensive than our current next cast we just replace it and then we add that cell to the queue and that's it done all right it'll loop back round as long as there's any cells left we haven't finished and when we've taken all of the cells out of the queue the job's done and this code is just has just been anonymized from a c function which is exactly the same and it wouldn't be much harder in any other language really as long as you've got a queue available um and you can write the other functions it's really quite straightforward i think so a couple of extra thoughts it's very easy when dealing with the maze to think in terms of the walls but actually the the mouse isn't interested in the walls actually it's interested in the exits it actually wants to see the gaps right it can only drive through the gaps there's no point in knowing about the walls you have to know about the gaps but you have to know that they're real if you care about whether or not a cell has been visited um and this is your homework right you can this is left as an exercise to the reader if the open cell data and the closed cell data is the same you have seen that cell and you need not actually have been in it you could have circumnavigated it and discovered that information and it will still work and that means that there is a circumstance under which a safe path can still go through an unexplored maze so this is the qualifier from japan 2007 and after all of the exploring is done you can see the little yellow splash there is where the safe path goes through a cell which has not actually been visited but it will still be safe because we have seen those two gaps we don't care about the walls we've seen the gaps that's it okay thank you peter questions i guess first for peter i've got i've got one yeah robert have you considered heuristics while you were talking i wrote down four heuristics uh do you wanna know what the hell if you would have thought about them um well at the moment explain what you mean by a heuristic for this right so obviously if you know you've got you've explored enough cells to know you've definitely got the the shortest path now you're talking about you might decide to run a do a speed run for instance uh ahead of that so for instance if your close cost is approaching your open cost maybe it's good enough to the speed run yes that's sorry just to stop you there because rather than deal them all at once uh yes um my current code um does or has something very similar to that and it says bearing in mind that i use a different and more complicated flooding method right because i want to take into account how long it takes to traverse straights and that kind of stuff but bearing all that in mind my current code says if the safe cost is close enough to the unsafe cost there's no point in wasting time trying to improve it right i care less on the japanese rules but under apec and former uk rules i certainly would say if it looks like i'm only going to get you know a five percent improvement in runtime do i really want to be spending the next five days trying to find it it's not just i mean there's a risk every cell you visit the risk of crashing even at slow speeds how do you i'm sorry peter i know your back lights are perfect yeah yes you're right the longer you carry on the more your chance of something going horribly wrong so there's yes so the other ones i've written down were uh if you're taking too much time i mean if you've got like a five-minute window or then then after three minutes you might go right okay i'm getting close let's do a speed run anyway so i have some sort of heuristic there which i think you mentioned anyway where you're talking the the other one is which is interesting to be a close path right if it's got uh if it's got high cost segments uh and this is why we use the word cost rather cell count it's got high cost segments then you might want to do some more searching a fuzzy logic type uh thinking whereas conversely if there's no high cast segments maybe you should just run it right away you know even if it's a long path it might be that if your mice is really good at straights if it's got a load of straights and no high cost segments then now i don't know once you've flood filled you'd have to go through and somehow divide that up down into segments and figure out hang on hang on let me stop you then because the cost that i talk about is cumulative so in every cell the recorded cost is the cost from that cell to the goal agreed but you might also be able to that that takes into account things like run length costs um true but if you've got say if you're moist you know it's poor at um uh sort of comb sections right and even though you've got your cost is you might want to you might as well as doing an entire end-to-end cost you might say well there's a risk of the particular types of features and if you plot it as a and get the mouse to you know there might be a water level on particular features that you you say right i'll run them if i have to run them so so you're doing a risk analysis on each segment as opposed to just looking at a cost less you can you can certainly do that um and i do that by weighting uh the individual maneuvers i don't weight a cell depending on on whether it's dangerous to run so the cones are dangerous but you could right you could say this cell has no walls and so i don't have any steering guidance and so i'll give it an extra weight that still ends up in the accumulated cost and it it would given a choice between you know turning left into a into a cell that's got a dangerous feature like a particular kind of turn that you know you don't like or no walls or something like that as against another one if you have weighted this cell a little bit more then the accumulated cost builds faster and you and you wouldn't do that um so yes all this can be done but it's a layer on top of the basic idea that i'm kind of yeah yeah yeah now i thought i thought just having closed paths as well as open paths it struck me that suddenly you've got a set of data combined beyond a simple end to start to target cost you know you could do it on a you know you could analyze the path to see how risky it is versus searching which has got risk i mean i'm not sure we could we could quantify the risk of particular features for a particular mouse but still it sort of gives you stuff that you can't even guess at with just an open mouse i'll stop talking now for the first time ever anymore any more peter yeah um could you um the obviously the the you're always going to end up with the the the four bits of the closed maze are going to be the same as uh basically the inverted um normal maze now so yeah inverted they'll be the same why would they be the same if you've got a oh yeah of course if you've got if you've got a gap yeah so they'll so they'll be the same so if they're going to be the same why can't you do the same calculations without recording them oh because they only end up the same yeah they only end up the same because of the way you have uh recorded the maze and and i didn't put in the the recording business but when you get to your sensing point and you have a look and say oh there are these walls here um then when you add the wall information to the maze you set a bit in the open maze for a wall present and you clear a bit in the closed maze for a wall absent right which yeah it goes against what i said before but that's before we're talking about it right and but when it was cleared in the first place right there's a bit there already yeah it yeah f0 uh and when you see a space you clear the closed maze bit and when you see a wall you set the open bit um yeah you can do it quite efficiently um but that means that they will eventually can converge and you're really only storing data on a wall by wall basis rather than a cell by cell basis yeah okay that's that's interesting because um the the algorithm we've got in pick one turbo does a lot of that stuff but it doesn't do it in that way and as you say you you need to sort of work out your route and then put another algorithm on top of that and then another algorithm on top of that and you sort of build up and you end up with the same thing so it can create roots that go through dead cells that it you know that it's never been to and know that they're safe but yeah that's an interesting way of doing it okay peter thank you brilliant um i have to say the only the only one i've written is for the pick one that the software that i put in the pick one and that was a bit more simplistic but i did look at walls so keep the individual track of each wall so you may not visit a cell but you'd still know the state of all the walls or all the gaps in that cell but usually i was so happy to get to the middle that all i wanted to do was get back and do it again before i ran into a wall well it turns out if you compare whatever you've code you've got now we're doing it this way um this turns out not really to be significantly more no i think it's simply only the only because because you've got that always got that exact same calculation right and you just pass in a number zero or four and the calculation is always the same there's never any decisions to make i once read a nice thing on programming which says that you should always try and get rid of all of the if statements if you possibly can and this does that right there is there's no decision to make you just set a number and the job's done um and so because all that makes things much simpler the only significant change that you need to make after that is when you do the initial mapping and that's the setting and clearing of bits yeah sensors and that's that's a relatively trivial thing to do right it's very tidy it reduced quite a lot of the conditional statements that that you see kicking around in a lot of these uh searches and and the fact that you could measure how close you are getting to the optimum by looking at the difference between the two costs i think is um so if you're running out of time entry time um you can just say okay cut and run do a run now peter have you actually coded this and tried it or is this your theory uh i haven't put it into the mouse because i still haven't bothered to put my maze back together but the code that you knew the the diagrams they're all running in a a mouth emulator and i've tested it against loads of mazes and really it's actually just a refactoring of existing code so i have no problems with it working cool any more last one for peter are we done okay peter thanks very much excellent again next up we've got