CSE 250A Lecture Notes, January 11, 2000

CSE 250A LECTURE NOTES

Monday, January 8, 2001

WELCOME

This is CSE 250A, Principles of 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:

No sections, no TA.
Four projects, three with programming or other computer work, and a written report.
First project description available Wed, deadline January 24.
Teams of three.
Absolute academic honesty is required.
There are detailed guidelines for the projects.
Easy to ask questions with the class bulletin board.
If you need a computer account, ask me after class.
Class will start at 1:50pm sharp and end at 3:10pm sharp.
The total amount of work is intended to be comparable to that of a graduate core course.

The advantages of multiple medium-size team projects include:

learn team time management and division of labor
learn team communication and leadership skills
learn to write technical reports
learn to do better from each project to the next
no end-of-quarter extra load
no busy work
multiple opportunities to initiate publishable research projects.

One final exam will reward individual performance. Its existence will help you concentrate on the lectures and the textbook as well as on the projects. There will be a sample exam.

CSE 250A TOPICS

Some specific AI topics that will be covered in CSE 250A include:

knowledge-based search algorithms
constraint satisfaction methods (CSP solvers)
randomized search methods, e.g. GSAT
knowledge representation in first-order logic (FOL)
resolution methods for reasoning in FOL
axiomatizing causal knowledge for planning
planning algorithms based on randomized search
representing probabilistic knowledge
fuzzy logic and fuzzy control.

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 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 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 imagining sequences 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.

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. This tree is called the search space, but this name is misleading.

The agent searches over the state space for a sequence of actions that lead to a goal state.

Important: typically the agent does not "know" the entire search space, 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 full search space, 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 well-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 isa-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".) 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.

The general search algorithm explores a tree of states, not the search space directly: compare the pictures on pages 62 and 71.

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 77 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 74 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.