Module: Artificial Intelligence

Assignment: Solution of n-Tile Problems

Learning outcomes

· Improve your understanding of basic and advanced search methods learnt in the course after applying and implementing them to solve search problems for the given n-tile puzzle.

· Enhance your Python programming and problem-solving skills for Artificial Intelligence application.

Specification

Overview

The aim of this coursework is to develop solutions for a classical AI search problem, to contrast the efficiency of the techniques implemented, and suggest how the techniques can be adapted to the solution of a variant of the problem.

Description

In this coursework you are asked to implement two state space search algorithms: Iterative Deepening Depth First Search (IDDFS) and Iterative Deepening A* (IDA*) for the solution of the n-tile problem. You are also asked to suggest how a variation of the problem could be solved efficiently. See Parts 1 and 2 for detail.

Part 1. Solution of n-tile problems (programming in Python)

Using the state representation seen in lectures, a state corresponding to the configuration of the 8-tile puzzle in the figure below can be described as

[2, 2, [[1, 2, 3], [4, 5, 6], [7, 8, 0]]]

You are asked to solve the following 8-puzzle instances, each with a corresponding goal state, in the smallest number of moves.

You have to create Python code to solve the instances with the Iterative Deepening Depth First Search (IDDFS) and Iterative Deepening A* (IDA*).

For each instance, both codes you have implemented for the IDDFS and IDA* should output to the console with the following information and results:

(1) Case number.

(2) The number of moves to solve the case (i.e. the number of states – 1 in the shortest path from the initial state to the goal).

(3) The number of nodes opened, that is, the number of yield made by the move

method during the search for a solution.

(4) The computing time the search took.

For the IDDFS, you are allowed to reuse/adapt the move method provided in our lecture notes. You can also reuse the DFS code provided.

As seen in the lab exercises, note that you may have to deal with the fact that Python lists are passed by reference. Hence, you may consider implementing a deep copy approach.

For the IDA*, you should rely on an h function made of the sum of evaluation functions of the numbered tiles (not including tile “0”), where the evaluation of a tile is the Manhattan distance between its position in the current state and its position in the goal state. This indicates the minimum number of moves that tile has to make to get into its final position.

Your code should also work for different n-tile designs; for example, 15-tile puzzle.

Part 2. Problem representation (problem-solving)

The objective of this part is not to provide code, but to explain how a variation of the n-tile problem (here called new problem) could be solved, assuming that you are addressing a programmer who has read your code for Part 1 and is sufficiently experienced on the topic.

First, in the new problem columns in the grid wrap around, i.e. the last row of the grid is a neighbour of the first row. For example, in the following configuration

the blank tile can be exchanged with tile number 3 to produce:

Question 2.1. What would be the changes to make to your IDA* code for Part 1 to consider this change into the n-tile problem specification?

In fact, the new problem also allows an extra type of move that consists in shifting all the rows circularly down or up by one position. For example, from the state

a down shift would produce

while an up shift would produce

Also, in this problem the cost of such shift moves is zero.

Question 2.2. Explain how you would modify your IDA* code for part 1 to solve this problem efficiently?

Question 2.3. What physical design of an n-tile-like puzzle would correspond to this problem? If you are not aware of any, how could you design one? Explain how it would work.

Relationship to formative assessment

Lecture slides and lab exercises provide the baseline to design solutions for the n-tile problem. Extension of work on search methods seen in labs.

Deliverables

You are required to produce two independent Python programs to solve the n-tile problem using:

1. Iterative Deepening Depth First Search (program should be named “IDDFS.py”)

2. Iterative Deepening A* (program should be named “IDAstar.py”)

Your programs must contain a function named solve_puzzle with two parameters (start_state and goal_state) and will return the output data described in Part 1. The aim of the function is to provide an entry point to test your work. Failure to define the solve_puzzle function may result in marks penalty.

def solve_puzzle(start_state, goal_state):

# Your code. You can make calls the methods you create. return (moves, yields, time, path)

You must provide a comment at the start of each program that contains the results you were asked to output, that is the output of the solution method used in the program for each of the provided instances in the order they are listed in this specification.

Note that solve_puzzle function returns the path (sequence of moves) to solve a test case from the initial to the goal state. It is not necessary to include the path in the comment at the start of each program along with the output results.

The code provided in the lectures and labs uses Python’s generators to create of new states. Your code must also rely on generators. Failure to implement generators may result in marks penalty.

Your Python code must be well structured, tidy, and well documented (i.e. adding comments to describe functions, generators, and lines that you consider very important).

In addition, you must answer Questions 1 and 2 of Part 2. The answers should be provided in a Word document named “Part2.docx”. Use the Part2.docx file provided on BB as a template (not a Word template). The answer to this part must not exceed one page. The submission must strictly follow the specification of the provided template, i.e. fonts, font sizes, line spacing and header/footer/margin sizes should not be changed. Any change or one-page exceed would result in a rejection of the document and a zero mark for Part 2 will be given.

Submission

Submit your two Python source files and your Word document as separate files to the designated point on the blackboard by the deadline.

You must not zip your three files into one compressed zip file.

Resources

· Lecture notes.

· Labsheet solution on search.

· Python tutorial: https://docs.python.org/3.7/tutorial/index.html

· Best practices for high-standard coding https://peps.python.org/pep-0008

Marking scheme

The Iterative Deepening Depth First Search program is worth 20 marks: 10 marks for the correctness on the test cases, 5 marks for code efficiency and robustness, and 5 marks for readability and code quality.

The Iterative Deepening A* program worth 50 marks: 20 marks for correctness on test cases; 25 marks for efficiency and robustness, and 5 marks for readability and code quality.

The answers to Part 2 are worth 30 marks: 20 marks for Q 2.1, 5 marks for Q 2.2 and 5 marks for Q 2.3.

Although readability of programs only counts for 5 marks at each program, students may be further penalised; for example, if they do not provide sufficient comments, or submit incomprehensible code and the correctness of which cannot be ascertained by the marker in reasonable time.

Total 100 marks.