How To Implement Tremaux Explore Algorithm For A Maze

Setup
My robot is an Mbot ranger Link which I have modified by adding five ultrasonic sensors two to each side of the robot and one at the front.

The image below shows the position of my sensors.
Sensor Image

The Goal:
The goal for this project is for the robot to explore a maze and return to the start, the method I would like to use is the Tremaux Algorithm, like in this video.

The rules for the algorithm are:

  1. Every time you visit a cell, mark it once.
  2. When you hit a dead end, turn around and go back.
  3. When you hit a junction you haven't visited, pick a new passage at random.
  4. If you're walking down a new passage and hit a junction you have visited, treat it like a dead end and go back.
  5. If walking down a passage you have visited before (i.e. marked once) and you hit a junction, take any new passage available, otherwise take an old passage (i.e. marked once).
  6. When you finally reach the end, follow cells marked exactly once back to the start.
  7. If the Maze has no solution, you'll find yourself at the start with all cells marked twice.

The Problem:
I am having a very hard time trying to figure out the best way to code this problem on arduino, I understand how the algorithm works but not sure how to code it. which includes how to map out and keep track of each tile visted.

Ideas:

  1. I was thinking of using arrays to create a 2D matrix of the maze as I map it out but, the problem I found is the maze width and length are unknown, and it not advised to make a dynamic array on arduino as it will use too much memory.

  2. I was trying to code the maze like a tree diagram, but I had no clue how to represent a tree diagram in code, I tried to search it up but didn't get anywhere.

  3. Maybe I should use a raspberry pi and attach it to my robot and use python in order to handle all maze mapping.

Any help/guidance would be greatly appreciated

the maze width and length are unknown, and it not advised to make a dynamic array on arduino as it will use too much memory.

Well, if the maze is large, you are going to need more memory. Using 2D arrays or other structures won't reduce the amount of memory required, unless perhaps there are large parts of the maze that are inacessible.

Using a pi0w would be an idea worth considering. You can use Python or C++. Python would make using dynamic structures easier, as would having much more memory. Plus you have command line access over WiFi to interrogate the robot when debugging. But a pi will drain the batteries faster.

Other options include Arduino with more speed an memory than Uno, such as Zero clones, Teensy 3.2+ etc.

AdaFruit have boards that run "Circuit Python".

The problem I see is the reference to "marking" points that you have visited. This necessarily requires effectively a graphical representation of the maze and the ability to accurately record positions. This is a major difficulty.

Trees in code are not too hard, usually appearing as double-linked lists. They do however, require essentially unlimited storage capacity exactly as your 2D matrix. You also have to decide first on a binary, ternary or whatever the maximum number of branches must be, and have a notation for the number of branches other than a fixed 2 or 3. Each node contains the address (absolute or relative) of each branch and its predecessor.

You don't need that much memory to map a regular rectangular maze - is that what you have? You can do it with a byte per cell to store wall data for four sides and use the other nibble to count visits to the cell.

The difficulty is not knowing the dimensions of the maze. Do you know the maximum you'll face? You could simply declare the biggest array that you have room for and if you find that the actual maze is larger fail with a "Maze too big" error.

Even an Uno could manage a fair sized maze without difficulty. If you have to handle something larger, get an Arduino with more RAM.

How do you know when you have reached the end of the maze?

The problem is the maze can be any size, but each tile is a sqaure and all these tiles are connected together in any arrangement to create a maze, the maze has no exit points, so it must explore every part of the maze, then return to the start. Would you recommend me creating an matrix 2D array such as 20x20 , then just update the array as I move though the maze, eg the array all starts with 0, meaning no wall, then as i move it will check left, right and front and change any walls to a 1, and will in turn map out the maze.

As already mentioned, a rectangular maze, of known size, is easy to handle. For other models a controller with much more RAM is required, because dynamic memory management has to take into account memory fragmentation and management overhead.

Each cell has (pointers to) 4 neighbours, with 2 special neighbours Unexplored and Wall. The random (or systematic) choice would select one of the Unexplored sides and continue exploration. For each non-Wall side a new cell has to be allocated and linked, unless that cell already has been visited and allocated - but how can we know that? Eventuallly each cell should have X and Y coordinates as well, so that a search across all allocated cells can reveal already visited cells, even in a non-rectangular maze. As a small optimization all the cells in a corridor, with no forks, can be represented by a single cell. Unfortunately all that is known only after all adjacent cells have completely been explored.

If all sides of a cell have been explored, the robot has to return to the preceding cell, from which this cell has been reached. In a random exploration algorithm the entire way has to be recorded, for backtracking.

Such a cell will have 20-30 bytes of descriptive information, some more for memory management, so that a useful controller should have several hundred kilobytes of RAM. I’d develop the implementation on a PC, with a nice GUI of the maze, construct a maze and then let the simulated robot explore that maze. If that works, for several test mazes, you know more about the required size of an Arduino for your project.

marcus_is_beast1:
Would you recommend me creating an matrix 2D array such as 20x20 , then just update the array as I move though the maze, eg the array all starts with 0, meaning no wall, then as i move it will check left, right and front and change any walls to a 1, and will in turn map out the maze.

That’s how I would start, although if you have the memory for it, DrDiettrich’s solution is more elegant.

There are other problems to solve before you worry about mapping the maze though. Can you detect the walls with your ultrasonics? Often those sensors can’t see things that are close. Are the tiles big enough that you can use them?

Then there’s wheel slip: when you make a turn, you likely won’t manage exactly ninety degrees, so you’ll need some method of lining up again.

I agree. Before you think about maze solving, you should make your maze into a simple rectangular racetrack and get your robot to move around the track many times completely without hitting, or even touching, the walls.

Have you already found out the size of your robot and required extra space for turns.? Then you'll know how big your physical maze may become, and then it may be possible to use a fixed size 2D array for it.

The reason I am asking about maze-mapping and solving is because I have created a simple turn left algorithm, which works perfectly, I have ultrasonic for wall following. For turning i use the gyro with the use of bumper switches and small ir sensor, which give me perfect 90 degree turns. So my robot can make it way around a maze using a left hand rule. Thats why i want to add mapping now.

marcus_is_beast1:
I have created a simple turn left algorithm, which works perfectly, I have ultrasonic for wall following. For turning i use the gyro with the use of bumper switches and small ir sensor, which give me perfect 90 degree turns. So my robot can make it way around a maze using a left hand rule.

Cool! If you had explained that before it would have been better. Many beginners get ahead of themselves, wanting to run before they learn to walk. We were assuming you were one of those beginners.