Reference no: EM132391050

CMPT 317 Introduction to Artificial Intelligence

Department of Computer Science - University of Saskatchewan, Canada

Assignment - AIMA Chapter 6: Constraint Satisfaction

Question 1 -

Purpose: To learn the API of the CMPT 317 CSP Solver (provided). To express a simple Constraint Satisfaction Problem in terms of variables, domains, and constraints, and get a Solver to solve it.

Degree of Difficulty: Easy.

The AIMA textbook uses a small example of Map Colouring in Chapter 6.1, and the lecture notes use it as well. The problem, stated informally, is to assign one of a small number of colours to each region in a map, so that no adjacent regions have the same colour.

On Moodle you will find an example file showing how to formulate the map colouring problem used in the AIMA textbook (and in the lecture slides), and use the Solver to solve the problem. Use the example as a guide for solving the following examples:

(a) A simple map is shown below. There are 5 regions, labelled 0-4. It can be coloured with three colours. Note: labels are identifiers for each region; labels are not colours!

Using the example, and Python, write a short script that sets up the problem, solves it, and produces an answer.

(b) A more complicated map is shown below. There are 8 regions, labelled 0-7.

This map cannot be coloured with 3 colours, but it can be coloured with 4 colours. Using the example, and the solver, write a short script that solves the problem with 4 colours, but fails when just 3 colours are used.

When completed, your script should run on the command-line, as follows:

UNIX$ python3 A3Q1_A .py

...

UNIX$ python3 A3Q1_B .py

...

Question 2 -

Purpose: To make use of unary constraints provided by the Solver API. To use the solution provided by the Solver API in a simple Python script.

Degree of Difficulty: Easy.

In class we've been using the Latin Square problem, which is informally described as follows: We take a N x N grid, and fill it with the numbers 1 through N, so that each number appears exactly once on each row and column. Problems of varying degree of difficulty can be created this way, if some of the cells in the grid are already filled in. The puzzle is to fill in the remainder of the cells. This problem is a little simpler than the popular Sudoku problems.

We can formulate this problem in terms of variables (the blank cells) and domain values (1 through N), and constraints (cells on the same row and column cannot be equal). But as you have noticed, there is information in the square in the form of cells that are already filled in by numbers.

The main purpose of this question is to give you good reason to work with unary constraints. Given the square above, you could reason that the top left cell cannot be 2, 3, or 4, using the numbers on its row and its column. In your script, you might hard-code an initial domain for this variable using the result of that reasoning. In a sense, you worked out some of the solution yourself. But imagine a bigger problem, e.g., size N = 100. You wouldn't want to do this reasoning yourself for all the cells before getting the computer to solve the rest.

Unary constraints allow us to automate the reasoning. In the Solver API, there is a Unary constraint class called UnaryNotEquals which lets you tell the Solver that a given variable cannot take a given value. For example, the top left cell cannot be 2. The unary constraint API requires one variable, and a single value, so you'll need more than one unary constraint for each blank cell.

This is a simple idea, but we can now imagine a program that could read a Latin Square problem from a file. For blank cells, we create variables. Binary constraints (not equals) are added between all pairs of variables appearing in the same row and column. And unary constraints are created for the numbers already entered in the grid.

There are a few details left to work out. Write a script that can solve the above problem, using unary constraints, and binary constraints without "hard-coding the initial domain" as described above. Don't worry about reading problems from a le (see Question 5). Figure out how to use the unary constraints with your variables and domains.

Finally, the Solver API returns a SearchTerminationRecord object, similar to the one in Assignment 1. It's a bit simpler, because the Solver only uses DFS, so we really don't need to keep track of the space used by the frontier. The record has the following public attributes:

• success: A Boolean value indicating whether a solution was found in the time available.
• result: A Python dictionary, whose keys are the variable identifiers you specified in your script, and the values the Solver worked out to satisfy the constraint.
• time: A floating point value showing the time taken in seconds. If this value is larger than your time limit, the Solver process was terminated before an answer was given. If the time is less than your time limit, then the CSP you specified has no solution; there is no way to satisfy the constraints.
• nodes: An integer value showing how many nodes the Solver expanded in the search. This is a time-independent measure of computational effort.

In Assignment 1, it was enough to use the display() method.

