1. Home
  2. General Robotics Forum
  3. Robot maze exploration algorithm

Robot maze exploration algorithm

Hello,

I am working on algorithm which would control a robot exploring unknown random maze. Maze in unknown. Robot may acquire information about what it sees using sensors in 4 directions. Size of maze may be e.g. 25x25 oraz 20x20. There are no open spaces in maze (in each cell, robot is close to at least one wall). Each step of robot costs energy point. When I discover new cell (it is not demand to move robot to that cell; it is enough that I see that cell using sensors) I earn energy point. I need to discover whole maze in as small number of moves as possible and earn as much points as possible. I developed my own algorithm which makes list of "oppenings" (cells which are connected to unknown regions of maze) indicating how much unknown "walls" each cell has (1, 2 or 3). There is also information, how much steps robot must do to move from actual position to each "opening". After small calculations, my algorithm chooses which oppening is the best and moves robot to it. My question is: is there any known algorithm which could I use in described exercise?

Thanks in advance for help and suggestions.

Best regards.

Reply to
Robbo
Loading thread data ...

--snip--

Robbo,

One of the simplest maze-solving algorithms is the Right-Hand Rule: place your left hand on a wall and start walking, keeping your hand touching the wall at all times. (Southpaws can use the equivalent Left-Hand Rule. )

This algorithm may fail if your maze contains "loops" or "cycles", but it's certainly a place to start. If you have enough data storage to build an internal model of the maze, you can be "smarter" by not entering sections of the maze you have already fully explored.

Also, if you do a 'Web search for literature on maze-solving algorithms I'm sure you'll find a lot more ways of approaching the problem (and opinions about which is best to go with them ).

This is all well and good if you're coding your algorithm for a "theoretical" robot, one that will only exist as a computer model. When you start dealing with physical sensors and actuators, with all their associated problems, even something as simple as determining your location becomes enormously complicated. Once your robot encounters TheRealWorld(tm), the high-level maze-solving logic may be the easiest part. A different challenge, but still fun.

Merry Christmas! Hope this gets you started.

Frank McKenney

Reply to
Frnak McKenney

Actually, I know at least a few algorithms to maze solving. As I have written, I use

1) choosing of oppenings to undiscovered parts of maze at "high level", and 2) A* to move robot to selected oppening at "low level". I would like to disscuss about good heuristics, not simple Right-Hand Rule. (I am interested in theoretical algorithm, not physical robot and problems connected with unperfect sensors).

Robbo

Reply to
Robbo

Ah. That was not clear from your original posting.

To physically move a mechanism? Or to choose which opening to enter?

Ah. A "virtual" robot. _Not_ dealing with TheRealWorld(tm). Much simpler.

So when you select a vertex (choice point) in the maze, you can immediately determine which paths "lead from" that vertex?

If so, if all you need to do is check each vertex so you can explore the maze, then it sounds like you're really interested in graph/tree traversal algorithms.

What have you discovered so far with Google (or your favorite search engine)?

Frank McKenney

Reply to
Frnak McKenney

First of all, I work on this problem from theoretical point of view and I am not interested in real world problems like unperfect sensors, etc.

Indeed, this problem is similar to graph traversal, but... graph traversal algorithm assumes visiting each node of graph. In my situation, I do not need to visit each node of graph/maze, to discover particular region of maze/graph, because my theoretical robot has sensors which are used to see, what robot sees straight ahead, behind, on the left and right. Well, lets imagine empty pice of paper taken from math exercise book. Empty cells means undiscovered yet cells of maze. Cells with "." means that this cell is discovered (remember, we do not need to visit this cell to discover it). Cell with "#" means that it is wall. In first steep, robot looks around, so it may discover some region of maze (some spot around its actual position). Now, what next?, where to move now? We have probably at least a few "openings" (cells which are gates to undiscovered regions of maze; cells which are placed at borders of already discovered region of maze). We need to choose one of this "openings" and move to it. But how choose the best oppening? Maybe the best opening is, when it is placed close to our actual position (remember: we earn points when discovering cells of maze and loose points when moving robot). Maybe better openings are these with 3 faces connected to undiscovered maze region (when robot moves at this position, its sensors may acquire data from 3 directions and probably we will earn more points), that with 2 or 1 face. Actually, I developed math formula which I use to choose the best opening. It is: numberOfFaces*NumberOfFaces*C - L. NumberOfFaces may be 1, 2 or 3 (how many faces/directions at this opening is connected to undiscovered maze part). C is constans and I chose it after experiments. L means, how many cells robot must move through to move from its actual position to opening's position. For a few days, I have been working on another heuristic -- maybe it would be better that this shown above. I look for better algorithm or better heuristic to my actual algorithm. Unfortunately, I have not found any good resource yet.

Robbo

Reply to
Robbo

PolyTech Forum website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.