Description

Informed and Uninformed Search
40 pts total
1 Defining a Problem
Consider the farmer, sheep, dog, and cabbage problem we discussed in class. (Refer to the slides for the exact problem specification.) Answer each of the following.
1.1 State Space
(2 pts) Describe the state space to this problem. What would the initial state be?
1.2 Possible Actions
(2 pts) Given a general state s, describe what an action means. Given the state (CD, FS) (i.e., the cabbage and the dog are on the left side of the river, and the farmer and sheep are on the right side), give a valid action.
1.3 Transition Model
(2 pts) Given a general state s, describe what the transition model returns.
Given the action you named above, what would the transition model return?
1.4 Goal Test
(2 pts) Given a general state s, describe what the goal test returns.
1.5 Path Cost
(2 pts) What would a potential path cost be, and what would it mean in terms of the search?
2 Uninformed Search

Figure 1: Question 2, 3 Graph
Given the above graph in Figure 1, assume node S is the start state and nodes K, M, and N are goal states. Execute each of the following search algorithms like we did in class. Assume expansion happens from left to right. If you encounter a tie, expand the node that comes first alphabetically (e.g., B before D). For full credit, be sure to show the Expanded (2 pts) and Frontier (2 pts) node lists at each step. Give the final path to the solution you found, along with the corresponding total cost (1 pt for both).
2.1
(5 pts) Breadth-First Search (BFS)
2.2
(5 pts) Depth-First Search (DFS)
2.3
(5 pts) Uniform-Cost Search (UCS)
2.4
(5 pts) Iterative-Deepening Search (IDS)
3 Informed Search
Refer once more to the graph in Figure 1. Assume the values for the heuristic function h(n) are those listed in Table 1, where nodes K – N all have value 4. Assume once more that S is the start state. This time, assume node J is the goal state. Execute each of the following search algorithms like we did in class. Assume expansion happens from left to right. If you encounter a tie, expand the node that comes first alphabetically (e.g., B before D). For full credit, be sure to show the Expanded (2 pts) and Frontier (2 pts) node lists at each step. Give the final path to the solution you found, along with the corresponding total cost (1 pt for both).
Node S A B C D E F G H I J K – N
h(n) 5 1 7 1 3 4 1 1 4 1 2 4
Table 1: Heuristic Function Values
3.1
(5 pts) Greedy Best-First Search
3.2
(5 pts) A* Search