Lecture 2

 Searching

Searching is very important in AI and appears everywhere.

Once we have a good representation for a problem we need to search for a solution.

We will look at the following methods:

  1. Some Path
    1. Depth-first
    2. Hill climbing
    3. Breadth-first
    4. Best-first
  2. Optimal Path
    1. British museum
    2. Branch and bound
    3. A*
  3. Games
    1. Minimax
    2. Alpha-beta pruning
    3. Progressive Deepening
    4. Heuristic pruning
    5. Heuristic continuation

Some Path

e.g. Find a way out of a maze or

Find the quickest route from Auckland to Wellington.

For the first, any route will do but for the second we want a near-optimal route.

We have a semantic net.

Easy solution: explore all possible paths.

We must avoid any repetition in the solution.

e.g. Auckland -> Hamilton -> Tauranga -> Taupo -> Hamilton

Bad Idea

The net is now a tree. For a net with n nodes the tree can have no more than n levels.

Depth First Search

If all that is required is a solution then the tree can be searched by looking at all the terminal nodes(those at the bottom) one at a time.

                     O1
                    / \
                   O2  O
                  /|\  |\
                 O3O O O O
                /| | |\  |\
               O4O9O O O O O
              / \  |  / \  |\
             O5  O6O O   O O O
                / \     / \
               O7  O8  O   O

Order that nodes are visited for depth first search.

Search Procedure:

  1. Form a one element queue consisting of the root node.
  2. Until the queue is empty or the root node has been reached, determine if the first element in the queue is the goal node.
    1. If it is the goal then do nothing
    2. otherwise: Remove the first element from the queue and add its children (if any) to the front of the queue.
  3. If the goal has been found then success otherwise failure.

Hill Climbing

If we can order the choices so that the most promising are explored first then the search will be more efficient.

Need a Heuristic

A heuristic is a measure of how close the solution is. For example, distance from Wellington or distance from maze exit would be good heuristics.

To Hill Climb:

  1. Form a one element queue consisting of the root node.
  2. Until the queue is empty or the goal has been reached, determine if the first element in the queue is the goal node.
    1. If it is the goal then do nothing
    2. otherwise: Remove the first element from the queue, sort the first element's children (if any) by estimated remaining distance, and add to the front of the queue.
  3. If the goal has been found then success otherwise failure.

e.g. find the highest point in Auckland city(OK).

or find the tallest building in Auckland city(not OK).

Two problems:

  1. Escaping from local solutions:
  2.               /\
          __     /  \
        _/  \___/    \
       /
  3. There is no hill to climb:
  4.             ____  
               |    |
    ___________|    |______
       

Breadth First

                     O1
                    / \
                   O2  O3
                  /|\  |\
                 O4O5O6O7O8
                /| | |\  |\
               O9O O O O O O
              / \  |  / \  |\
             O   O O O   O O O
                / \     / \
               O   O   O   O

Search Procedure:

  1. Form a one element queue consisting of the root node.
  2. Until the queue is empty or the goal has been reached, determine if the first element in the queue is the goal node.
    1. If it is the goal then do nothing
    2. otherwise: Remove the first element from the queue and add its children (if any) to the back of the queue.
  3. If the goal has been found then success otherwise failure.

Best First Search

Use a heuristic to decide which node to look at next.

Search Procedure:

  1. Form a one element queue consisting of the root node.
  2. Until the queue is empty or the goal has been reached, determine if the first element in the queue is the goal node.
    1. If it is the goal then do nothing
    2. otherwise: Remove the first element from the queue and add its children (if any) to the queue, and sort the entire queue by estimated remaining distance.
  3. If the goal has been found then success otherwise failure.

In practice the queue need not be sorted, a hash table can be used.

Comparison of various search methods:

Optimal Path

Now we need to find not just a solution, but the best solution. Assume there is a cost associated with every node.

British Museum

Search all possible paths. Use Breadth or Depth first but continue after a solution has been found. Choose the solution with the lowest cost.

Impractical except for trivial problems.

Branch and Bound

Instead of searching all possible paths, search in order of lowest cost. The first path found will be optimal.

Search Procedure:

  1. Form a queue of partial paths. Let the initial queue consist of the zero length, zero step path from the root node to nowhere.
  2. Until the queue is empty or the goal has been reached, determine if the first path in the queue reaches the goal node.
    1. If the first path reaches the goal node then do nothing
    2. otherwise:
      1. Remove the first path from the queue.
      2. Form new paths from the removed path by extending one step.
      3. Add the new paths to the queue.
      4. Sort the queue by total cost, with least cost at the front.
  3. If the goal has been found then success otherwise failure.

A*

As well as a cost associated with each path, there may be a minimum possible distance to the goal. For example consider the following:

      T---4----G--4--C
     /\        |         W
    /  \       5        /
   3    5      |       3
  /      \     |      /
 A---4----H-2--B--4--P

Problem: find the optimum path from A to W

The minimum possible distance from any node to W is the straight line distance to W. We can use this to help the branch and bound algorithm.

Instead of using the cost, use the cost + minimum distance left. This will discourage steps away from the solution.

Some paths may be redundant e.g. A->T->H is a valid path but A-> H has a lower cost and so the former is redundant.

The A* procedure is a branch and bound search with the inclusion of a lower-bound estimate of remaining cost and removal of redundant paths.

Search Procedure:

  1. Form a queue of partial paths. Let the initial queue consist of the zero length, zero step path from the root node to nowhere.
  2. Until the queue is empty or the goal has been reached, determine if the first path in the queue reaches the goal node.
    1. If the first path reaches the goal node then do nothing
    2. otherwise:
      1. Remove the first path from the queue.
      2. Form new paths from the removed path by extending one step.
      3. Add the new paths to the queue.
      4. Sort the queue by the sum of total cost and a lower-bound estimate of the cost remaining, with least cost at the front.
      5. If two or more paths reach a common node, delete all those paths except for the one that reaches the common node with minimum cost.
  3. If the goal has been found then success otherwise failure.