The Maze

The Maze represents typical state space search task, we support solutions both in Java and Python.

• Effective algorithms solving this task can be reused in wide spectrum of search problems.
• Similar problems can be found in robotics and AI research.
• Shows how GPS navigations find the shortest way between two places and why does it take so long.

Lets us have a square board of N x N squares. The playing board is clearly delimited and board's edges do not neighbor each other. (We can imagine typical chessboard.) For each square, we will define its four-neighborhood, in other words each square has only four neighbors, those it shares an edge with.

On the playing board, there is one square that is marked S (start), another one that is marked G (goal). All squares are then marked either free ( ) or full(blocked) (+). For obvious reasons, squares marked either S or G are always free.

We place a robot on the starting square, which has to move to the goal square in the least number of moves. We can also imagine the robot moves like the tower in chess does.

Create an algorithm, which will lead the robot on shortest path through the maze. You will have access to the whole playing board, like you were looking on a chessboard, not like you were a robot with limited field of view.

Algorithm is going to be tested on a set of maps and it will be evaluated based on its performance according to the following criteria. (Sorted by their priority):

1. Number of mazes, in which it has found the shortest correct (can be followed) path. If there are more optimal paths than one, one is enough.
2. Number of mazes, in which there has been found a correct path, but not optimal path.
3. Total relative length of all the paths found. (The length is weighted by the size of the maze.)

Correct path, if it exists:

1. has to start in S square and end in G square.
2. be continuous in its four-neighborhood
3. can only go through empty squares

During this assignment we will see the following properties of this kind of problems.

• Basic pitfalls of searching
  • Problems with search as combinatorial explosion.
  • Search algorithms effectivity
• Generalization of this assignment to other tasks, that can be solved using the same or very similar approach.

Just like in the whole course, foremost we value your effort. You do not have to worry about not finishing this course just because of this assignment. However, during the work on this assignment, there are several defined control points, where you can check your progress. At the end, all the algorithms will be compared by testing them and you will try to score as high as you can.

• You should be able to understand the assignment and implement simple player (searcher/robot)
• You should be able to design and implement more sophisticated algorithm, which can solve bigger and more difficult mazes.

More details are here.

Results can be found here

You can download support classes (Java) here.

You can download support modules (Python) here.