Hello everyone, I'm working on school project where my robot needs to go through the whole maze which is on grid and then draws its map. The robot is already capable of going through the maze, but I'm using a simple right wall following routine so that means he can get stuck in certain situations and just goes in circle. I probably need an algorithm which will remember on every junction the path that the robot didn't choose so that he can go back to the square which he has in memory after he comes to the end of the first chosen path. My idea was to use a flood fill algorithm which will assign 0 to a square where the robot is now and 1 to available paths then he chooses path, moves to a new square, assigns 0 to it and add 1 to a square in front of him and to squares behind him. After he comes to the end of his chosen path the robot then returns to the square where he had 2 possible paths and chooses the way he didn't go yet. Since I think this is way to hard for me to program, does anyone have any idea how this can be simplified?
Algorithms to solve such mazes are complex and cannot be simplified. Making a robot search and solve such mazes is much more difficult than a wall-following type, requiring more complex sensors and a more powerful microcontroller with more speed and memory than a basic Arduino like Uno.
What does your teacher say about those mazes that cannot be explored by right wall following? Does he expect you to implement (copy&paste) one of the sophisticated algorithms, or does he want you to solve the simple case and only add maze mapping?
Well, the teacher wants me to adress those possible maze structures, but he didn't specify the way I should approach them, to be exact he said thats my job to do it somehow. I don't know if I could even use maze solving algorithm, because the robot does not solve the maze, he needs to go through every possible path in the maze.
I've never tried to build a maze solving robot, so maybe I'm barking up the wrong tree here, and it depends what sensors you already have mounted, but this:
I'm using a simple right wall following routine so that means he can get stuck in certain situations and just goes in circle. I probably need an algorithm which will remember on every junction the path that the robot didn't choose
... surely means a more sophisticated sensor system than just "looking to the right" so to speak.
To follow a wall as a human, you can keep your eyes closed and keep a hand on the wall. You don't need any knowledge of the intersections: it makes no difference if it's a t-junction or a + or whatever. In fact you don't even need to have the notion of an intersection at all. But to remember where you didn't go, means having knowledge of each intersection's possibilities.
Seems to me that's a far more sophisticated physical device (algorithms and coding aside) that can "see" each intersection, rather than just keeping right with its eyes closed.
In the rare cases where not all four sides of a cell have been explored, the robot can turn around there so that the right hand sensor is still sufficient.
The robot has 3 ultrasonic sensors and it goes trhough the maze like this: move to a next square, ping obstacles in front and on sides, decides where it can go, if there is no obstacle in right turn right, if there is obstacle on right and no obstacles in front and on the left, first go forward and if there are obstacles in front and on the right turn left, and if there are obstacles in all 3 sides turn 180.
DrDiettrich:
So you can use floodfill to explore the maze.
Thats what I'm afraid of. I don't even know hot to start with it and my biggest fear is finding path back to the junction.
You have plenty of RAM then. Floodfill sounds like a viable option, assuming you know where the target cell is. Do you? Or are you looking for a gap in the perimeter to let you out?
You can read up about flood fill but it is fairly simple once you have your data structures defined to hold wall data and step counts.
wildbill:
Floodfill sounds like a viable option, assuming you know where the target cell is. Do you? Or are you looking for a gap in the perimeter to let you out?
I'm looking for a gap, but I think I'm able to say what coordinates the targeted cell has because I'm calculating diferences for every square.
I think I'd flood fill every time I identify a new wall and then move towards what I believe to be the nearest unexplored cell that's on the perimeter.
The target cell will likely change as new walls are discovered and that may lead to some apparently irrational to & fro, so once it's working you might want to add some extra heuristics - perhaps prefer to continue moving forward rather than reverse direction if there are unexplored cells ahead.
If you assign each visited cell a weight, start with W=1 and assign all reachable neighbours the weight W+1=2, and so on. To return you follow the surrounding cell with the lowest weight.
And do I assign cells from the start or on every junction so that the robot can go back to the junction square? Also I sitll don't understant the return to a cell. For now the robot goes through maze like this: go to a new cell, ping sensors, send zour coordination and position of obstacles to the database, decide where to go next and go there. I probably need to add some vector or stack to save the not selected square and after the robot gets to it, remove the cell from a memory. So theoretically could it be done like this: robot comes to a junction, pings sensors, sends coordinates with obstacle placement, assign the cell with weight, remembers path that he didn't choose, moves throught the chosen path assigning weights to a new cells and after he comes to the end of his path then he moves back cell by cell to the lowest weight?
It is certainly an excellent idea to ignore all the work on maze solving that thousands of other people have done, and work this out entirely by yourself!
Especially when you do your thinking post by post, on a public forum.