In anticipation of the first beach day of the year, plan your route from Bristol to Matunuck Beach using the driving distances below.

		Distance (cost)
Bristol	Newport	15
Bristol	Fall River	10
Bristol	Providence	14
Fall River	Providence	22
Providence	Kingstown	30
Newport	Jamestown	5
Kingstown	Jamestown	12
Kingstown	Matunuck	6
Jamestown	Matunuck	20

The start state is Bristol and goal is Matunuck. Assume that you may only travel through the towns and cities listed above, that the only roads are those connecting cities for which I have given a distance, and that you may travel in either direction between listed pairs of towns.

a.Formalize this problem as a state space search problem (define the states, actions, path costs, and goal test)

b.Draw the state space graphic.(1 point) Draw the first four levels of the search treed.For each of the following search strategies give 1) the path returned and 2) the number of nodes expanded (Recall that a node is expanded when it is removed from the frontier). To cut down on the number of different correct solutions, please add states alphabetically when adding to the frontier and break ties in a priority queue alphabetically according to the final node in the path. Use an expanded set to avoid cycles and the heuristic given below.

i.Depth first

ii.Breath first

iii.Uniform cost

iv.Iterative deepening

v.Greedy best first vi.A*

vii.Branch and bound

Location	Heuristic
Bristol	10
Fall River	12
Providence	8
Jamestown	2
Newport	5
Kingstown	3
Matunuck Beach	0

d. Is the given heuristic admissible? Support your answer.

e. Is the given heuristic consistent? Support your answer.

f. Construct an admissible heuristic that dominates the heuristic given above. Give justification that it is admissible and dominates.