Hello world,
I’m sorry to disturb you, but for a school project I have a robot equipped only with color sensors at the front. The goal of the robot is to go through a maze to find a treasure, then it must return to its starting point by the shortest path. The maze lines are black, the intersections blue, the dead ends green and the treasure yellow. At first the maze was perfect (No loops), and there I have no problems (Left hand algorithm, and I record the directions taken (North, South, East, West) before simplifying them for the return).
But now the maze contains loops, and there I can’t find a solution. I’ve seen a lot of algorithms, like the “breadth-first search”, but either they need to know the position of the robot (Very difficult to have because the trajectories of the robot are not perfect), or they don’t find the fastest way for the return.
I specify that the loops can have any shape, and that the treasure can be in a loop as well as elsewhere. Anyone have a suggestion? Because I’ve been stuck for more than two weeks…
Thanks for reading me!
Hello.
Looped maze solving can be quite a challenge! A simple algorithm like the left- or right-hand rule just isn’t enough. To reliably solve the maze, the robot typically needs to keep track of where it has been, and where it could go next. Essentially, it has to map out the maze as it travels through it.
The way I went about doing this in the looped maze solving competition we did with our local robotics club (several years ago now!) was to store a 2D array that represented the grid. Each time the robot traveled to a new spot on the grid, it would do several things:
- Mark that spot as “seen”.
- Mark the possible exits from that spot.
- Determine where to go next. (I think I had it prefer the left-most option that hadn’t yet been explored)
Please note that if your robot travels through a grid location that is just a straight line, it will not detect an intersection, which you will have to account for. This can be tricky if your robot does not have encoders, but it is doable with some careful timing.
Another tricky thing is that you have to keep track of your robot’s orientation in order to accurately keep track of where you are in the grid. For example, if your robot is traveling North on the grid and detects an exit to its left, that is very different from detecting an exit to the left when traveling East.
Personally, I found it easiest to use object-oriented programming to store an object for each location of the grid that held the details (things like if it had been seen, what the possible exits/entrances are, and later, how far away it is from the exit).
Once you find the exit, you should have enough information to determine the shortest known path. I found it easiest to work backward from the exit and assign distance values to connected grid spaces. For example, the “exit” cell would have a distance value of 0. The cell (or cells) connected to it have a distance value of 1, and so on, until all of the cells have a distance value (if two cells converge on a cell, and have two different distance values to it, you would take the lower one). Then, you have the robot trace back through the cells, looking for the connected cell with the lowest number. This is essentially the A* pathfinding algorithm. However, please note that this only solves for the shortest KNOWN path; just because you found the exit, doesn’t mean you have enough information for the shortest possible path. One solution for this is to check what the distance is to all “unseen” cells, and determine if it is possible for them to offer a shorter path to the finish. Alternatively, you could just keep searching until every cell that has an accessible entrance has been seen (which would be slower, but probably simpler).
Brandon