Introduction to AI - Worksheet 8

EXERCISE: 1

Uninformed Search (taken from [Luger 2004])

Give a graph presentation for the search in the farmer, wolf, goat, and cabbage problem.

A farmer with his wolf, goat, and cabbage comes to the edge of a river they wish to cross. There is a boat at the river's edge, but, of course, only the farmer can row. The boat also can carry only two things (including the rower) at a time. If the wolf is left alone with the goat, the wolf will eat the goat; similarly, if the goat is left alone with the cabbage, the goat will eat the cabbage. Devise a sequence of crossings of the river so that all four characters arrive safely on the other side of the river.

Let the nodes represent states of the world, for instance, the farmer and the goat are on the west bank and the wolf and cabbage on the east. Discuss the advantages of breadth-first, depth-first, depth bounded depth-first, and iterative deepening for searching this space.

EXERCISE: 2

Informed Search (taken from [Luger 2004])

The sliding-tile puzzle consists of three black tiles, three white tiles, and an empty space in the configuration

  B   B   B         W   W   W

The puzzle has two legal moves with associated costs:

The goal is to have all the white tiles to the left of all the black tiles. The position of the blank is not important.

  1. Analyse the state space with respect to complexity and looping.
  2. Propose a heuristic for solving this problem. How do greedy search and the A*-algorithm perform with your heuristic. Are the algorithms admissible (that is, are they guaranteed to find a minimal path to the solution)?

EXERCISE: 3

Why may the A*-algorithm miss the optimal solution if the heuristic function h is not optimistic?


© Noel Welsh & Manfred Kerber, 2004, Introduction to AI
16.11.2004
The URL of this page is ftp://ftp.cs.bham.ac.uk/pub/authors/M.Kerber/Teaching/AI/e8.html.
URL of module http://www.cs.bham.ac.uk/~mmk/Teaching/AI/