I refer back to Ben and Brandon’s forum threads, 2974, 7240, and 22889 as input to this question.
.
Assume we have a line maze developed on a grid. Such a maze is similar to those used in the LVBots 2014 competitions. Each junction is at a crossing of the grid lines. Not all crossings need to be junctions. The robot must traverse the maze to discover the placement of junctions–it has no beginning map.
For a non-looped maze, a solution may be found using a left or right hand rule. The optimal path can be determined by eliminating dead end traces from the stack. This technique does not depend on tracking compass headings (NESW). It only depends on keeping a stack of directions (left, forward, right, reverse) the robot takes leaving each junction.
For a looped maze this method may not be adequate because the robot may be trapped in a maze loop.
Assume the robot must traverse the maze to create a looped maze map:
Is it possible to expand the left hand rule to cover looped mazes?
Are there maze solutions based on counting turns in each direction?
Do known methods require monitoring the robot’s relative heading?
I am not aware of a sure-fire ways to solve a looped-maze by simply modifying the left-hand rule. Did you have something in mind?
The robot will likely do many turns in both directions while solving the maze; you could probably determine which direction the goal is facing by just keeping track of the number of turns, but you will need to do more to determine where that goal is (and how to get to it again). If your maze is grid-based like the one in our LVBots competition, keeping track of the robot’s relative heading is just one step further than counting turns.
I am not familiar with any methods of solving a looped-maze without keeping track of the robot’s relative heading and some sense of where it has been in the maze. There are typically two phases of maze solving. The first phase involves learning the maze and usually not caring about how much time it takes; then the second phase is using that information to solve the course as quickly as possible. With some luck, you might be able to eventually solve the maze in the first phase without keeping track of the relative heading of the robot, but it would be necessary for gathering the kind of information you would need to solve the maze in the second phase (which is essentially a digital representation of the maze). More details about the method I used can be found in this post that you alluded to.
I conceptualize the maze as a tree with the root as the starting point and and one or more branches ending in the goal.
Use the “flood fill” algorithm to eliminate path segments that don’t lead from root to goal. This method is used for looped mazes.
For non-loop mazes the “left hand rule” uses a method like the flood fill to eliminate paths that don’t lead to the goal. In effect we remove any branch that results in a dead end. If we take the moves preceding and following the dead end we generate one of eight moves to replace the dead end.
Looped maze solving algorithms generally depend on building the maze in memory; generating the x, y coordinates of each junction and recording the directions a robot can exit the junction. It is a placement in space algorithm.
The non-loop maze algorithm has no placement in space. It is strictly “what turn do I take?”
Can the left hand rule be expanded to solve looped mazes? This is a theoretical question.
Brandon, I’m not trying to put you on the spot. This is a question for the general robotics community. But in the history of looped maze solutions you and Ben stand out in internet searches. I wonder where else to go?
I cannot think of a way to use something like the left hand rule that would ensure the robot will finish a looped maze.
In theory, something like a random walk would eventually finish the maze if you let it run long enough, but there’s no guarantee it will finish in a sensible amount of time, especially if you’re using a sizable or complicated maze. There are usually time restrictions in maze solving competitions (not to mention battery concerns). Additionally, it wouldn’t be able to be optimized for the second phase without some way of tracking the maze layout.
I would certainly be interested in hearing if anyone else has some suggestions though.
Out of curiosity, is there some reason why you do not want to track the relative heading of the robot or map out the maze, or is this more of a thought experiment?
Thank you for your feedback. I agree the random walk doesn’t make sense.
I’m not opposed to tracking the robot heading. I’ve written code that inputs the robot turn leaving a junction (left, forward, right, back) and translates it into a new compass heading and a new junction with x, y coordinates. I’m just not yet convinced the headings are mandatory.
My logic: I read that flood fill is a method to eliminate all paths in a looped maze except for paths to the goal. But flood fill does not require robot heading, or a map of maze junctions.
Suppose we have a tree branch that starts at the root and all the limbs end in dead ends. The robot will take the left hand edge of the branch, arriving at a dead end. It will then backtrack, proceed forward from the next junction until it reaches the next dead end. This process continues until the entire branch, from root forward is eliminated from a possible path. This entire branch has been flood filled. Neither robot heading nor a generated maze map were required.
The robot now moves to the next branch at the root. Assume this branch has a path to the goal. At some point the robot may get stuck in a loop. At this point we must recognize the loop and alter the left turn priority to leave it. Tracking the robot heading history, or the history of visited junctions may provide a method to recognize the loop. But I’m not yet convinced it is necessary. The flood fill algorithm doesn’t need headings to deal with a loop.
The maze must be fairly simple if the robot must traverse it to solve it. The LVBots 1014, looped maze was a matrix of 7 x 15 junctions. If the maze gets much bigge, solving for the optimal path tests robot endurance. Of course, the maze could be stored in robot memory, but then only the optimal run is required. All the course calculations can be made in software.
My next moves involve simulations. I start with a line maze similar to the LVBots competition. At a start point I take an imaginary robot and direct it to the next junction. I load into the program the sensor states leaving that junction (left, right, forward, dead end). I will save the x, y coordinates of each junction to ensure expected versus computed tracks are the same. Running through a loop I want to see if I can solve the looped maze without resorting to robot compass headings.
The two obstacles I see with your description of not mapping maze junctions are determining when the robot is in a loop and figuring out how to get out of it.
I think you will find that trying to have your robot physically flood fill the maze will require information about the junctions. For example, you mention having the robot backtrack and proceed toward the next junction, but it wouldn’t have enough information to know where the “next” junction is.
It sounds like you are describing mapping out the junctions. I am not sure how you plan on going about doing that accurately in a looped maze without taking into account the robot’s heading, but I would be interested to see what you come up with.
