Robot maze exploration algorithm

Posted by Robbo on December 23, 2009, 11:33 am

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.

Posted by Frnak McKenney on December 25, 2009, 8:40 am

> 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).

--snip--

> My question is: is there any known algorithm
> which could I use in described exercise?

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. <grin!>)

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 <grin!>).

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. <grin!>

Merry Christmas! Hope this gets you started.

Frank McKenney
--
The vice of the modern notion of mental progress is that it is
always concerned with the breaking of bonds, the effacing of
boundaries, the casting away of dogmas. But if there is such a
thing as mental growth, it must mean the growth into more and
more definite dogmas. The human brain is a machine for coming to
conclusions; if it cannot come to conclusions it is rusty.
-- G.K. Chesterton: Concluding Remarks on the
Importance of Orthodoxy (1905)
--
Frank McKenney, McKenney Associates
Richmond, Virginia / (804) 320-4887
Munged E-mail: frank uscore mckenney ayut mined spring dawt cahm (y'all)

Posted by Robbo on December 27, 2009, 6:31 am

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

Posted by Frnak McKenney on January 2, 2010, 1:44 pm

> Actually, I know at least a few algorithms
> to maze solving.

Ah. That was not clear from your original posting.

> ... 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".

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

> 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).

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

simpler. <grin!>

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
--
...the fact that some geniuses were laughed at does not imply
that all who are laughed at are geniuses. They laughed at
Columbus, they laughed at Fulton, they laughed at the Wright
Brothers. But they also laughed at Bozo the Clown.
-- Carl Sagan
--
Frank McKenney, McKenney Associates
Richmond, Virginia / (804) 320-4887
Munged E-mail: frank uscore mckenney ayut mined spring dawt cahm (y'all)

Posted by Robbo on January 4, 2010, 7:53 am

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.

> 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.

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

Similar Threads	Posted
PID algorithm?	March 3, 2010, 9:52 pm
Lee's algorithm - Described?	February 5, 2007, 12:09 pm
Motion Planning Algorithm	August 12, 2008, 4:06 pm
Astar algorithm, problem	December 5, 2009, 6:11 pm
Visual recognition and the SIFT algorithm	February 23, 2006, 2:31 pm
More Visual Recognition and the SIFT algorithm	February 24, 2006, 5:53 pm
The SIFT visual recognition algorithm	February 24, 2006, 10:07 pm
Algorithm for counting number of lines travelled over	December 22, 2005, 8:44 am
Closed-loop proportional motion control algorithm.	October 10, 2005, 11:03 pm
Mars Exploration Rover Update - May 1, 2006	May 2, 2006, 11:43 am