hi everyone,
i have a project in my hand which requires me solving a grid.but for that i need to understand the concept of it. i ve just learnt of how to read and write stuff in EPROM.If any1 could help me explain the algorithm for solving a grid?thanks in adavnce!
Sorry but solving a grid means nothing to me, can you explain what this term means please.
OK.Sorry for not providing the details.its an 16X16 grid and the bot has to reach boxes at two positions pick them up and then place them back the starting point.i have attached the picture of the arena.i have the necessary hardware i just need the proper algorithm for it.waiting for your reply..
Oh, I assume it is not always that pattern and you can follow the white lines.
It's not quite my field but:-
Well that's where the ingenuity comes in. One simple algorithm is wall following, that is always take a left (or right but make it the same) turn at every junction. It's not the quickest but it is simple.
For further reading see:-
Grumpy_Mike:
Oh, I assume it is not always that pattern and you can follow the white lines.It's not quite my field but:-
Well that's where the ingenuity comes in. One simple algorithm is wall following, that is always take a left (or right but make it the same) turn at every junction. It's not the quickest but it is simple.
For further reading see:-
Maze-solving algorithm - Wikipedia
The wall following algorithm will only work if there is a continuous wall from the starting point, to the end point, which in this case I don't think there is (although I could be wrong as the map is quite hard to read in my tired state), due to the grid shaped parts you will end up going round in circles.
Is the map given before hand? I.E does the robot know the maze layout?
the robot will be given time to map the grid on eeprom.and then it has to find the path and move to the red areas.it cannot pass the black junctions.and also i dont know how to map these bridges.can anyone help??
the robot will be given time to map the grid on eeprom
Is this something the robot itself will have to be programmed to accomplish, or will you be allowed to 'feed' it the map?
I'm assuming the robot can only follow the white lines, and the angled lines are paths around the black junctions.
I'm also assuming that the robot has to figure out it's own course through the grid, and not be fed a course predetermined by you.
You have a lot more to accomplish here than just 'solving a grid'.
- How are you detecting and following the white lines?
- How are you detecting the intersections?
2a. How are you detecting which type of interesection you are at? There are three possibilities. A passable 4 way intersection, a blocked 4 way intersection, and a bypassing angled intersection (assuming that is actually what they are)
None of those tasks are trivial.
If the robot has to map out the grid on it's own, that's also a very significant task in itself.
Once all that is taken care of, the process of navigating the grid is probably the most significant task of them all. One standard method of handling such navigation is to use a graph data structure to store the map, then use one of the readily available algorithms for finding a path through the graph. See Graph (abstract data type) - Wikipedia for an introduction. Of course, that's only computing the high level path through the grid. You then have to convert that into actions the robot must take to physically navigate the grid as well.
And trying to accomplish all that on just an Arduino only ramps up the difficulty level even more.
That all assumes that I have correctly interpreted your description of the task, which may not be the case at all.
the robot will be given time to map the grid on eeprom.and then it has to find the path and move to the red areas.it cannot pass the black junctions.and also i dont know how to map these bridges.can anyone help??
Seems you have rules that you did not make on your own. So would you please tell us why you need to stick to these rules? Is this some kind of course assignment? What are you trying to accomplish?
Thanks for your help!.now,
i would like to tell u that all your assumptions are correct! and also i would also like to tell you a little about my bot. it has a 5 array sensor,the inner 3 for line following and the outer one s for the blocking node and junction detections.(which i am able to do).now the problem is
how should i save the bridge ways. the one s to avoid the nodes.if u could think of some logic for that it would be of great help.waiting for replies..