Assignment #1

  • Worth: 5%

  • DUE: September 26th at 11:55pm; submitted on MOODLE.

Objectives

The main objective of this assignment is to compare the blind search algorithms covered during the first lectures. The comparison needs to be done on different points:

  • Performance.

  • Time complexity.

  • Space complexity.

Note

If you can think of other relevant comparison point, feel free to add them. It may lead to bonus points if they are particularly relevant. You are highly encouraged to ask question about the assignment.

The other objective is for you to learn how to use Latex (https://www.latex-project.org/), the language used to write and compile scientific articles.

Problem

In this assignment we are considering a grid world in which a robot needs to move to reach the goal. Each cell of the grid can be of two types:

  • Free

  • Obstacle

The starting and goal positions are generated randomly in the environment at the beginning of each mission. You will assume that these positions are known by the robot. The only difficulty for the robot is to compute the optimal path using blind search algorithms.

The following image is an example of the problem:

_images/grid.png

Implementation

All the code needs to be written in Python.

First, you need to implement the environment generator that has the following specification:

  • Generates a grid world.

  • The size of the grid can be given in argument.

  • The grid can be a square or a rectangle.

  • The obstacles are generated randomly.

  • You can save a grid.

I do not require a user interface. If I can launch everything in a terminal, it’s enough for me.

Secondly, you need to implement the solver. It should contain the following algorithms:

  • BFS

  • DFS

  • Dijsktra

  • Dynamic programming algorithm

The solver needs to take in arguments a grid previously generated. How you implement the solver is up to you, as it depends on the types of results that you want.

I have some recommendations:

  • Define the same initial condition for each algorithm.

    • Same start and goal.

    • If the initial conditions are different, the results cannot be compared.

  • Save the result for each simulation.

  • For the same grid, use different initial conditions.

    • You can use them to compute the average, etc.

  • You should vary the size of the grids.

Warning

This is not a programming assignment! Producing and submitting a good code alone will not grant you a passing grade. However, your code needs to be clear, modular and easily understandable. If the code submitted does not respect these conditions, penalty can be applied. Finally, this is an individual work; thus you cannot use or share your code with other students.

Report

After running your experiments, you are required to write a report in Latex. Latex is free and open-source, but by default does not propose an editor. Some solutions exist like TexMaker (Software) or Overleaf (Web application).

The report needs to have the following structure:

  • Introduction

  • Problem definition

    • Mathematical formulation of the problem

    • Algorithms used

  • Experiments

  • Results

  • Conclusion

Submission

The submission of the assignment needs to be done on Moodle. I am expecting the following files:

  • Your report in pdf.

  • Your code in an archive file (.zip, .rar, etc.)

Warning

It is your responsibility to submit the required files on Moodle before the deadline. Issues with Moodle are not valid excuses for late submission.

Grading Scheme

The assignment is graded based on the report submitted.

The report will be graded on the following points:

  • The problem is correctly defined

  • The quality of the experiments

    • Relevance of the experiments

    • Quantity of the experiments

    • Correctness of the protocol

  • Results and Conclusion

Note

Points can be deduced if the code is not up to the standard specified before.