[chbot] Micromouse maze solving strategies and maze construction.

[Richard Jones]

Here's my take on competition maze solving.

Given that the solution is unknown it may not be possible to
fully optimise search strategies, it is the luck of the draw
for a given maze. A really dumb solver might stumble into
the solution quicker than a smart algorithm for some mazes,
but probably much less often. Given that, including mouse
dynamics in the choice of which paths to search first and
not searching areas that can't be part of the solution seem
sensible to minimise the search time.

I have an intention to do something with Python and SWIG to
replace my old solver with something that is more up to date
for working under Linux and Windows GUIs. (Any other
sugestions would be most welcome). I should be able to dig
out all the code for the old simulator and email it to
anyone who wants to read it. I think the solver itself is
only a few lines of 'C'. There is an assumption that the
maze has no walls, as the mouse starts to explore it adds
the discovered walls in to the image of the maze and
re-solves to decide where to go next.

Now that holidays are over and family have all left I will
have more time for robotics, once I've got MythTv working
with my new satellite receiver ;-)

I have built two maze sections 6 x 6 cells and one 3 x 3
cells. I have a box full of walls but have not counted them
recently. Most of my maze walls include one end post (some
have none or two included in the length). This is probably
enough for debugging and demonstating mice, but if we want
to run a competition we need to design and build a full size
maze or buy one.

This is the best source of micromouse ideas that I have
found: http://micromouse.cannock.ac.uk/

Cheers

Richard

> I've been thinking this problem through and I can see that
> finding the  shortest/fastest path is equivalent to the
> shortest path problem in  graph theory.
>
> Now Im thinking about the process of discovery, an whether
> you'd need to  investigate the whole maze or not. The
> obvious process to discover the  maze is to always go
> straight, right, left or back as possible and  backtrack
> to spots where there were more than one possibility. This
> is  gaurenteed to discover the whole maze and seems to be
> what the simulator  program does.
>
> If the goal always is always in the center of the maze,
> would it be  possible to gear the turn decisions with the
> goal of discovering the  area between the center of the
> maze and start point first? C
>
> _______________________________________________
> Chchrobotics mailing list
> Chchrobotics@lists.linuxnut.co.nz
> http://lists.ourshack.com/mailman/listinfo/chchrobotics
>