COMP3411/9414 Artificial Intelligence
Session 1, 2019

Week 4 Tutorial

Activitity 4.1 Path Search Algorithms on a Graph
Consider the task of finding a path from start state S to goal state G, given the distances and heuristic values in this diagram:
For each of the following strategies, list the order in which the states are expanded. Whenever there is a choice of states, you should select the one that comes first in alphabetical order. In each case, you should skip any states that have previously been expanded, and you should continue the search until the goal node is expanded.
  1. Breadth First Search
  2. Depth First Search
  3. Uniform Cost Search [Hint: first compute g() for each state in the graph]
  4. Greedy Search, using the heuristic shown
  5. A*Search, using the heuristic shown
Activitity 4.2 A*Search for the 8-Puzzle
Consider the following arrangement of tiles in the 8-puzzle:

123
85
476

Keeping in mind that the goal state is:

123
456
78

Trace the A*Search algorithm using the Total Manhattan Distance heuristic, to find the shortest path from the initial state shown above, to the goal state.

Activitity 4.3 Relationships Between Search Strategies
Prove each of the following statements, or give a counterexample:

  1. Breadth First Search is a special case of Uniform Cost Search
  2. Breadth First Search, Depth First Search and Uniform Cost Search are special cases of best-first search.
  3. Uniform Cost Search is a special case of A*Search

Activitity 4.4 Heuristic Path Algorithm
The heuristic path algorithm is a best-first search in which the objective function is
f(n) = (2-w)g(n) + wh(n)
What kind of search does this perform when w=0? when w=1? when w=2?
For what values of w is this algorithm complete? For what values of w is it optimal, assuming h() is admissible?

Activitity 4.5 Understanding Informed Search Algorithms with Mazes
Discuss your findings and insights from the 'Fun with Mazes' activity. Compare your findings and discuss any discrepancies.
  1. Use the widget to create a maze for which Bidirectional Search would find a solution faster than Breadth First Search.

  2. an environment for which Greedy Search takes much longer than A*Search.

  3. an environment for which Greedy Search produces a path that is much longer than the optimal path.

  4. an environment for which A*Search with the Euclidean Distance heuristic takes much longer than with the Manhattan Distance heuristic.

  5. an environment that is interesting for some other reason.