MIT Open course

6.034 Artificial Intelligence by T. Lozano-Perez and L. Kaelbling. Copyright © 2003 by Massachusetts Institute of Technology.

6.034 Notes: Section 2.1

Slide 2.1.1

Search plays a key role in many parts of AI. These algorithms provide the

conceptual backbone of almost every approach to the systematic exploration of

alternatives.

We will start with some background, terminology and basic implementation

strategies and then cover four classes of search algorithms, which differ along two

dimensions: First, is the difference between uninformed (also known as blind)

The search methods we will be dealing with are defined on trees and graphs, so we

need to fix on some terminology for these structures:

● A tree is made up of nodes and links (circles and lines) connected so that there

are no loops (cycles). Nodes are sometimes referred to as vertices and links as

edges (this is more common in talking about graphs).

● A tree has a root node (where the tree "starts"). Every node except the root has

a single parent (aka direct ancestor). More generally, an ancestor node is a node

that can be reached by repeatedly going to a parent node. Each node (except the

terminal (aka leaf) nodes) has one or more children (aka direct descendants).

More generally, a descendant node is a node that can be reached by repeatedly

6.034 Artificial Intelligence by T. Lozano-Perez and L. Kaelbling. Copyright © 2003 by Massachusetts Institute of Technology.

And, undirected graphs where the links go both ways. You can think of an

undirected graph as shorthand for a graph with directed links going each way

between connected nodes.

Slide 2.1.5

Graphs are everywhere; for example, think about road networks or airline routes or

computer networks. In all of these cases we might be interested in finding a path

through the graph that satisfies some property. It may be that any path will do or we

may be interested in a path having the fewest "hops" or a least cost path assuming

the hops are not all equivalent, etc.

Slide 2.1.6

graph that is of more general interest in AI.

Slide 2.1.7

One general approach to problem solving in AI is to reduce the problem to be solved

to one of searching a graph. To use this approach, we must specify what are the

states, the actions and the goal test.

A state is supposed to be complete, that is, to represent all (and preferably only) the

relevant aspects of the problem to be solved. So, for example, when we are planning

the cheapest round-the-world flight plan, we don't need to know the address of the

airports; knowing the identity of the airport is enough. The address will be

important, however, when planning how to get from the hotel to the airport. Note

6.034 Artificial Intelligence by T. Lozano-Perez and L. Kaelbling. Copyright © 2003 by Massachusetts Institute of Technology.

Note that we've indicated that (in general) we need a test for the goal, not just one specific goal state. So, for example, we might be interested any city in

Germany rather than specifically Frankfurt. Or, when proving a theorem, all we care is about knowing one fact in our current data base of facts. Any

final set of facts that contains the desired fact is a proof.

In principle, we could also have multiple starting states, for example, if we have some uncertainty about the starting state but, for now, we are not

addressing issues of uncertainty either in the starting state or in the result of the actions.

Slide 2.1.8

Note that trees are a subclass of directed graphs (even when not shown with arrows

on the links). Trees don't have cycles and every node has a single parent (or is the

root). Cycles are bad for searching, since, obviously, you don't want to go round and

round getting nowhere.

When asked to search a graph, we can construct an equivalent problem of searching

a tree by doing two things: turning undirected links into two directed links; and,

more importantly, making sure we never consider a path with a loop or, even better,

tree has a leaf node for every non-looping path in the graph starting at S.

Also note, however, that even though we avoided loops, some nodes (the colored

ones) are duplicated in the tree, that is, they were reached along different non-

looping paths. This means that a complete search of this tree might do extra work.

The issue of how much effort to place in avoiding loops and avoiding extra visits to

nodes is an important one that we will revisit later when we discuss the various

search algorithms.

Slide 2.1.10

One important distinction that will help us keep things straight is that between a

state and a search node.

constructs an explicit tree of nodes while searching. Each node refers to some state,

but not uniquely. Note that a node also corresponds to a path from the start state to

the state associated with the node. This follows from the fact that the search

algorithm is generating a tree. So, if we return a node, we're returning a path.

6.034 Notes: Section 2.2

6.034 Artificial Intelligence by T. Lozano-Perez and L. Kaelbling. Copyright © 2003 by Massachusetts Institute of Technology.

So, let's look at the different classes of search algorithms that we will be exploring.

The simplest class is that of the uninformed, any-path algorithms. In particular, we

will look at depth-first and breadth-first search. Both of these algorithms basically

look at all the nodes in the search tree in a specific order (independent of the goal)

and stop when they find the first path to a goal state.

Slide 2.2.2

The next class of methods are informed, any-path algorithms. The key idea here is to

exploit a task specific measure of goodness to try to either reach the goal more quickly

Finally, we look at informed, optimal algorithms, which also guarantee finding the

best path but which exploit heuristic ("rule of thumb") information to find the path

faster than the uninformed methods.

6.034 Artificial Intelligence by T. Lozano-Perez and L. Kaelbling. Copyright © 2003 by Massachusetts Institute of Technology.

Slide 2.2.5

The search strategies we will look at are all instances of a common search algorithm,

which is shown here. The basic idea is to keep a list (Q) of nodes (that is, partial

paths), then to pick one such node from Q, see if it reaches the goal and otherwise

extend that path to its neighbors and add them back to Q. Except for details, that's all

there is to it.

Note, by the way, that we are keeping track of the states we have reached (visited) and

Slide 2.2.6

The key questions, of course, is which entry to pick off of Q and how precisely to add

the new paths back on the Q. Different choices for these operations produce the

one of the descendants of that node's state.

One good thing about depth-first search is that Q never gets very big. We will look

at this in more detail later, but it's fairly easy to see that the size of the Q depends on

the depth of the search tree and not on its breadth.

Slide 2.2.8

Breadth-first is the other major type of uninformed (or blind) search. The basic

approach is to once again pick the first element of Q to examine BUT now we place

the extended paths at the back of Q. This means that the next path pulled off of Q

will typically not be a descendant of the current one, but rather one at the same level

in tree.

Note that in breadth-first search, Q gets very big because we postpone looking at

longer paths (that go to the next level) until we have finished looking at all the paths

at one level.

We'll look at how to implement other search strategies in just a bit. But, first, lets