CSE 150 – Introduction to Artificial Intelligence
Week 1 –Discussion Notes
September 27, 2004

Outline:
1) Informed Search Algorithms
2) The A* Informed Search Algorithm
3) Taxonomy of Search Algorithms
4) Code design for Assignment 1
1) Informed Search Algorithms

Last week, we discussed the general search problem, and how it is often represented by a search graph where each state is a vertex and each operator (aka action) is an edge in the graph.  The cost of an action is represented as a number associated with an edge on the graph.

This week, we continue with the Romanian Airport problem. That is, we start in city A and have to get to a city with an airport. The only city that has an airport, and thus fits the goal description, is city B. Our contraint is that we have to use the public roads to get between cities. Each city has an associated cost which, in our example, is the number of road miles that we need to drive to get from one city to another. Our objective is to find a path from our initial state (A) to a goal state that minimizes the total number of miles that we need to travel.

Romanian Search Graph with Costs
In lecture, we will explored two "informed" search alogorithms, Greedy Best-First and A*, which are unlike the "uninformed" algorithms (Breadth-First Search (BFS) and Depth-First Search (DFS)) in that they make use of additional information to guide the search process. The addional information is a function called a heuristic function, denoted h(n), which takes a state n and returns an estimated cost to the closest goal state. If the estimated cost is always an underestimate for all states, h(n) is called an "admissible heuristic function."

In our Romanian Airport example, an example of a heuristic function h(n) would be the "as the crow flies" distance between each state n and the closest goal state. In this case, h(n) is admissible since "as the crow flies" distance is a straight line from a state to the goal, and the shortest distance between two points is a straight line (by the triangle inequality.) Figure 2 is a representation of h(n) in our example

Hueristic Function Graph

2) The A* Search Algorithm

Last week, we went over the pseudo-code for the general search algorithm. It is recreated here for your convience:

Search Problem Pseudo-Code
In addition to the heuristic function h(n), let g(n) be the cost of the path from the initial state to the current state n. We can sum these two functions we get an Evaluation Function f(n). That is f(n)= h(n)+g(n). We will  refer to f(n) as the f-value for a state n.

The A* Search algorithm is simply the general search algorithm with the queue implemented by a priority queue sorted on the f-values of the states in the queue. That's all there is too it from an implemenation standpoint.

However, from a theoretical standpoint, A* is much more interesting. If h(n) is admissible, then A* is optimal: A* will always find the minimum cost path from the initial state to a goal state. The proof of this is very intuitive and was shown it class by Prof. Elkan. It is can also be found in AIMA starting at the very bottom of page 97. (As a side note, the * in A* is a convention for denoting "optimal solution".) In section this week, rather than go over the proof, we work through the algorithm using the Romanian Airport Problem. See Figure 4.3 on page 98 in AIMA for more details.
3) Taxonomy of Search Algorithms

Now that we have seen a number of different search algorithms, we will put them in context with one another. Note that search problems can be represented as a search graph with associated states, operators (also know as actions) and costs. They also make use of the General Search Algorithm pseudo-code found in Figure 3.

Search Algorithm Taxonomy

It is not enough to simply memorize the relationships between all 7 of these algorithms. You must understand how they work with the General Search algorithm pseudo-code, the behavior of each algorithm on a specific example, and the theoretical properties of each algorithm. Theoretical properties include time and space complexity, as well as whether the algorithm is complete and/or optimal.

4) Code design for Assignment 1

The following is only a suggestion for designing your code for Assignment 1. We will use an Object-Oriented (Java, C++) approach, but you may prefer the non-Objected Oriented (C) approach. Either way, the first thing we need to do is describe the input and output for our programs.
Problem
 Input
 Output
eight_puzzle
 text file with multiple 3 x 3 matrices of integers 0..8
 * Optimal Solution Path
* Solution Cost
* Depth of Solution
* Number of Nodes Generated
robot navigation
 text file with multiple instance of  start, goal, and obstacles
missionary_cannibal
 ---

(Note that for the eight puzzle problem you will also have to create you own "random instance problem generator" which will provide input to you eight_puzzle program.)

If we take the "object oriented", we will need to create a "state", a "node", and a "search" object.  The A* search object will need to be initialized with a initial state object, an isGoal() function, an h() heuristic function, an expand() function and maybe a printOutput() function.  You may want to include additional information for bookkeeping purposes based on the output requirements. Below is a visual representation of what information might be maintained your object:
Search Objects

For the missionary_cannibal problem, the state object may be represented as a an array of three integers where the first integer is the number of missionaries on the west shore, the second integer is the number of cannibals on the west shore, and the last interger is 1 if the boat is on the west shore or 0 if the boat is on the east shore. The initial state would then be the array '3 3 1'. The isGoal() function would compare the state of the node to the array '0 0 0'. The expand() function would move one node from the queue to the expanded list, and add up to five nodes  (based on the five possible actions) to the queue. (See Week 1 Discussion - Missionaries and Cannibals Problem Formulation.) The h() function would be used to calculate a new f-value for each node added to the queue. The printOutput() function would print out all the require output information for the problem.

(c) This page was prepared for CSE 150 by Douglas Turnbull (dturnbul@cs.ucsd.edu) on October 6st 2004.