CSE 150 Lecture Notes, January 6, 2004

CSE 150 LECTURE NOTES

Tuesday January 6, 2004

WELCOME

This is CSE 150, Introduction to Artificial Intelligence. Please see today's introductory handout that describes the organization of the course.

If this is not the course you expected to find in this room, stick around anyhow: this will probably be more interesting than the course you were looking for.

Some points to note:

Friday section, three excellent, experienced TAs.
Do come to lectures, but not if you won't pay attention. No cell phones or other disturbances
First assignment will be available Thursday, deadline Tuesday January 20.
Absolute academic honesty is required.
Will be easy to ask questions with the class bulletin board.
Account slips on Thursday.
Class will start at 2pm sharp and end at 3:20pm sharp.

The midterm is mostly intended as a sample of what the final exam will be like. Exams will help you concentrate on the lectures and the textbook as well as on the projects.

We'll talk about the history of AI and philosophical questions a few times during the quarter. For now I want to start with technical material, i.e. algorithms.

PLANNING AS SEARCH

Consider an AI agent that is trying to find a plan for achieving a goal.

Formally, a goal is a description of a set of desirable states of the world and a plan is a sequence of actions. An action takes the agent from one state to another state.

Example: if you are in Arad (Romania) and your visa will expire tomorrow, your goal is to reach Bucharest airport.

Be sure to notice and understand the difference between a state that satisfies a goal and a description of a goal. Technically, "reach Bucharest airport" is a description of a goal. You can apply this description to particular states and decide yes/no whether they belong to the set of goal states.

Problem formulation means choosing a relevant set of states to consider, and a feasible set of operators for moving from one state to another.

The relevant set of states should include the current state, which is the initial state, and (at least one!) goal state. The operators correspond to actions that the agent might take.

Search is the process of imaginingsequences of operators applied to the initial state, and checking which sequence reaches a goal state.

A standard example of a planning problem formulated as a search problem is the so-called 8-puzzle (see pictures in book).

States: Each state is a particular assignment of the eight numbered tiles or the blank to the nine available positions. There are 9! = 362 880 different states.
Goal: There is just one goal state.
Operators: the blank moves left, right, up, or down.

After the best sequence of operators has been discovered in imagination by search, this sequence can be executed in the real world.

SEARCHING A STATE SPACE

We are studying intelligent agents that achieve goals by formulating search problems. The problem formulation implicitly defines a graph where

a node is a state of the world, and
an edge links two nodes if an action by the agent can change one state into another

Note that this graph is actually a tree, and its vertices are not states. Instead they are nodes that represent states. The same state can be represented by more than one node. In some domains it is easy to test whether multiple nodes correspond to the same state in the "real world". In other domains it is impossible.

Important: typically the agent does not "know" the entire set of states, where "know" means "has available an explicit representation of". What is called a "representation" in AI is often called a data structure elsewhere in computer science.

Instead of "knowing" the set of all states, the agent knows the initial state, and it knows operators. An operator is a function which "expands" a node. "Expanding" a node means computing the node(s) (zero, one, or many) that the agent could move to using all applicable operators.

With this available knowledge, the general search algorithm that the agent can use is:

input: a properly formulated search problem
        a function "insert" to place new nodes into a queue
fringe := make-queue(initial-node)
loop
   if empty?(fringe) then return FAIL
   else
     X := remove-front(fringe)
     if satisfies-goal(state(X)) then return X
     else
        fringe := insert(fringe,expand(X))
end loop

The algorithm above assumes that when a node is chosen, all available operators are also chosen. Alternatively expansion could be viewed as a process with two inputs: the node to start from, and the operator to be used.

When a node is expanded, it may prove to have no children.

Expanding a leaf node may lead to another node that has already been visited. In general the search algorithm does not "know" this. (Remember that "know" means "has available a directly usable explicit representation".) The general search algorithm generates a tree of nodes, not the search space directly: compare the pictures on pages ? and ?.

Different algorithms use different insert functions, but always remove nodes one by one from the front of the fringe.

DEPTH-FIRST SEARCH (DFS)

DFS is the general search algorithm where the heuristic policy is also to always let X be the first node in the fringe. But nodes discovered by expansion are added to the fringe at the beginning, so they are expanded first.

DFS goes down a path until it reaches a node that has no children. Then DFS "backtracks" and expands a sibling of the node that had no children. If this node has no siblings, then DFS looks for a sibling of the grandparent, and so on.

See the picture on page ? for an illustration of DFS.

BREADTH-FIRST SEARCH (BFS)

BFS is the general search algorithm where the heuristic policy is to always let X be the first node in the fringe. Nodes discovered by expansion are added to the fringe at the end, so they are expanded last.

BFS first considers all paths of length 1, then all paths of length 2, and so on. This is why it is called "breadth-first".

The picture on page ? shows intuitively how BFS works.

The search algorithm needs an efficient representation of the fringe. We shall use a queue, i.e. a special list where you can remove elements from the front and you can insert new elements into the middle.

DEPTH-LIMITED SEARCH

No matter how deep the current node is, DFS will always go deeper if it has a child. The major weakness of DFS is that it will fail to terminate if there is an infinite path "to the left of" the path to the first solution.

Depth-limited search is the same as DFS except a nodes of depth equal to a fixed maximum (say M) are not expanded.

If a solution exists at depth M or less, then M-limited DFS will find it, and this algorithm is very space-efficient, since it uses only O(b*M) space.

ITERATIVE DEEPENING

The idea is to do depth-limited DFS repeatedly, with an increasing depth limit, until a solution is found.