Assignment #2

  • Worth: 5%

  • DUE: November 7th at 11:55pm; submitted on MOODLE.

Objectives

The main objective of this assignment is to compare the informed search algorithm and linear space algorithms covered until now. 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.

Problem

In this assignment we are considering the \((n^2 -1)\)-Puzzle problem.

  • In this problem the number of states is \(\frac{(n^2)!}{2}\).

  • Meaning that for the 8-puzzle example we have \(181440\) states.

  • And for the 15-puzzle we have \(1.05\times10^{13}\) states.

We have seen in class that the search can be accelarated with the use of pattern database.

However, these methods increase the space use by the algorithms that can make this techniques intractable for an embbeded system.

In this assignment, you will study the impact of the regular \(\text{A}^*\) algorithms, with the use of pattern database (or not) with linear space search algorithms.

You will explain the results obtained and conclude on which algorithms are more appropriate depending on the situation.

Implementation

All the code needs to be written in Python.

First, you need to implement the \((n^2 -1)\)-puzzle generator that has the following specification:

  • Generates a \((n^2 -1)\)-Puzzle

  • The size of the puzzle will be given in argument.

  • The position of the tiles is random.

  • You can save a \((n^2 -1)\)-puzzle.

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

  • \(\text{A}^*\)

  • DFS Branch and Bound

  • Depth-First Iterative-Deepening

  • \(\text{IDA}^*\)

  • Recursive Best-First

The solver needs to take in arguments a \((n^2 -1)\)-puzzle previously generated.

I should be able to run your code just by doing something similar to:

python puzzle --solver <name_of_the_algorithm> --puzzle <name_of_the_puzzle>

I have some recommendations to generate results:

  • Save the result for each simulation.

  • For the same size of puzzle generates different puzzles.

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

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.

Reminder

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

    • Experiments 1

    • Experiments 2

  • Results

    • Result of experiment 1

    • Result of experiment 2

    • Summary

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