CS C 421 Artificial Intelligence

Assignment 1

1. (2 points) Solve the problem of finding a route from Timisoara to

Bucharest using the various uninformed search strategies (both tree-search

and graph-search variants) discussed and report statistics (number of

expansions and solution cost). See the slides for the Romania map. The

accompanying code has implementations for several search strategies, but

not all, e.g. iterative deepening is not implemented (you should implement

it).

2. (2.5 points) Use the straight-line heuristic function (see slides) to solve the

Romania route problem (starting from Timisoara going to Bucharest) efficiently

using A* TreeSearch and A* GraphSearch. Report statistics. Draw (or print out)

the final search tree, and add at each node its path cost value (g), the heuristic

function value (h), their sum (f=g+h), and the order of expansion, e.g. the root

will be 0, then the next node expanded will be 1, etc.

You can solve this by hand on paper, or create a PrintTree method which

takes the list of all created (search-tree) nodes and prints them in a nested

form, e.g.

Timisoara(g=0.0, h=329.0, f=329.0) order=0

Arad(g=118.0, h=366.0, f=484.0) order=3

…

Lugoj(g=111.0, h=244.0, f=355.0) order=1

…

3. (2 points) Consider the following problem:

Three missionaries and three cannibals seek to cross a river, say

from the left bank to the right bank. A boat that may be navigated

by any combination of one or two people is available on their side

of the river. If cannibals outnumber the missionaries on either side

of the river at any time, the cannibals will indulge in their

anthropophagic tendencies and do away with the missionaries.

Find a sequence of boat trips that will permit all the missionaries

and cannibals to cross the river safely.

Code this problem. Partial code provided. You should fill

in the TODO parts.

Solve the problem using the various uninformed search

control strategies provided.

4. (2 points) Consider the following problem (Water Jugs Problem). You

have three jugs, measuring 12 gallons, 8 gallons, and 3 gallons, and a

water faucet. You can fill the jugs up, or empty them out from one another

or onto the ground. You need to measure out exactly one gallon.

Consider a variant of the Water Jugs Problem in which we are interested

in minimizing the amount of water that must be poured. Filling the large

jug when it is empty requires pouring 12 gallons into it. Likewise,

transferring water from a full large jug into an empty small jug requires

pouring 3 gallons. A lazy person might not mind a longer solution to the

problem if it in fact reduced the amount of water they had to heft and pour.

Attempt to solve the problem using the various uninformed search control

strategies provided and report statistics.

5. (1.5 points) Devise a heuristic function for the missionaries and cannibals

problem. Then, solve the problem using that heuristic and report statistics.