In your script for this question, you should use the result dictionary to discover the values the Solver found for each variable, and then display a nice square with all the solution values in the right places. This will require a bit of thoughtful programming, but it is not an AI problem.

Question 3 -

Purpose: To practice creating constraints using the relation representation.

Degree of Difficulty: Easy.

The N-Queens problem is to place N Queens on a N x N grid so that no two Queens are in the same row, column or diagonal. Below is an example of one solution to the N = 8 case:

Figure2

Formulate this problem as a Constraint Satisfaction Problem in terms of variables, domains, and constraints. Then use the Solver API to solve it. When you're finished, your script should take a value for N on the command-line, and display a solution (if given enough time).

The Solver API does not have a built-in constraint for checking diagonals. But this is not a big problem: the constraint class BinaryRelation can represent any arbitrary binary constraint. All you need to do is figure out which pairs of values are allowed, if two queens cannot be on the same diagonal.

When completed, your script should run on the command-line, where N is given as an argument. Optionally, you can allow the time limit to be set on the command-line as well.

The diagram above is optional. However, your script should use the result dictionary returned in the SearchTerminationRecord object, and check the solution. This is not optional.

Hints: Consider the queen in column 3 and another queen in column 6 (assuming N ≥ 6).

• These queens are on the same row if their row values are equal. To prevent this, you may use the BinaryNotEquals constraint. Yes, you can add multiple constraints between the same pair of variables. All constraints must be satisfied!
• These queens are on the same diagonal if the difference in their row number is equal to the different in the column number. To allow upward or downward diagonals, take the absolute difference in rows, and the absolute difference in columns. These differences cannot be equal. See the diagram below, where k is used to represent a distance in rows and columns; here k = 3.

Write a simple script hard-coded for N = 4 first. When you get correct solutions to that, you can generalize for any given N. Don't worry if your script can't solve for large N in reasonable time.

Question 4 -

Purpose: To formulate a non-trivial problem in two different ways, and compare the results.

Degree of Difficulty: Tricky.

AIMA Exercise 6.3 describes a problem to construct crossword puzzles. The idea is to try to fill a grid with letters so that sequences of grids horizontally and vertically form real words. The problem came up in lecture as well.

For example, consider the following grid:

