  ### CS4341 Introduction to Artificial Intelligence  Project 1 - B 2003

#### PROF. CAROLINA RUIZ

PART I (Homework). DUE DATE: Friday, November 07, 10:00 am (beginning of Friday's class).
PART I (Homework). HELP SESSION: Thursday, November 06, 1-2 pm FL A22.
Part II (project). DUE DATE: Monday, November 10, 9:00 pm.
BS/MS assignment. DUE DATE: Monday, November 10, 9:00 pm. Homework and 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.

1. Depth 1st search
3. Depth-limited search (depth-limit = 3)
4. Iterative deepening search (show all iterations, not just the iteration that succeeds)
5. Basic Branch-and-bound (= Uniform cost search) with neither Estimated Distance nor Dynamic Programming
6. Greedy search (= Best 1st search)
7. A*
8. Hill-climbing
9. Beam search (w = 2)

The goal of this project and homework matches the following Course Objectives:

• Learning to apply course material (to improve thinking, problem solving, and decision) during the design, implementation, and analysis of computer programs that reason and/or act intelligently.
• Learning fundamental principles about and generalizations of computational problem solving strategies.
• Developing creative capacities for the design, implementation, and analysis of computer programs that reason and/or act intelligently.
• Learning to analyze and experimentally evaluate designs and implementations of the intelligent computer programs, in particular those developed during the course projects.

This project consists of two parts:

1. Part I. A written homework assignment. Please hand in a HARDcopy of your group solutions at the beginning of class on Friday Nov. 07.
2. Part II. An implementation project. Please submit your group solutions using the turnin system by Monday, Nov. 10 at 9:00 pm.

Part I. Homework Assignment:

Suppose that you need to find a path between S and G in the following graph. See the description of this graph input format below.
```S M 15
S A 1
M G 15
A I 5
A C 2
A B 50
C E 1
C D 10
I J 4
J K 50
J L 5
K L 5
L M 35
#####
S 22
M 14
I 10
J 8
K 6
L 4
E 18
C 16
D 20
A 12
B 24

```

A picture of this graph is included below. Note that the (under)estimated distance of each node to the goal is included inside the node. (Special thanks to Peter Mardziel for creating this picture). The homework assignment is the following:

• For EACH of the search methods above,
1. follow by hand the way in which the search method seeks a path from S to G. Follow the output specifications of the project (Part II) to show for each method (as your computer program will do),
1. the list of nodes in the order in which they were EXPANDED (not just explored), and
2. the state of the "queue" when the node was expanded.
2. show for each search method the search tree constructed during the search.
Note that the homework solutions should follow exactly the same conventions as the project description below. In particular, the children of a node should be considered ordered in alphabetical order.

Homework Submission:

The homework is due at 10 am on Friday November 07, 2003.  Please hand in one HARDcopy of your group solutions to the homework assignment by the beginning of the class on Friday, Nov. 07.

• Each of the 9 search methods will be worth 11 points. These 11 points are distributed in the following way:
• 1 points for the list of expanded nodes in the correct order
• 6 points for handling the queue correctly according to the particular search method
• 1 point for expanding the path at the front of the queue
• 3 point for storing the children of the expanded node in the right position in the queue
• 1 point for sorting the queue if necessary
• 1 point for eliminating more expensive, redundant paths if necessary
• 4 points for the correct search tree
• 1 point for submit the homework (just to make the score sum up to 100 points :-)
• Total: 100 points.

Part II. Project Assignment:

• Your program must run on the CCC Unix machines
• You may use any high-level language (Java, Lisp, Prolog, C, C++, ...).
• Your program must demonstrate each and everyone of the search methods listed above.
• 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 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
```
Please note that after F 3.0 there is a newline character. Also, note that the (under)estimate of the distance between the goal state G and itself is always 0 and hence not included in the file.

Output Specifications:

Your program should output the trace of EACH search method, in the order listed above. In particular, you should print:

• (1) the name of the search method;
• (2) the name of each node in the order it was EXPANDED, (not just explored); and
• (3) the state of the "queue" when the node was expanded.
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. When cost/value of a path is considered (e.g. branch-and-bound, greedy search, A*, hill climbing, and beam search), and you need to decide the order of the paths in the queue according to their values (either f, g, or h values), follow the sorting procedure below:
• If two paths have different values then
• put the one with the lowest value first in the queue
(e.g. 15<L,M,S> will go before 24<A,S>)
• else (* the two paths have the same value *)
• If the two paths end at different nodes then
• put first in the queue the one that ends at the node that is first in alphabetical order
(e.g. 15<L,J,I,S> would go before 15<M,S>)
• else (* the two paths end at the same node *)
• If the two paths are of different length then
• put first in the queue the shortest one (e.g. 15<M,S> will go before 15<M,L,S>)
• else (* the two paths end at the same node and are of the same length *)
• sort the two paths in lexicographic order
(e.g. 15<M,B,S> will go before 15<M,L,S>)

For example, the trace of the net shown in Figure 4.1 in Winston's textbook and informed with the estimates in Figure 4.5 would produce:

```
Depth 1st search
Expanded  Queue
S      [<S>]
A      [<A,S>  <D,S>]
B      [<B,A,S> <D,A,S> <D,S>]
C      [<C,B,A,S> <E,B,A,S> <D,A,S> <D,S>]
E      [<E,B,A,S> <D,A,S> <D,S>]
D      [<D,E,B,A,S> <F,E,B,A,S> <D,A,S> <D,S>]
F      [<F,E,B,A,S> <D,A,S> <D,S>]
G      [<G,F,E,B,A,S> <D,A,S> <D,S>]
goal reached!

Expanded  Queue
S      [<S>]
A      [<A,S> <D,S>]
D      [<D,S> <B,A,S> <D,A,S>]
B      [<B,A,S> <D,A,S> <A,D,S> <E,D,S>]
D      [<D,A,S> <A,D,S> <E,D,S> <C,B,A,S> <E,B,A,S>]
A      [<A,D,S> <E,D,S> <C,B,A,S> <E,B,A,S> <E,D,A,S>]
E      [<E,D,S> <C,B,A,S> <E,B,A,S> <E,D,A,S> <B,A,D,S>]
C      [<C,B,A,S> <E,B,A,S> <E,D,A,S> <B,A,D,S> <B,E,D,S> <F,E,D,S>]
E      [<E,B,A,S> <E,D,A,S> <B,A,D,S> <B,E,D,S> <F,E,D,S>]
E      [<E,D,A,S> <B,A,D,S> <B,E,D,S> <F,E,D,S> <D,E,B,A,S> <F,E,B,A,S>]
B      [<B,A,D,S> <B,E,D,S> <F,E,D,S> <D,E,B,A,S> <F,E,B,A,S> <B,E,D,A,S> <F,E,D,A,S>]
B      [<B,E,D,S> <F,E,D,S> <D,E,B,A,S> <F,E,B,A,S> <B,E,D,A,S> <F,E,D,A,S> <C,B,A,D,S> <E,B,A,D,S>]
F      [<F,E,D,S> <D,E,B,A,S> <F,E,B,A,S> <B,E,D,A,S> <F,E,D,A,S> <C,B,A,D,S> <E,B,A,D,S> <A,B,E,D,S> <C,B,E,D,S>]
D      [<D,E,B,A,S> <F,E,B,A,S> <B,E,D,A,S> <F,E,D,A,S> <C,B,A,D,S> <E,B,A,D,S> <A,B,E,D,S> <C,B,E,D,S> <G,F,E,D,S>]
F      [<F,E,B,A,S> <B,E,D,A,S> <F,E,D,A,S> <C,B,A,D,S> <E,B,A,D,S> <A,B,E,D,S> <C,B,E,D,S> <G,F,E,D,S>]
B      [<B,E,D,A,S> <F,E,D,A,S> <C,B,A,D,S> <E,B,A,D,S> <A,B,E,D,S> <C,B,E,D,S> <G,F,E,D,S> <G,F,E,B,A,S>]
F      [<F,E,D,A,S> <C,B,A,D,S> <E,B,A,D,S> <A,B,E,D,S> <C,B,E,D,S> <G,F,E,D,S> <G,F,E,B,A,S> <C,B,E,D,A,S>]
C      [<C,B,A,D,S> <E,B,A,D,S> <A,B,E,D,S> <C,B,E,D,S> <G,F,E,D,S> <G,F,E,B,A,S> <C,B,E,D,A,S> <G,F,E,D,A,S>]
E      [<E,B,A,D,S> <A,B,E,D,S> <C,B,E,D,S> <G,F,E,D,S> <G,F,E,B,A,S> <C,B,E,D,A,S> <G,F,E,D,A,S>]
A      [<A,B,E,D,S> <C,B,E,D,S> <G,F,E,D,S> <G,F,E,B,A,S> <C,B,E,D,A,S> <G,F,E,D,A,S> <F,E,B,A,D,S>]
C      [<C,B,E,D,S> <G,F,E,D,S> <G,F,E,B,A,S> <C,B,E,D,A,S> <G,F,E,D,A,S> <F,E,B,A,D,S>]
G      [<G,F,E,D,S> <G,F,E,B,A,S> <C,B,E,D,A,S> <G,F,E,D,A,S> <F,E,B,A,D,S>]
goal reached!

Depth-limited search (depth-limit = 3)
Expanded  Queue
S      [<S>]
A      [<A,S> <D,S>]
B      [<B,A,S> <D,A,S> <D,S>]
D      [<D,A,S> <D,S>]
D      [<D,S>]
A      [<A,D,S> <E,D,S>]
E      [<E,D,S>]

Iterative deepening search
Expanded  Queue
L=1   S      [<S>]

L=2   S      [<S>]
A      [<A,S> <D,S>]
D      [<D,S>]

L=3   S      [<S>]
A      [<A,S> <D,S>]
B      [<B,A,S> <D,A,S> <D,S>]
D      [<D,A,S> <D,S>]
D      [<D,S>]
A      [<A,D,S> <E,D,S>]
E      [<E,D,S>]

L=4   S      [<S>]
A      [<A,S> <D,S>]
B      [<B,A,S> <D,A,S> <D,S>]
C      [<C,B,A,S> <E,B,A,S> <D,A,S> <D,S>]
E      [<E,B,A,S> <D,A,S> <D,S>]
D      [<D,A,S> <D,S>]
E      [<E,D,A,S> <D,S>]
D      [<D,S>]
A      [<A,D,S> <E,D,S>]
B      [<B,A,D,S> <E,D,S>]
E      [<E,D,S>]
B      [<B,E,D,S> <F,E,D,S>]
F      [<F,E,D,S>]
[]

L=5   S      [<S>]
A      [<A,S> <D,S>]
B      [<B,A,S> <D,A,S> <D,S>]
C      [<C,B,A,S> <E,B,A,S> <D,A,S> <D,S>]
E      [<E,B,A,S> <D,A,S> <D,S>]
D      [<D,E,B,A,S> <F,E,B,A,S> <D,A,S> <D,S>]
F      [<F,E,B,A,S> <D,A,S> <D,S>]
D      [<D,A,S> <D,S>]
E      [<E,D,A,S> <D,S>]
B      [<B,E,D,A,S> <F,E,D,A,S> <D,S>]
F      [<F,E,D,A,S> <D,S>]
D      [<D,S>]
A      [<A,D,S> <E,D,S>]
B      [<B,A,D,S> <E,D,S>]
C      [<C,B,A,D,S> <E,B,A,D,S> <E,D,S>]
E      [<E,B,A,D,S> <E,D,S>]
E      [<E,D,S>]
B      [<B,E,D,S> <F,E,D,S>]
A      [<A,B,E,D,S> <C,B,E,D,S> <F,E,D,S>]
C      [<C,B,E,D,S> <F,E,D,S>]
F      [<F,E,D,S>]
G      [<G,F,E,D,S>]
goal reached!

Basic Branch-and-bound
Expanded  Queue
S      [0<S>]
A      [3<A,S> 4<D,S>]
D      [4<D,S> 7<B,A,S> 8<D,A,S>]
E      [6<E,D,S> 7<B,A,S> 8<D,A,S> 9<A,D,S>]
B      [7<B,A,S> 8<D,A,S> 9<A,D,S> 10<F,E,D,S> 11<B,E,D,S>]
D      [8<D,A,S> 9<A,D,S> 10<F,E,D,S> 11<B,E,D,S> 11<C,B,A,S> 12<E,B,A,S>]
A      [9<A,D,S> 10<E,D,A,S> 10<F,E,D,S> 11<B,E,D,S> 11<C,B,A,S> 12<E,B,A,S>]
E      [10<E,D,A,S> 10<F,E,D,S> 11<B,E,D,S> 11<C,B,A,S> 12<E,B,A,S> 13<B,A,D,S>]
F      [10<F,E,D,S> 11<B,E,D,S> 11<C,B,A,S> 12<E,B,A,S> 13<B,A,D,S> 14<F,E,D,A,S> 15<B,E,D,A,S>]
B      [11<B,E,D,S> 11<C,B,A,S> 12<E,B,A,S> 13<B,A,D,S> 13<G,F,E,D,S> 14<F,E,D,A,S> 15<B,E,D,A,S>]
C      [11<C,B,A,S> 12<E,B,A,S> 13<B,A,D,S> 13<G,F,E,D,S> 14<F,E,D,A,S> 15<A,B,E,D,S> 15<B,E,D,A,S>15 <C,B,E,D,S>]
E      [12<E,B,A,S> 13<B,A,D,S> 13<G,F,E,D,S> 14<F,E,D,A,S> 15<A,B,E,D,S> 15<B,E,D,A,S> 15<C,B,E,D,S>]
B      [13<B,A,D,S> 13<G,F,E,D,S> 14<D,E,B,A,S> 14<F,E,D,A,S> 15<A,B,E,D,S> 15<B,E,D,A,S> 15<C,B,E,D,S> 16<F,E,B,A,S>]
G      [13<G,F,E,D,S> 14<D,E,B,A,S> 14<F,E,D,A,S> 15<A,B,E,D,S> 15<B,E,D,A,S> 15<C,B,E,D,S> 16<F,E,B,A,S> 17<C,B,A,D,S> 18<E,B,A,D,S>]
goal reached!

Greedy search
Expanded  Queue
S      [11.0<S>]
D      [8.9<D,S> 10.4<A,S>]
E      [6.9<E,D,S> 10.4<A,S> 10.4<A,D,S>]
F      [3.0<F,E,D,S> 6.7<B,E,D,S> 10.4<A,S> 10.4<A,D,S>]
G      [0<G,F,E,D,S> 6.7<B,E,D,S> 10.4<A,S> 10.4<A,D,S>]
goal reached!

A*
Expanded  Queue
S      [11.0<S>]
D      [12.9<D,S> 13.4<A,S>]
E      [12.9<E,D,S> 13.4<A,S> 19.4<A,D,S >]
F      [13<F,E,D,S> 13.4<A,S> 17.7<B,E,D,S>]
G      [13<G,F,E,D,S> 13.4<A,S> 17.7<B,E,D,S>]
goal reached!

Hill-climbing
Expanded  Queue
S      [11.0<S>]
D      [8.9<D,S> 10.4<A,S>]
E      [6.9<E,D,S> 10.4<A,D,S> 10.4<A,S>]
F      [3.0<F,E,D,S> 6.7<B,E,D,S> 10.4<A,D,S> 10.4<A,S>]
G      [0<G,F,E,D,S> 6.7<B,E,D,S> 10.4<A,D,S> 10.4<A,S>]
goal reached!

Beam search (w = 2)
Expanded  Queue
S      [11.0<S>]
A      [10.4<A,S> 8.9<D,S>]
D      [8.9<D,S> 6.7<B,A,S> 8.9<D,A,S>]
B      [6.7<B,A,S> 8.9<D,A,S > 10.4<A,D,S > 6.9<E,D,S>]
E      [6.9<E,D,S> 4<C,B,A,S> 6.9<E,B,A,S>]
C      [4<C,B,A,S> 6.9<E,B,A,S > 6.7<B,E,D,S > 3<F,E,D,S>]
F      [3<F,E,D,S>]
G      [0<G,F,E,D,S>]
goal reached!

```

(Note that for branch-and-bound 'C' is expanded even though no diagram shows this in Figure 5.2 in the textbook.  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 in the textbook 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) must 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 must use a general search procedure and a general data structure (that we'll refer to in class and in this project statement as "the 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 must have a procedure that implements the following pseudo-code (adapted from Russell's and Norvig's textbook):

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

Your procedure implementing this pseudo-code must be named General-Search as shown above.

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.

Note that in order to avoid loops, you need to store not just the name of node being explored in your "queue", but also the path used to arrive to that node from the source node.

Project Submission:

Project 1 is due at 9 pm on November 10, 2003.  One (and only one) member of your group should submit the following files using the turnin program. The name of the turnin directory is proj1.

• proj1_script.scr: A capture script of your program working on the sample file net.txt.
• The source code for your program
• Any ancillary files that your program requires

• Your program will be tested using test files other than net.txt and second.txt.
• 10 points will be for creating the general search procedure as described above and making each of the search methods be a call to this general procedure.
• Each search method that works successfully and that has been correctly implemented will be worth 9 points. These 9 points are distributed in the following way:
• 1.5 points for correctly calling the general search procedure General-Search.
• 3 points for handling the queue correctly according to the particular search method
• 4.5 for running correctly over the 3 test files (1.5 for each test)
• 9 points will be for Documentation. This documentation includes both the documentation standard and code comments. Make sure you describe what parts of the code are contained in each file and a general description of how the program runs.
• Total: 100 points.