1. Localization in a Maze

  • Worth: 5%

  • DUE: February 15th, 2023 at 11:55pm; submitted on MOODLE.

Warning

For this assignment, you may not work with anyone else.

You need to work independently.

1.1. Context

In this assignment you will implement a localization system for a robot in a maze.

The maze is a represented by a discrete grid, each cell of the grid can either contain a wall, the robot or nothing.

The maze should be partially symmetric, for example:

../_images/maze_example.drawio.png

The robot receives a measurement \(z_t = [z_n, z_s, z_e, z_w]\) where each \(z_i \in z_t\) is a boolean indicating a wall.

Example

If the robot is in the following cell:

../_images/maze_measurement.drawio.png

It should receive the measurement \(z_t = [0, 0, 1, 1]\) if the sensor is perfect.

The robot navigates in the maze until it is confident (\(> 80\%\)) about its position.

1.2. Instructions

This part gives you the instructions for the assignment.

1.2.1. Maze

  • You need to create 3 different mazes.

  • Each maze need to have a size of at least \(8\times 8\).

  • They should be close to be symmetric, but not exactly.

  • You need to represent them by using a 2D numpy array.

Example

The previous maze would be represented by the following numpy array:

maze = np.array([[1,1,1,1,1,1,1,1],
                 [1,0,0,1,0,1,0,1],
                 [1,1,0,1,0,1,0,1],
                 [1,0,0,0,0,1,0,1],
                 [1,0,1,1,0,0,0,1],
                 [1,0,1,0,0,0,1,1],
                 [1,0,1,0,1,0,0,1],
                 [1,1,1,1,1,1,1,1]])

1.2.2. Motion and measurement model

You need to implement the motion model.

  • The motion model \(p(x_t|x_{t-1},u_t,m)\) is not perfect.

  • When the robot moves in one direction there is probability of 10% to undershoot, 10% to overshoot and 80% to reach the correct cell.

../_images/maze_mov_uncertainty.drawio.png

  • The robot can only move one cell at a time.

  • If there is a wall it stays in the cell just before the wall.

You need to implement the measurement model \(p(z_t|x_t,m)\).

  • You have 75% to receive the correct measurement.

  • You have a uniform probability on the other measurements.

1.2.3. Simulator

You need to create a simulator, the simulator will run a simulation:

  • It will select an initial random position in the maze.

  • It will maintain both the belief and the true position.

  • It will select an action based on the current initial belief in the direction of an empty cell.

  • It will apply the motion model based on the true position.

  • It will generate a measurement based on the true position and the measurement model.

  • It will apply the Markov localization algorithm to update the belief.

  • It will save each belief and true positions.

1.2.4. Results

You will need to provide the results of your simulations:

  • You will plot the beliefs as heatmaps (only a few steps) for each simulation.

  • You will plot the true positions for each simulation

1.3. Submission

You need to submit on Moodle the following:

  • The code correctly commented.

    • The code allows the user to select the maze and run the simulation.

    • The code needs to save the results.