There are 8 boxes (we don't use the grey box). This grid can fit four 3-letter words. The words read horizontally, left to right, and vertically top down. As is common for crosswords, we can label the 4 sequences using the numbers in the top left corner of some boxes. The grid needs a 3-letter word starting at box 1, going across, and another word starting at box 1 going down. Similarly, we need a 3-letter word vertically starting at box 2, and a 3-letter word horizontally starting at box 3.

The problem is to find 3-letter words that t into the grid. Words that intersect have to use the same letter at the intersection. In the example above, the word at 1 Across could be ACE so the word at 2 Down has to start with E, maybe EYE.

This is a construction problem, because we are just trying to find words that fit. There are no clues to give hints for the words. You might use a program like this to construct a crossword puzzle, and then add clues later.

To keep things simple, we'll only use 3 letter words, and we'll have 3 examples to work on. The above grid (the donut), and the following two grids (a square, and a braid):

On Moodle, you'll find a text file containing the 3 letter words you're allowed to use. This list was borrowed from a website for other word games.

The problem can be formulated in two rather distinct ways (as mentioned in AIMA Execise 6.3):

1. Variables are sequences of locations for complete words, e.g., 1-Across, 1-Down, 2-Down, etc.

2. Variables are the locations for individual letters.

Of course, you'll need to think about domains and constraints for the two formulations, and thinking about those is part of the problem. What are appropriate domains? What are appropriate constraints? This question is about trying to work out these issues with little guidance from the question.

Formulate the problem using both approaches above, writing two separate scripts. They'll set up the 3 problems, and solve them. Make sure they run from the command-line as before.

Compare the performance of the Solver, in terms of time, and nodes expanded (use the information in the SearchTerminationRecord). Which of the two methods was better (time, or nodes expanded)? Which was easier to formulate?

Question 5 -

Purpose: To apply the Solver API to the Graph Colouring Problem.

Degree of Difficulty: Moderate.

In this question, you'll write a Python script to solve the Graph Colouring Problem. Like Assignments 1 and 2, there are a bunch of les full of problem instances to solve. You'll write the script here, and generate results which you will present and discuss in the next question.

The graph colouring problem is basically the same as the map colouring problem (Question 1), except we colour vertices in a graph instead of regions in a map. In Question 1, you were given a couple of diagrams, and it was your task to identify which regions were adjacent, and specify the appropriate constraints. In this question, we will use the language of undirected graphs to represent the map. A vertex in the graph is a region, and the edges in the graph indicate which regions are adjacent. For example, here's a small graph (on the left) and a corresponding map-like diagram on the right. You might recognize this one from Question 1.

The vertices (and regions) have identifiers consisting of the integers 0 through 4 (inclusive). These are vertex names, not colours! There are 6 edges in the graph, and 5 vertices. This particular example can be coloured with k = 3 colours.

A number of example files have been provided. Each file defines some number of graphs. All examples, even the very largest, can be labelled with k = 4 colours; some of the smaller ones can be labelled with just k = 3 colours.

Each example graph is described using an adjacency list representation, as follows. Suppose there are 5 vertices in an example graph. The vertices will be represented by integers 0 through 4. Each vertex will appear as the first number on a line, which is then followed by a sequence of all of its neighbours in the graph.

The first line indicates that there are exactly 5 vertices in the graph, and therefore exactly 5 lines in the description. Each line after the first describes one of the vertices. The line starting with 0 indicates that there is an edge from vertex 0 to vertex 3, and another edge from vertex 0 to vertex 4. The vertex 1 has edges to vertices 2 and 4. The vertex 2 has edges to vertices 1 and 4. Etc.

There are multiple graphs in each file. Each file of graphs will start with single integer that indicates how many graphs are in the le. There is exactly one blank line following each example graph. The files generally describe graphs of increasing size, and so will provide more challenge for your implementation. But they are randomized, so they are not strictly increasing in difficulty. By chance, it might be easier to colour a specific graph with 500 vertices than some other graph with only 400 vertices.

Write a Python script that reads a given file of example problems and uses the Solver API to solve the problems in the file simpleGC.txt as follows.

The command-line above has 3 command-line arguments: the file of problems to solve (simpleGC.txt), the number of colours to try (4), and the time limit in seconds (10). Most of the problems can be solved in less than a second.

Question 6 -

Purpose: To apply local search to a search problem, and present results.

Degree of Difficulty: Easy. Just run your implementation on the datales given, and produce the tables. It might take some time to gather the results.

Use the program you wrote from Question 5, and use it to solve the problems in the given problem set files:

• a200.txt: 10 graphs with 200 vertices each.
• b200.txt: 10 graphs with 200 vertices each.
• c400.txt: 10 graphs with 400 vertices each.
• d400.txt: 10 graphs with 400 vertices each.

Produce the following table (one for each file):

Problem set	Number of Colours
	k = 3			k = 4
	# solved	Ave Time	Ave Nodes	# solved	Ave Time	Ave Nodes
a200.txt
a200.txt
a400.txt
a400.txt

For this table, use a time limit of 10 seconds, and include in your averages all the data, even if no solution was found.

In your tables, limit your precision to 5 significant figures (roughly). In other words, don't produce tables that show all 15 digits of a double-precision floating point number. Only the first 5 or so digits are meaningful. You can do this in your program by formatting your output, or you can do this by hand as you enter the data.

Questions to answer -

1. For a graph colouring problem with N vertices and k colours, how big is the search tree?

2. Using your data for k = 4 on the problem set a200.txt, calculate an average number of nodes per second to solve the problems, then predict how much time it would take to search the full search tree for N = 200 and k = 4 (i.e., if every option were tried, and only a complete assignment was checked for consistency with the constraints - this is the very worst case).

3. Compare the average number of nodes reported by the Solver with the value for N on each set. Explain why the average number of nodes explored is so close to N.

4. Some of the problems in d400.txt may have been terminated before the Solver was able to find a solution. But the Solver probably found a solution for every single problem in c400.txt in much less than a second. Explain why.

5. For fun, let your program run for a long time to try to solve the problems that did not get solved in the 10 second time limit. Did you eventually find a solution, and if so, how long did it take. If not, what is the longest amount of time that you tried?

Attachment:- Introduction to Artificial Intelligence Assignment Files.rar