Society of Robots - Robot Forum
Software => Software => Topic started by: superchiku on March 17, 2008, 12:55:15 PM
-
i have been thinking of making the micromouse maze solving bot and i guess the flood fill algorithm will be the best ...anybody who has done such a bot, can u explain how u programmed ur bot and abt the sensors too so that ill have some idea and experience how to do the bot..
-
these bots are easy to make, just use the wavefront algorithm, read admins .
if you want somethin a little more complicated us e A-star, i think its the optimal algorithm as it provides control over its speed and accuracy.
google A* and yoh have lots of info about it
i am workin on a project that uses an algorithm based on the A star , its developed to embedd orientation of the vehicle
its like A star but with 8 layers ,so each square can have up tp 8 indices in the closed list,but with diiferent parents
still workin on the subject
-
I am part way through building a micromouse bot. I have documented what i have up to now on my member tutorial.
http://www.societyofrobots.com/member_tutorials/node/93 (http://www.societyofrobots.com/member_tutorials/node/93)
Look at the theory page for the algorithm i use.
EDIT: Oh and I forgot, my micromouse build thread - http://www.societyofrobots.com/robotforum/index.php?topic=2741.0 (http://www.societyofrobots.com/robotforum/index.php?topic=2741.0)
-
its a nice tutorial sure keep in touch but really micromouse is blowing my brains off
-
A* algorithms are hardly used in micromouse. Flood-fill and some of its modifications are the most commonly used. Dijstra algo is also used, which also takes care that a path with more turns may take more time....
Since the winner is decided by the time of the fast runs...the top speed and acceleration of your bot are the most important things.
Building a competitive mouse(under 10s fast run) will take lot of hard work and may take years..
www.micromouseinfo.com (http://www.micromouseinfo.com) and http://micromouse.cannock.ac.uk/ (http://micromouse.cannock.ac.uk/) are very informative...
also have a look at this active micromouse forum: http://www.micromouseonline.com/ (http://www.micromouseonline.com/)
-
Dijstra algo is also used, which also takes care that a path with more turns may take more time....
this one is relativley slow compared to the A* ,,
if you want a fast running algorithm you showed use A* and your heauristic should be an over-estimate.
I still believe that Floodfill one is faster...
-
well knowing abt the algorithm is easy implementing it is difficult ,
now i wanna ask suppose the maze is completely unknown then how do u navigate the maze
-
Let me try explaining flood-fill...
In this method you need to have an array(say ff[][]) that stores the floodfill values which represent distances from the goal.
define a flood function that does the following steps:
1.Initialize all ff[][] to 255
2. Say your target cordinates be TX,TY. Then assign ff[TX][TY]=0
3. Implement a queue (http://www.cs.bu.edu/teaching/c/queue/array/types.html). Push the target co-ordinates into the queue.
Repeat the following steps untill the queue is empty.
4.Pop an element from the queue.Say its co-ordinates be RX,RY.
5.Now look for cells that are accesible from RX,RY using the wall information.
If the flood-fill value of that cell is 255 then assign ( ff[RX][RY]+1 ) as the new flood-fill value and also push that cell into the queu.
now i wanna ask suppose the maze is completely unknown then how do u navigate the maze
*In the beginning, you don't have any wall information. You only know the target co-ordinates.
*Assume that there are no walls. Now flood the maze using the above algorithm.
*Find the cells that are accessible from the cell your bot is currently present.
Move to that cell that has the minimum flood-fill values among these cells. If there are more than one cell with minimum value, give preference to your front cell, left cell, right cell and then the behind cell.
*Upon reaching the new cell, you may have find new walls. Update your wall information, and again flood the maze using the new wall information and follow the above method to choose the next cell.
*Do the above procedure until you reach your target cell.
Based on your present wall information, the shortest path as calculated can have some cells that are unvisited. Your strategy should be to visit these cells, before you make your fast run. You can also develop other strategies.
See this page. It describes the flood-fill and some other algos:
http://www.micromouseinfo.com/introduction/software.html (http://www.micromouseinfo.com/introduction/software.html)
-
well another doubt i meant the maze how do iknow if it is 5*5 or 20*20 matrix or whatever
-
Your mouse should know certain information about the maze even before it starts solving the maze. Have a look at the maze description in micromouse rules. http://micromouse.cannock.ac.uk/maze/index.htm (http://micromouse.cannock.ac.uk/maze/index.htm)
The maze is normally 16 x 16 square array of 180 mm x 180 mm unit squares.
So typically your mouse should know beforehand that its a 16x16 maze and you should try to reach centre (8,8)
-
oooh
and i thought the mouse has to find out everything...my bad.