Assignment 1 Solution

Question 1 (30 points) (Search on the Missionaries and Cannibals Problem)




The “missionaries and cannibals” problem is a variant of the river crossing problem discussed in class. Three missionaries and three cannibals are on one side of the river, along with a boat that can hold one or two people. Find a way to get everyone to the other side of the river without ever leaving a group of missionaries outnumbered by the cannibals on either side of the river. That is, at any time, on either side of the river, if there is a positive number of missionaries and the number of cannibals is greater than the number of missionaries, the missionaries will get eaten. The boat must have at least one person in it to cross the river.




Formulate this problem as a search problem. Be sure to describe the definition of the states, the start state, the goal state, the successor function, and the costs in detail.



Draw the complete search graph, which contains all of the states and all of the arcs based on the successor function.



Draw the search tree of Breadth-First Search until you have expanded 6 nodes.



Draw the search tree of Depth-First Search until you have expanded 6 nodes.



Propose an admissible heuristic function h and describe it in detail. Be sure to explain why it is admissible. Your heuristic will be judged by how good it is.



Describe an optimal solution to this problem and the cost of this optimal solution. You do not need to show how you obtained the solution.






Please submit a writeup containing the answers to all the six questions above.



























CS 486/686 Introduction to Artificial Intelligence Fall 2018







Question 2 (50 points) (A* search on the Traveling Salesperson Problem)




You will implement a search algorithm to solve the Traveling Salesperson Problem (TSP).




In a TSP, a salesperson must start from a city, visit every one of n cities exactly once and return to the starting city. The goal is to find the tour with the lowest total distance. Assume that the distance of traveling from one city to another is the Euclidean distance between the two cities. For example, given two cities with coordinates (x1, y1), and (x2, y2), the distance between the two cities is the square root of ((x1 – x2)^2 + (y1 – y2)^2).




We have provided you with many instances of the TSP problem. You can find them in the file tsp_problems.zip in the Assignment 1 folder on the course website.




The format of each problem instance file is as follows:




<number of cities




<city id <X <Y




<city id <X <Y




… … …




<city id <X <Y




The first line has the number of cities. Each subsequent line contains the letter and the location of one city. On each line, there is a capital letter <city id, followed by the <X coordinate and the <Y coordinate of the city. The X and Y coordinates are integers.




Write a program that uses the A* search algorithm to solve the TSP problem. Let the cost to move from one city to another be the Euclidean distance between the two cities.




Use the following conventions in your program formulation and your implementation.

Assume that A is always the starting city.
Generate the successors of any state in alphabetical order.



Complete the following tasks and write a short report to describe the results.




Formulate the TSP problem as a search problem. Include the definition of a state, the start state, the goal state, and the successor function.



Choose a good admissible heuristic function h and describe h in detail in your



report. Be careful with choosing the heuristic function. For some poor choices of the h function, A* search may not terminate in a reasonable amount of time.




See further instructions on the next page.




3
CS 486/686 Introduction to Artificial Intelligence Fall 2018







Implement and run A* search with your heuristic function h on the provided TSP problems.



If your program spends more than 5 minutes on a 10-city TSP problem, something is going horribly wrong. Terminate your run, rethink your heuristic function and debug your implementation.




Otherwise, if you program can solve a 10-city TSP problem quickly, then it is like that your heuristic and implementation are fine.




For each number of cities (from 1 to 16), determine and plot the average number of nodes that A* search generates for each number of cities. We have provided you with 10 TSP problem instances for each number of cities (from 1 to 16).




Based on the plots from part (c), extrapolate the number of nodes A* search would generate for a 36-city TSP problem. (You may want to use a logarithmic scale on the y-axis.)



Give an estimate of how long the A* search with your heuristic function would take to solve a 36-city TSP problem instance.




(You can try running your implementation on the 36-city problem instance, but we do not require your implementation to solve this problem instance.)




Repeat part (c) with the heuristic function h(n) = 0 for all n.



For each number of cities (from 1 to 16), determine and plot the average number of nodes that A* search generates.




If the search takes more than 5 minutes (or you run out of memory) on any of the runs, then you can stop early and record that it did not terminate.




Based on the plots from part (e), give an estimate of how long the A* search with the heuristic function h(n) = 0 for all n would take to solve a 36-city TSP problem instance.



Discuss the difference in the performance of A* search when using the two different heuristic functions. 1-2 paragraphs should suffice.



See a list of items that you need to submit on the following page.

























4
CS 486/686 Introduction to Artificial Intelligence Fall 2018







Please submit the following:




Your problem representation.



The description of your heuristic function.



A well document copy of your code.



A plot of the average number of nodes generated for each number of cities for your heuristic function.
A discussion of how you expect A* search to perform on a 36-city problem instance for your heuristic function.
The plot of the average number of nodes generated for each number of cities for the heuristic function h(n) = 0.
A discussion of how you expect A* search to perform on a 36-city problem instance for the heuristic function h(n) = 0.
A discussion on the difference in performance when using the two different heuristic functions.




































































































































5
CS 486/686 Introduction to Artificial Intelligence Fall 2018







Question 3 (50 points) (CSP and backtracking search on Sudoku)




In the question you are asked to implement a CSP algorithm for solving Sudoku puzzles. Sudoku is a simple game of deduction, usually played on a 9x9 grid. In the goal state, each number from 1 to 9 appears exactly once in each row and column on the grid. Additionally, the grid is subdivided into 9 3x3 non-overlapping sub-grids, and each number must appear exactly once in each sub-grid. A Sudoku puzzle usually starts with some numbers filled in, so that there is a single unique solution. An example of such a puzzle is given below:



































































We have provided you with many instances of the Sudoku problem. You can find them in the file sudoku_problems.zip on the course website. In a particular sub-directory, all puzzles in a particular sub-directory have the same number of initial values (corresponding to the name of the sub-directory).




Each file contains 9 rows of exactly 9 numbers. Numbers within a line are separated by whitespace. The value 0 is used to indicate a blank space in the grid. For example, the first line of the example puzzle above would be written:




530070000




See instructions on the next page.











































6
CS 486/686 Introduction to Artificial Intelligence Fall 2018







Write a formal description of Sudoku as a CSP, giving a list of variables, their domains, and the constraints between them.



Implement three version of a CSP solver for Sudoku. For each version, count the total number of variable assignments it makes (including when it backtracks).



Version A : Standard backtracking search




Version B : Standard backtracking search + forward checking




Version C : Standard backtracking search + forward checking + heuristics (minimum-remaining-values heuristic, degree heuristic and least-constraining-value heuristic).




Run each of the 3 versions of your solver on each problem instance, counting the number of variable assignments made on each instance. To avoid spending a (very) long time collecting data, your solver should ‘give up’ if it needs to do more than 10,000 variable assignments.



For each version of your solver, create a plot of your findings. The x-axis has the number of initial values, and the y-axis has the average number of variable assignments for each initial value.



You can produce three different plots (one for each version of your solver) or include the three plots in a single graph. Make sure that everything is well labelled on your plots.



Describe your findings and provide an explanation for what you observe. 1-3 paragraphs should suffice.



Please submit the following.




Your CSP representation.



A well-documented copy of your code.



The plot of the average number of variable assignments against the number of initial values for the provided Sudoku problems.
A discussion of your findings and an explanation for why your program behaves as it does.






























7