Artificial Intelligence:

a) Uninformed and Heuristic Search. Simulate the behavior of Breadth-First Search and A* search for the above graph with start node 0 and goal node 7. Show the evolution of the search and the path found, with costs. For each search, indicate whether the solution is optimal. Break ties in ascending order of node number (lower-numbered nodes are expanded first in case of a tie). Breadth-First Search: Path found: _______________________________________________________ Optimal path cost in this case? Y / N A* search: Path found: _______________________________________________________ Optimal path cost in this case? Y / N b) Admissibility. Is the heuristic above admissible? Why or why not? c) Consistency. Is the heuristic consistent? Why or why not? (Use an illustration if it helps.) Is it possible for a heuristic to be admissible but not consistent? Why or why not? d) Heuristic Quality and Efficiency. Is the heuristic worse or better than h = 0? Why? (What does this have to do with the number of nodes expanded?)

h(3) = 3 h(0) = 7 4 3 N h(5) = 1 0 3 7 5 h(1) = 4 4 6 h(4) = 2 h(6) = 2 4 h(2) = 2 1 1 2 6 3 2 4 7 h(3) = 0