Artificial Intelligence Assignment 1

CS C 421 Artificial Intelligence
Assignment 1
 (e-submission only, submit code and results)
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.