COMP3411/9414 Artificial Intelligence
Session 1, 2019

Week 3 Tutorial

Activity 3.1 (Exercise 3.9 from Russell & Norvig)
The "Missionaries and Cannibals" problem is usually stated as follows: Three missionaries and three cannibals are on one side of the river, along with a boat that can hold one or two people. Find a way to get everyone to the other side, without ever leaving a group of missionaries in one place outnumbered by the cannibals in that place. This problem is famous in AI because it was the subject of the first paper that approached problem formulation from an analytical viewpoint (Amarel, 1968). (You can even play the puzzle on-line at www.learn4good.com/games/puzzle/boat.htm")

  1. Formulate the problem precisely, making only those distinctions necessary to ensure a valid solution, and draw a diagram of the complete state space.

  2. Solve the problem optimally using an appropriate search algorithm; is it a good idea to check for repeated states?

  3. Why do you think people have a hard time solving this puzzle, given that the state space is so simple?

Activity 3.2 Refining Your Understanding of Searches using Mazes
Discuss your findings and insights from the 'Fun with Mazes' activity. Compare your findings and discuss any discrepancies.
  1. Generate a random Tree Maze and compare the running time of Breadth First Search and Depth First Search on this maze. Repeat this for a couple of other random Tree Mazes. Time the algorithms with a stopwatch if you can. Which algorithm is faster?
  2. Repeat the steps from part (a), this time with Concentric Graph Mazes. Which algorithm is faster?
  3. Use the widget to edit a maze by clicking on the coloured squares, and then clicking on the Maze. Try to design a maze for which BFS finds a solution considerably faster than DFS. You can change the structure of the maze, and specify a starting and ending point anywhere inside the maze. Try to (briefly) explain in words what makes your environment easy for BFS but hard for DFS.

  4. Use the widget to create a maze for which DFS would find a solution considerably faster than BFS. You should assume that there can be multiple ending points (red squares) and that the algorithm only needs to reach one of them. Try to explain in words what makes your environment easy for DFS but hard for BFS.

  5. Try running Iterative Deepening Search on a random maze. Why is it so slow?
    For which type of problem (probably not a maze) would IDS be superior to both BFS and DFS?
Activity 3.3 Further Discussion
Any remaining tutorial time can be used for further discussion related to uninformed search strategies, including the Pick a Problem and Map out the State Space activity on the Path Search Problems page; for example:

If additional time remains in the tutorial, you can skip ahead to cover Activities 4.3 and 4.4 from next week's tutorial questions.
Answers to Romania Path Search Activities: