2. Monte-Carlo Localization in a Maze

  • Worth: 5%

  • DUE: March 16th, 2023 at 11:55pm; submitted on MOODLE.

Warning

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

You need to work independently.

2.1. Context

In this assignment you will implement the Monte-Carlo localization system for a robot in a maze. it is similar to the previous assignment.

This time the maze is not represented by a discrete grid. You will consider a distance of 2 units between each wall.

The maze should be partially symmetric, for example:

../_images/not_discrete_maze_example.drawio.png

The robot receives a measurement \(z_t = [x, y]\) the localization in the maze.

Example

If the robot is in the following cell:

../_images/not_discrete_maze_measurement.drawio.png

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

The robot navigates in the maze for \(10\) steps.

2.2. Instructions

This part gives you the instructions for the assignment.

2.2.1. Maze

  • You need to use the 3 mazes that you created for the last assignment.

  • Ensure that each maze has the correct size.

  • You can use the 2D numpy array representation, but you need to have a function to convert it to a continuous environment.

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

  • I recommend to use the motion model odometry with the following errors:

    • \(alpha = [0.01,0.01,0.01,0.0]\)

  • The robot should move only one meter in a direction.

  • If there is a wall, it stays 1 unit before the wall.

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

  • You will implement a Gaussian function centered on the position of the robot (true position) and with a covariance \([[1,0],[0,1]]\).

2.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 true position in the direction free of obstacles.

  • 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 Monte-Carlo localization algorithm to update the belief.

  • It will save each belief and true positions.

2.2.4. Results

You will need to provide the results of your simulations:

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

  • You will plot the true positions for each simulation

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