CMPT 317 Winter 2023 Introduction to Artificial Intelligence Assignment 1

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CMPT 317

Winter 2023

Introduction to Artificial Intelligence

Assignment 1

Search Problems

The Water Jugs problem

Consider the following form of a classic logic puzzle.

You have threejugs, with capacities 15 liters, 7 liters and 4 liters, along with a water faucet with infinite water. You have some target value G, meaning that you want to end up in a situation where you have EXACTLY G liters of water in one of the jugs (it does not matter to you which one).

Your possible actions consist of:

•  Filling a particular jug from the faucet (regardless of whether it was empty or not)

•  Emptying a particular jug onto the ground

•  Pouring water from one jug to another, but you must always pour exactly as MUCH as you can without spilling (Example: if you pour from a (full) 15 liter jug to an (empty) 4 liter jug, you will end up with 11 liters left in the big jug and 4 liters in the small jug)

A solution to a Water Jugs problem consists of a sequence of actions taken from the above possibilities that results in exactly G liters in one of the jugs.

Obviously, if G is either 15, 7, or 4, the solution is trivial: simply fill the matchingjug from the faucet. For other values of G, it may not be so easy and may require a combination of fills, dumps, and transfers.

Question 1 (5 points):

Purpose: To understand the dynamics of a problem

AIMA Chapter(s):  2 to 3.4

Part 1

By hand, without using any program, find a solution to the Water Jugs problem for a target value of 1. List the actions you would need to take to end up with exactly 1 liter of water in one of the jugs, and indicate WHICH jug contains the 1 liter at the end.

Part 2

By hand, without using any program, find a solution to the Water Jugs problem this time for a target value of 2. List the actions you would need to take to end up with exactly 2 liters of water in one of the jugs, and indicate WHICH jug contains the 2 liters at the end.

Part 3

Do you think there are any target values between 1 and 15 that are impossible to achieve with the jugs that you have?  If so, which ones?  There are no right or wrong answers here, just write down your first impression and one or two sentences explaining why.

What to Hand In

• A file named a1q1 .pdf (or .txt, .rtf, .docx) containing your answers to the parts above           Be sure to include your name, NSID, student number, and course number at the top of your file

Evaluation

• 2 marks: Solution listed for 1 liter

• 2 marks: Solution listed for 2 liters

• 1 mark: Impression on impossible values


Question 2 (5 points):

Purpose: To apply uninformed search algorithms

AIMA Chapter(s):  3.1-3.4

For this question, your task is to impelement the Water Jugs problem as a search problem.

You have been provided with several Python files. These include a generalized, object-oriented imple- mentations of the basic search algorithms below:

•  Breadth-first (BFS)

•  Depth-first (DFS)

•  Iterative-deepening (IDS)

Each of the algorithms above can be run using either the Tree search or Graph search variants.                  The only file you need to CHANGE is WaterJugs .py.  This file implements both the State and Problem classes that are used by the search algorithms.  The provided version of WaterJugs .py contains only

method headers.  You need to implement these methods correctly to capture the specific dynamics of the Water Jugs problem, using your understanding of search problem encoding and of AIMA Chapter 3.  When you are done, you can test your implementation by running see_solutions .py with the following arguments:

python   see _ solutions . py   1   ids   graph   10


If everything is working correctly, this should find a solution to the Water Jug problem for the target value of 1 liter.

However, BEFORE you do this, it is crucial that you ensure your state and problem implementation is cor- rect. Testing via search is a BAD idea, as the search may examine thousands or even millions of nodes. A simple example of a test file is provided to give you some testing ideas. You don’t need to hand in this testing, but there is virtually no chance that your implementation will be correct if you don’t do it.

Hint: By far the most common problem in implementing a search problem is "not copying things that need to be copied" when you create a new state. For example, recall that in Python, you can easily create a (shallow) copy of a list like so:

new _ list   =   [ x   for  x   in   old _ list ]


What to Hand In

• Your problem implementation in a file called WaterJugs .py. You do NOT need to re-hand-in any of the other provided files.

Be sure to include your name, NSID, student number, and course number at the top of all documents.

Evaluation

• 5 marks: Your implementation of the State and Problem classes are correct


Question 3 (5 points):

Purpose: To understand the differences between search algorithms

AIMA Chapter(s):  3.1-3.4                                                                                                                                   This question assumes that you have a working State and Problem class for the Water Jugs problem.       For this question, you will run several different provided search algorithms and summarize the results in table.                                                                                                                                                                  Run all of the search algorithms shown in the table below to try to find the solution to a Water Jugs problem with a target value of 2, using a time limit of 10 seconds. You can do this by running see_solutions .py with different command line parameters. A quick look at the code in the file should make it obvious how to do this.

 

BFS-T

BFS-G

DFS-T

DFS-G

IDS-T

IDS-G

# actions in solution

 

 

 

 

 

 

Time used (secs)

 

 

 

 

 

 

Memory used (nodes)

 

 

 

 

 

 

Your table should be neat and readable (use tabs in plain text, or a table in Word, etc). Round or truncate the time values to 3 decimal points worth of precision (i.e. number of milliseconds).

After collecting the data, answer the following questions.

• Overall, which algorithm performed the best for this problem?

•  Do you notice a difference between the tree-search and graph-search variants of these algorithms? Why do you think that is?

What to Hand In

• Your data table as described above. You can use a plain text file, or you can submit a MSWord doc- ument, or PDF. Name your document a1q3_TABLES with an appropriate extension (e.g., txt, pdf, docx, etc).

• Your answer about the search approaches. This can be in the same document as your table.        Be sure to include your name, NSID, student number, and course number at the top of all documents.

Evaluation

• 3 marks: Your tables are neat and show plausible results

• 2 marks: You analyzed the data and showed an understanding of the difference between tree and graph search


2023-01-29