### CS4341 Introduction to Artificial Intelligence  Project 1 - D 2001

#### By Chris Shoemaker and Carolina Ruiz

DUE DATE: Friday, Mar. 23 at 5 pm.

Project Goal:

The goal of Project 1 is to help you understand exactly how different search strategies work.  You will implement each of nine net search algorithms.  Among the searches are basic searches, heuristically informed searches, and optimal searches.

Project Assignment:

• Your program must run on the CCC Unix machines
• You may use any high-level language (Prolog, C, C++, Java, ...).
• Your program must demonstrate the following search methods:
• Depth 1st search
• Depth-limited search (depth-limit = 3)
• Iterative deepening search (show all iterations, not just the iteration that succeeds)
• Basic Branch-and-bound (= Uniform cost search) with neither Estimated Distance nor Dynamic Programming
• Greedy search (= Best 1st search)
• A*
• Hill-climbing
• Beam search (w = 2)
• All searches must terminate.
• No search results should contain any loops.

Input Specifications:

Your program must read the net to be searched from a file.  The format of the file is as follows:

The net file has two sections.  The first section describes the topology of the net and the weights (costs, distances) of the paths between nodes.  The second section provides heuristic estimates for the distances from each node to the goal node.

In the first section, each line contains all the information about one connection between two adjacent nodes.  Each of these lines has 3 fields, and each field is separated by whitespace.

• The first field is the name of a node.  All nodes are named by a single capital letter.  Therefore, the length of the first field is always one byte (one character).
• The second field is also the name of a node, and is also one character long.  In the net, this node is adjacent to the node named in the first field.
• The third field is the actual length of the connection between the node named in the first field and the node named in the second field.  It is a float value.

In total, the first section will contain as many lines as there are connections in the net.  You may assume that every net contains a node named 'S' and a node named 'G'.  You may also assume that the net is finite (of course).  These are the starting and goal nodes, respectively.  After the first section there will be a line separating the two sections.  This line will contain only 5 pound signs.  i.e. "#####"

The second section contains heuristic information about each node in the net (except for the goal node).  Only the heuristically informed methods should use this information.  Each line has 2 fields.

• The first field is the name of a node.  Again, it is one character.
• The second field is the estimated distance from the node named in the first field to the goal.

The net shown in Figure 4.1 on p. 64 of Winston's AI textbook, with the heuristic information given in Figure 4.5 is described by this file: net.txt

```S A 3.0
S D 4.0
A B 4.0
B C 4.0
A D 5.0
B E 5.0
D E 2.0
F E 4.0
G F 3.0
#####
S 11.0
A 10.4
D 8.9
B 6.7
E 6.9
C 4.0
F 3.0```

Output Specifications:

Your program should output the trace of EACH search method, in the order listed above.  In particular, you should print the name of each node in the order it was EXPANDED, (not just explored).  When a search method backtracks past a node that has already been expanded do NOT print the name of the node again.  Also, notice that you must expand a node in order to discover anything about its neighbors (children, in a search tree), but that the heuristically informed methods are not required to expand a node when they learn the node's estimated distance to the goal.  The children of a node should be considered ordered in alphabetical order, that is if a node has children D, B, and F, then B will considered the 1st (or leftmost) child, D the 2nd (or middle) child, and F the last (or rightmost) child of the node. Separate each node name with whitespace, and try to show the trace for one search on one line.  For example, the trace of the net shown in Figure 4.1 (p. 87) and informed with the estimates in Figure 4.5 (p. 71) would produce:

S A B C E D F G

S A D B D A E C E E B B F D F B F C E A C G

S A B C E D E D A B E B F

S S A D S A B D D A E S A B C E D E D A B E B F S A B C E D F D E B F D A B C E E B A C F G

S A D E B D A E F B C E B G

S D E F G

S D E F G

S D E F G

S A D B E C F G

(Note that for branch-and-bound 'C' is expanded even though no diagram shows this in Figure 5.2.  This is because it has no children, but the search still had to expand node C in order to determine that.  Also, note that Figure 4.8 is incorrect, because S-D-E-B should never be expanded.)

The search ends when the goal node is expanded.  Therefore if the goal is reached, it will be the last node listed.  Since some of these searches are not complete (even for finite nets!) it will be possible that the goal is not found.  In this case, the trace will end with the last node expanded before the search terminated.

Your program (or an accompanying script, as described in your program documentation) should accept the name of the file to read the net from.  For example, your program could be run by typing "java Search net.txt" or "search net.txt" or "runsearch net.txt"

Your solution should use a general search procedure and a general data structure ("queue") so that each of the search strategies calls the general search procedure with a parameter specifying which search method to use.  That is, you should have a procedure that implements the following pseudo-code:

function General-Search (problem, search-method) returns either a solution or failure
queue = Make-Queue(Make-Node(problem.initial-state)
loop do
if queue is empty then return failure
node = Remove-Front(queue)
if State[node] is a solution of problem then return State[node]
opened-nodes = Expand(node)
queue = opened-nodes added to queue according to search-method
end

More details about this general procedure will be given in class. For an example of how to implement each of the search strategies as a call to this general procedure, see Russell's and Norvig's online code. Although you are welcome to look at their code to guide the design of your program, you MUST submit your own original code.

Project Submission:

Project 1 is due at 5pm on March 23, 2001.  One (and only one) member of your group should submit the following files using the turnin program: